Computational Complexity of Natural Morphology Revisited (2024)

Abstract: This paper revisits a classical, yet fundamental, discussion of theoretical computational linguistics: the computational complexity of natural languages. Past studies have revealed that syntax, as observed in Swiss-German, is not weakly context-free. Concerning morphology, Culy (1985) employed a construction in Bambara to show that morphology is not weakly context-free; however, Manaster-Ramer (1988) pointed out that the Bambara case can be problematic because the wordhood of the construction is reliant on special tonal behaviors, and it is ambiguous whether the behaviors belong to the morphological domain. This raises doubts about whether the case can be considered a genuine morphological phenomenon. In this paper, we argue that Classical Ainu, a language we examine, also defies weak context-freeness at the morphological level. The construction we introduce is unambiguously morphological because this language’s valency-sensitive structure and valency-changing operations, such as noun incorporation, preclude its grammatical interpretation as syntactic.

## data this section provides real-world examples in a natural language that supports the validity of a set of formal rules used in section 4. similar to the case of the defunct language old georgian, which @xcite used in their complexity study, today it is practically impossible to directly assess the grammaticality of classical ainu words with native speakers because this language is highly endangered @xcite . therefore, we collected linguistic data to support the construction as far as possible. ## proof we define ad-hoc lexical models that are intended to capture the properties of the classical ainu lexicon. more refined approaches may model the lexical semantics of verb arguments @xcite ; however, it is beyond the scope of this study. definition 4.1 (base valency-sensitive lexicon). first, we define a base valency-sensitive lexicon l ⊆ σ × z × i × τ , where there may be several lexemes (entries) for one string. for instance, in english, the verb ''give'' has three entries (give, 1, ∅, head), (give, 2, ∅, head), (give, 3, ∅, head), which correspond to monovalent (intransitive), bivalent (monotransitive), and trivalent (ditransitive), respectively. ## conclusion this study demonstrates that classical ainu is not weakly context-free unambiguously at the morphological level because of its valency-sensitive structure and valency-changing operators. thus, we reconfirmed the weak inadequacy of cfgs for natural morphology. however, the properties of valency, polysynthesis, ni, and af have not yet been fully explored in computational linguistics. further examinations may provide more insight into natural languages and aid cognitive and engineering studies.