\begin{thebibliography}{10} \bibitem{aho-hopcroft-ullman} Alfred~V. Aho, John~E. Hopcroft, and Jeffrey~D. Ullman. \newblock {\em The Design and Analysis of Computer Algorithms}. \newblock Addison-Wesley, 1974. \bibitem{aho-sethi-ullman} Alfred~V. Aho, Ravi Sethi, and Jeffrey~D. Ullman. \newblock {\em Compilers. Principles, Techniques and Tools}. \newblock Addison Wesley, 1986. \bibitem{bird-ellison} Steven Bird and T.~Mark Ellison. \newblock One-level phonology: Autosegmental representations and rules as finite automata. \newblock {\em Computational Linguistics}, 20(1):55--90, 1994. \bibitem{carpenter92} Bob Carpenter. \newblock {\em The Logic of Typed Feature Structures}. \newblock Cambridge University Press, New York, 1992. \bibitem{daciuk-phd} Jan Daciuk. \newblock {\em Incremental Construction of Finite-state Automata and Transducers, and their Use in the Natural Language Processing}. \newblock PhD thesis, Technical University of Gda\'nsk, 1998. \bibitem{daciuk00:compr} Jan Daciuk. \newblock Experiments with automata compression. \newblock In M.~Daley, M.~G. Eramian, and S.~Yu, editors, {\em Conference on Implementation and Application of Automata CIAA'2000}, pages 113--119, London, Ontario, Canada, July 2000. University of Western Ontario. \bibitem{descriptionalcomplexity} J\"urgen Dassow, Gheorge Paun, and Arto Salomaa. \newblock Grammars with controlled derivations. \newblock In Grzegorz Rozenberg and Arto Salomaa, editors, {\em Handbook of Formal Languages Vol.2 Linear Modeling: Background and Application}, pages 101--154. Springer, 1997. \bibitem{eisner} Jason Eisner. \newblock Efficient generation in primitive optimality theory. \newblock In {\em 35th Annual Meeting of the Association for Computational Linguistics and 8th Conference of the European Chapter of the Association for Computational Linguistics}, pages 313--320, 1997. \bibitem{gerdemann-vannoord} Dale Gerdemann and Gertjan van Noord. \newblock Transducers from rewrite rules with backreferences. \newblock In {\em Ninth Conference of the European Chapter of the Association for Computational Linguistics}, Bergen Norway, 1999. \bibitem{eacl99-gerdemann-vannoord} Dale Gerdemann and Gertjan van Noord. \newblock Transducers from rewrite rules with backreferences. \newblock In {\em Ninth Conference of the European Chapter of the Association for Computational Linguistics}, pages 126--133, Bergen Norway, 1999. \bibitem{gildea-jurafsky} Daniel Gildea and Daniel Jurafsky. \newblock Learning bias and phonological-rule induction. \newblock {\em Computational Linguistics}, 22(4):497--530, 1996. \bibitem{hopcroft} John~E. Hopcroft. \newblock An $n$ log $n$ algorithm for minimizing the states in a finite automaton. \newblock In Z.~Kohavi, editor, {\em The Theory of Machines and Computations}, pages 189--196. Academic Press, 1971. \bibitem{hopcroft-ullman} John~E. Hopcroft and Jeffrey~D. Ullman. \newblock {\em Introduction to Automata Theory, Languages and Computation}. \newblock Addison Wesley, 1979. \bibitem{instruction-computation} J.~Howard Johnson and Derick Wood. \newblock Instruction computation in subset construction. \newblock In Darrell Raymond, Derick Wood, and Sheng Yu, editors, {\em Automata Implementation}, pages 64--71. Springer Verlag, 1997. \newblock Lecture Notes in Computer Science 1260. \bibitem{kart-fst} Lauri Karttunen. \newblock Finite-state constraints. \newblock In {\em Proceedings International Conference on Current Issues in Computational Linguistics}, pages 23--40, Universiti Sains Malaysia, Penang, 1991. \bibitem{kart:95} Lauri Karttunen. \newblock The replace operator. \newblock In {\em 33th Annual Meeting of the Association for Computational Linguistics}, pages 16--23, M.I.T. Cambridge Mass., 1995. \bibitem{karttunen:96} Lauri Karttunen. \newblock Directed replacement. \newblock In {\em 34th Annual Meeting of the Association for Computational Linguistics}, pages 108--115, Santa Cruz, 1996. \bibitem{kart:regu96} Lauri Karttunen, Jean-Pierre Chanod, Gregory Grefenstette, and Anne Schiller. \newblock Regular expressions for language engineering. \newblock {\em Natural Language Engineering}, 2(4):305--238, 1996. \newblock http://www.rxrc.xerox.com/research/mltt/fst/articles/jnle-97/rele.html. \bibitem{kempe-factorization} Andr\'e Kempe. \newblock Factorization of ambiguous finite-state transducers. \newblock In {\em CIAA 2000. Fifth International Conference on Implementation and Application of Automata. Preproceedings}, pages 157--164, London, Ontario, Canada, 2000. \bibitem{KempeKarttunen} Andr\'e Kempe and Lauri Karttunen. \newblock Parallel replacement in the finite-state calculus. \newblock In {\em Proceedings of the 16th International Conference on Computational Linguistics (COLING)}, pages 622--627, Copenhagen, Denmark, 1996. \bibitem{kiraz-wia99} George~Anton Kiraz. \newblock Compressed storage of sparse finite-state transducers. \newblock In O.~Boldt, H.~J\"urgensen, and L.~Robbins, editors, {\em Workshop on Implementing Automata WIA99 - Pre-Proceedings}, Potsdam, July 1999. \bibitem{Kla:MonaFido:logic:aut:conn} Nils Klarlund. \newblock Mona \& fido: The logic-automaton connection in practice. \newblock In {\em Computer Science Logic, CSL '97}, LNCS, 1998. \newblock LNCS 1414. \bibitem{knuth-art-sorting-searching} Donald~E. Knuth. \newblock {\em The Art of Computer Programming, Volume 3, Sorting and Searching}. \newblock Addison Wesley, second edition edition, 1998. \bibitem{kowaltowski93} Tomasz Kowaltowski, Cl\'audio~L. Lucchesi, and Jorge Stolfi. \newblock Minimization of binary automata. \newblock In {\em First South American String Processing Workshop}, Belo Horizonte, Brasil, 1993. \bibitem{mohri-min} Mehryar Mohri. \newblock Compact representations by finite-state transducers. \newblock In {\em 32th Annual Meeting of the Association for Computational Linguistics}, pages 204--209, New Mexico State University, 1994. \bibitem{mohri-det} Mehryar Mohri. \newblock On some applications of finite-state automata theory to natural language processing. \newblock {\em Natural Language Engineering}, 2:61--80, 1996. \newblock Originally appeared in 1994 as Technical Report, institut Gaspard Monge, Paris. \bibitem{mohri-tcs} Mehryar Mohri. \newblock Minimization algorithms for sequential transducers. \newblock {\em Theoretical Computer Science}, 234:177--201, 2000. \bibitem{ONCINA93} J.~Oncina, P.~Garc\'\i{}a, and E.~Vidal. \newblock Learning subsequential transducers for pattern recognition interpretation tasks. \newblock {\em IEEE Transactions on Pattern Analysis and Machine Intelligence}, 15:448--458, 1993. \bibitem{perrin} Dominique Perrin. \newblock Finite automata. \newblock In J.~van Leeuwen, editor, {\em Handbook of Theoretical Computer Science. Volume B: Formal Models and Semantics}, pages 1--57. Elsevier and the MIT Press, 1990. \bibitem{reutenauer} C.~Reutenauer. \newblock Subsequential functions: Characterizations, minimization, examples. \newblock In {\em Proceedings of the International Meeting of Young Computer Scientists}, Berlin, 1993. Springer. \newblock Lecture Notes in Computer Science. \bibitem{roche-schabes} Emmanuel Roche and Yves Schabes. \newblock Deterministic part-of-speech tagging with finite-state transducers. \newblock {\em Computational Linguistics}, 21(2):227--253, 1995. \bibitem{roch:lang97} Emmanuel Roche and Yves Schabes. \newblock Introduction. \newblock In Emmanuel Roche and Yves Schabes, editors, {\em Finite-State Language Processing}. MIT Press, Cambridge, Mass, 1997. \bibitem{art-of-prolog} Leon Sterling and Ehud Shapiro. \newblock {\em The Art of {Prolog}}. \newblock MIT Press, Cambridge Mass., 1994. \newblock Second Edition. \bibitem{wia99} Gertjan van Noord and Dale Gerdemann. \newblock An extendible regular expression compiler for finite-state approaches in natural language processing. \newblock In O.~Boldt, H.~Juergensen, and L.~Robbins, editors, {\em Workshop on Implementing Automata; WIA99 Pre-Proceedings}, Potsdam Germany, 1999. \bibitem{walther} Markus Walther. \newblock One-level prosodic morphology. \newblock Technical Report~1, Instit\"ut f\"ur Germanistische Sprachwissenschaft, Philipps-Universit\"at Marbug, 1999. \newblock cs.CL/9911011. \bibitem{walther-naacl00} Markus Walther. \newblock Finite-state reduplication in one-level prosodic morphology. \newblock In {\em First Conference of the North American Chapter of the Association for Computational Linguistics}, pages 296--302, Seattle, 2000. \bibitem{watson-kornai} Bruce~W. Watson. \newblock Implementing and using finite automata toolkits. \newblock In A.~Kornai, editor, {\em Extended Finite State Models of Language}, pages 19--36. Cambridge University Press, 1999. \bibitem{watson-predicates-jp} Bruce~W. Watson. \newblock The {OpenFIRE} initiative. \newblock In Junichi Aoe, editor, {\em Proceedings of the International Conference on Computer Processing of Oriental Languages}, pages 421--424, Tokushima, Japan, 1999. \end{thebibliography}