Re: Regular Tree Grammar vs. Context-Free Grammar

In article <87irgjdd8d.fsf@xxxxxxxxx>, Ben Bacarisse
<ben.usenet@xxxxxxxxx> wrote:

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.

I did not look at the equivalence so much in detail. But I am working with
tree languages in order to achieve syntactic independence (in the context
of a theorem prover) - I do not know how that relates to this stuff.

But if one has a formal theory of trees, then one can construct a
formal theory of strings by writing each tree such that the
tree comes back when parsed. For example, one might use Lukasiewicz
(prefix) notation.

It seems you do something similar.

--
Hans Aberg
.

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: New Methodology on Analysis of Language Change
    ... the methodology is identical to Ringe et al.'s (yet I didn't notice ... > chart for 5000 languages and come up with a classification that had ... "Trees were then generated for each set of data using maximum parsimony ... Because of the relatively high level of homoplasy found ...
    (sci.lang)
  • Famous Family Trees
    ... Trees": http://groups.google.com/group/famous-family-trees. ... It is supposed to host family trees of every kind except ordinary ... computer languages, Microsoft Windows, the US government organization ... Uralo-Yukaghir Language Super Family.ged ...
    (soc.genealogy.misc)
  • Re: function notation and linguistics (was: Whats so great about lisp?)
    ... S-expressions was probably motivated by syntax trees of natural ... Lisp is designed to be its own metalanguage: ... building new languages on that same format and reasoning about ... it's used for both N expressions and A,NP expressions. ...
    (comp.lang.functional)
  • Re: Where does the drive to syntax come from?
    ... > than parens and prefix notation.) ... > non-programmers have an idea what languages should look like and it's ... data trees. ... (And so lisp is an ~first-order data type in lisp). ...
    (comp.lang.lisp)