Abstract of Paper

A completeness property of Wilkes tree algebras
by Saeed Salehi

Abstract:

Wilke.s tree algebra formalism for characterizing families of
tree languages is based on six operations involving letters, binary trees
and binary contexts. In this paper a completeness property of these operations
is studied. It is claimed that all functions involving letters, binary
trees and binary contexts which preserve all syntactic tree algebra congruence
relations of tree languages are generated by Wilke.s functions,
if the alphabet contains at least seven letters. The long proof is omitted
due to page limit. Instead, a corresponding theorem for term algebras,
which yields a special case of the above mentioned theorem, is proved:
in every term algebra whose signature contains at least seven constant
symbols, all congruence preserving functions are term functions.