\begin{thebibliography}{34}
\expandafter\ifx\csname natexlab\endcsname\relax\def\natexlab#1{#1}\fi
\expandafter\ifx\csname url\endcsname\relax
  \def\url#1{{\tt #1}}\fi

\bibitem[Allauzen et~al.(2004)Allauzen, Mohri, and Roark]{webgrm}
Cyril Allauzen, Mehryar Mohri, and Brian Roark.
\newblock {A General Weighted Grammar Library}.
\newblock In {\em Proceedings of the Ninth International Conference on Automata
  (CIAA 2004)}, Kingston, Ontario, Canada, July 2004.
\newblock URL \url{http://www.research.att.com/sw/tools/grm}.

\bibitem[Berg et~al.(1984)Berg, Christensen, and Ressel]{berg}
Christian Berg, Jens Peter~Reus Christensen, and Paul Ressel.
\newblock {\em Harmonic Analysis on Semigroups}.
\newblock Springer-Verlag: Berlin-New York, 1984.

\bibitem[Berstel(1979)]{berstel}
Jean Berstel.
\newblock {\em Transductions and Context-Free Languages}.
\newblock Teubner Studienbucher: Stuttgart, 1979.

\bibitem[Berstel and Reutenauer(1988)]{berstel-reutenauer}
Jean Berstel and Christophe Reutenauer.
\newblock {\em Rational Series and Their Languages}.
\newblock Springer-Verlag: Berlin-New York, 1988.

\bibitem[Boser et~al.(1992)Boser, Guyon, and Vapnik]{bgv}
Bernhard~E. Boser, Isabelle Guyon, and Vladimir~N. Vapnik.
\newblock A training algorithm for optimal margin classifiers.
\newblock In {\em Proceedings of the Fifth Annual Workshop of Computational
  Learning Theory}, volume~5, pages 144--152, Pittsburg, 1992. ACM.

\bibitem[Cortes et~al.(2003{\natexlab{a}})Cortes, Haffner, and Mohri]{icassp}
Corinna Cortes, Patrick Haffner, and Mehryar Mohri.
\newblock {Lattice Kernels for Spoken Dialog Classification}.
\newblock In {\em Proceedings ICASSP'03}, Hong Kong, 2003{\natexlab{a}}.

\bibitem[Cortes et~al.(2003{\natexlab{b}})Cortes, Haffner, and Mohri]{colt}
Corinna Cortes, Patrick Haffner, and Mehryar Mohri.
\newblock {Positive Definite Rational Kernels}.
\newblock In {\em Proceedings of The 16th Annual Conference on Computational
  Learning Theory (COLT 2003)}, volume 2777 of {\em Lecture Notes in Computer
  Science}, pages 41--56, Washington D.C., August 2003{\natexlab{b}}. Springer,
  Heidelberg, Germany.

\bibitem[Cortes et~al.(2003{\natexlab{c}})Cortes, Haffner, and Mohri]{kernel}
Corinna Cortes, Patrick Haffner, and Mehryar Mohri.
\newblock {Rational Kernels}.
\newblock In {\em Advances in Neural Information Processing Systems (NIPS
  2002)}, volume~15, Vancouver, Canada, March 2003{\natexlab{c}}. MIT Press.

\bibitem[Cortes et~al.(2003{\natexlab{d}})Cortes, Haffner, and Mohri]{euro}
Corinna Cortes, Patrick Haffner, and Mehryar Mohri.
\newblock {Weighted Automata Kernels -- General Framework and Algorithms}.
\newblock In {\em Proceedings of the 9th European Conference on Speech
  Communication and Technology (Eurospeech '03), Special Session Advanced
  Machine Learning Algorithms for Speech and Language Processing}, Geneva,
  Switzerland, September 2003{\natexlab{d}}.

\bibitem[Cortes and Mohri(2004)]{icml}
Corinna Cortes and Mehryar Mohri.
\newblock {Distribution Kernels Based on Moments of Counts}.
\newblock In {\em Proceedings of the Twenty-First International Conference on
  Machine Learning (ICML 2004)}, Banff, Alberta, Canada, July 2004.

\bibitem[Cortes and Vapnik(1995)]{ccvv}
Corinna Cortes and Vladimir~N. Vapnik.
\newblock {Support-Vector Networks}.
\newblock {\em Machine Learning}, 20\penalty0 (3):\penalty0 273--297, 1995.

\bibitem[Dongarra et~al.(1979)Dongarra, Bunch, Moler, and Stewart]{dongarra}
Jack~J. Dongarra, Jim~R. Bunch, Cleve~B. Moler, and G.~W. Stewart.
\newblock {\em {LINPACK User's Guide}}.
\newblock SIAM Publications, 1979.

\bibitem[Durbin et~al.(1998)Durbin, Eddy, Krogh, , and Mitchison]{durbin}
Richard Durbin, Sean Eddy, Anders Krogh, , and Graeme Mitchison.
\newblock {\em {Biological Sequence Analysis: Probabilistic Models of Proteins
  and Nucleic Acids}}.
\newblock Cambridge University Press, Cambridge UK, 1998.

\bibitem[Eilenberg(1974)]{eilenberg}
Samuel Eilenberg.
\newblock {\em Automata, Languages and Machines}, volume A-B.
\newblock Academic Press, 1974.

\bibitem[Haffner et~al.(2003)Haffner, Tur, and Wright]{hmihy-svm}
Patrick Haffner, Gokhan Tur, and Jeremy Wright.
\newblock {Optimizing {SVM}s for complex Call Classification}.
\newblock In {\em Proceedings ICASSP'03}, 2003.

\bibitem[Haussler(1999)]{haussler}
David Haussler.
\newblock {Convolution Kernels on Discrete Structures}.
\newblock Technical Report UCSC-CRL-99-10, University of California at Santa
  Cruz, 1999.

\bibitem[Kuich and Salomaa(1986)]{kuich}
Werner Kuich and Arto Salomaa.
\newblock {\em Semirings, Automata, Languages}.
\newblock Number~5 in {EATCS} Monographs on Theoretical Computer Science.
  Springer-Verlag, 1986.

\bibitem[Lawler(1976)]{lawler}
Eugene~L. Lawler.
\newblock {\em Combinatorial Optimization: Networks and Matroids}.
\newblock Holt, Rinehart, and Winston, 1976.

\bibitem[Leslie et~al.(2003)Leslie, Eskin, Weston, and Noble]{mismatch}
Christina Leslie, Eleazar Eskin, Jason Weston, and William~Stafford Noble.
\newblock {Mismatch String Kernels for SVM Protein Classification}.
\newblock In {\em NIPS 2002}, Vancouver, Canada, March 2003. MIT Press.

\bibitem[Levenshtein(1966)]{levenshtein}
Vladimir~I. Levenshtein.
\newblock {Binary codes capable of correcting deletions, insertions, and
  reversals.}
\newblock {\em Soviet Physics - Doklady}, 10:\penalty0 707--710, 1966.

\bibitem[Lodhi et~al.(2001)Lodhi, Shawe-Taylor, Cristianini, and
  Watkins]{gappy}
Huma Lodhi, John Shawe-Taylor, Nello Cristianini, and Chris Watkins.
\newblock Text classification using string kernels.
\newblock In Todd~K. Leen, Thomas~G. Dietterich, and Volker Tresp, editors,
  {\em NIPS 2000}, pages 563--569. MIT Press, 2001.

\bibitem[Mohri(2002)]{mohri52}
Mehryar Mohri.
\newblock {Semiring Frameworks and Algorithms for Shortest-Distance Problems}.
\newblock {\em Journal of Automata, Languages and Combinatorics}, 7\penalty0
  (3):\penalty0 321--350, 2002.

\bibitem[Mohri(2003)]{mohri60}
Mehryar Mohri.
\newblock {Edit-Distance of Weighted Automata: General Definitions and
  Algorithms}.
\newblock {\em International Journal of Foundations of Computer Science},
  14\penalty0 (6):\penalty0 957--982, 2003.

\bibitem[Mohri et~al.(1996)Mohri, Pereira, and Riley]{mohri8}
Mehryar Mohri, Fernando C.~N. Pereira, and Michael Riley.
\newblock {Weighted Automata in Text and Speech Processing}.
\newblock In {\em Proceedings of the 12th biennial European Conference on
  Artificial Intelligence (ECAI-96), Workshop on Extended finite state models
  of language}, Budapest, Hungary, 1996. John Wiley and Sons, Chichester.

\bibitem[Mohri et~al.(2000)Mohri, Pereira, and Riley]{webfsm}
Mehryar Mohri, Fernando C.~N. Pereira, and Michael Riley.
\newblock {The Design Principles of a Weighted Finite-State Transducer
  Library}.
\newblock {\em Theoretical Computer Science}, 231:\penalty0 17--32, January
  2000.
\newblock URL \url{http://www.research.att.com/sw/tools/fsm}.

\bibitem[Pereira and Riley(1997)]{PereiraRiley}
Fernando C.~N. Pereira and Michael~D. Riley.
\newblock Speech recognition by composition of weighted finite automata.
\newblock In {\em Finite-State Language Processing}, pages 431--453. {MIT}
  Press, Cambridge, Massachusetts, 1997.

\bibitem[Salomaa and Soittola(1978)]{soittola}
Arto Salomaa and Matti Soittola.
\newblock {\em Automata-Theoretic Aspects of Formal Power Series}.
\newblock Springer-Verlag: New York, 1978.

\bibitem[Schapire and Singer(2000)]{boostexter00}
Robert~E. Schapire and Yoram Singer.
\newblock Boostexter: A boosting-based system for text categorization.
\newblock {\em Machine Learning}, 39\penalty0 (2/3):\penalty0 135--168, 2000.

\bibitem[Sch{\"o}lkopf(2001)]{scholpkof}
Bernhard Sch{\"o}lkopf.
\newblock {The Kernel Trick for Distances}.
\newblock In Todd~K. Leen, Thomas~G. Dietterich, and Volker Tresp, editors,
  {\em NIPS 2001}, pages 301--307. MIT Press, 2001.

\bibitem[Sch{\"o}lkopf and Smola(2002)]{smbook}
Bernhard Sch{\"o}lkopf and Alex Smola.
\newblock {\em Learning with Kernels}.
\newblock MIT Press: Cambridge, MA, 2002.

\bibitem[Shafran et~al.(2003)Shafran, Riley, and Mohri]{vsign}
Izhak Shafran, Michael Riley, and Mehryar Mohri.
\newblock {Voice Signatures}.
\newblock In {\em Proceedings of The 8th IEEE Automatic Speech Recognition and
  Understanding Workshop (ASRU 2003)}, St. Thomas, U.S. Virgin Islands,
  November 2003.

\bibitem[Takimoto and Warmuth(2003)]{manfred}
Eiji Takimoto and Manfred~K. Warmuth.
\newblock Path kernels and multiplicative updates.
\newblock {\em The Journal of Machine Learning Research (JMLR)}, 4:\penalty0
  773 -- 818, 2003.

\bibitem[Vapnik(1998)]{vapnik98}
Vladimir~N. Vapnik.
\newblock {\em Statistical Learning Theory}.
\newblock John Wiley \& Sons, 1998.

\bibitem[Watkins(1999)]{watkins}
Chris Watkins.
\newblock Dynamic alignment kernels.
\newblock Technical Report CSD-TR-98-11, Royal Holloway, University of London,
  1999.

\end{thebibliography}
