LIPIcs.STACS.2008.1318.pdf
- Filesize: 170 kB
- 12 pages
Document
Weak index versus Borel rank
Author
-
Part of:
Volume:
25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution-NoDerivs 3.0 Unported license
- Publication Date: 2008-02-06
Cite AsGet BibTex
Filip Murlak. Weak index versus Borel rank. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 573-584, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/LIPIcs.STACS.2008.1318
https://doi.org/10.4230/LIPIcs.STACS.2008.1318
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.
Keywords
- Weak index
- Borel rank
- deterministic tree automata
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads