Efficient inclusion testing for simple classes of unambiguous -automata

DOI10.1016/J.IPL.2012.04.010MaRDI QIDQ436610zbMATHOpenAlexFDO

Authors Dimitri Isaak, Christof Löding

Publication date 25 July 2012

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2012.04.010

zbMATH Keywords

automata theoryformal languagesinclusion\(\omega \)-automataunambiguous automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Unambiguous Büchi automata.
• Publication:4508396
• Equivalence and inclusion problem for strongly unambiguous Büchi automata
• Efficient Inclusion Checking for Deterministic Tree Automata and DTDs
• Efficient reduction of nondeterministic automata with application to language inclusion testing

Cites work

• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• scientific article; zbMATH DE number 2206109 (Why is no real title available?)
• Complementation, Disambiguation, and Determinization of Büchi Automata Unified
• Deciding Equivalence of Finite Tree Automata
• Equivalence and inclusion problem for strongly unambiguous Büchi automata
• On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
• On the minimization of XML schemas and tree automata for unranked trees
• Rational \(\omega\)-languages are non-ambiguous
• Unambiguous Büchi automata.

Cited in

(7)

• Process-centric views of data-driven business artifacts
• Short Witnesses and Accepting Lassos in ω-Automata
• Efficient Inclusion Checking for Deterministic Tree Automata and DTDs
• From LTL to unambiguous Büchi automata via disambiguation of alternating automata
• From LTL to unambiguous Büchi automata via disambiguation of alternating automata
• Markov chains and unambiguous automata
• Testing language containment for \(\omega\)-automata using BDDs

This page was built for publication: Efficient inclusion testing for simple classes of unambiguous \(\omega \)-automata

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