Multi-solid varieties and Mh-transducers

Slavcho Shtrakov

Algebra and discrete mathematics, no. 3 (2007), pp. 113-131

Résumé

We consider the concepts of colored terms and multi-hypersubstitutions. If $t\in W_\tau(X)$ is a term of type $\tau$, then any mapping $\alpha_t:Pos^\mathcal F(t)\to\mathbb N$ of the non-variable positions of a term into the set of natural numbers is called a coloration of $t$. The set $W_\tau^c(X)$ of colored terms consists of all pairs $\langle t,\alpha_t\rangle$. Hypersubstitutions are maps which assign to each operation symbol a term with the same arity. If $M$ is a monoid of hypersubstitutions then any sequence $\rho= (\sigma_1,\sigma_2,\ldots)$ is a mapping $\rho:\mathbb N\to M$, called a multi-hypersubstitution over $M$. An identity $t\approx s$, satisfied in a variety $V$ is an $M$-multi-hyperidentity if its images $\rho[t\approx s]$ are also satisfied in $V$ for all $\rho\in M$. A variety $V$ is $M$-multi-solid, if all its identities are $M-$multi-hyperidentities. We prove a series of inclusions and equations concerning $M$-multi-solid varieties. Finally we give an automata realization of multi-hypersubstitutions and colored terms.

Détail

Keywords: Colored term; multi-hypersubstitution; deduction of identities.