Back to Search
Start Over
BORDERS AND FINITE AUTOMATA
- Source :
- International Journal of Foundations of Computer Science. 18:859-871
- Publication Year :
- 2007
- Publisher :
- World Scientific Pub Co Pte Lt, 2007.
-
Abstract
- A border of a string is a prefix of the string that is simultaneously its suffix. It is one of the basic stringology keystones used as a part of many algorithms in pattern matching, molecular biology, computer-assisted music analysis and others. The paper offers the automata-theoretical description of Iliopoulos's ALL_BORDERS algorithm. The algorithm finds all borders of a string with don't care symbols. We show that ALL_BORDERS algorithm is an implementation of a finite state transducer of specific form. We describe how such a transducer can be constructed and what should be the input string like. The described transducer finds a set of lengths of all borders. Last but not least, we define approximate borders and show how to find all approximate borders of a string when we concern Hamming distance definition. Our solution of this problem is based on transducers again. This allows us to use analogy with automata-based pattern matching methods. Finally we discuss conditions under which the same principle can be used for other distance measures.
Details
- ISSN :
- 17936373 and 01290541
- Volume :
- 18
- Database :
- OpenAIRE
- Journal :
- International Journal of Foundations of Computer Science
- Accession number :
- edsair.doi...........620d82ad72d1e5f38d742a8ae5e3d90c