Re: Regular Tree Grammar vs. Context-Free Grammar

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:

I am wondering if anyone can help me with information about
the relationship between regular tree grammars and CFGs? In particular
do the languages accepted by CFGs include (subsume) the languages
accepted by regular tree grammars?
The right hand sides of the productions of an RTG are trees and those
of a CFG are sequences, but the way the productions of an RTG are
written gives you a CFG if you just turn the meta-notation into
notation! Construct a CFG whose terminal alphabet is augmented with
three symbols: "{", ";" and "}" and turn each RTG production of the
form:

A -> f(X,Y)

into:

A -> f { X ; Y }

and so on. I've changed the brackets and separator to make the
transformation clearer, but there is no need to.
Perhaps you might add this to:
http://en.wikipedia.org/wiki/Regular_tree_grammar

I am a little unsure about the value of saying anything. The trouble
is that the equivalence is not very formal. The Languages of RTGs are sets
of trees and those of CFGs are sets of strings.

All one can say, formally, is that one can construct a CFG whose
language can be mapped to that of the RTG with a rather trivial 1-to-1
function. There is no CFG that describes the same language as an RTG.

And you might just as well augment the terminal set by a disjoint union of
the set {'(', ',', ')'}, a way to say that if these already exist, add a
formally distinct copy. Use indices to make a distinction at need. Then
A -> f(X,Y)
is replaced by
A -> f '(' X ',' Y ')'
which by "abuse of notation" may be written
A -> f(X,Y)
:-)

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.

.

Relevant Pages

  • Re: Regular Tree Grammar vs. Context-Free Grammar
    ... the relationship between regular tree grammars and CFGs? ... do the languages accepted by CFGs include the languages ... The right hand sides of the productions of an RTG are trees and those ... of a CFG are sequences, but the way the productions of an RTG are ...
    (comp.theory)
  • Re: GMP vs. straight C arithmetic
    ... They are higher level instructions than ... with complex objects, stacks, autosizeable matrix arrays and tree ... PROSE, one add operation can be used for creating a new ... I'm not interested in type pre-declared languages. ...
    (comp.programming)
  • Re: New Methodology on Analysis of Language Change
    ... Austronesian languages, then applied to the Papuan languages of Island ... linguistics to show statistical evidence for ancient links between ... languages, from which we obtained a consensus tree [tree length, 224 steps; ...
    (sci.lang)
  • Re: Request
    ... >In this case however I think that "how descent works" is ... >of the family tree of primates. ... No one has yet answered the question of why similarity automatically ... >What on earth makes you think that computer languages _aren't_ ...
    (talk.origins)
  • FW: How come Ada isnt more popular?
    ... In one with representation sharing (and that ... When the GC hits it just traverses the tree ... languages in general and general purpose languages. ... I think that it is very important to be able to get high performace ...
    (comp.lang.ada)