CSIT 570, FALL 2004: ARTICLES

  • NEW!!

    Gerth S. Brodal, Finger Search Trees with Constant Insertion Time, January 1998.
    Brodal

  • Donald E. Knuth, James H. Morris & Vaughan R. Pratt, Fast Pattern Matching in Strings, SIAM Journal on Computing, 6:2, 323--350, June 1977.
    URL: None available.
  • Robert S. Boyer and J. Strother Moore, A Fast String Searching Algorithm, Communications of the ACM, 20:10, 762--772, 1977.
    Boyer & Moore
  • Andrew Hume and Daniel Sunday, Fast String Searching, Software-Practice and Experience, 21:11, 1221--1248, November 1991.
    Hume and Sunday
  • Alfred V. Aho and Margaret J. Corasick, Efficient String Matching: An Aid to Bibliographic Search, Communications of the ACM, 18:6, 333--340, June 1975.
    Aho & Corasick
  • Beate Commentz-Walter, A String Matching Algorithm Fast on the Average, Proceedings of ICALP '79, 118--132, 1979.
    URL: None available.
  • Ken Thompson, Regular Expression Search Algorithm, Communications of the ACM, 11:6, 419--422, 1968.
    Thompson
  • Dora Giammarresi, Jean-Luc Ponty and Derick Wood, Glushkov and Thompson Constructions: A Synthesis, HKUST Theoretical Computer Science Center Research Report HKUST-TCSC-99-11, 1998.
    GiammarresiPW
  • Edward Fredkin, Trie Memory, Communications of the ACM 3:9, 490--500, 1960.
    Fredkin
  • Edward.H. Sussenguth, Jr., Use of Tree Structures for Processing Files, Communications of the ACM 6:5, 272--279, 1963.
    Sussenguth
  • Donald R. Morrison, PATRICIA---Practical Algorithm to Retrieve Information Coded in Alphameric, Journal of the ACM 15:4, 514--534, 1968.
    Morrison
  • Robert McNaughton and H. Yamada, Regular Expressions and State Graphs for Automata, IEEE Transactions on Electronic Computers,9:1, 39--47, 1960.
    URL: None available.
  • Anne Brueggemann-Klein, Regular Expressions into Finite Automata, Theoretical Computer Science.120, 197--213,1993.
    Brueggemann-Klein
  • Anne Brueggemann-Klein and Derick Wood, One-Unambiguous Regular Languages, Information and Computation,142:2, 182--206, 1998.
    Brueggemann-KleinW

    • CSIT 570, FALL 2004: TEXTS

  • Efim Kinber and Carl Smith, Theory of Computing: A Gentle Introduction, Prentice Hall, 2001.
    This text is exactly what it is says: A gentle introduction!!! It provides information about regular expressios and finite-state machines very gently.

  • Forbes D. Lewis, Essentials of Theoretical Computer Science, published on-line, date unknown.
    FDLewisRegExp Check out "Regular Sets and Expressions". It provides a basic introduction to this area.


    FDLewisFinAuto Check out (with somewhat more care) "Finite Automata" (the notation is somewhat different from mine).

  • Jeffrey E.F. Friedl, Mastering Regular Expressions, Second Edition, O'Reilly, 2002.
    This book is a must for anyone wanting to know more about regular expressions from a practical viewpoint,

  • Timothy C. Bell, John G. Cleary, and Ian H. Witten, Text Compression, Prentice-Hall, 1990.
  • Maxime Crochemore and Wojceich Rytter, Text Algorithms, Oxford University Press, 1994.
  • Maxime Crochemore and Wojceich Rytter, Jewels of Stringology, World Scientific, 2002.
  • Peter D. Smith, An Introduction to Text Processing, The MIT Press, 1990.
  • Graham A. Stephen, String Searching Algorithms, World Scientific, 1994.
  • Ian H. Witten, Alistair Moffat and Timothy C. Bell, Managing Gigabytes: Compressing and Indexing Documents and Images, Van Nostrand Reinhold, 1994.

    • Last updated by Derick Wood, 06/09/2004