Emptiness of Ordered Multi-Pushdown Automata is 2ETIME-Complete

DOI10.1142/S0129054117500332zbMath1387.68129OpenAlexW2788350744MaRDI QIDQ4639894

Peter Habermehl, Benedikt Bollig, Mohamed Faouzi Atig

Publication date: 14 May 2018

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054117500332

zbMATH Keywords

emptiness problemmulti-pushdown automata

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items

Unnamed Item, Unnamed Item, On exteriority notions in book embeddings and treewidth

Cites Work

• Unnamed Item
• Ordered multi-stack visibly pushdown automata
• The structure of the models of decidable monadic theories of graphs
• Iterated stack automata and complexity classes
• Global Model Checking of Ordered Multi-Pushdown Systems
• MSO Decidability of Multi-Pushdown Systems via Split-Width
• A Temporal Logic for Multi-threaded Programs
• A Unifying Approach for Multistack Pushdown Automata
• Scope-bounded multistack pushdown systems: fixed-point, sequentialization, and tree-width
• Reachability of Multistack Pushdown Systems with Scope-Bounded Matching Relations
• Adding nesting structure to words
• Emptiness of Multi-pushdown Automata Is 2ETIME-Complete
• An Infinite Automaton Characterization of Double Exponential Time
• From Multi to Single Stack Automata
• Games on Multi-stack Pushdown Systems
• Alternation
• Linear-Time Model-Checking for Multithreaded Programs under Scope-Bounding
• ADJACENT ORDERED MULTI-PUSHDOWN SYSTEMS
• The tree width of auxiliary storage
• Interprocedural Analysis of Concurrent Programs Under a Context Bound
• Context-Bounded Analysis of Concurrent Queue Systems
• MULTI-PUSH-DOWN LANGUAGES AND GRAMMARS
• Tools and Algorithms for the Construction and Analysis of Systems
• Scope-Bounded Pushdown Languages
• Reachability analysis of pushdown automata: Application to model-checking