Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Congruence Preserving Function...

Congruence Preserving Functions of Wilke's Tree Algebras

Saeed Salehi, Congruence Preserving Functions of Wilke's Tree Algebras. TUCS Technical Reports 614, Turku Centre for Computer Science, 2004.

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,
tress 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.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tSalehi04a,
  title = {Congruence Preserving Functions of Wilke's Tree Algebras},
  author = {Salehi, Saeed},
  number = {614},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2004},
  keywords = {Tree Languages, Term Algebra, Congruence Preserving Functions, Affine-complete Algebras},
  ISBN = {952-12-1370-1},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication