• 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. TUCS Technical Reports 622, Turku Centre for Computer Science, 2004.

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.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tSaPe04a,
  title = {Positive Varieties of Tree Languages},
  author = {Petkovic, Tatjana and Salehi, Saeed},
  number = {622},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2004},
  keywords = {Tree languages, Tree automata, Variety theorem, Ordered algebra, Ordered monoids},
  ISBN = {952-12-1415-5},
}

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

Edit publication