Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Tree Algebras and Varieties of...

Tree Algebras and Varieties of Tree Languages

Saeed Salehi, Magnus Steinby, Tree Algebras and Varieties of Tree Languages. TUCS Technical Reports 761, Turku Centre for Computer Science, 2006.

Abstract:

We consider several aspects of Wilke's (1996) tree algebra
formalism for representing binary labelled trees and compare it
with approaches that represent trees as terms in the traditional
way. A convergent term rewriting system yields normal form
representations of binary trees and contexts, as well as a new
completeness proof and a computational decision method for the
axiomatization of tree algebras. Varieties of binary tree
languages are compared with varieties of tree languages studied
earlier in the literature. We also prove a variety theorem thus
solving a problem noted by several authors. Syntactic tree
algebras are studied and compared with ordinary syntactic
algebras. The expressive power of the language of tree algebras is
demonstrated by giving equational definitions for some well-known
varieties of binary tree languages.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tSaSt06a,
  title = {Tree Algebras and Varieties of Tree Languages},
  author = {Salehi, Saeed and Steinby, Magnus},
  number = {761},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2006},
  keywords = {Tree automata, Tree languages, Tree algebras, Binary trees, Varieties of tree languages, Syntactic tree algebras.},
  ISBN = {952-12-1707-3},
}

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

Edit publication