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

A Completeness Property of Wilke's Tree Algebras

Saeed Salehi, A Completeness Property of Wilke's Tree Algebras. In: Mathematical Foundations of Computer Science 2003, Lecture Notes in Computer Science 2747, 662–670, Springer-Verlag, 2003.

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.

BibTeX entry:

@INPROCEEDINGS{inpSalehi03a,
  title = {A Completeness Property of Wilke's Tree Algebras},
  booktitle = {Mathematical Foundations of Computer Science 2003},
  author = {Salehi, Saeed},
  volume = {2747},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {662–670},
  year = {2003},
}

Belongs to TUCS Research Unit(s): Other

Publication Forum rating of this publication: level 1

Edit publication