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

DOI10.1016/0020-0190(90)90093-DMaRDI QIDQ910223zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 8782
• Logical complexity of graphs: a survey
• scientific article; zbMATH DE number 4001498
• Capacity complexity of the accessibility problem for frontally bounded digraphs
• Expressiveness and complexity of graph logic
• scientific article; zbMATH DE number 1351076
• Parameterized complexity of graph constraint logic
• A complexity problem for Borel graphs
• The critical complexity of graph properties
• scientific article; zbMATH DE number 219271

Cites work

• scientific article; zbMATH DE number 3909742 (Why is no real title available?)
• scientific article; zbMATH DE number 3987266 (Why is no real title available?)
• scientific article; zbMATH DE number 4051004 (Why is no real title available?)
• A complexity theory based on Boolean algebra
• Modified branching programs and their computational power
• Relationships between nondeterministic and deterministic tape complexities
• Symmetric space-bounded computation

Cited in

(3)

• Lower bounds for the modular communication complexity of various graph accessibility problems
• scientific article; zbMATH DE number 4001498 (Why is no real title available?)
• Capacity complexity of the accessibility problem for frontally bounded digraphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q910223)