Deciding emptiness for stack automata on infinite trees

DOI10.1006/INCO.1994.1073MaRDI QIDQ1333263zbMATH OpenOpenAlexFDO

Authors David Harel, Danny Raz

Publication date 13 September 1994

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/inco.1994.1073

zbMATH Keywords

pushdown automatainfinite treesemptiness problemstack automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Decidability of theories and sets of sentences (03B25) Logic in computer science (03B70)

Recommendations

• A NEW TYPE OF PUSHDOWN AUTOMATA ON INFINITE TREES
• PUSHDOWN AUTOMATA ON INFINITE TREES AND NONDETERMINISTIC CONTEXT-FREE PROGRAMS
• Tree-stack automata
• scientific article; zbMATH DE number 7168170

Cited in

(8)

• Emptiness of zero automata is decidable
• The emptiness problem is undecidable for domains of partial monadic 2- modular tree transformations
• Efficient CTL model-checking for pushdown systems
• Efficient CTL model-checking for pushdown systems
• Modular strategies for recursive game graphs
• Emptiness problems for distributed automata
• Stack and locally finite transformations on structures with reversible transitions
• The tree width of auxiliary storage

This page was built for publication: Deciding emptiness for stack automata on infinite trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1333263)