Re: Regular Tree Grammar vs. Context-Free Grammar

Eric Wohlstadter <wohlstad@xxxxxxxxx> writes:

Yes, this is exactly my interest. If there is an isomorphism from tree
structures to word structures (strings), then we should be able to
evaluate the "power" of regular tree grammars relative to the
classical Chomsky hierarchy of grammars. My thought is that they lie
between regular grammars and context-free grammars. Although, I can't
seem to find any references which actually state this.

Eric

Ben Bacarisse wrote:
haberg@xxxxxxxxxx (Hans Aberg) writes:

In article <87mz5zdru4.fsf@xxxxxxxxx>, Ben Bacarisse
<ben.usenet@xxxxxxxxx> wrote:
.... [stuff deleted]
Indeed. But one also has to add the tedious detail that one is
building a CFG whose language is {flatten(t) | t ∈ L_r} with
flatten: T_Σ ↦ Σ'*
flatten(s) = s
flatten(s(t₁, … t_n)) = s '(' flatten(t₁) ',' … flatten(t_n) ')'
so the result is not equivalent except to computer scientist who can
see that flatten (and, importantly, its inverse) are trivial to compute.


Well, prefix and postfix traversals of trees correspond to Polish and
Reverse Polish (or vice-versa) notations. Those are tivial to
compute, and I don't think you need more than 1 correspondence to get
what you want, e.g. prefix with [Reverse?] Polish and back. You do
need a stack to do the correspondence, so it isn't regular, but it is
context free--in fact, I would be surprised if it wasn't strong LL(1).
There has to be a proof in a compiler (or automata) book of that
somewhere.

This is assuming fixed arity trees, with unambiguous labels. However,
if one is allowed to construct ones own notation for representing that
tree (as one should be allowed, since we are defining that we wish to
map this tree to a traversal), then one simply constructs an
unambiguous notation, such that each tree, has a unique string that
represents it, and exactly it. If the tree family has a node type
which takes an arbitrary number of children, one simply encodes that
number of children that the specific tree being traversed actually
has--parenthesis can do that even for arbitarily long lists.

Hope this helps,
-Chris

*****************************************************************************
Chris Clark Internet : compres@xxxxxxxxxxxxx
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)
------------------------------------------------------------------------------

.

Relevant Pages

  • Re: Three Kinds of Logical Trees
    ... >> That strikes me as a nonstardard definition of the use of metadata, ... I would be surprised if all you really care about is strings. ... Having the tree as the only possible structure is worse than having ... > SQL does not handle well. ...
    (comp.databases.theory)
  • Re: XMas tree lights? Jeez
    ... >lights built into the tree are out. ... >Now it did say when ONE goes out, they dont ALL go out in the strings. ... >Tree is going STRAIGHT BACK to fortunoff this weekend, ... Series-wired lights can be tested easily if you know how they're ...
    (alt.home.repair)
  • Re: Get reference to object in Set
    ... Java is that a Java char is 16 bits wide. ... Strings memoizing their hashes. ... patricia tree than using a HashMap or similar structure. ...
    (comp.lang.java.programmer)
  • Re: Three Kinds of Logical Trees
    ... haven't done a lot of work with XML compared to others, ... metadata & data from an RDBMS into an xml dom tree. ... person might not feel as in touch with Strings as with Documents, ... >> instances of such a type then, no, SQL doesn't handle all trees of this ...
    (comp.databases.theory)
  • Re: Yet again, human evolution: huh?
    ... >> I think they believe that phylogenetic analysis showing a relation ... text strings where errors are introduced into the strings. ... I have a recursive tree drawing program that draws ... introduce additional confusion about how recursion ...
    (talk.origins)