DAG/POSET Consultancy Fee Conjecture and Chomsky's Formal Language Hierarchy

From: David Halitsky (dhalitsky_at_cumulativeinquiry.com)
Date: 07/29/04 

Date: 29 Jul 2004 12:03:19 -0700

---------------------------------------------------------------
Relevant sci.math thread for context:

The DAG/POSET Conjecture and Quadric Surfaces: Sole Thread for
Discussion/Disclosure
-----------------------------------------------------------------

Background

In message #1 of the above-referenced thread, D Halitsky (Cumulative
Inquiry)
wrote:

****************************************************************************
It is not difficult to prove that if G is any finite rooted
directed tree on just N vertices such that G is one of following
two types:

[ a [ b [ c d] ] ] (i.e. uniformly right-branching binary)
 A B C C B A

[ a [ b [ c ] ] ] (i.e. derivation tree of "right-regular"
derivation)
 A B C C B A

then the vertices of G represented as (pi,ti,di) will all lie
on two rulings in the surface of a hyperbolic parabolid with equation:

t = (p - ((N-1)/2))**2 - (d - ((N-1)/2))**2

relative to a PTD coordinate system

And if G is any left-branching version of these two trees (instead
of right-branching), then the vertices of G represenrted as (pi,ti,di)
will all also all lie on two rulings of a hyperolic paraboloid
with equation:

 p = (t - ((N-1)/2))**2 - (d - ((N-1)/2))**2

relative to a PTD coordinate system.
*****************************************************************************

Relevance to Chomsky's Formal Language Hierarchy

If this relationship between "dim2-orderable" DAGs and hypars is not
simply a terrible coincidence (cf. JH Conway "The devil bears gifts
also"),
then the relationship indicates that something may be awry in
Chomsky's
original statement of his hierarchy of formal languages. Cause the
kind of tree above in which the deepest vertex has one child IS
the derivation tree of a derivation in a right (or left) linear
grammar
(i.e. a finite-state grammar), whereas the kind of tree above in
which the deepest vertex has two children IS NOT (technically
speaking)
a tree of the derivation in a finite-state grammar, but rather the
tree of a derivation in a very trivial context-free grammar (the next
level up in Chomsky's hierarchy.)

When I saw Noam last fall at MIT (believe me, I was nostalgic for
the old ratty office in the barracks), he understood the point but
immediately asked about the DAG/POSET conjecture in relation to
context-free grammars. At the time I told him I had no answer, but
that one might be forthcoming "soon". (Yeah right!, forth-coming.
fifth-coming, ...)

I think that the work being posted/to be posted by
Stas/Guenter/Robin/Jerry/
David (Wagner) at the sci,math thread:

-------------------------------------------------------------------------------
DAG/POSET consultancy fee conjecture: sole thread here for all future
postings
-------------------------------------------------------------------------------

may lead to an interesting answer to Noam's question along the
following lines:

There IS a class of derivation trees which can be built up one vertex
at
a time (using the vertex-addition method outlined in the first thread
referenced above re quadric surfaces), and this natural class includes
all finite-state derivation trees plus a large class of context-free
derivation trees satisfying a very elegant symmetry condition
discovered
and proved for Cumulative Inquiry by Dr. Robert T. Jamison (Clemson)
several years ago. (I am hoping to convince Robert to let me post a
link
to this work.)

There MAY be a natural class of context-free derivation trees not in
the
above "one vertex at a time" class, but rather definable as being
constructible
by successively adding certain types of small trivial DAGs (each on
more than
one vertex.)

There MAY ALSO be a natural class of context-sensitive derivation
trees which
correspond to natural classes of "dim2 orderable DAGs" in which two
vertices
CAN share children.

What should be kept in mind here is that Noam and SOME of his students
have moved away from a top-down generative model of syntax in which
phrase-structure rewrite rules generate initial derivation trees to a
bottom up generative model of syntax in which the same kinds of
initial
derivation trees are built bottom-up via binary adjunction of small
trees representing words and phrases. (As Noam observes, there's no
real difference except that the latter method permits a stronger
statement of the "autonomous syntax" principle in as much as it
obviates the need for "category" symbols of the type that appear to
the left of the arrow in derivation trees; an another way of saying
this is that it permits non-maximal vertices of derivation trees to
be viewed as "projections" of certain initial maximal vertices.)

So who knows - maybe I will be able to visit Noam sometime in the not
too
distant future and say, OK, here's a neat way of looking at it all the
way
from finite-state to context-sensitive. In which case, I will owe
Stas/Guenter/Robin/Jerry/David the kind of debt that cannot be repaid
by any size consultancy fee.