Emptiness of Multi-pushdown Automata Is 2ETIME-Complete

DOI10.1007/978-3-540-85780-8_9MaRDI QIDQ3533004zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

Recommendations

• Emptiness of ordered multi-pushdown automata is 2ETIME-complete
• From multi to single stack automata
• Model-checking of ordered multi-pushdown automata
• A unifying approach for multistack pushdown automata
• Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata

Cites work

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

Cited in

(20)

• Context-free ambiguity detection using multi-stack pushdown automata
• Context-bounded analysis of TSO systems
• Bounded context switching for valence systems
• 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
• Budget-bounded model-checking pushdown systems
• Parameterized verification under TSO with data types
• 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

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)