Logic vs. complexity theoretic properties of the graph accessibility problem for directed graphs of bounded degree

DOI10.1016/0020-0190(90)90093-DzbMath0695.68042OpenAlexW2047540023MaRDI QIDQ910223

Christoph Meinel

Publication date: 1990

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(90)90093-d

zbMATH Keywords

graph accessibility problemlogarithmic space-bounded computationnonuniform branching programs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Automata and formal grammars in connection with logical questions (03D05)

Cites Work

• Symmetric space-bounded computation
• Modified branching programs and their computational power
• Relationships between nondeterministic and deterministic tape complexities
• A complexity theory based on Boolean algebra
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Logic vs. complexity theoretic properties of the graph accessibility problem for directed graphs of bounded degree