Complete systems of \(\mathcal B\)-rational identities (Q1177930)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Complete systems of \(\mathcal B\)-rational identities |
scientific article |
Statements
Complete systems of \(\mathcal B\)-rational identities (English)
0 references
26 June 1992
0 references
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.
0 references
\(\mathcal B\)-rational expressions
0 references
matrix identities
0 references
+ operation
0 references
maximal ideals of a semigroup
0 references