Emptiness of Multi-pushdown Automata Is 2ETIME-Complete

DOI10.1007/978-3-540-85780-8_9zbMath1161.68509OpenAlexW1603445208MaRDI QIDQ3533004

Mohamed Faouzi Atig, Benedikt Bollig, Peter Habermehl

Publication date: 30 October 2008

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85780-8_9

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Realizability of concurrent recursive programs ⋮ On the Complexity of Intersecting Regular, Context-Free, and Tree Languages ⋮ Ordered multi-stack visibly pushdown automata ⋮ The complexity of model checking multi-stack systems ⋮ Automata and Logics for Concurrent Systems: Five Models in Five Pages ⋮ On store languages and applications ⋮ Emptiness of Multi-pushdown Automata Is 2ETIME-Complete ⋮ Temporal logics for concurrent recursive programs: satisfiability and model checking ⋮ Budget-bounded model-checking pushdown systems ⋮ Emptiness of Ordered Multi-Pushdown Automata is 2ETIME-Complete ⋮ Bounded Context Switching for Valence Systems ⋮ Beyond \(\omega \)-regular languages: \(\omega T\)-regular expressions and their automata and logic counterparts ⋮ Context-Bounded Analysis of TSO Systems ⋮ Decidable models of integer-manipulating programs with recursive parallelism ⋮ Context-Free Ambiguity Detection Using Multi-stack Pushdown Automata ⋮ Data Multi-Pushdown Automata

Cites Work

• Iterated stack automata and complexity classes
• Emptiness of Multi-pushdown Automata Is 2ETIME-Complete
• An Infinite Automaton Characterization of Double Exponential Time
• Alternation
• Context-Bounded Analysis of Concurrent Queue Systems
• MULTI-PUSH-DOWN LANGUAGES AND GRAMMARS
• Reachability analysis of pushdown automata: Application to model-checking