3
$\begingroup$

I have been reading the book Tata (Tree Automata Techniques and Applications), and there is a sentence I have read thousands of times, yet still don't quite understand.

In the beginning of Chapter 2, the authors want to show that regular string languages and regular tree languages have very much in common:

We shall see [...] that many properties and concepts on regular word languages smoothly generalize to regular tree languages, and that algebraic characterizations of regular languages do exist for tree languages.

The sentence I don't understand then follows:

Actually, this is not surprising since tree languages can be seen as word languages on an infinite alphabet of contexts.

How can I see a tree language as a word language on an infinite alphabet of contexts?

Improve this question
$\endgroup$
4
  • $\begingroup$ Would it make sense to "encode" the derivation path from the root for every leaf in one symbol? A sequence of such symbols might be sufficient to represent trees and can be seen as word language over an infinite alphabet. $\endgroup$
    – Raphael ♦
    Sep 26, 2014 at 10:31
  • $\begingroup$ Maybe. But I do think that the "context"-part in "infinite alphabet of contexts" is important. I don't think they merely mean an infinite alphabet. $\endgroup$
    – john_leo
    Sep 26, 2014 at 12:13
  • 1
    $\begingroup$ I'd say the "derivation path" counts as "context" of the leaf under consideration. Just guessing here, though. $\endgroup$
    – Raphael ♦
    Sep 26, 2014 at 12:35
  • $\begingroup$ Note that "context" is a technical term in this work, page 17, and is like a small tree with varables at its leaves. I cannot explain the observation quoted above, though. $\endgroup$
    – Hendrik Jan
    Sep 26, 2014 at 15:51

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.