\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}
