Simultaneous Amalgamation - Computational Linguistics and Talking Robots - page 152

Applied to LA-content, this phenomenon makes it possible for a raw input
to match (a) more than one concept, (b) more than one proplet shell, and/or
(c) more than one elementary signature. Thereby, (a) and (b) correspond to a
lexical ambiguity in natural language interpretation, and (c) corresponds to a
syntactic-semantic ambiguity. What is the impact of these ambiguities on the
complexity of LA-content defined in 8.2.1?

8.3 Linear Complexity of LA-Content

It is well-known that the only source of complexity in the class of constant
LA-grammars (C-LAGs) is recursive ambiguities (TCS'92). The parsing of an
input is recursively ambiguous if (i) it is recursive and (ii) the recursion repeats
the same kind of ambiguity, resulting in a polynomial or exponential number
of derivation steps (parallel readings). 6 Formal languages with recursive am-
biguity are WW R , accepting input like abcd...dcba (context-free), and WW ,
accepting input like abcd...abcd... (context-sensitive). In these two formal
languages the recursive ambiguity arises in worst-case inputs like aaaaaa . 7
C-LAGs for input without any recursive ambiguity form a sub-class called
C1-LAGs and parse in linear time. The C1-LAGs recognize many context-
sensitive languages, such as a k b k c k ,a k b k c k d k , andsoon, a 2 i , a n 2 , a i ! ,etc.
Given the long history of attempting to fit natural languages into the Phrase
Structure Hierarchy of complexity (cf. FoCL'99, Sects. 8.4 and 8.5), we would
like to know how natural languages fit into the alternative complexity hierar-
chy of LA-grammar. This is equivalent to the empirical question of whether
there exist natural language constructions which are not only ambiguous, but
also recursively ambiguous (cf. FoCL'99, Sect. 12.5).
Recursive/iterative 8 structures are relatively numerous in natural language.
Consider the following examples:

8.3.1 R ECURSIVE STRUCTURES IN NATURAL LANGUAGE

1. Intrapropositional coordination
Examples: (i) The man, the woman, the child, ..., and the cat (noun co-
ordination); cf. rule 5 (N

−

N) in 8.2.1. (ii) Peter bought, peeled, cooked,

6 See FoCL'99, Sects. 11.3 and 11.4.
7 According to the PSG hierarchy, the complexity of WW R is context-free (n 3 ), while that of WW
is context-sensitive (2 n or more; we know of no explicit Phrase Structure Grammar for this context
sensitive language). In LA-grammar, in contrast, both are C2-languages (n 2 polynomial). The formal
LA-grammars for WW R and WW are defined in FoCL'99, 11.5.4 and 11.5.6, respectively.
8 In computer science, every recursive function may be rewritten as an iteration, and vice versa. The
choice between the two usually depends on the application and associated considerations of efficiency.