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

Minimal Recognizers and Syntactic Monoids of DR Tree Languages

Ferenc Gecseg, Magnus Steinby, Minimal Recognizers and Syntactic Monoids of DR Tree Languages. In: G. Paun M. Ito, S. Yu (Eds.), Words, Semigroups and Transductions, 155–167, World Scientific, 2001.

Abstract:

The sets recognized by deterministic root-to-frontier tree recognizers, the DR tree languages, are determined by their path
languages. The path language of a tree language T consists of the words describing the paths leading from the root of a
tree in T to its leaves labeled with a given leaf symbol. The Nerode path congruence of a tree language T is defined as
the greatest right congruence saturating all path languages of T. We prove a Nerode-like theorem for DR tree languages
and show how Nerode path congruences correspond to minimal DR recognizers. Similarly, the greatest congruence saturating
the path languages yields the syntactic path monoid of T which is finite for a path closed T exactly in case T is a DR tree
language.

BibTeX entry:

@INBOOK{cGeSt01a,
  title = {Minimal Recognizers and Syntactic Monoids of DR Tree Languages},
  booktitle = {Words, Semigroups and Transductions},
  author = {Gecseg, Ferenc and Steinby, Magnus},
  editor = {M. Ito, G. Paun and S. Yu},
  publisher = {World Scientific},
  pages = {155–167},
  year = {2001},
  keywords = {tree languages, syntactic monoids, deterministic root-to-frontier recognizers},
}

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

Publication Forum rating of this publication: level 2

Edit publication