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 “Lower bounds on the complexity of real-time 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:
Decomposing a -valued transducer into unambiguous ones
Andreas Weber (1996)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Algebraic complexity of path problems
Bernd Mahr (1982)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Complexity theoretical results on nondeterministic graph-driven read-once branching programs
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...
Normalization of place/transition-systems preserves net behaviour
E. Pelz (1992)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Cutwidth of the de Bruijn graph
André Raspaud, Ondrej Sýkora, Imrich Vrt'o (1995)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity: