Dynamic complexity of the Dyck reachability

DOI10.1007/978-3-662-54458-7_16MaRDI QIDQ2988373zbMATH OpenOpenAlexFDO

Authors Patricia Bouyer, Vincent Jugé

Publication date 19 May 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.07499

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Dynamic complexity is concerned with updating the output of a problem when the input is slightly changed. We study the dynamic complexity of Dyck reachability problems in directed and undirected graphs, where updates may add or delete edges. We show a strong dichotomy between such problems, based on the size of the Dyck alphabet. Some of them are P-complete (under a strong notion of reduction) while the others lie either in DynFO or in NL.

Recommendations

• Dynamic complexity theory revisited
• STACS 2005
• Dynamic complexity of directed reachability and other problems
• Dynamic Complexity under Definable Changes
• On the Quantifier-Free Dynamic Complexity of Reachability

Cites work

• Complexity models for incremental computation
• Dyn-FO: A parallel, dynamic complexity class
• Dynamic complexity of the Dyck reachability
• Dynamic complexity theory revisited
• Dynamic graph queries
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• Incremental and decremental evaluation of transitive closure by first- order queries
• On uniformity within \(NC^ 1\)
• Reachability in Succinct and Parametric One-Counter Automata
• Reachability is in DynFO
• The dynamic complexity of formal languages
• The dynamic complexity of transitive closure is in DynTC\(^{0}\).
• The effects of bounding syntactic resources on Presburger LTL

Cited in

(9)

• Dynamic complexity of expansion
• Dynamic complexity theory revisited
• On the Quantifier-Free Dynamic Complexity of Reachability
• Dynamic complexity of the Dyck reachability
• Dynamic Complexity under Definable Changes
• An Efficient Algorithm for Solving the Dyck-CFL Reachability Problem on Trees
• scientific article; zbMATH DE number 1476488 (Why is no real title available?)
• Dynamic complexity of directed reachability and other problems
• STACS 2005

This page was built for publication: Dynamic complexity of the Dyck reachability

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