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

Positive Varieties of Tree Languages

Tatjana Petkovic, Saeed Salehi, Positive Varieties of Tree Languages. Theoretical Computer Science 347(1-2), 1–35, 2005.

Abstract:

Pin's variety theorem for positive varieties of string languages
and varieties of finite ordered semigroups is proved for trees,
i.e., a bijective correspondence between positive varieties of
tree languages and varieties of finite ordered algebras is
established. This, in turn, is extended to generalized varieties
of finite ordered algebras, which corresponds to Steinby's
generalized variety theorem. Also, families of tree languages and
classes of ordered algebras that are definable by ordered (syntactic or translation) monoids are characterized.

BibTeX entry:

@ARTICLE{jPeSa05a,
  title = {Positive Varieties of Tree Languages},
  author = {Petkovic, Tatjana and Salehi, Saeed},
  journal = {Theoretical Computer Science},
  volume = {347},
  number = {1-2},
  pages = {1–35},
  year = {2005},
}

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

Publication Forum rating of this publication: level 2

Edit publication