×

Complete systems of \(\mathcal B\)-rational identities. (English) Zbl 0737.68053

Two conjectures of Conway on rational expressions of languages are proved: the two following systems of identities are complete systems of identities (i.e. each rational identity is a consequence of the system):
1. The identities \((M)\), \((S)\) and \(P(M)\) for each finite monoid \(M\).
2. The identities \((M)\), \((S)\) and \(P(G)\) for each finite group \(G\).
There special identities are: \((M)\) \((ab)^*=1+a(ba)^*b\); \((S)\) \((a+b)^*=(a^*b)^*a^*\); \(P(M)\) \(A^*_ M=\sum_{m\in M}\varphi^{-1}_ M(m)\), where \(A_ M\) is an alphabet in bijection with \(M\), \(\varphi_ M: A^*_ M\to M\) the natural monoid homomorphism, and \(\varphi^{-1}_ M(m)\) represents a rational expression naturally associated to this language.
The considerable work done by the author in order to solve these conjectures has many byproducts: completeness of certain meta-rule systems; characterization fo aperiodic semigroups by deductibility of their rational expression from \((M)\) and \((S)\); formal proof of Schützenberger’s star-free theorem; deduction of the matrix semigroup identity from the semigroup identity; stability of identities under operations (subsemigroup, quotient, semidirect product), which allows to use the theorem of Krohn-Rhodes; completeness of \((M)\), \((S)\) together with the symmetric group identities.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barwise, J., Handbook of Mathematical Logic (1978), North-Holland: North-Holland Amsterdam · Zbl 0443.03001
[2] Berstel, J.; Reutenauer, C., Les Se´ries Formelles et leurs Langages (1985), Masson: Masson Paris · Zbl 0573.68037
[3] Boffa, M., Une remarque sur les syste“mes complets d”identite´s rationelles, Theoret. Inform. Applic., 24, 4, 419-423 (1990) · Zbl 0701.68059
[4] Bourbaki, N., Alge‘bre (1981), CCLS, Chap. 1-3
[5] Bouvier, A.; Richard, D., Groupes (1979), Hermann: Hermann Paris · Zbl 0408.20002
[6] Brzozowski, J. A., Derivatives of regular expressions, J. Assoc. Comput. Mach., 11, 4, 481-494 (1964) · Zbl 0225.94044
[7] Conway, J. H., Regular Algebras and Finite Machines (1974), Chapman & Hall: Chapman & Hall London · Zbl 0231.94041
[8] Eilenberg, S., Automata, Languages and Machines, Vol. A (1972), Academic Press: Academic Press New York
[9] Eilenberg, S., Automata, Languages and Machines, Vol. B (1976), Academic Press: Academic Press New York · Zbl 0359.94067
[10] Jacobson, N., Basic Algebra, Vol. II (1980), Freeman: Freeman New York · Zbl 0441.16001
[11] Krob, D., Expressions \(K\)-rationnelles, (LITP Technical Report (1988), Doctorat d’Universite´, University of Paris 7), 23-88
[12] Krob, D., On aperiodic semigroups, LITP Technical Report, 76-89 (1989)
[13] D. Krob, Expressions rationnelles sur un anneau:Proc. Se´minaire d’ Alge‘bre M.P. Malliavin; D. Krob, Expressions rationnelles sur un anneau:Proc. Se´minaire d’ Alge‘bre M.P. Malliavin
[14] Krob, D., A complete system ofB-rational identities, (Proc. ICALP 90. Proc. ICALP 90, Lecture Notes in Computer Science, Vol. 443 (1990), Springer: Springer Berlin), 60-73 · Zbl 0766.68081
[15] Lallement, G., Combinatorial Semigroup Theory (1979), Wiley: Wiley New York · Zbl 0428.20034
[16] Perrin, D., Finite automata, LITP Technical Report, 26-89 (1989)
[17] Pin, J. E., Varie´t’es de Langages Formel (1985), Masson: Masson Paris
[18] Platieau, J., Automates finis et alge‘bres régulie‘res de Kleene, (Me´moire de Licence (1984), University of Mons)
[19] Redko, V. N., On the determining totality of an algebra of regular events, Ukrain. Mat. Z., 16, 120-126 (1964), (in Russian) · Zbl 0199.04302
[20] Redko, V. N., On the algebra of commutative events, Ukrain. Mat. Z., 16, 185-195 (1964), (in Russian) · Zbl 0199.04303
[21] Renault, G., Alge‘bre Non Commutative (1975), Gauthiers-Villars: Gauthiers-Villars Paris · Zbl 0307.16001
[22] J. Sakarovitch, Cours de DEA, 86-87, University of Paris VI.; J. Sakarovitch, Cours de DEA, 86-87, University of Paris VI.
[23] Salomaa, A., Two complete axiom systems for the algebra of regular events, J. Assoc. Comput. Mach., 13, 1, 158-169 (1966) · Zbl 0149.24902
[24] Salomaa, A., On regular expressions and regular canonical systems, Math. Systems Theory, 2, 341-355 (1968) · Zbl 0177.01904
[25] Schu¨tzenberger, M. P., On finite monoids having only trivial subgroups, Inform. and Control, 8, 190-194 (1965) · Zbl 0131.02001
[26] Serre, J. P., Repre´sentation Line´aire des Groupes Finis (1979), Hermann: Hermann Paris
[27] Tenam, R., Analyse nume´rique, (Cours de Maitrise (1969/70), University of Orsay)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.