Characterizing Classes of Regular Languages Using Prefix Codes of Bounded Synchronization Delay

Authors Volker Diekert, Tobias Walter



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.129.pdf
  • Filesize: 0.56 MB
  • 14 pages

Document Identifiers

Author Details

Volker Diekert
Tobias Walter

Cite AsGet BibTex

Volker Diekert and Tobias Walter. Characterizing Classes of Regular Languages Using Prefix Codes of Bounded Synchronization Delay. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 129:1-129:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ICALP.2016.129

Abstract

In this paper we continue a classical work of Schützenberger on codes with bounded synchronization delay. He was interested in characterizing those regular languages where the groups in the syntactic monoid belong to a variety H. He allowed operations on the language side which are union, intersection, concatenation and modified Kleene-star involving a mapping of a prefix code of bounded synchronization delay to a group G in H, but no complementation. In our notation this leads to the language classes SD_G(A^{infinity}) and SD_H(A^{infinity}). Our main result shows that SD_H(A^{infinity}) always corresponds to the languages having syntactic monoids where all subgroups are in H. Schützenberger showed this for a variety H if H contains Abelian groups, only. Our method shows the general result for all H directly on finite and infinite words. Furthermore, we introduce the notion of local Rees extensions which refers to a simple type of classical Rees extensions. We give a decomposition of a monoid in terms of its groups and local Rees extensions. This gives a somewhat similar, but simpler decomposition than in Rhodes' synthesis theorem. Moreover, we need a singly exponential number of operations, only. Finally, our decomposition yields an answer to a question in a recent paper of Almeida and Klíma about varieties that are closed under Rees extensions.
Keywords
  • formal language
  • synchronization delay
  • variety
  • Rees extension

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Jorge Almeida and Ondřej Klíma. On the irreducibility of pseudovarieties of semigroups. Journal of Pure and Applied Algebra, 220(4):1517-1524, 2016. URL: http://dx.doi.org/10.1016/j.jpaa.2015.09.015.
  2. André Arnold. A syntactic congruence for rational ω-languages. Theoretical Computer Science, 39:333-335, 1985. Google Scholar
  3. Jean-Camille Birget and John L. Rhodes. Almost finite expansions of arbitrary semigroups. Journal of Pure and Applied Algebra, 32(3):239-287, 1984. Google Scholar
  4. Jean-Camille Birget and John L. Rhodes. Group theory via global semigroup theory. Journal of Algebra, 120(2):284-300, 1989. URL: http://dx.doi.org/10.1016/0021-8693(89)90199-3.
  5. Volker Diekert and Manfred Kufleitner. Omega-rational expressions with bounded synchronization delay. Theory Comput. Syst., 56:686-696, 2015. Google Scholar
  6. Volker Diekert and Manfred Kufleitner. A survey on the local divisor technique. Theoretical Computer Science, 610:13-23, 2015. URL: http://dx.doi.org/10.1016/j.tcs.2015.07.008.
  7. Volker Diekert, Manfred Kufleitner, and Pascal Weil. Star-free languages are Church-Rosser congruential. Theoretical Computer Science, 454:129-135, 2012. URL: http://dx.doi.org/10.1016/j.tcs.2012.01.028.
  8. Volker Diekert and Grzegorz Rozenberg, editors. The Book of Traces. World Scientific, Singapore, 1995. Google Scholar
  9. Samuel Eilenberg. Automata, Languages, and Machines, volume B. Academic Press, New York and London, 1976. Google Scholar
  10. Dominique Perrin. Recent results on automata and infinite words. In Mathematical foundations of computer science, 1984 (Prague, 1984), volume 176 of Lecture Notes in Comput. Sci., pages 134-148. Springer, Berlin, 1984. Google Scholar
  11. Dominique Perrin and Jean-Éric Pin. Infinite words, volume 141 of Pure and Applied Mathematics. Elsevier, Amsterdam, 2004. Google Scholar
  12. Jean-Éric Pin. Varieties of Formal Languages. North Oxford Academic, London, 1986. Google Scholar
  13. John Rhodes and Dennis Allen. Synthesis of the classical and modern theory of finite semigroups. Advances in Mathematics, 11(2):238-266, 1973. URL: http://dx.doi.org/10.1016/0001-8708(73)90010-8.
  14. John L. Rhodes and Benjamin Steinberg. The 𝔮-theory of finite semigroups. Springer Monographs in Mathematics. Springer, 2009. Google Scholar
  15. Marcel-Paul Schützenberger. On finite monoids having only trivial subgroups. Information and Control, 8:190-194, 1965. Google Scholar
  16. Marcel-Paul Schützenberger. Sur les monoides finis dont les groupes sont commutatifs. Rev. Française Automat. Informat. Recherche Opérationnelle Sér. Rouge, 8(R-1):55-61, 1974. Google Scholar
  17. Marcel-Paul Schützenberger. Sur certaines opérations de fermeture dans les langages rationnels. In Symposia Mathematica, Vol. XV (Convegno di Informatica Teorica, INDAM, Roma, 1973), pages 245-253. Academic Press, 1975. Google Scholar
  18. Howard Straubing. Families of recognizable sets corresponding to certain varieties of finite monoids. Journal of Pure and Applied Algebra, 15(3):305-318, 1979. Google Scholar
  19. Howard Straubing. Finite Automata, Formal Logic, and Circuit Complexity. Birkhäuser, Boston, Basel and Berlin, 1994. Google Scholar
  20. Howard Straubing, Denis Thérien, and Wolfgang Thomas. Regular languages defined with generalized quantifiers. Inform. and Comput., 118(2):289-301, 1995. Google Scholar
  21. Wolfgang Thomas. Automata on infinite objects. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, chapter 4, pages 133-191. Elsevier Science Publishers B. V., 1990. Google Scholar
  22. \Thomas Wilke. An algebraic theory for regular languages of finite and infinite words. International Journal of Algebra and Computation, 3(4):447-489, 1993. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail