Zero-One Law for Regular Languages and Semigroups with Zero

Preprint English OPEN
Sin'ya, Ryoma;
(2015)
  • Subject: Computer Science - Formal Languages and Automata Theory
    arxiv: Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)

A regular language has the zero-one law if its asymptotic density converges to either zero or one. We prove that the class of all zero-one languages is closed under Boolean operations and quotients. Moreover, we prove that a regular language has the zero-one law if and ... View more
  • References (17)
    17 references, page 1 of 2

    1. Libkin, L.: Elements of Finite Model Theory. SpringerVerlag (2004)

    2. Eilenberg, S., Tilson, B.: Automata, languages and machines. Volume B. Pure and applied mathematics. Academic Press, New-York, San Franciso, London (1976)

    3. Reiterman, J.: The Birkhoff theorem for finite algebras. Algebra Universalis 14 (1982) 1-10

    4. Pin, J.E.: Mathematical foundations of automata theory. http://www.liafa. jussieu.fr/~jep/MPRI/MPRI.html.

    5. Gehrke, M., Grigorieff, S., Pin, J.E.: Duality and equational theory of regular languages. In: Proceedings of the 35th International Colloquium on Automata, Languages and Programming, Part II. ICALP '08, Berlin, Heidelberg, SpringerVerlag (2008) 246-257

    6. Simon, I.: Piecewise testable events. In: Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, London, UK, UK, Springer-Verlag (1975) 214-222

    7. Diekert, V., Gastin, P., Kufleitner, M.: A survey on small fragments of first-order logic over finite words. International Journal of Foundations of Computer Science 19(3) (June 2008) 513-548

    8. Schu¨tzenberger, M.: On finite monoids having only trivial subgroups. Information and Control 8(2) (1965) 190 - 194

    9. Schu¨tzenberger, M.: Sur le produit de concatenation non ambigu. Semigroup Forum 13(1) (1976) 47-75

    10. Rystsov, I.K.: Reset words for commutative and solvable automata. Theoretical Computer Science 172 (1997) 273-279

  • Related Organizations (4)
  • Metrics
Share - Bookmark