Paper Info
Title
Characterizing Classes Of Regular Languages Using Prefix Codes Of Bounded Synchronization Delay
Abstract
This paper is motivated by the work of Schutzenberger on codes with bounded synchronization delay. He was interested in characterizing those regular languages where groups in the syntactic monoid belong to a variety H. 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 G is an element of H, but no complementation. In our notation, this leads to the language classes SDH(A8). Our main result shows that SDH(A8) coincides with the class of languages having syntactic monoids where all subgroups are in H. We show that this statement holds for all varieties H of finite groups, whereas Schutzenberger proved this result for varieties H containing Abelian groups, only. Our method shows the result for all H 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 Klima about varieties that are closed under Rees extensions.
Year
DOI
Venue
2016
10.1142/S021819671750028X
INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION
Keywords
DocType
Volume
Formal language, synchronization delay, variety, Rees extension
Conference
27
Issue
ISSN
Citations 
6
0218-1967
2
PageRank 
References 
Authors
0.43
5
2
Name
Order
Citations
PageRank
Volker Diekert170267.46
Tobias Walter211710.92