Abstract
In this paper, we study boolean (not necessarily positive) combinations of open sets. In other words, we study positive boolean combinations of safety and reachability conditions. We give an algorithm, which inputs a regular language of infinite trees, and decides if the language is a boolean combination of open sets.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Blumensath, A.: An algebraic proof of Rabin’s theorem (unpublished manuscript)
Bojańczyk, M.: Algebra for trees. In: Handbook of Automata Theory. European Mathematical Society Publishing House (to appear)
Bojańczyk, M.: A Bounding Quantifier. In: Marcinkowski, J., Tarlecki, A. (eds.) CSL 2004. LNCS, vol. 3210, pp. 41–55. Springer, Heidelberg (2004)
Bojańczyk, M., Idziaszek, T.: Algebra for Infinite Forests with an Application to the Temporal Logic EF. In: Bravetti, M., Zavattaro, G. (eds.) CONCUR 2009. LNCS, vol. 5710, pp. 131–145. Springer, Heidelberg (2009)
Grädel, E., Thomas, W., Wilke, T. (eds.): Automata, Logics, and Infinite Games. LNCS, vol. 2500. Springer, Heidelberg (2002)
McNaughton, R., Papert, S.: Counter-Free Automata. MIT Press (1971)
Perrin, D., Pin, J.-É.: Infinite Words. Elsevier (2004)
Schützenberger, M.P.: On finite monoids having only trivial subgroups. Information and Control 8 (1965)
Straubing, H.: Finite Automata, Formal Languages, and Circuit Complexity. Birkhäuser (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bojańczyk, M., Place, T. (2012). Regular Languages of Infinite Trees That Are Boolean Combinations of Open Sets. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds) Automata, Languages, and Programming. ICALP 2012. Lecture Notes in Computer Science, vol 7392. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31585-5_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-31585-5_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31584-8
Online ISBN: 978-3-642-31585-5
eBook Packages: Computer ScienceComputer Science (R0)