All this is fact. Fact explains nothing. On the contrary, it is fact that requires explanation. Marilynne Robinson, Housekeeping 1 Background 1.1 Parameterized Complexity Analysis We can now talkabout algorithm efficiency. Typicalcomputational resources of interest are time and space, which correspond to the number of instruct ions executed or the amount of memory used by the algorithm when it is implementedon some standard type of computer, e.g., adeterministicTuring machine(fordetaileddescriptions of the variouskinds ofTuring machines, see[2,3,4]). For some resource R and problem , let RA : D 7→ N be be the function that gives the amount of resource R that is used by algorithm A to solve a given instance of . The resource-usage behavior of an algor ithm over all possible instances of its associated problem is typically stated in terms of a function of instance size that summarizes thisbehavior in some useful manner. The creation of such functions has three steps: 1. Defineaninstance-lengthfunctionsuch that eachinstanceof theprobl em of interest can be assigned a positive integer size. Let the size of instance I be denoted by |I|. 2. Define a “raw” resource-usage function that summarizes the resource- usage behavior of A for each possible instance size. Let Rn = A {RA(I)|I is an instance of the problemsolved by A and |I|= n}be the R-requirements of algorithm A for all instances of size n. For each instance-size n, choose either one element of or some function of Rn to A represent Rn Several popular ways of doing this are: A. 1 • The highest value in Rn (m worst-case). A • The lowest value in Rn (m best-case). A • The average value of Rn relative to some probability distribution A on instances of size n (m average-case). Let SA : N7→N bethefunctionthatgivesthis chosen valuefor n> 0. 3. “Smooth” the raw resource-usage function SA(n) via a function CA : N7→ N that asymptotically bounds SA(n) in some fashion. Several standard types of asymptotic bounding functions g on a function f are: • m Asymptotic upper bound: f ∈ O(g)if there exists a constant c and n0 ≥ 0 such that for all n> n0, f(n) 0 such that for all n> n0, f(n)>c · g(n). • m Asymptotic tight bound: f ∈ (g)if f ∈ O(g)and f ∈ (g). 1.2 PhonologicalMechanismsasFinite-StateAutomata Definition 1 A m configuration of a FSA A = hQ,,δ,s,Fi is a pair (q,x) where q ∈ Q and x ∈ ∗ . Definition 2 Given two configurations (q,x) and (q ′ ,x ′ ) of aFSA A = hQ,,δ,s,Fi,m (q,x) yields (q ′ ,x ′ ) in one step, i.e., (q,x) ⊢ (q ′ ,x ′ ), if x = wx ′ for some w ∈ ∪{ǫ}and (q,w,q ′ )∈ δ. Let ⊢∗ represent the reflexive transitive closure of the yield relation, i.e., ⊢∗ ′′ ) ′′ (q,x)(q,x if and only if either q = q and x = x or there exists some sequence(q1,x1),(q2,x2),..., (qn,xn)of one or more configurations such that (q,x)⊢ (q1,x1)⊢ (q2,x2)⊢ ··· ⊢ (qn,xn)⊢ (q ′ ,x ′ ). Definition 3 Given a FSA A = hQ,,δ,s,Fi and string x ∈ ∗ , x is m accepted by A if and only if (s,x)⊢∗ (q,ǫ)for some q ∈ F. Essentially, a computation of a FSA on a given string x is a path p in the transition diagram for that FSA such that p starts at the vertex correspondi ng to s and the concatenation of the edge-labels of the edges in p is x; if the final vertex in p corresponds to a state in F, then x is accepted by the FSA. 2 Example 1 Consider the computation of the FSA in [3] on several given strings. If thegiven string is x = baabb, x is accepted as there is a computat ion of the FSA on x which ends at state q3 ∈ F. (q1,baabb) ⊢ (q1,aabb) ⊢ (q2,abb) ⊢ (q2,bb) ⊢ (q3,b) ⊢ (q3,ǫ) However, if x = baabbab, as the state q4 in the final configuration is not in F, x is not accepted. (q1,baabbab) ⊢ (q1,aabbab) ⊢ (q2,abbab) ⊢ (q2,bbab) ⊢ (q3,bab) ⊢ (q3,ab) ⊢ (q4,b) ⊢ (q4,ǫ) Each FSA can be visualized as encoding a set of strings. In the case of those operations defined above which create automata of exactly thesametypeastheirgivenpair of automata, e.g., i/o-deterministic FST intersection, it is possible to define versions of those operations that take as input an arbitrarily large number of automata. Two possible ways of defining these operations are (1) extend the constructions given above relativeto crossproducts onarbitrary numbersof ratherthanpairs of state- sets and(2) iteratethepairwise operations overthegiven set of automata, i.e., repeatedly remove two automata from the given set, apply the pairwise operation, and put the created automaton back in the set until only one automaton is left in the set. For the sake of simplicity, only alternative (2) will be considered in more detail here. In the case of intersection, the automata can be combined in a pairwise fashion in any order; however, as composition is sensitive to the order of its operands, e.g., the composition of A1 and A2 is not necessarily equivalent to the composition of A2 and A1, the automata must be combined in a specified order. For simplicity in 3 the analyses below, assume that automata in a given set are combined in a pairwise manner relative to their order ofappearance whenthat setis written down, i.e., given a set of automata A = {A1,A2,...,Ak }, A1 and A2 will be combined to create A ′ , A ′ and A3 will be combined to create A ′′ , and so on. Under this scheme, for a given set of automata A = {A1,A2,...,Ak }of the appropriate type such that |Q|is the maximum number of states in any automaton in A and ||is the maximum number of symbolsin any alphabet associated with an automaton in A, the time complexities of this iterative process relative to several operations on automata are derived as follows: • ǫ-free FST composition: Given that the composition FST of two ǫf reeFSTA1 = hQ1,i,1,o,1,δ1,s1,F1iand A2 = hQ2,o,1,o,2,δ2,s2,F2i inAcanbe computedin O((|Q1||Q2|)2|i,1||o,1|2|o,2|)= O(|Q|4|||4)= c|Q|4||4 time for some constant c> 0, the composition FST of A can be computed in k O(|Q|2i||4)= c||4k |Q|2i i=2 i=2 ≤ c||4k|Q|2k = O(|Q|2k ||4k) time. • DFA intersection: Given that theintersectionDFA of twoDFA A1 = hQ1,,δ1,s1,F1i and A2 = hQ2,,δ2,s2,F2i in A can be computed in O(|Q1||Q2|||2)= O(|Q|2||2)= c|Q|2||2 time for some constant c> 0, the intersection DFA of A can be computed in k O(|Q|i||2)= c||2k |Q|i i=2 i=2 c||2k |Q|i ≤ i=0 = c||2(|Q|k+1 −1)/(|Q|−1) ≤ c||2|Q|k+1 O(|Q|k+1||2) = time. The time complexities of these operations and upper bounds on the sizes of thecreated automataaregivenforeach of theseoperationsinTable1. Note that if the number of states in each of the given automata is the same, the Upper Bound on Asymptotic Worst-Case Automaton Operation Automaton Size Time Complexity of States Transitions Automaton Creation ǫ-free FST composition i/o-FST intersection |Q|k|Q|k||2 O(|Q|k+1||4), (|Q|k||2) |Q|2k ||2 |Q|k O(|Q|2k ||4k), (|Q|2k ||2) DFA intersection |Q|k |Q|k || O(|Q|k+1||2), (|Q|k ||) |Q|2k ||2 |Q|k ǫ-free FST intersection O(|Q|2k ||4k), (|Q|2k ||2) Table 1: Characteristics of Iterated Finite-State Automaton Operations. This table gives the asymptotic worst-case time complexities of the opera tions of(as well as upperbounds onthe sizes of automata createdby) itera ting various operationsdefined onpairs of automata over sets of automata, where k is the number of automata in the given set, |Q| is the maximum number of states in any automaton in that set, and || is the maximum number of symbols in any alphabet associated with an automaton in that set. given upper bounds on the sizes of automata created by these operations are exact, in that automata may be created that have numbers of states and transitions that are equal to these upper bounds. Hence, though there exist implementations of some of these operations that can be much more efficientthanthegiven naiveimplementationsin certain applications[5,6], the worst-case running times of all such implementations are lower-bounded by the given upper bounds on the sizes of the created automata. Analysis of KIMMO System As KIM-Encode and KIM-Decode are special cases of KIM(N)-Encode and KIM(N)-Decode, respectively, all NP-and W-hardness results der ived above still hold for these new problems. Having insertions and delet ions does allow certain hardness results to hold in more restricted cases; for instance, using the trickgivenin the reductionin[1,Section5.7.2]in which a givenformin a reduction consists oftwodummy terminator symbols and the FST in A are restructured to construct arbitrary requested forms over the nulls in the given form, it is possible to rephrase all hardness results above such that the size of the given form alphabet and the length of the given form are both 2. It seems inevitable that allowing insertions and deletions will also both allow certain hardness results to hold relative to higher leve ls of the W hierarchy and allowparameterizedproblemsthat wereformerly known tohaveFPT algorithms tobe shown W-hard. Thefull extent of these changes will not be addressed here. For now, simply observe that the FPT algorithms based on FST intersection will still work if each FST is modified to accept arbitrary numbers of lexical or surface nulls at any point in proc essing(thiscanbe ensuredby adding to eachFSTthe sets oftransitions {δ(q,0,x)= q |x ∈ s}and {δ(q,x,0)= q |x ∈ u}for every state q ∈ Q), and theFPT algorithmsbased onbrute-force enumeration of allpossible req uested forms will work if the maximum number of nulls that can be added is also a aspectintheparameter(thisis sobecausethe number ofpossible null-augmented versions of a form f over an alphabet that incorporate at Pk |f|+ i most k nulls is |||f | i=1 i ≤|||f |k(|f|+k)k , which is a function of ||, |f|, and k). References [1] G. Edward Barton, Robert C. Berwick, and Eric S. Ristad. 1987. Comp utational Complexity and Natural Language. MIT Press, Cambridge, MA. [2] Michael R. Garey and David S. Johnson. 1979. Computers and Int ractability: A Guide to the Theory of NP-Completeness. W. H. Freem an and Company, San Francisco. [3] JohnE. HopcroftandJeffreyD. Ullman.1979. Introduction toAutomata Theory, Languages, and Computation. Addison-Wesley, Reading, MA. [4] Harry R. Lewis and Christos H. Papdimitriou. 1981. Elements of the Theory of Computation. Prentice Hall, Englewood Cliffs, NJ. [5] Fernando C.N. Pereira and Michael D. Riley. 1997. Speech Recognition by Composition of Weighted Finite Automata. In Emmanuel Roche and Yves Schabes, eds., Finite-State Language Processing, pages 431– 453. MIT Press, Cambridge, MA. [6] Pasi Tapanainen. 1997. Applying a Finite-State Intersection Grammar. InEmmanuelRocheandYvesSchabes,eds., Finite-StateLanguage Proc essing, pages 311–327. MIT Press, Cambridge, MA. Candidate Constraint Violations Full Forms c1 c2 c3 f1 {a1,a1,b1} {b2} φ f2 {b1} {a2} {a3} f3 {b1} {b2} {b3} (a) Candidate Constraint Violations Full Forms c1 c2 c3 f1 [ 2 1 ] [ 0 1 ] [ 0 0 ] f2 [ 0 1 ] [ 1 0 ] [ 1 0 ] f3 [ 0 1 ] [ 0 1 ] [ 0 1 ] (b) Candidate Constraint Violations Full Forms [ c1 c2 c3 ] f1 [ 2 1 0 1 0 0 ] f2 [ 0 1 1 0 1 0 ] f3 [ 0 1 0 1 0 1 ] (c) Figure 1: Evaluation of Candidate Full Forms in Optimality Theory. (a) Marks assigned to candidate full forms f1, f2, and f3 by binary constraints c1, c2, and c3 which have the associated mark-sets {a1,b1}, {a2,b2}, and {a3,b3}, respectively. (b)Evaluation of candidates when c1 ≫ c2 ≫ c3 and ai ≻ bi,1 ≤ i ≤ 3. Note that sets of marks from (a) have been replaced by the appropriately-ordered weight vectors. Optimal candidates are flagged by an arrow (⇒), mark-values that caused the elimination of candidates are underlined, e.g., 1, and mark-values that resulted in a candidate being chosen as optimal areframedby abox, e.g., 0 .(c)Evaluationof(b)relative to appropriately concatenated weight vectors. This shows more clearly the lexicographic optimality ordering on weight vectors.