On a representation of tree automata (Q1098636): Difference between revisions

All algebras (or tree automata) considered in this paper are finite with a finite number of operations of some fixed arity. In the usual Gluskov- type general product of algebras there is a feedback function which selects for each component algebra the operation to be performed next. The authors introduce a similar product in which the components are finite systems of one-operation algebras and the feedback function selects from each system the algebra to be activated at a given moment. These so called selective products can be employed for representing one- operation algebras. By placing the natural restrictions on the feedback functions one can define selective \(\alpha\) \({}_ i\)-products, quasidirect products etc. Since every algebra decomposes into a system of one-operation algebras and, conversely, each system of one-operation algebras can be combined to form one many-operation algebra, there is a natural correspondence between selective products and one-input general products. The main part of the paper concerns homomorphic representations of unary algebras, a fact the title could have reflected. The authors prove that it is decidable whether a finite mono-unary algebra can be homomorphically represented by an \(\alpha_ 0\)-product (i.e. a loop-free product) of algebras from a given finite set of unary algebras, thus solving a special case of an important representation problem of finite automata. They also give criteria for \(\alpha_ 0\)-completeness of classes of unary algebras and examples of \(\alpha_ 0\)-complete classes. Further results along the same lines concern general products and \(\alpha_ i\)-products with \(i>0\).