• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Congruence Preserving Functions of Wilke's Tree Algebras

Saeed Salehi, Congruence Preserving Functions of Wilke's Tree Algebras. Algebra Universalis 53(4), 451 – 470, 2005.

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.

BibTeX entry:

@ARTICLE{jSalehi05b,
  title = {Congruence Preserving Functions of Wilke's Tree Algebras},
  author = {Salehi, Saeed},
  journal = {Algebra Universalis},
  volume = {53},
  number = {4},
  publisher = {Birkhäuser Basel},
  pages = {451 – 470},
  year = {2005},
}

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

Publication Forum rating of this publication: level 1

Edit publication