文档介绍:: .
INFORMATION AND CONTROL 24, 305-335 (1974)
Syntactic Complexity*
BARRY K. ROSEN
IBM Thomas J. Watson Research Center, Yorktown Heights, New York 10598
Several measures of syntactic complexity in mathematical linguistics allow
infinitely many sentences to share a complexity value. Thus there is doubt
about the existence of bounds on the memory requirements of parsing mecha-
nisms in terms of the complexities of their inputs. This paper establishes the
existence of such bounds for all measures which satisfy certain postulates.
The general theorems are applied to the familiar measures of depth, nesting,
and self-embedding, as well as to a new measure. The methods of proof lead to
unexpected linguistic interpretations of the results.
1. INTRODUCTION
In most studies of computational complexity there is little doubt as to how
to measure the complexity of the input to an algorithm; we use the length of a
string, the absolute value of an integer, and the number of nodes and arcs
in a graph. Nor is there doubt that the complexity of the computation is
bounded by some function of the complexity of the input; each complexity
value is assumed by only finitely many inputs. In mathematical linguistics,
however, there is an anomalous situation. Several measures for the syntactic
complexity of sentence structures have been proposed, infinitely many
sentence structures can share a complexity value, and there has been some
disagreement over the abilities of these measures to bound the resource