Complexity of the Simplified Segmental Phonology
Report ID: TR-388-92Author: Ristad, Eric Sven
Date: 1992-08-00
Pages: 19
Download Formats: |Postscript|
Abstract:
This article presents detailed complexity analysis of the encoding and decoding problems for the segmental phonology. The segmental model is a generative theory of phonological dependencies. As such, it poses two computational problems. The first computational problem is the problem of actually encoding the dependencies of a given phonology into a given representation of phonological knowledge (the encoding problem). The second computational problem is the problem of deciding whether a given phonological representation encodes the dependencies of a given phonology (the decoding problem). We begin by proving that the encoding and decoding problems are both undecidable in the segmental model. Next, we motivate a simplified segmental model, that more accurately models the phonological dependencies actually proposed in the phonological literature. The simplified segmental model is a more restricted and more natural reformalization of the segmental model. To conclude, we prove that the encoding and decoding problems are NP-complete in this simplified segmental model.