Emptiness of zero automata is decidable

DOI10.4230/LIPICS.ICALP.2017.106MaRDI QIDQ5111438zbMATH OpenFDO

Authors Mikołaj Bojańczyk, Hugo Gimbert, Edon Kelmendi

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1702.06858

zbMATH Keywords

monadic second-order logicprobabilistic automatatree automata

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Automata and formal grammars in connection with logical questions (03D05) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 7168170
• Alternating nonzero automata
• When are emptiness and containment decidable for probabilistic automata?
• Probabilistic automata on finite words: decidable and undecidable problems
• Deciding emptiness for stack automata on infinite trees

Cited in

(4)

• Monadic Second Order Logic with Measure and Category Quantifiers
• scientific article; zbMATH DE number 1829145 (Why is no real title available?)
• Alternating nonzero automata
• Polynomial automata: zeroness and applications

This page was built for publication: Emptiness of zero automata is decidable

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