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)jxj c where f is an arbitrary function, jxj is the size of the input x to the algorithm, k is an aspect of the problem, and c is a constant independent of jxj 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 specied set of aspects of a given NP-hard problem. This set of results denes an \intractability map " that shows relative t