2026-07-23T06:05:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6264 2024-03-06T10:37:55Z ddc:004 open_access

Characterizing Classes of Regular Languages Using Prefix Codes of Bounded Synchronization Delay Diekert, Volker Walter, Tobias formal language synchronization delay variety Rees extension 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Volker Diekert and Tobias Walter 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.129 urn:nbn:de:0030-drops-62642 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.129 eng https://creativecommons.org/licenses/by/3.0/legalcode