×

Hiérarchies de concaténation. (French) Zbl 0559.68062

Un article de style algébrique haut, avec un résumé suffisamment étendu: ”On sait qu’il existe une correspondence bijective entre les variétés de langages reconnaissables et les variétés de semi- groupes finis. Dans cet article, je définis des hiérarchies de variétés de langages basées sur le produit de concaténation et je donne une description purement algébrique des hiérarchies de semi- groupes correspondantes. On retrouve ainsi comme cas particuliers diverses hiérarchies déjà connues. La construction proposée repose sur le résultat suivant: tout langage reconnu par le produit de Schützenberger de monoïdes \(M_ 0,...,M_ n\) est dans l’algèbre de Boole engendrée par les langages de la forme \(L_{i_ 0}a_ 1L_{i_ 1}...a_ rL_{i_ r}\quad (0\leq i_ 0<i_ 1<...<i_ r\leq n)\) où les \(a_ k\) sont des lettres et les \(L_{i_ k}\) des langages reconnus par \(M_{i_ k}\) (0\(\leq k\leq r)\). Enfin je montre un résultat général de décidabilité qui permet de retrouver un résultat de théorie des semi-groupes: étant donné un semi-groupe fini S et un entier n, on peut décider si S divise un produit en couronne de n demi-treillis.”
Reviewer: G.Păun

MSC:

68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.
PDF BibTeX XML Cite
Full Text: EuDML

References:

[1] 1. J. A. BRZOZOWSKI, Hierarchies of Aperiodic Languages, R.A.I.R.O., Informatique Théorique, vol. 10, 1976, p. 33-49. MR428813
[2] 2. J. A. BRZOZOWSKI et R. KNAST, The Dot-Depth Hierarchy of Star-Free Languages is Infinite, J. Computer and System Sciences, vol. 16, 1978, p. 37-55. Zbl0368.68074 MR471451 · Zbl 0368.68074
[3] 3. J. A. BRZOZOWSKI et I. SIMON, Characterizations of Locally Testable Events, Discrete Mathematics, vol. 4, 1973, p. 243-271. Zbl0255.94032 MR319404 · Zbl 0255.94032
[4] 4. S. EILENBERG, Automata, Languages and Machines, vol. B, Academic Press, New York, 1976. Zbl0359.94067 MR530383 · Zbl 0359.94067
[5] 5. R. KNAST, Some Theorems on Graph Congruences, R.A.I.R.O., Informatique Théorique, vol. 17, n^\circ 4, 1983, p. 331-342. MR743893
[6] 6. R. KNAST, A Semigroup Characterization of Dot-Depth One Languages, R.A.I.R.O., Informatique Théorique, vol. 17, n^\circ 4, 1983, p. 321-330. Zbl0522.68063 MR743892 · Zbl 0522.68063
[7] 7. G. LALLEMENT, Semigroups and Combinatorial Applications, Wiley, New York, 1979. Zbl0421.20025 MR530552 · Zbl 0421.20025
[8] 8. J. E. PIN, Variétés de langages et variétés de semi-groupes, Thèse, Paris, 1981.
[9] 9. J. E. Pin et J. SAKAROVITCH, Une application de la représentation matricielle des transductions (à paraître). Zbl0563.68064 · Zbl 0563.68064
[10] 10. J. E. PIN et H. STRAUBING, Monoids of Upper-Triangular Matrices (à paraître). Zbl0635.20028 · Zbl 0635.20028
[11] 11. C. REUTENAUER, Sur les variétés de langages et de monoïdes, Lect. Notes in Computer Science, n^\circ 67, Springer Verlag, Berlin, 1979, p. 260-265. Zbl0411.68066 MR568110 · Zbl 0411.68066
[12] 12. I. SIMON, Hierarchies of Events with Dop-Depth One, Thèse, Université de Waterloo, 1972.
[13] 13. I. SIMON, Piecewise Testable Events, Lect. Notes in Computer Science, n^\circ 33, Springer Verlag, Berlin, 1975, p. 214-222. Zbl0316.68034 MR427498 · Zbl 0316.68034
[14] 14. H. STRAUBING, A Generalization of the Schützenberger Product of Finite Monoids, Theor. Comp. Sc., vol. 13, 1981, p. 137-150. Zbl0456.20048 MR594057 · Zbl 0456.20048
[15] 15. H. STRAUBING, Finite Semigroup Varieties of the Form V * D (à paraître). Zbl0561.20042 · Zbl 0561.20042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.