On the complexity of L-reachability

DOI10.3233/FI-2016-1371MaRDI QIDQ4976380zbMATH OpenFDO

Authors Balagopal Komarath, Jayalal Sarma M. N., K. S. Sunil

Publication date 28 July 2017

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/FI-2016-1371

zbMATH Keywords

CFL-reachabilityL-reachabilitystructural complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• On the complexity of L-reachability
• Nodes connected by path languages
• Space complexity of reachability testing in labelled graphs
• Space Complexity of Reachability Testing in Labelled Graphs
• Directed planar reachability is in unambiguous log-space

Cited in

(13)

• Reachability and the power of local ordering
• Difficult configurations -- on the complexity of LTrL
• Space complexity of reachability testing in labelled graphs
• On the Quantifier-Free Dynamic Complexity of Reachability
• ReachFewL = ReachUL
• Formal language constrained reachability and model checking propositional dynamic logics
• scientific article; zbMATH DE number 4215383 (Why is no real title available?)
• scientific article; zbMATH DE number 3943037 (Why is no real title available?)
• scientific article; zbMATH DE number 1414308 (Why is no real title available?)
• Nodes connected by path languages
• On the complexity of L-reachability
• Space Complexity of Reachability Testing in Labelled Graphs
• \textsc{ReachFewL} = \textsc{ReachUL}

This page was built for publication: On the complexity of L-reachability

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