Ensembles code-compatibles et une généralisation du théorème de Sardinas-Patterson. (French) Zbl 0574.20053

Do Long Van

Theor. Comput. Sci. 38, 123-132 (1985).

Author’s abstract: One denotes by \(A^{\infty}\) the monoid of all finite and infinite words over an alphabet \(A\). The code-compatibility of a pair \((X,Y)\) of subsets of \(A^{\infty}\) is here defined. A necessary and sufficient condition, which is a generalization of the Sardinas-Patterson theorem [IER Conv. Record 8, 104–108 (1953)], for \((X,Y)\) to be code-compatible is established. It is shown that the class of the submonoids of \(A^{\infty}\) generated by an infinitary code is closed under intersection, and also that, for any two infinitary codes \(X\) and \(Y\), \(X^*\cap Y^*=(X\cap Y)^*\) iff (X,Y) is code-compatible.”

Reviewer: Bedřich Pondělíček (Praha)

MSC:

20M35	Semigroups in automata theory, linguistics, etc.
68Q45	Formal languages and automata

Keywords:

infinite words; code-compatibility; Sardinas-Patterson theorem; submonoids; infinitary code

References:

[1]	Berstel, J.; Perrin, D.; Schützenberger, M.P., Théorie des codes, (1981), LITP Paris, Chapitres I-IV
[2]	Eilenberg, S., ()
[3]	Riley, J.A., The sardinas/patterson and levenstein theorems, Inform. control, 10, 120-136, (1967) · Zbl 0148.40306
[4]	Sardinas, A.A.; Patterson, G.W., A necessary and sufficient condition for unique decomposition of coded message, IER conv. record, 8, 104-108, (1953)
[5]	Tilson, B., The intersection of free submonoids of a free monoid is free, Semigroup forum, 4, 345-350, (1972) · Zbl 0261.20060
[6]	Van, D.L., Codes avec des mots infinis, RAIRO informatique théorique, 16, 371-386, (1982) · Zbl 0498.68053
[7]	Van, D.L., Sous-monoïdes et codes avec des mots infinis, Semigroup forum, 26, 75-87, (1983) · Zbl 0504.68054