Computational structure of generative phonology and its relation to language comprehension.

Computational structure of generative phonology and its relation to language comprehension. Eric Sven Ristad* MIT Artificial Intelligence Lab 545 Technology Square Cambridge, MA 02139 Abstract We analyse the computational complexity of phonological models as they have developed over the past twenty years. The major results ate that generation and recognition are undecidable for segmental models, and that recognition is NP- hard for that portion of segmental phonology sub- sumed by modern autosegmental models. Formal restrictions are evaluated. 1 Introduction Generative linguistic theory and human language comprehension may both be thought of as com- putations. The goal of language comprehension is to construct structural descriptions of linguistic sensations, while the goal of generative theory is to enumerate all and only the possible (grammat- ical) structural descriptions. These computations are only indirectly related. For one, the input to the two computations is not the same. As we shall see below, the most we might say is that generative theory provides an extensional chatacterlsation of language comprehension, which is a function from surface forms to complete representations, includ- ing underlying forms. The goal of this article is to reveal exactly what generative linguistic theory says about language comprehension in the domain of phonology. The article is organized as follows. In the next section, we provide a brief overview of the com- putational structure of generative phonology. In section 3, we introduce the segmental model of phonology, discuss its computational complexity, and prove that even restricted segmental mod- els are extremely powerful (undecidable). Subse- quently, we consider various proposed and plausi- ble restrictions on the model, and conclude that even the maximally restricted segmental model is likely to be intractable. The fourth section in-. troduces the modern autosegmental (nonlinear) model and discusses its computational complexity. "The author is supported by a IBM graduate fellowship and eternally indebted to Morris Halle and Michael Kenstowicz for teaching him phonol- ogy. Thanks to Noam Chomsky, Sandiway Fong, and Michael Kashket for their comments and assistance. 235 We prove that the natural problem of construct- ing an autosegmental representation of an under- specified surface form is NP-hard. The article concludes by arguing that the complexity proofs are unnatural despite being true of the phonolog- ical models, because the formalism of generative phonology is itself unnatural. The central contributions of this article ate: (i) to explicate the relation between generative theory and language processing, and argue that generative theories are not models of language users primarily because they do not consider the inputs naturally available to language users; and (ii) to analyze the computational complexity of generative phonological theory, as it has developed over the past twenty years, including segmental and autosegmental models. 2 Computational structure of generative phonology The structure of a computation may be described at many levels of abstraction, principally includ- ing: (i) the goal of the computation; (ii) its in- put/output specification (the problem statement), (iii) the algorithm and representation for achiev- ing that specification, and (iv) the primitive opera- tions in which terms the …

Content truncated to 500 words