Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Generalized Contexts and n-ary...

Generalized Contexts and n-ary Syntactic Semigroups of Tree Languages

Antonio Cano Gómez, Magnus Steinby, Generalized Contexts and n-ary Syntactic Semigroups of Tree Languages. TUCS Technical Reports 968, Turku Centre for Computer Science, 2010.

Abstract:

A new type of syntactic monoid and semigroup of tree languages is introduced. For each n ¸ 1, we define for any tree language T its n-ary syntactic monoid M^n(T) and its n-ary syntactic semigroup S^n(T) as quotients of the monoid or semigroup, respectively, formed by certain new generalized contexts. For n = 1 these contexts are just the ordinary contexts (or ’special trees’) and M^1(T) is the syntactic monoid introduced by W. Thomas (1982,1984). Several properties of these monoids and semigroups are proved. For example, it is shown that M^n(T) and S^n(T) are isomorphic to certain monoids and semigroups associated with the minimal tree recognizer of T. Using these syntactic monoids or semigroups, we can associate with any variety of finite monoids or semigroups, respectively, a variety of tree languages. Although there are varieties of tree languages that cannot be obtained this way, we prove that the definite tree languages can be characterized by the syntactic semigroups S^2(T), which is not possible using the classical syntactic monoids or semigroups.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tCaSt10a,
  title = {Generalized Contexts and n-ary Syntactic Semigroups of Tree Languages},
  author = {Cano Gómez, Antonio and Steinby, Magnus},
  number = {968},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2010},
}

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

Edit publication