Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
M. Krause, Ch. Meinel, St. Waack (1992)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Displaying similar documents to “A note on read- times branching programs”
Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
Separating from co-, and for oblivious Turing machines of linear access
Matthias Krause (1992)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
On the complexity of the hidden weighted bit function for various BDD models
Beate Bollig, Martin Löbbing, Martin Sauerhoff, Ingo Wegener (1999)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication
Beate Bollig (2001)
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 have been studied intensively. In this paper the expressive power of nondeterministic read-once branching programs, more precisely the class of functions representable in polynomial size, is investigated. For that reason two restricted models of nondeterministic read-once branching programs are defined and a lower bound method is presented. Furthermore, the first...
On the positive and the inversion complexity of Boolean functions
V. Dičiūnas (1993)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Bounded queries to arbitrary sets
A. Lozano (1996)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity: