Properties of Switch-List Representations of Boolean Functions
Authors: Miloš Chromý, Ondřej Čepek
JAIR 2020 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we focus on a less usual way to represent Boolean functions, namely on representations by switch-lists, which are closely related to interval representations. ... First, we compare switch-list representations with a number of standard representations (such as CNF, DNF, and OBDD) with respect to their relative succinctness. ... Next, using the succinctness result between switch-lists and OBDDs, we develop a polynomial time compilation algorithm from switch-lists to OBDDs. Finally, we analyze which standard transformations and queries (those considered by Darwiche and Marquis) can be performed in polynomial time with respect to the size of the input if the input knowledge is represented by a switch-list. ... This is a theory paper that establishes the properties of SLRs and places the languages based on SLRs into KCM. |
| Researcher Affiliation | Academia | Ondrej Cepek EMAIL Milos Chromy EMAIL Dept. of Theoretical Computer Science and Mathematical Logic Faculty of Mathematics and Physics, Charles University Prague, Czech Republic |
| Pseudocode | No | The paper describes algorithms for compilation from SL to BDT (Section 4.1) and from BDT to OBDD (Section 4.2) in detailed prose. For example, in Section 4.1, it states: "We start by creating the root node, assigning the interval [0, 2n 1] and variable x1 to the root node, and inserting the root node into a queue. Then we start processing the nodes from the queue in the following manner. Extract the first node v with an assigned interval [a, b] and a variable xk from the queue. Scan the input switch-list until one of the following two situations occurs..." This description provides the steps of an algorithm but is not formatted as a structured pseudocode block or explicitly labeled as such. |
| Open Source Code | No | The paper does not contain any explicit statements about the release of source code or provide links to any code repositories for the described methodologies. |
| Open Datasets | No | The paper focuses on theoretical properties and representations of Boolean functions. It does not use or reference any specific datasets for empirical evaluation, therefore, no information on public availability of datasets is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve experiments with datasets. Consequently, no information regarding training, testing, or validation dataset splits is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setup or report on hardware used for running experiments. |
| Software Dependencies | No | The paper focuses on theoretical algorithms and properties of Boolean function representations. It does not mention any specific software dependencies or version numbers used for implementation or experimentation. |
| Experiment Setup | No | The paper is theoretical and does not involve empirical experiments. Therefore, no experimental setup details, such as hyperparameters or training configurations, are provided. |