Product form parametric representation of the solutions to a quadratic boolean equation
Y. Crama, P. L. Hammer, B. Jaumard, B. Simeone (1987)
RAIRO - Operations Research - Recherche Opérationnelle
Similarity:
Y. Crama, P. L. Hammer, B. Jaumard, B. Simeone (1987)
RAIRO - Operations Research - Recherche Opérationnelle
Similarity:
Henrik Brosenne, Matthias Homeister, Stephan Waack (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
We investigate well-structured graph-driven parity-FBDDs, which strictly generalize the two well-known models parity OBDDs and well-structured graph-driven FBDDs. The first main result is a characterization of the complexity of Boolean functions represented by well-structured graph-driven parity-FBDDs in terms of invariants of the function represented and the graph-ordering used. As a consequence, we derive a lower bound criterion and prove an exponential lower bound for certain linear...
Beate Bollig (2003)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Branching programs are a well-established computation model for boolean functions, especially read-once branching programs (BP1s) have been studied intensively. Recently two restricted nondeterministic (parity) BP1 models, called nondeterministic (parity) graph-driven BP1s and well-structured nondeterministic (parity) graph-driven BP1s, have been investigated. The consistency test for a BP-model is the test whether a given BP is really a BP of model . Here it is proved that the consistency...
Plotnikov, Anatoly D. (2001)
International Journal of Mathematics and Mathematical Sciences
Similarity:
Jean-Francis Michon, Jean-Baptiste Yunès, Pierre Valarcher (2005)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
We investigate the structure of “worst-case” quasi reduced ordered decision diagrams and Boolean functions whose truth tables are associated to: we suggest different ways to count and enumerate them. We, then, introduce a notion of complexity which leads to the concept of “hard” Boolean functions as functions whose QROBDD are “worst-case” ones. So we exhibit the relation between hard functions and the Storage Access function (also known as Multiplexer).
Henrik Brosenne, Matthias Homeister, Stephan Waack (2002)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
We investigate well-structured graph-driven parity-FBDDs, which strictly generalize the two well-known models parity OBDDs and well-structured graph-driven FBDDs. The first main result is a characterization of the complexity of Boolean functions represented by well-structured graph-driven parity-FBDDs in terms of invariants of the function represented and the graph-ordering used. As a consequence, we derive a lower bound criterion and prove an exponential lower bound for certain linear...
Umberto Bertelè, Francesco Brioschi (1971)
RAIRO - Operations Research - Recherche Opérationnelle
Similarity:
Jochen Harant (2000)
Discussiones Mathematicae Graph Theory
Similarity:
For a finite undirected graph G on n vertices some continuous optimization problems taken over the n-dimensional cube are presented and it is proved that their optimum values equal the independence number of G.