Definable Operations On Weakly Recognizable Sets of Trees

Details

Serval ID
serval:BIB_EBB4FD4B6C9F
Type
Inproceedings: an article in a conference proceedings.
Collection
Publications
Institution
Title
Definable Operations On Weakly Recognizable Sets of Trees
Title of the conference
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2011, December 12-14, 2011, Mumbai, India
Author(s)
Duparc J., Facchini A., Murlak F.
Publication state
Published
Issued date
2011
Volume
13
Series
Leibniz International Proceedings in Informatics
Pages
363-374
Language
english
Notes
DBLP:conf/fsttcs/DuparcFM11
Abstract
Alternating automata on infinite trees induce operations on languages which do not preserve natural equivalence relations, like having the same Mostowski--Rabin index, the same Borel rank, or being continuously reducible to each other (Wadge equivalence). In order to prevent this, alternation needs to be restricted to the choice of direction in the tree. For weak alternating automata with restricted alternation a small set of computable operations generates all definable operations, which implies that the Wadge degree of a given automaton is computable. The weak index and the Borel rank coincide, and are computable. An equivalent automaton of minimal index can be computed in polynomial time (if the productive states of the automaton are given).
Keywords
alternating automata, Wadge hierarchy, index hierarchy
Web of science
Create date
09/09/2014 10:09
Last modification date
20/08/2019 16:13
Usage data