Reachability and the power of local ordering

DOI10.1016/0304-3975(95)00034-TzbMATH Open0884.68053MaRDI QIDQ1367543FDOQ1367543

Authors Kousha Etessami, Neil Immerman 

Publication date 29 September 1997

Published in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

jumping automaton on graphstransitive closure operator

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 1414308
• On the complexity of L-reachability
• On the complexity of L-reachability
• scientific article; zbMATH DE number 4041256

Cites Work

• scientific article; zbMATH DE number 3819693 (Why is no real title available?)
• scientific article; zbMATH DE number 4106276 (Why is no real title available?)
• scientific article; zbMATH DE number 167884 (Why is no real title available?)
• scientific article; zbMATH DE number 1414308 (Why is no real title available?)
• An optimal lower bound on the number of variables for graph identification
• Expressibility and Parallel Complexity
• Languages that Capture Complexity Classes
• Nondeterministic Space is Closed under Complementation
• Reachability is harder for directed than for undirected finite graphs
• Space Lower Bounds for Maze Threadability on Restricted Machines
• Tree canonization and transitive closure
• Upper and lower bounds for first order expressibility

Cited In (5)

• Monadic Second-Order Logic and Transitive Closure Logics over Trees
• Using Program Schemes to Capture Polynomial-Time Logically on Certain Classes of Structures
• Title not available (Why is no real title available?)
• Pure Pointer Programs with Iteration
• The locally definable property of the product control structure

This page was built for publication: Reachability and the power of local ordering

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