Dynamic Complexity of the Dyck Reachability

DOI10.1007/978-3-662-54458-7_16zbMath1486.68125arXiv1610.07499OpenAlexW2539473767MaRDI QIDQ2988373

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)

Related Items (2)

Dynamic Complexity of the Dyck Reachability ⋮ Dynamic complexity of expansion

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity models for incremental computation
• Dyn-FO: A parallel, dynamic complexity class
• The dynamic complexity of transitive closure is in DynTC\(^{0}\).
• Incremental and decremental evaluation of transitive closure by first- order queries
• On uniformity within \(NC^ 1\)
• Dynamic complexity theory revisited
• The dynamic complexity of formal languages
• Dynamic Complexity of the Dyck Reachability
• Reachability in Succinct and Parametric One-Counter Automata
• Reachability is in DynFO
• The Effects of Bounding Syntactic Resources on Presburger LTL

This page was built for publication: Dynamic Complexity of the Dyck Reachability