Abstract
It has been proved by Niwiński and Walukiewicz that a deterministic tree language is either Π\(_{\rm 1}^{\rm 1}\)-complete or it is on the level Π\(_{\rm 3}^{\rm 0}\) of the Borel hierarchy, and that it can be decided effectively which of the two takes place. In this paper we show how to decide if the language recognized by a given deterministic tree automaton is on the Π\(_{\rm 2}^{\rm 0}\), the Σ\(^{\rm 0}_{\rm 2}\), or the Σ\(^{\rm 0}_{\rm 3}\) level. Together with the previous results it gives a procedure calculating the exact position of a deterministic tree language in the topological hierarchy.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bradfield, J.C.: The modal mu-calculus alternation hierarchy is strict. Theoret. Comput. Sci. 195, 133–153 (1998)
Browne, A., Clarke, E.M., Jha, S., Long, D.E., Marrero, W.: An improved algorithm for the evaluation of fixpoint expressions. Theoret. Comput. Sci. 178, 237–255 (1997)
Emerson, E.A., Jutla, C.S.: The complexity of tree automata and logics of programs. In: Proc. FoCS 1988, pp. 328–337. IEEE Computer Society Press, Los Alamitos (1988)
Jurdziński, M., Vöge, J.: A discrete strategy improvement algorithm for solving parity games. In: Emerson, E.A., Sistla, A.P. (eds.) CAV 2000. LNCS, vol. 1855, pp. 202–215. Springer, Heidelberg (2000)
Kechris, A.S.: Classical Descriptive Set Theory. Graduate Texts in Mathematics, vol. 156. Springer, Heidelberg (1995)
Kupferman, O., Safra, S., Vardi, M.: Relating Word and Tree Automata. In: 11th IEEE Symp. on Logic in Comput. Sci., pp. 322–332 (1996)
Lenzi, G.: A hierarchy theorem for the mu-calculus. In: Meyer auf der Heide, F., Monien, B. (eds.) ICALP 1996. LNCS, vol. 1099, pp. 87–109. Springer, Heidelberg (1996)
Mostowski, A.W.: Hierarchies of weak automata and weak monadic formulas. Theoret. Comput. Sci. 83, 323–335 (1991)
Niwiński, D.: On fixed point clones. In: Kott, L. (ed.) ICALP 1986. LNCS, vol. 226, pp. 464–473. Springer, Heidelberg (1986)
Niwiński, D., Walukiewicz, I.: Relating hierarchies of word and tree automata. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol. 1373, pp. 320–331. Springer, Heidelberg (1998)
Niwiński, D., Walukiewicz, I.: A gap property of deterministic tree languages. Theoret. Comput. Sci. 303, 215–231 (2003)
Niwiński, D., Walukiewicz, I.: Deciding nondeterministic hierarchy of deterministic tree automata. In: Proc. WoLLiC 2004(2004) (to appear in Electronic Notes in Theoretical Computer Science)
Otto, M.: Eliminating recursion in μ-calculus. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 531–540. Springer, Heidelberg (1999)
Rabin, M.O.: Decidability of second-order theories and automata on infinite trees. Trans. Amer. Soc. 141, 1–35 (1969)
Seidl, H.: Fast and simple nested fixpoints. Information Processing Letters 59, 303–308 (1996)
Skurczyński, J.: The Borel hierarchy is infinite in the class of regular sets of trees. Theoret. Comput. Sci. 112, 413–418 (1993)
Thomas, W.: Languages, automata, and logic. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 3, pp. 389–455. Springer, Heidelberg (1997)
Urbański, T.F.: On deciding if deterministic Rabin language is in Büchi class. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol. 1853, pp. 663–674. Springer, Heidelberg (2000)
Wagner, K.: Eine topologische Charakterisierung einiger Klassen regulärer Folgenmengen. J. Inf. Process. Cybern. EIK 13, 473–487 (1977)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Murlak, F. (2005). On Deciding Topological Classes of Deterministic Tree Languages. In: Ong, L. (eds) Computer Science Logic. CSL 2005. Lecture Notes in Computer Science, vol 3634. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11538363_30
Download citation
DOI: https://doi.org/10.1007/11538363_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28231-0
Online ISBN: 978-3-540-31897-2
eBook Packages: Computer ScienceComputer Science (R0)