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)

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

zbMATH Keywords

jumping automaton on graphstransitive closure operator

Mathematics Subject Classification ID

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

Cites Work

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

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 that?)
• 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)