publication . Preprint . 2015

Zero-One Law for Regular Languages and Semigroups with Zero

Sin'ya, Ryoma;
Open Access English
  • Published: 13 May 2015
Abstract
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 only if its syntactic monoid has a zero element. Our proof gives both algebraic and automata characterisation of the zero-one law for regular languages, and it leads the following two corollaries: (i) There is an O(n log n) algorithm for testing whether a given regular language has the zero-one law. (ii) The Boolean closure of existential first-order logic over finite words has the zero-one law.
Subjects
arXiv: Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)
free text keywords: Computer Science - Formal Languages and Automata Theory
Download from
17 references, page 1 of 2

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

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 [OpenAIRE]

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 [OpenAIRE]

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 [OpenAIRE]

11. Berstel, J.: Sur la densit´e asymptotique de langages formels. In: International Colloquium on Automata, Languages and Programming (ICALP, 1972), France, North-Holland (1973) 345-358 [OpenAIRE]

12. Salomaa, A., Soittola, M.: Automata: Theoretic Aspects of Formal Power Series. Springer-Verlag New York, Inc., Secaucus, NJ, USA (1978)

13. Bodirsky, M., Grtner, T., von Oertzen, T., Schwinghammer, J.: Efficiently computing the density of regular languages. In Farach-Colton, M., ed.: LATIN 2004: Theoretical Informatics. Volume 2976 of Lecture Notes in Computer Science. Springer Berlin Heidelberg (2004) 262-270

14. Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press, New York, NY, USA (2009)

15. Kl´ıma, O.: On varieties of automata enriched with an algebraic structure (extended abstract). In: Proceedings 14th International Conference on Automata and Formal Languages, Szeged, Hungary, May 27-29, 2014. Volume 151 of Electronic Proceedings in Theoretical Computer Science., Open Publishing Association (2014) 49-54

17 references, page 1 of 2
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue