文章基本信息

标题：Definable Operations On Weakly Recognizable Sets of Trees
本地全文：下载
作者：Jacques Duparc ; Alessandro Facchini ; Filip Murlak 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2011
卷号：13
页码：363-374
DOI：10.4230/LIPIcs.FSTTCS.2011.363
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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).
关键词：alternating automata; Wadge hierarchy; index hierarchy