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.


68Q45 Formal languages and automata
Full Text: DOI


[1] Barwise, J., Handbook of mathematical logic, (1978), North-Holland Amsterdam
[2] Berstel, J.; Reutenauer, C., LES se´ries formelles et leurs langages, (1985), Masson Paris
[3] Boffa, M., Une remarque sur LES syste‘mes complets d’identite´s rationelles, Theoret. inform. applic., 24, 4, 419-423, (1990)
[4] Bourbaki, N., Alge‘bre, (1981), CCLS, Chap. 1-3
[5] Bouvier, A.; Richard, D., Groupes, (1979), Hermann Paris
[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 London · Zbl 0231.94041
[8] Eilenberg, S., Automata, languages and machines, Vol. A, (1972), Academic Press New York
[9] Eilenberg, S., Automata, languages and machines, Vol. B, (1976), Academic Press New York
[10] Jacobson, N., Basic algebra, Vol. II, (1980), Freeman New York · Zbl 0441.16001
[11] Krob, D., ExpressionsK-rationnelles, (), 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, Lecture Notes in Mathematics (Springer, Berlin) to appear.
[14] Krob, D., A complete system ofb-rational identities, (), 60-73 · Zbl 0766.68081
[15] Lallement, G., Combinatorial semigroup theory, (1979), 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 Paris
[18] Platieau, J., Automates finis et alge‘bres régulie‘res de Kleene, ()
[19] Redko, V.N., On the determining totality of an algebra of regular events, Ukrain. mat. Z., 16, 120-126, (1964), (in Russian)
[20] Redko, V.N., On the algebra of commutative events, Ukrain. mat. Z., 16, 185-195, (1964), (in Russian)
[21] Renault, G., Alge‘bre non commutative, (1975), Gauthiers-Villars Paris
[22] 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 Paris
[27] Tenam, R., Analyse nume´rique, ()
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.