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

DOI10.1142/S021819671750028XMaRDI QIDQ4588867zbMATH OpenOpenAlexFDO

Authors Volker Diekert, Tobias Walter

Publication date 3 November 2017

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.08981

zbMATH Keywords

formal languageRees extensionsynchronization delayvariety

Mathematics Subject Classification ID

Varieties and pseudovarieties of semigroups (20M07) Semigroups in automata theory, linguistics, etc. (20M35) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Abstract: In this paper we continue a classical work of Sch"utzenberger on codes with bounded synchronization delay. He was interested to characterize 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 $GinH$, but no complementation. In our notation this leads to the language classes $S{D}_G(A^{i}nfty)$ and $S{D}_H(A^{i}nfty$). Our main result shows that $S{D}_H(A^{i}nfty)$ always corresponds to the languages having syntactic monoids where all subgroups are in $H$. Sch"utzenberger 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 products 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 products. 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'ima about varieties that are closed under Rees products.

Recommendations

• Characterizing classes of regular languages using prefix codes of bounded synchronization delay
• Omega-rational expressions with bounded synchronization delay
• Bounds on the variety generated by completely regular syntactic monoids from finite prefix codes
• Bounded synchronization delay in omega-rational expressions
• Completing circular codes in regular submonoids

Cites work

• A survey on the local divisor technique
• A syntactic congruence for rational -languages
• Almost finite expansions of arbitrary semigroups
• AN ALGEBRAIC THEORY FOR REGULAR LANGUAGES OF FINITE AND INFINITE WORDS
• Discrete algebraic methods. Arithmetic, cryptography, automata and groups
• Families of recognizable sets corresponding to certain varieties of finite monoids
• First-order definable languages
• Global structure theories for finite semigroups. Introduction. I: Extension of the fundamental theorem of finite semigroups. II: Axioms for complexity for all finite semigroups. III: Complexity of two-\(J\) class semigroups. IV: Synthesis of the classical
• Group theory via global semigroup theory
• scientific article; zbMATH DE number 3924161 (Why is no real title available?)
• scientific article; zbMATH DE number 4028925 (Why is no real title available?)
• scientific article; zbMATH DE number 3654376 (Why is no real title available?)
• scientific article; zbMATH DE number 3460555 (Why is no real title available?)
• scientific article; zbMATH DE number 3561239 (Why is no real title available?)
• scientific article; zbMATH DE number 3559875 (Why is no real title available?)
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• scientific article; zbMATH DE number 1142314 (Why is no real title available?)
• scientific article; zbMATH DE number 2206109 (Why is no real title available?)
• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• Omega-rational expressions with bounded synchronization delay
• On finite monoids having only trivial subgroups
• On the irreducibility of pseudovarieties of semigroups.
• Regular languages defined with generalized quantifiers
• Star-free languages are Church-Rosser congruential
• The \(\mathfrak q\)-theory of finite semigroups.
• The Schützenberger category of a semigroup.

Cited in

(7)

• Omega-rational expressions with bounded synchronization delay
• Bounded synchronization delay in omega-rational expressions
• Deciding Whether or Not a Synchronous Relation is Regular Prefix
• Characterizing classes of regular languages using prefix codes of bounded synchronization delay
• On All Things Star-Free
• Decidability of membership problems for flat rational subsets of \(\mathrm{GL}(2,\mathbb{Q})\) and singular matrices
• Closing star-free closure

This page was built for publication: Characterizing classes of regular languages using prefix codes of bounded synchronization delay

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4588867)