tailieunhanh - Báo cáo khoa học: "Computational structure of generative phonology and its relation to language comprehension."

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 NPhard for that portion of segmental phonology subsumed by modern autosegmental models. Formal restrictions are evaluated. | 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 analyze the computational complexity of phonological models as they have developed over the past twenty years. The major results are that generation and recognition are undecidable for segmental models and that recognition is NP-hard for that portion of segmental phonology subsumed by modern autosegmental models. Formal restrictions are evaluated. 1 Introduction Generative linguistic theory and human language comprehension may both be thought of as computations. 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 grammatical 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 characterisation of language comprehension which is a function from surface forms to complete representations including 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 computational structure of generative phonology. In section 3 we introduce the segmental model of phonology discuss its computational complexity and prove that even restricted segmental models are extremely powerful undecidable . Subsequently we consider various proposed and plausible restrictions on the model and conclude that even the maximally restricted segmental model is likely to be intractable. The fourth section introduces the modern autosegmental nonlinear model and discusses its computational complexity. The author is supported by a .