PHRASE STRUCTURE TREES BEAR MORE FRUIT THAN YOU WOULD HAVE THOUGHT* 
Aravind K. Joshi and Leon "S." Levy 
Department of Computer and Bell Telephone Laboratories 
Information Science Whippany, NJ 07981 
The Moore School/D2 
University of Permsylvania 
Philadelphia, PA 1910B 
EXTENDED ABSTRACT** 
There is renewed interest in examining the descriptive 
as well as generative power of phrase s~-~uctur~ gram- 
mars. The primary motivation has come from the recent 
investigations in alternatives to t-~ansfor~ational 
gremmmrs \[e.g., i, 2, 3, 4\]. We will present several 
results and ideas related to phrase structure trees 
which have significant relevance to computational lin- 
guistics. 
We %~_nT to accomplish several objectives in this paper. 
I. We will give a hrief survey of some recent results 
and approaches by various investigators including, of 
course, our own work~ indicating their interr~laticn- ships. 
Here we will review the work related to the notion of 
node admissibility starring with Chomsky) followed by 
the work by McCawley, Peters and Ritchie, Joshi and 
Levy, a~d more recent work of Gazdar. 
We will also discuss other amendments to context-free 
grammars which increase the descriptive power but not 
the generative power. In particular, we will discuss 
the notion of categories with holes as recently intro- 
duced by Gazdam \[3\]. There is an interesting history 
behind this notion. Sage~'s parser explieitly exploits 
such a convention and, in fact, uses it to do some co- 
ordinate st-ructnK-a computation. We suspect that some 
other parsers have this feature also, perhaps ~plicit- 
ly. We will discuss this matter, which obviously is 
of great interes~ to computational linguists. 
2. Our work on local constraints on st-r~/cin/ral descrip- 
tions, \[5, 6\], which is ccmputationally relevant both 
to linguistics and programming language theory, has 
art-~'acted some attention recently; however, the demon- 
srration of these results has re~.ained somewhat inac- 
cessible to many due to the technicalities of the tree 
automata theory. Recently, we have found a way of 
providing an intuitive explanation of these results in 
terms of intel"acting finite state machines (of the , 
usual kind). Besides providing an intuitive and a more 
transparent explanation of our results, this approach 
is computationally more interesting and allows us to 
formulate an interesting question: How large a variable 
set (i.e., the set of nonterminals) is required for a 
phrase slx~cture grammar or how much information does 
a nontermdmal encode? We will present this new 
approach. 
3. We will present some new results which extend the 
"po~er" of local constraints without affecting the chax~ 
acter of earlier results. In particular, we will show 
That local constraints can include, besides the pmope~ 
analysis (PA) predicates and domination (~) pmadicates, 
* This work was partially supported by NSF grant MCS79- 
08401. 
** Full paper will be available at the time of the 
meeting. 
mor~ complex predicates of the following form. 
(1) (PRED N 1 N 2 ... Nn) 
where N I, N2, ... N n are nonterminals mentioned in the 
PA and/or ~ constraint of the rule in which (i) appears 
and PR~ is a predicate which, r~ughly speaking, checks 
fo~ certain domination or left-of (or right-of) rela- 
Tionships among its arguments. Two examples of inTer~ 
est are as follows. 
(2) (CCOFMAND A B C) 
CC0~LND holds if B immediately dominates A and B domi- 
nates C, not necessarily ~iately. Usually the B 
node is an S node. 
(3) (LEFTMOSTSISTER A B) 
LEFTMOSTSISTER holds if A is the leftmost sister of B. 
We will show that introduction of predicates of the type 
(I) do not change the character of our result on local 
cons~-raints. This extension of our earlier work has 
relevance to the forTm~ation of some long distance rules 
without %-mansformations (as well as without the use of 
The categories with holes as suggested by Gazdar). 
We will discuss some of the processing as well as lin- 
guistic relevance of these results. 
4. We will tr~y to compare (at least along two dimen- 
sions) the local const-raint approach to that of Gazdar's 
(specifically his use of categories with holes) and to 
that of Peters' use of linked nodes (as presented 
orally at Stanford recently). 
The dimensions for cc~ison would be (a) economy of 
representation, (b) proliferation of categories, by and 
large semantically vacuous, and (c) computational rele- 
vance of (a) and (b) above. 
5. Co~positional semantics \[8\] is usually context-free, 
i.e., if nodes B and C are immediate descendants of 
node A, then the semantics of A is a composition (de- 
fined appropriately) of the semantics of B and semantics 
of C. Semantics of A depends only on nodes B and C and 
not on any other part of the st-ruerural description in 
which A may appear. Our method of local constraints 
(and to sQme extent Peters' use of linked nodes) opens 
the possibility of defining the semantics of A not only 
in terms of the semantics of B and C, but also in terms 
of sc~e parts of the sZ~-uc~ description in which A 
appears. In this sense, the semantics will be contex-t- 
sensitive. We have achieved some success with This 
aFpLuaeh to the semantics of progr~g languages. We 
will discuss some of ou~ preliminary ideas for extending 
this approach to natural language, in particular, in 
specifying scopes for variable binding. 
6. While developing our theory of local constrains and 
some other related work, we have discovered that it is 
possible to characterize structural descriptions (for 
phrase sl-r~crure gz%m~mars) entirely in terms of trees 
without any labels, i.e., trees which capture the group- 
ing structure wi~hou~ the syntactic categories (which is 
the same as the constitn/ent st-r~cture without the node 
labels \[7\]. This is a surprising result. This result 
41 
provides a way of deter~ how much "~" 
~zerm/nels (syntactic cazeEories) encode and there- 
fore clearly, it has ca~aticnal si~icance. 
Moreover, ~o The extent That The cla/m ~ha~ natural 
languages ere conzex~-bree is valid, this result has 
significant z~levancs to leamabili~y ~\]~eories, 
because our result suEges~s that it might be possible 
to "infer" a phrase s~ruc'~r,e ~ L,-,, jus~ the 
grouping s~ruc~ure of ~he input (i.e., j us~ 
phrase boundaries). Pur~her, the set of 
descrip~iuns wit.bout labels are directly rela~ed to 
the ~ descz'ip~ic~s of a context-free Eramn~z-; 
hence, we may be able to specify '~aTural" syntactic 
categories. 
In summery, we will prese~1: a selectian of mathematical 
resul:s which have sisnifj~lnt z~l.evancs to m=~y aspec~ 
of con~tional lin~is~ics. 
SELECTED R~2~ 
\[I\] Bresnan, J.W., '~vidence for an unbounded T/leory of 
~z~nsformations," ki~ic Analysis, Vol. 2, 
1976. 
\[2\] Gezdar, .G.J.M., "Phrase s-~,%~-%n0z~ grammar," to 
appear zn The Nal-ure of S},nr.actic Representation, 
(eds. P. Jacobscn and G.K. Pu/_Itm~), 1979. 
\[3\] Sazdar, G.J.M., "I~ as a eont~cee language," 
unpublished ms., 1978. 
\[~\] Gazdar, G.J.M., "Unbounded dependencies and c'o- 
ordinate s~I-ocrure," unpublished ms. 1979. 
\[5\] Joshi, A.K. and Levy, L.S., "Local ~,~msforma- 
1:ions," SIAM Journal of Com~inK, 1977. 
\[6\] Joshi, A.K., Levy, L.S., and Yueh, K., "Local 
~ts in uhe syntax and semantics of 
~ing ~," to appear in Journal of 
Theoretical Cc~er Science, 1980. 
~\] Levy, L.S. and Joshi, A.K., "Skeletal 
descriptions," Information and Control, Nov. ig78. 
~\] Knuth, D.E., "Semantics of context-free ~," 
Mar.hem~%-ica.l Systems Theory, 1968. 
\[9\] Sager, N., "$ynr.ac~ic analysis of narura.l lan- 
&,~a~es," in Advances in Cc, mpuzers (eds. M. AI~ and 
M. Rub~ff)~ ~l. 8, Academic Press, New York, 
1967. 
