Abstract
We modify an acceptance condition of Büchi automaton on infinite trees: rather than to require that each computation path is successful, we impose various restrictions on the number of successful paths in a run of the automaton on a tree. All these modifications alter the recognizing power of Büchi automata. We examine the classes induced by the acceptance conditions that require ≤α, ≥α, =α successful paths, where α is a cardinal number. It turns out that, except some trivial cases, the “≤” classes are uncomparable with the class Bü of Büchi acceptable tree languages, while the classes “≥” are strictly included in Bü.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Büchi,J.R. (1962) On a decision method in restricted second order arithmetic, in “Logic, Methodology and Philosophy of Science. Proc.1960 Intern. Congr. (E.Nagel et al. eds.),pp. 1–11.
Emerson, E.A. and Jutla, C. (1988) The Complexity of Tree Automata and Logics of Programs, Proc. 29th IEEE FOCS,pp. 328–337.
Rabin, M.O. (1969) Decidability of second-order theories and automata on infinite trees, Trans. AMS 141, pp. 1–35.
Rabin, M.O. (1970) Weakly definable relations and special automata, in “Mathematical Logic and Foundations of Set Theory” (Y.Bar-Hillel, ed.), pp. 1–23.
Street R.S. (1982), Propositional dynamic logic of looping and converse, Inform. Contr. 54, pp. 121–141.
Thomas, W. (1990), Automata on Infinite Objects, in “Handbook of Theoretical Computer Science” (J.v.Leeuwen,ed.).
Vardi, M.Y. and Stockmeyer, L. (1985), Improved Upper and Lower Bounds for Modal Logics of Programs, in Proc.26th FOCS.
Vardi, M.Y. and Wolper, P. (1984), Automata-Theoretic Technics for Modal Logics of Programs in Proc. 16th ACM STOC, pp. 446–456.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Beauquier, D., Nivat, M., Niwiński, D. (1991). About the effect of the number of successful paths in an infinite tree on the recognizability by a finite automaton with Buchi conditions. In: Budach, L. (eds) Fundamentals of Computation Theory. FCT 1991. Lecture Notes in Computer Science, vol 529. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-54458-5_58
Download citation
DOI: https://doi.org/10.1007/3-540-54458-5_58
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-54458-6
Online ISBN: 978-3-540-38391-8
eBook Packages: Springer Book Archive