Abstract
A new class of languages of infinite words is introduced, called the max-regular languages, extending the class of ω-regular languages. The class has two equivalent descriptions: in terms of automata (a type of deterministic counter automaton), and in terms of logic (weak monadic second-order logic with a bounding quantifier). Effective translations between the logic and automata are given.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abdulla, P.A., Krcál, P., Yi, W.: R-automata. In: CONCUR, pp. 67–81 (2008)
Arnold, A.: A syntactic congruence for rational omega-language. Theor. Comput. Sci. 39, 333–335 (1985)
Bojańczyk, M.: A bounding quantifier. In: Computer Science Logic. Lecture Notes in Computer Science, vol. 3210, pp. 41–55. Springer, Berlin (2004)
Bojańczyk, M., Colcombet, T.: Omega-regular expressions with bounds. In: Logic in Computer Science, pp. 285–296 (2006)
Bojańczyk, M., Toruńczyk, S.: Deterministic automata and extensions of weak MSO. Submitted
Colcombet, T.: Factorization forests for infinite words and applications to countable scattered linear orderings. Theor. Comput. Sci. 411(4–5), 751–764 (2010). doi:10.1016/j.tcs.2009.10.013, DBLP, http://dblp.uni-trier.de
Colcombet, T., Löding, C.: The nesting-depth of disjunctive mu-calculus for tree languages and the limitedness problem. In: Computer Science Logic. Lecture Notes in Computer Science, vol. 5213. Springer, Berlin (2008)
Colcombet, T., Löding, C.: The non-deterministic Mostowski hierarchy and distance-parity automata. In: International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 5126, pp. 398–409. Springer, Berlin (2008)
Droste, M., Gastin, P.: Weighted automata and weighted logics. Theor. Comput. Sci. 380(1–2), 69–86 (2007)
Hashiguchi, K.: Algorithms for determining relative star height and star height. Inf. Comput. 78(2), 124–169 (1988)
Kechris, A.S.: Classical Descriptive Set Theory. Graduate Texts in Mathematics, vol. 156. Springer, Berlin (1995)
Kirsten, D.: Distance desert automata and the star height problem. Theor. Inform. Appl. 39(3), 455–511 (2005)
Perrin, D., Pin, J.-É.: Infinite Words. Elsevier, Amsterdam (2004)
Schützenberger, M.P.: On the definition of a family of automata. Inf. Control 4, 245–270 (1961)
Siefkes, D.: The recursive sets in certain monadic second order fragments of arithmetic. Arch. Math. Log. Grundlagenforschung 17, 71–80 (1975)
Thomas, W.: Languages, automata, and logic. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Language Theory, vol. III, pp. 389–455. Springer, Berlin (1997)
Author information
Authors and Affiliations
Corresponding author
Additional information
Author supported by ERC Starting Grant “Sosna”.
Rights and permissions
About this article
Cite this article
Bojańczyk, M. Weak MSO with the Unbounding Quantifier. Theory Comput Syst 48, 554–576 (2011). https://doi.org/10.1007/s00224-010-9279-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-010-9279-2