License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2011.363
URN: urn:nbn:de:0030-drops-33361
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3336/
Go to the corresponding LIPIcs Volume Portal

Duparc, Jacques ; Facchini, Alessandro ; Murlak, Filip

Definable Operations On Weakly Recognizable Sets of Trees

pdf-format:
18.pdf (0.6 MB)

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).

BibTeX - Entry

@InProceedings{duparc_et_al:LIPIcs:2011:3336,
  author =	{Jacques Duparc and Alessandro Facchini and Filip Murlak},
  title =	{{Definable Operations On Weakly Recognizable Sets of Trees}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{363--374},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Supratik Chakraborty and Amit Kumar},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3336},
  URN =		{urn:nbn:de:0030-drops-33361},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.363},
  annote =	{Keywords: alternating automata, Wadge hierarchy, index hierarchy}
}

Keywords: alternating automata, Wadge hierarchy, index hierarchy
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)
Issue Date: 2011
Date of publication: 01.12.2011

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI