Easy multiplications. I: The realm of Kleene's theorem

DOI10.1016/0890-5401(87)90020-4zbMath0642.20043OpenAlexW2047831757WikidataQ56481486 ScholiaQ56481486MaRDI QIDQ1101553

Jacques Sakarovitch

Publication date: 1987

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(87)90020-4

zbMATH Keywords

Green's relationsfree productfree monoidKleene's theoremExtensionsrational monoidsmultiplication of low complexityRees' quotient

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items

On the termination problem for one-rule semi-Thue system ⋮ Slightly commutative Kleene semigroups ⋮ Linear numeration systems of order two ⋮ Quasi-automatic semigroups ⋮ A note on the definition of small overlap monoids. ⋮ A Fibonacci analogue of the two’s complement numeration system ⋮ Generic complexity of finitely presented monoids and semigroups ⋮ Easy multiplications. II: Extensions of rational semigroups ⋮ The homomorphism problem for trace monoids. ⋮ On commutative Kleene monoids ⋮ Which Kleene semigroups are finite? ⋮ ON UNIFORM DECISION PROBLEMS AND ABSTRACT PROPERTIES OF SMALL OVERLAP MONOIDS ⋮ Basic notions of universal algebra for language theory and graph grammars ⋮ Strongly automatic semigroups ⋮ A finiteness criterion for inverse semigroups ⋮ Semigroup automata with rational initial and terminal sets ⋮ ON THE STRUCTURE OF FINITELY GENERATED SEMIGROUPS OF UNARY REGULAR LANGUAGES ⋮ Finite transducers for divisibility monoids ⋮ Small overlap monoids. I: The word problem. ⋮ Small overlap monoids. II: Automatic structures and normal forms. ⋮ Rational Transformations and a Kleene Theorem for Power Series over Rational Monoids ⋮ Where Automatic Structures Benefit from Weighted Automata ⋮ On finitely generated submonoids of virtually free groups ⋮ Equidivisible Kleene monoids and the Elgot-Mezei theorem ⋮ Automata and rational expressions ⋮ Automatic semigroups ⋮ On finitely recognizable semigroups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Equidivisible semigroups
• On Relations Defined by Generalized Finite Automata
• Generalizations of regular events