Bibliography

1

Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman.
The Design and Analysis of Computer Algorithms.
Addison-Wesley, 1974.

2

Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman.
Compilers. Principles, Techniques and Tools.
Addison Wesley, 1986.

3

Steven Bird and T. Mark Ellison.
One-level phonology: Autosegmental representations and rules as finite automata.
Computational Linguistics, 20(1):55-90, 1994.

4

Bob Carpenter.
The Logic of Typed Feature Structures.
Cambridge University Press, New York, 1992.

5

Jan Daciuk.
Incremental Construction of Finite-state Automata and Transducers, and their Use in the Natural Language Processing.
PhD thesis, Technical University of Gdansk, 1998.

6

Jan Daciuk.
Experiments with automata compression.
In M. Daley, M. G. Eramian, and S. Yu, editors, Conference on Implementation and Application of Automata CIAA'2000, pages 113-119, London, Ontario, Canada, July 2000. University of Western Ontario.

7

Jürgen Dassow, Gheorge Paun, and Arto Salomaa.
Grammars with controlled derivations.
In Grzegorz Rozenberg and Arto Salomaa, editors, Handbook of Formal Languages Vol.2 Linear Modeling: Background and Application, pages 101-154. Springer, 1997.

8

Jason Eisner.
Efficient generation in primitive optimality theory.
In 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.

9

Dale Gerdemann and Gertjan van Noord.
Transducers from rewrite rules with backreferences.
In Ninth Conference of the European Chapter of the Association for Computational Linguistics, Bergen Norway, 1999.

10

Dale Gerdemann and Gertjan van Noord.
Transducers from rewrite rules with backreferences.
In Ninth Conference of the European Chapter of the Association for Computational Linguistics, pages 126-133, Bergen Norway, 1999.

11

Daniel Gildea and Daniel Jurafsky.
Learning bias and phonological-rule induction.
Computational Linguistics, 22(4):497-530, 1996.

12

John E. Hopcroft.
An n log n algorithm for minimizing the states in a finite automaton.
In Z. Kohavi, editor, The Theory of Machines and Computations, pages 189-196. Academic Press, 1971.

13

John E. Hopcroft and Jeffrey D. Ullman.
Introduction to Automata Theory, Languages and Computation.
Addison Wesley, 1979.

14

J. Howard Johnson and Derick Wood.
Instruction computation in subset construction.
In Darrell Raymond, Derick Wood, and Sheng Yu, editors, Automata Implementation, pages 64-71. Springer Verlag, 1997.
Lecture Notes in Computer Science 1260.

15

Lauri Karttunen.
Finite-state constraints.
In Proceedings International Conference on Current Issues in Computational Linguistics, pages 23-40, Universiti Sains Malaysia, Penang, 1991.

16

Lauri Karttunen.
The replace operator.
In 33th Annual Meeting of the Association for Computational Linguistics, pages 16-23, M.I.T. Cambridge Mass., 1995.

17

Lauri Karttunen.
Directed replacement.
In 34th Annual Meeting of the Association for Computational Linguistics, pages 108-115, Santa Cruz, 1996.

18

Lauri Karttunen, Jean-Pierre Chanod, Gregory Grefenstette, and Anne Schiller.
Regular expressions for language engineering.
Natural Language Engineering, 2(4):305-238, 1996.
http://www.rxrc.xerox.com/research/mltt/fst/articles/jnle-97/rele.html.

19

André Kempe.
Factorization of ambiguous finite-state transducers.
In CIAA 2000. Fifth International Conference on Implementation and Application of Automata. Preproceedings, pages 157-164, London, Ontario, Canada, 2000.

20

André Kempe and Lauri Karttunen.
Parallel replacement in the finite-state calculus.
In Proceedings of the 16th International Conference on Computational Linguistics (COLING), pages 622-627, Copenhagen, Denmark, 1996.

21

George Anton Kiraz.
Compressed storage of sparse finite-state transducers.
In O. Boldt, H. Jürgensen, and L. Robbins, editors, Workshop on Implementing Automata WIA99 - Pre-Proceedings, Potsdam, July 1999.

22

Nils Klarlund.
Mona & fido: The logic-automaton connection in practice.
In Computer Science Logic, CSL '97, LNCS, 1998.
LNCS 1414.

23

Donald E. Knuth.
The Art of Computer Programming, Volume 3, Sorting and Searching.
Addison Wesley, second edition edition, 1998.

24

Tomasz Kowaltowski, Cláudio L. Lucchesi, and Jorge Stolfi.
Minimization of binary automata.
In First South American String Processing Workshop, Belo Horizonte, Brasil, 1993.

25

Mehryar Mohri.
Compact representations by finite-state transducers.
In 32th Annual Meeting of the Association for Computational Linguistics, pages 204-209, New Mexico State University, 1994.

26

Mehryar Mohri.
On some applications of finite-state automata theory to natural language processing.
Natural Language Engineering, 2:61-80, 1996.
Originally appeared in 1994 as Technical Report, institut Gaspard Monge, Paris.

27

Mehryar Mohri.
Minimization algorithms for sequential transducers.
Theoretical Computer Science, 234:177-201, 2000.

28

J. Oncina, P. García, and E. Vidal.
Learning subsequential transducers for pattern recognition interpretation tasks.
IEEE Transactions on Pattern Analysis and Machine Intelligence, 15:448-458, 1993.

29

Dominique Perrin.
Finite automata.
In J. van Leeuwen, editor, Handbook of Theoretical Computer Science. Volume B: Formal Models and Semantics, pages 1-57. Elsevier and the MIT Press, 1990.

30

C. Reutenauer.
Subsequential functions: Characterizations, minimization, examples.
In Proceedings of the International Meeting of Young Computer Scientists, Berlin, 1993. Springer.
Lecture Notes in Computer Science.

31

Emmanuel Roche and Yves Schabes.
Deterministic part-of-speech tagging with finite-state transducers.
Computational Linguistics, 21(2):227-253, 1995.

32

Emmanuel Roche and Yves Schabes.
Introduction.
In Emmanuel Roche and Yves Schabes, editors, Finite-State Language Processing. MIT Press, Cambridge, Mass, 1997.

33

Leon Sterling and Ehud Shapiro.
The Art of Prolog.
MIT Press, Cambridge Mass., 1994.
Second Edition.

34

Gertjan van Noord and Dale Gerdemann.
An extendible regular expression compiler for finite-state approaches in natural language processing.
In O. Boldt, H. Juergensen, and L. Robbins, editors, Workshop on Implementing Automata; WIA99 Pre-Proceedings, Potsdam Germany, 1999.

35

Markus Walther.
One-level prosodic morphology.
Technical Report 1, Institüt für Germanistische Sprachwissenschaft, Philipps-Universität Marbug, 1999.
cs.CL/9911011.

36

Markus Walther.
Finite-state reduplication in one-level prosodic morphology.
In First Conference of the North American Chapter of the Association for Computational Linguistics, pages 296-302, Seattle, 2000.

37

Bruce W. Watson.
Implementing and using finite automata toolkits.
In A. Kornai, editor, Extended Finite State Models of Language, pages 19-36. Cambridge University Press, 1999.

38

Bruce W. Watson.
The OpenFIRE initiative.
In Junichi Aoe, editor, Proceedings of the International Conference on Computer Processing of Oriental Languages, pages 421-424, Tokushima, Japan, 1999.