scientific article; zbMATH DE number 2205458

From MaRDI portal
Publication:5316809





There is a well-known connection, described by \textit{W. Taylor} [Aequationes Math. 23, 30--49 (1981; Zbl 0491.08009)], between hyperindentities of an algebra and indentities satisfied by the clone of the algebra. The clone of an algebra is a heterogeneous algebra, and the correspondence between hyperindentities and clone indentities is rather complicated to work with. In the paper this correspondence is studied in a restricted setting, that of hyperindentities of unary algebras (of arbitrary unary type) and identities in the unary clone of unary term operations. This unary clone is just a monoid, usually called the transition monoid of the unary algebra. This correspondence is an important one in automata theory, since any finite unary algebra \(A\) can be regarded as an automaton: the set \(A\) is regarded as the set of states, with one state chosen as an initial state and a subset of \(A\) chosen as the set of final states, and the operations of the algebra regarded as inputs. Then terms and indentities over the unary algebra \(A\) correspond to monoid words from the free monoid generated by the operations of \(A\). In the paper, the correspondence between hyperindentities and clone indentities in this special case of unary algebras and transition monoids is studied. If \(s=t\) is an identity in a finite unary algebra, then the word \(t^A\) is recognized by the automaton corresponding to the unary algebra iff the word \(s^A\) is recognized. If \(s=t\) is even an identity in the finite transition monoid, and, as the authors prove, a hyperindenty in the algebra \(A\), then all words which arise from \(s^A\) by replacing the input letters by arbitrary words are recognized iff the same holds for \(t^A\). The authors also look at generalizations of this approach to algebras of type \((n,n,\dots)\) and the corresponding \(n\)-clones, which correspond to tree automata of type \((n,n,\dots)\).











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5316809)