Abstract
There are two ways of using the nondeterministic finite automata (NFA). The first one is the transformation to the equivalent deterministic finite automaton and the second one is the simulation of the run of NFA. In this paper we discuss the second way. We present an overview of the simulation methods that have been found in the approximate string matching. We generalize these simulation methods and form the rules for the usage of these methods.
This research was partially supported by grant 201/98/1155 of the Grant Agency of Czech Republic and by internal grant 3098098/336 of Czech Technical University.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
R. A. Baeza-Yates and G. H. Gonnet. A new approach to text searching. Commun. ACM, 35(10):74–82, 1992.
Z. Galil and K. Park. An improved algorithm for approximate string matching. In G. Ausiello, M. Dezani-Ciancaglini, and S. Ronchi Della Rocca, editors, Proceedings of the 16th International Colloquium on Automata, Languages and Programming, number 372 in Lecture Notes in Computer Science, pages 394–404, Stresa, Italy, 1989. Springer-Verlag, Berlin.
J. Holub. Reduced nondeterministic finite automata for approximate string matching. In J. Holub, editor, Proceedings of the Prague Stringologic Club Workshop’ 96, pages 19–27, Prague, Czech Republic, 1996. Collaborative Report DC-96-10.
J. Holub. Simulation of NFA in approximate string and sequence matching. In J. Holub, editor, Proceedings of the Prague Stringology Club Workshop’ 97, pages 39–46, Czech Technical University, Prague, Czech Republic, 1997. Collaborative Report DC-97-03.
J. Holub. Simulation of nondeterministic finite automata in approximate string matching. In WORKSHOP’ 98, pages 211–212, Czech Technical University, Prague, Czech Republic, February 1998.
J. Holub. Simulation of nondeterministic finite automata in approximate string and sequence matching. Technical report, Czech Technical University, Prague, Czech Republic, April 1998. Research Report DC-98-04.
J. E. Hopcroft and J. D. Ullman. Introduction to automata, languages and computations. Addison-Wesley, Reading, MA, 1979.
B. Melichar. String matching with. k differences by finite automata. In Proceedings of the 13th International Conference on Pattern Recognition, volume II., pages 256–260, Vienna, Austria, 1996. IEEE Computer Society Press.
P. H. Sellers. The theory and computation of evolutionary distances: Pattern recognition. J. Algorithms, 1(4):359–373, 1980.
E. Ukkonen. Finding approximate patterns in strings. J. Algorithms, 6(1-3):132–137, 1985.
S. Wu and U. Manber. Fast text searching allowing errors. Commun. ACM, 35(10):83–91, 1992.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Holub, J., Melichar, B. (1999). Implementation of Nondeterministic Finite Automata for Approximate Pattern Matching. In: Champarnaud, JM., Ziadi, D., Maurel, D. (eds) Automata Implementation. WIA 1998. Lecture Notes in Computer Science, vol 1660. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48057-9_8
Download citation
DOI: https://doi.org/10.1007/3-540-48057-9_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66652-3
Online ISBN: 978-3-540-48057-0
eBook Packages: Springer Book Archive