Emptiness of Multi-pushdown Automata Is 2ETIME-Complete
From MaRDI portal
Publication:3533004
DOI10.1007/978-3-540-85780-8_9zbMATH Open1161.68509OpenAlexW1603445208MaRDI QIDQ3533004FDOQ3533004
Authors: 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
Recommendations
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Alternation
- Iterated stack automata and complexity classes
- Emptiness of Multi-pushdown Automata Is 2ETIME-Complete
- Context-Bounded Analysis of Concurrent Queue Systems
- MULTI-PUSH-DOWN LANGUAGES AND GRAMMARS
- Reachability analysis of pushdown automata: Application to model-checking
- An Infinite Automaton Characterization of Double Exponential Time
Cited In (20)
- Beyond \(\omega \)-regular languages: \(\omega T\)-regular expressions and their automata and logic counterparts
- Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata
- On the complexity of intersecting regular, context-free, and tree languages
- Emptiness of Multi-pushdown Automata Is 2ETIME-Complete
- Automata and Logics for Concurrent Systems: Five Models in Five Pages
- Temporal logics for concurrent recursive programs: satisfiability and model checking
- Decidable models of integer-manipulating programs with recursive parallelism
- Parameterized verification under TSO with data types
- Budget-bounded model-checking pushdown systems
- Ordered multi-stack visibly pushdown automata
- Emptiness of ordered multi-pushdown automata is 2ETIME-complete
- The complexity of model checking multi-stack systems
- On store languages and applications
- Data multi-pushdown automata
- Realizability of concurrent recursive programs
- On pure multi-pushdown automata that perform complete pushdown pops
- From multi to single stack automata
- Context-bounded analysis of TSO systems
- Bounded context switching for valence systems
- Context-free ambiguity detection using multi-stack pushdown automata
This page was built for publication: Emptiness of Multi-pushdown Automata Is 2ETIME-Complete
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3533004)
