|Title:||Systematic Parameterized Complexity Analysis in Computational Phonology|
|Abstract:||Systematic Parameterized Complexity Analysis in Computational Phonology
Many computational problems are NP-hard and hence probably do not have
fast, i.e., polynomial time, algorithms. Such problems may yet have
non-polynomial time algorithms, and the non-polynomial time complexities
of these algorithms will be functions of particular aspects of that
problem, i.e., the algorithm's running time is upper bounded by
f(k)|x|^c where f is an arbitrary function, |x| is the size of the
input x to the algorithm, k is an aspect of the problem, and c is a
constant independent of |x| and k. Given such algorithms, it may still
be possible to obtain optimal solutions for large instances of NP-hard
problems for which the appropriate aspects are of small size or value.
Questions about the existence of such algorithms are most naturally
addressed within the theory of parameterized computational complexity
developed by Downey and Fellows.
This thesis considers the merits of a systematic parameterized
complexity analysis in which results are derived relative to all subsets
of a specified set of aspects of a given NP-hard problem. This set of
results defines an ``intractability map'' that shows relative to which
sets of aspects algorithms whose non-polynomial time complexities are
purely functions of those aspects do and do not exist for that problem.
Such maps are useful not only for delimiting the set of possible
algorithms for an NP-hard problem but also for highlighting those
aspects that are responsible for this NP-hardness.
These points will be illustrated by systematic parameterized complexity
analyses of problems associated with five theories of phonological
processing in natural languages -- namely, Simplified Segmental
Grammars, finite-state transducer based rule systems, the KIMMO system,
Declarative Phonology, and Optimality Theory. The aspects studied in
these analyses broadly characterize the representations and mechanisms
used by these theories. These analyses suggest that the computational
complexity of phonological processing depends not on such details as
whether a theory uses rules or constraints or has one, two, or many
levels of representation but rather on the structure of the
representation-relations encoded in individual mechanisms and the
internal structure of the representations.