No label defined (Q5316809)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2205458
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 2205458 |
Statements
15 September 2005
0 references
solid variety
0 references
hyperindentity
0 references
unary clone
0 references
transition semigroup
0 references
transition monoid
0 references
unary algebra
0 references
automata
0 references
0.8293184041976929
0 references
0.7869023084640503
0 references
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)\).
0 references