Theory Group

A Partial Possible Paper Introduction

Jim's asked that I try to come up with an introduction for the Multidimensional trees paper. The tentative approach is to try to start out by showing the two representations of plain-old 2D CFLs (rewriting, local trees), and then raise this comparison to 3+-dimensionality (using TAG as a starting point, or more precisely, the equivalance between the 3-dimensional grammars and TAG). This is very much in flux right now - Jim hasn't had a chance to look at it yet, which means is could easily have big problems.

Traditionally, the context-free grammars are represented as a set of
string replacement rules: given a symbol alphabet $\sigma$, some initial
symbol $I$, a set of terminal symbols $F$, and some set of string
rewriting rules $V$ (each of which map a symbol, $x \in \sigma$, to a
string of symbols, $y \in \sigma^*$), a string $s$ is in the language if
and only if $s \in F^*$ and $s$ can be generated by one or more
successive applications of the rules in $V$.

    Rule 1: S -> S S
    Rule 2: S -> ( S )
    Rule 3: S -> ( )

    String: (())()()

    One possible parse:
      S                   (Initial symbol)
      S S                 (Rule 1)
      ( S ) S             (Rule 2)
      ( S ) S S           (Rule 1)
      ( ( ) ) S S         (Rule 3)
      ( ( ) ) ( ) S       (Rule 3)
      ( ( ) ) ( ) ( )     (Rule 3)

  Figure 1.1:
    Rewriting with a simple 2-dimensional grammar


Equivalently, one can represent the context-free grammars using
two-dimensional trees.  Let $V$ be a set of local trees, each of which
is a one-dimensional ordering of symbols in $\sigma^*$, dominated in the
second dimension by a symbol in $\sigma - F$. Let each member of $F$ be
the one-dimensional root of an empty local tree.  Let the initial symbol
$I$ be the one-dimensional root of an empty derivation tree.
Context-free generation can then be performed by adjoining local trees
in $V$ to the derivation tree - by replacing some one-dimensional leaf
in $I$ with a two-dimensional local tree in $V$ one or more times. The
derived string, at any point in the process, is the one-dimensional
yield of $I$.


    Rule 1:     S
               /
              S---S

    Rule 2:     S
               /
              (-S-)

    Rule 3:     S
               /
              (---)


    One possible parse, with labeled roots:

             (1) S
                 /
            (2) S---------S (1)
               /         /
              /     (3) S------S (3)
             /         /      /
        (3) (--S--)   (---)  (---)
              /
             (---)

    One-dimensional yield:
            ((   ))   (   )  (   )


  Figure 1.2:
    Figure 1.1 using local trees in left-child/right-sibling form

The tree adjoining grammars (TAG) raise the context-free grammars into
three dimensions. A rewriting rule in TAG maps some one-dimensional leaf
node to a two-dimensional tree.

Posted by brownda at July 22, 2004 06:34 PM