Ambiguity hierarchy of regular infinite tree languages

MaRDI QIDQ5155680zbMATH OpenFDO

Authors Doron Tiferet

Publication date 8 October 2021

Full work available at URL https://arxiv.org/abs/2009.02985, https://lmcs.episciences.org/8356

zbMATH Keywords

automata ambiguityparity tree automataregular tree languages

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Recommendations

• On degrees of ambiguity for Büchi tree automata
• scientific article; zbMATH DE number 17556
• On unambiguous regular tree languages of index (0,2)
• On the finite degree of ambiguity of finite tree automata
• Unambiguous languages exhaust the index hierarchy

Cites work

• Ambiguity, nondeterminism and state complexity of finite automata
• Choice functions and well-orderings over the infinite binary tree
• Decidability of Second-Order Theories and Automata on Infinite Trees
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
• Expressing cardinality quantifiers in monadic second-order logic over trees
• scientific article; zbMATH DE number 6680130 (Why is no real title available?)
• scientific article; zbMATH DE number 176157 (Why is no real title available?)
• scientific article; zbMATH DE number 1142314 (Why is no real title available?)
• scientific article; zbMATH DE number 2206109 (Why is no real title available?)
• MSO on the Infinite Binary Tree: Choice and Order
• On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
• Rabin's uniformization problem
• Rational \(\omega\)-languages are non-ambiguous
• Succinct representation of regular languages by Boolean automata
• Testing and generating infinite sequences by a finite automaton
• Unambiguity in automata theory
• Unambiguous languages exhaust the index hierarchy

Cited in

(1)

• scientific article; zbMATH DE number 929652 (Why is no real title available?)

This page was built for publication: Ambiguity hierarchy of regular infinite tree languages

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