Abstract
We show that a Rabin recognizable set of trees is uncountable iff it is of the cardinality continuum iff it contains a non-regular tree. If a Rabin recognizable set L is countable, it can be represented as
where M is a regular set of finite terms and t 1, ..., t n are regular trees. We also design an algorithm which, given a Rabin automaton A, computes the cardinality of the set of trees recognized by A.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
B. Courcelle(1983) Fundamental properties of infinite trees, Theor.Comput.Sci. 25, 95–169.
E.A. Emerson(1985) Automata, tableaux and temporal logics, in: Proc. Workshop on Logics of Programs, LNCS 193, 79–88.
E.A.Emerson and C.Jutla (1988) The complexity of tree automata and logics of programs, Proc. 29th IEEE Symp. on Foundations of Computer Science,, N.Y.,328–337.
F.Gecseg and M.Steinby (1984) Tree Automata, Akademiai Kiado, Budapest.
K.Kuratowski and A.Mostowski(1976) Set Theory, North-Holland.
M.O. Rabin(1969) Decidability of second-order theories and automata on infinite trees, Trans.Amer.Soc.141, 1–35.
M.O.Rabin (1970) Weakly definable relations and special automata, in: Mathematical Logic in Foundations of Set Theory (Y.Bar-Hillel,ed.),1–23.
M.O.Rabin(1972) Automata on infinite objects and Church's problem, Amer.Math.Soc., 1–22.
M.O.Rabin(1977) Decidable theories, in: Handbook of Mathematical Logic (J.Barwise,ed
S. Safra(1988) On The Complexity of ω-Automata, Proc. 29th IEEE Symp. on Foundations of Computer Science, White Plains, N.Y., 319–327.
W. Thomas(1990) Automata on infinite objects, in: Handbook of Theoretical Computer Science, vol.B (J.van Leeuven,ed.), 133–191.
M.Y. Vardi and P.L. Wolper(1986) Automata-theoretic techniques for modal logics of programs, J. Comput.System Sci. 32, 183–221.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Niwiński, D. (1991). On the cardinality of sets of infinite trees recognizable by finite automata. In: Tarlecki, A. (eds) Mathematical Foundations of Computer Science 1991. MFCS 1991. Lecture Notes in Computer Science, vol 520. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-54345-7_80
Download citation
DOI: https://doi.org/10.1007/3-540-54345-7_80
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-54345-9
Online ISBN: 978-3-540-47579-8
eBook Packages: Springer Book Archive