Emptiness of ordered multi-pushdown automata is 2ETIME-complete

DOI10.1142/S0129054117500332MaRDI QIDQ4639894zbMATH OpenOpenAlexFDO

Authors Mohamed Faouzi Atig, Benedikt Bollig, Peter Habermehl

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)

Recommendations

• Emptiness of Multi-pushdown Automata Is 2ETIME-Complete
• Model-checking of ordered multi-pushdown automata
• Global model checking of ordered multi-pushdown systems
• Ordered multi-stack visibly pushdown automata
• From multi to single stack automata

Cites work

• A Temporal Logic for Multi-threaded Programs
• A unifying approach for multistack pushdown automata
• Adding nesting structure to words
• Adjacent ordered multi-pushdown systems
• Alternation
• An Infinite Automaton Characterization of Double Exponential Time
• Context-Bounded Analysis of Concurrent Queue Systems
• Emptiness of Multi-pushdown Automata Is 2ETIME-Complete
• From multi to single stack automata
• Games on Multi-stack Pushdown Systems
• Global model checking of ordered multi-pushdown systems
• scientific article; zbMATH DE number 1059243 (Why is no real title available?)
• Interprocedural Analysis of Concurrent Programs Under a Context Bound
• Iterated stack automata and complexity classes
• Linear-time model-checking for multithreaded programs under scope-bounding
• MSO decidability of multi-pushdown systems via split-width
• MULTI-PUSH-DOWN LANGUAGES AND GRAMMARS
• Ordered multi-stack visibly pushdown automata
• Reachability analysis of pushdown automata: Application to model-checking
• Reachability of multistack pushdown systems with scope-bounded matching relations
• Scope-bounded multistack pushdown systems: fixed-point, sequentialization, and tree-width
• Scope-bounded pushdown languages
• The structure of the models of decidable monadic theories of graphs
• The tree width of auxiliary storage
• Tools and Algorithms for the Construction and Analysis of Systems

Cited in

(8)

• On exteriority notions in book embeddings and treewidth
• Model-checking of ordered multi-pushdown automata
• Emptiness of Multi-pushdown Automata Is 2ETIME-Complete
• From multi to single stack automata
• scientific article; zbMATH DE number 7471708 (Why is no real title available?)
• scientific article; zbMATH DE number 7559472 (Why is no real title available?)
• Forwards- and backwards-reachability for cooperating multi-pushdown systems
• Backwards-reachability for cooperating multi-pushdown systems

This page was built for publication: Emptiness of ordered 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 Q4639894)