License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1318
URN: urn:nbn:de:0030-drops-13182
URL: http://drops.dagstuhl.de/opus/volltexte/2008/1318/
Go to the corresponding Portal

Murlak, Filip

Weak index versus Borel rank

pdf-format:
Document 1.pdf (171 KB)

Abstract

We investigate weak recognizability of deterministic languages of infinite trees. We prove that for deterministic languages the Borel hierarchy and the weak index hierarchy coincide. Furthermore, we propose a procedure computing for a deterministic automaton an equivalent minimal index weak automaton with a quadratic number of states. The algorithm works within the time of solving the emptiness problem.

BibTeX - Entry

@InProceedings{murlak:LIPIcs:2008:1318,
  author =	{Filip Murlak},
  title =	{{Weak index versus Borel rank}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{573--584},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Susanne Albers and Pascal Weil},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1318},
  URN =		{urn:nbn:de:0030-drops-13182},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.STACS.2008.1318},
  annote =	{Keywords: Weak index, Borel rank, deterministic tree automata}
}

Keywords: Weak index, Borel rank, deterministic tree automata
Seminar: 25th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2008
Date of publication: 06.02.2008

DROPS-Home | Fulltext Search | Imprint Published by LZI