Characterizing classes of regular languages using prefix codes of bounded synchronization delay

摘要

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.