Congruence preserving functions of Wilke’s tree algebras |
| |
Authors: | Saeed Salehi |
| |
Affiliation: | (1) Turku Center for Computer Science, Lemminkäisenkatu 14 A, 20520 Turku, Finland |
| |
Abstract: | As a framework for characterizing families of regular languages of binary trees, Wilke introduced a formalism for defining binary trees that uses six many-sorted operations involving letters, trees and contexts. In this paper a completeness property of these operations is studied. It is shown that all functions involving letters, binary trees and binary contexts which preserve congruence relations of the free tree algebra over an alphabet, are generated by Wilke’s functions, if the alphabet contains at least seven letters. That is to say, the free tree algebra over an alphabet with at least seven letters is affine-complete. The proof yields also a version of the theorem for ordinary one-sorted term algebras: congruence preserving functions on contexts and members of a term algebra are substitution functions, provided that the signature consists of constant and binary function symbols only, and contains at least seven symbols of each rank. Moreover, term algebras over signatures with at least seven constant symbols are affine-complete.Received March 18, 2004; accepted in final form October 8, 2004. |
| |
Keywords: | 08A30 08A40 08A70 68Q45 68Q68 68Q70 68Q42 |
本文献已被 SpringerLink 等数据库收录! |
|