Unambiguous Büchi Is Weak

DOI10.1007/978-3-662-53132-7_26MaRDI QIDQ2817398zbMATH OpenOpenAlexFDO

Authors Henryk Michalewski, Michał Skrzypczak

Publication date 30 August 2016

Published in Developments in Language Theory (Search for Journal in Brave)

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

zbMATH Keywords

infinite treesRabin-Mostowski indexunambiguity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: A non-deterministic automaton running on infinite trees is unambiguous if it has at most one accepting run on every tree. The class of languages recognisable by unambiguous tree automata is still not well-understood. In particular, decidability of the problem whether a given language is recognisable by some unambiguous automaton is open. Moreover, there are no known upper bounds on the descriptive complexity of unambiguous languages among all regular tree languages. In this paper we show the following complexity collapse: if a non-deterministic parity tree automaton $A$ is unambiguous and its priorities are between $i$ and $2n$ then the language recognised by $A$ is in the class $Comp(i+1,2n)$. A particular case of this theorem is for $i=n=1$: if $A$ is an unambiguous Buchi tree automaton then $L(A)$ is recognisable by a weak alternating automaton (or equivalently definable in weak MSO). The main motivation for this result is a theorem by Finkel and Simonnet stating that every unambiguous Buchi automaton recognises a Borel language. The assumptions of the presented theorem are syntactic (we require one automaton to be both unambiguous and of particular parity index). However, to the authors' best knowledge this is the first theorem showing a collapse of the parity index that exploits the fact that a given automaton is unambiguous.

Recommendations

• On the power of unambiguity in Büchi complementation
• scientific article; zbMATH DE number 2019881
• scientific article; zbMATH DE number 5233159
• The Büchi Complementation Saga
• The weakest prespecification
• The weakest specifunction
• On weakened quantification
• On weak structures
• Weakly unambiguous morphisms
• Weakly unambiguous morphisms

Cites work

• A gap property of deterministic tree languages.
• Ambiguous classes in \(\mu\)-calculi hierarchies
• Choice functions and well-orderings over the infinite binary tree
• Deciding the weak definability of Büchi definable tree languages
• Forms of determinism for automata
• Games for the -calculus
• scientific article; zbMATH DE number 1304332 (Why is no real title available?)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• scientific article; zbMATH DE number 1136070 (Why is no real title available?)
• scientific article; zbMATH DE number 1136080 (Why is no real title available?)
• scientific article; zbMATH DE number 3339435 (Why is no real title available?)
• On recognizable tree languages beyond the Borel hierarchy
• Rabin-Mostowski index problem: a step beyond deterministic automata
• The Wadge Hierarchy of Deterministic Tree Languages
• Theμ-calculus alternation-depth hierarchy is strict on binary trees

Cited in

(6)

• scientific article; zbMATH DE number 1512707 (Why is no real title available?)
• On the strength of unambiguous tree automata
• Unambiguous languages exhaust the index hierarchy
• On the Way to Alternating Weak Automata
• On unambiguous regular tree languages of index (0,2)
• On the power of finite ambiguity in Büchi complementation

This page was built for publication: Unambiguous Büchi Is Weak

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