Reachability and the power of local ordering

DOI10.1016/0304-3975(95)00034-TzbMath0884.68053MaRDI QIDQ1367543

Kousha Etessami

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)

Related Items (3)

Using Program Schemes to Capture Polynomial-Time Logically on Certain Classes of Structures ⋮ Pure Pointer Programs with Iteration ⋮ Monadic Second-Order Logic and Transitive Closure Logics over Trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Upper and lower bounds for first order expressibility
• An optimal lower bound on the number of variables for graph identification
• Tree canonization and transitive closure
• Reachability is harder for directed than for undirected finite graphs
• Languages that Capture Complexity Classes
• Nondeterministic Space is Closed under Complementation
• Space Lower Bounds for Maze Threadability on Restricted Machines
• Expressibility and Parallel Complexity

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