Sur le théorème du defaut

DOI10.1016/0021-8693(79)90113-3zbMath0421.20027OpenAlexW2011933258MaRDI QIDQ1132974

Jean Berstel, J. F. Perrot, Antonio Restivo, Dominique Perrin

Publication date: 1979

Published in: Journal of Algebra (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0021-8693(79)90113-3

zbMATH Keywords

cardinality of a basefree subsemigroups of free semigroupsintersection of free submonoidsrecognizable subsets

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (31)

Many aspects of defect theorems ⋮ On the defect theorem and simplifiability ⋮ A defect property of codes with unbounded delays ⋮ Primitive sets of words ⋮ Elementariness of a finite set of words is co-NP-complete ⋮ The meet operation in the lattice of codes ⋮ On the maximality of languages with combined types of code properties ⋮ Recognizability of morphisms ⋮ Compatibility relations on codes and free monoids ⋮ Sur la détermination du rang d'une équation dans le monoide libre ⋮ A three-word code which is not prefix-suffix composed ⋮ A string-matching interpretation of the equation \(x^ m y^ n = z^ p\) ⋮ On the rank of the subsets of a free monoid ⋮ On the decomposition of prefix codes ⋮ Defect theorems with compatibility relations. ⋮ Deciding whether a finite set of words has rank at most two ⋮ Codes and equations on trees ⋮ Binary codes that do not preserve primitivity ⋮ A note on intersections of free submonoids of a free monoid ⋮ FREE MONOID THEORY: MAXIMALITY AND COMPLETENESS IN ARBITRARY SUBMONOIDS ⋮ On the deficit of a finite set of words ⋮ The intersection of \(3\)-maximal submonoids ⋮ On codes with finite interpreting delay: a defect theorem ⋮ Some algorithms on the star operation applied to finite languages ⋮ Solutions principales et rang d'un système d'équations avec constantes dans le monoide libre ⋮ On the lattice of prefix codes. ⋮ The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids ⋮ A defect theorem for bi-infinite words. ⋮ Binary codes that do not preserve primitivity ⋮ Locally complete sets and finite decomposable codes ⋮ Binary equality sets are generated by two words

Cites Work

• Quelques constructions et algorithmes rélatifs aux sous-monoides d'un monoide libre
• The intersection of free submonoids of a free monoid is free
• A note on variable length codes
• The decidability of the dol prefix problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Sur le théorème du defaut