Paper Info
Title
On The Strength Of Unambiguous Tree Automata
Abstract
This work is a study of the class of non-deterministic automata on infinite trees that are unambiguous i.e. have at most one accepting run on every tree. The motivating question asks if the fact that an automaton is unambiguous implies some drop in the descriptive complexity of the language recognised by the automaton. As it turns out, such a drop occurs for the parity index and does not occur for the weak parity index.More precisely, given an unambiguous parity automaton A of index (i, 2j), we show how to construct an alternating automaton TRANSFORMATION (A) which accepts the same language, but is simpler in terms of the acceptance condition. In particular, if A is a Buchi automaton (i = 0, j = 1) then TRANSFORMATION (A) is a weak alternating automaton. In general, TRANSFORMATION (A) belongs to the class Comp(i + 1, 2j), what implies that it is simultaneously of alternating index (i, 2j) and of the dual index (i + 1, 2j + 1). The transformation algorithm is based on a separation procedure of Arnold and Santo-canale (2005).In the case of non-deterministic automata with the weak parity condition, we provide a separation procedure analogous to the one used above. However, as illustrated by examples, this separation procedure cannot be used to prove a complexity drop in the weak case, as there is no such drop.
Year
DOI
Venue
2018
10.1142/S012905411842011X
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Keywords
Field
DocType
Infinite trees, unambiguity, Rabin-Mostowski index
Discrete mathematics,Combinatorics,Automaton,Transformation algorithm,Descriptive complexity theory,Parity (mathematics),Mathematics,Büchi automaton
Journal
Volume
Issue
ISSN
29
5
0129-0541
Citations 
PageRank 
References 
0
0.34
2
Authors
2
Name
Order
Citations
PageRank
Henryk Michalewski14012.07
Michal Skrzypczak22311.34