Constructing factor oracles

Article, Report English OPEN
Cleophas, L.G.W.A.; Zwaan, G.; Watson, B.W.;
(2007)
  • Publisher: Technische Universiteit Eindhoven

Abstract. A factor oracle is a data structure for weak factor recognition. It is an automaton built on a string p of length m that is acyclic, recognizes at least all factors of p, has m + 1 states which are all final, and has m to 2m - 1 transitions. In this paper, we ... View more
  • References (11)
    11 references, page 1 of 2

    1. Cyril Allauzen, Maxime Crochemore, and Mathieu Ra not. E cient Experimental String Matching by Weak Factor Recognition. In Proceedings of the 12th conference on Combinatorial Pattern Matching, volume 2089 of LNCS, pages 51{72, 2001.

    2. Cyril Allauzen and Mathieu Ra not. Oracle des facteurs d'un ensemble de mots. Technical Report 99-11, Institut Gaspard-Monge, Universite de Marne-la-Vallee, 1999.

    3. Loek Cleophas, Gerard Zwaan, and Bruce W. Watson. Constructing Factor Oracles. In Proceedings of the Prague Stringology Conference 2003, 2003.

    4. Loek G.W.A. Cleophas. Towards SPARE Time: A New Taxonomy and Toolkit of Keyword Pattern Matching Algorithms. Master's thesis, August 2003.

    5. Maxime Crochemore and Wojciech Rytter. Text Algorithms. Oxford University Press, 1994.

    6. Maxime Crochemore and Wojciech Rytter. Jewels of Stringology - Text Algorithms. World Scienti c Publishing, 2003.

    7. E. Fredkin. Trie memory. Communications of the ACM, 3(10):490{499, 1960.

    8. Arnaud Lefebvre and Thierry Lecroq. Computing repeated factors with a factor oracle. In L. Brankovic and J. Ryan, editors, Proceedings of the 11th Australasian Workshop on Combinatorial Algorithms, pages 145{158, 2000.

    9. Arnaud Lefebvre and Thierry Lecroq. Compror: on-line losless data compression with a factor oracle. Inf. Process. Lett., 83(1):1{6, 2002.

    10. Arnaud Lefebvre, Thierry Lecroq, and J. Alexandre. Drastic improvements over repeats found with a factor oracle. In E. Billington, D. Donovan, and A. Khodkar, editors, Proceedings of the 13th Australasian Workshop on Combinatorial Algorithms, pages 253{265, 2002.

  • Similar Research Results (3)
  • Metrics
Share - Bookmark