Quick links

Complexity of the Simplified Segmental Phonology

Report ID:
TR-388-92
Date:
July 1992
Pages:
19
Download Formats:

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.

Follow us: Facebook Twitter Linkedin