[Author Login]
Title:Systematic Parameterized Complexity Analysis in Computational Phonology
Authors:Todd Wareham
Abstract:Systematic Parameterized Complexity Analysis in Computational Phonology

Todd Wareham

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.
Article:Version 1