We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Characterizing classes of regular languages using prefix codes of bounded synchronization delay.
- Authors
Diekert, Volker; Walter, Tobias
- Abstract
This paper is motivated by the work of Schützenberger on codes with bounded synchronization delay. He was interested in characterizing those regular languages where groups in the syntactic monoid belong to a variety . On the language side he allowed the operations union, intersection, concatenation and modified Kleene-star involving a mapping of a prefix code of bounded synchronization delay to a group , but no complementation. In our notation, this leads to the language classes . Our main result shows that coincides with the class of languages having syntactic monoids where all subgroups are in . We show that this statement holds for all varieties of finite groups, whereas Schützenberger proved this result for varieties containing Abelian groups, only. Our method shows the result for all simultaneously on finite and infinite words. Furthermore, we introduce the notion of local Rees extension which refers to a restricted type of the classical Rees extension. 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 the synthesis theorem of Rhodes and Allen. 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.
- Subjects
PROGRAMMING languages; ENTROPY codes; SYNCHRONIZATION; NONPROCEDURAL languages (Programming languages); GROUP theory
- Publication
International Journal of Algebra & Computation, 2017, Vol 27, Issue 6, p561
- ISSN
0218-1967
- Publication type
Article
- DOI
10.1142/S021819671750028X