Fundamental algorithms for a declarative pattern matching system

The present thesis provides a systematic and detailed consideration on the embedding of fundamental string algorithms in the functional programming paradigm. In particular, a thorough development and complete implementation of several string searching and comparison algorithms is given applying the structuring methods of functional languages to construct implementations from individual reusable components. A high degree of modularity is achieved by using higher order functions and lazy-evaluation to combine the program components. The lazy functional language Miranda is used for program notation. Based on these language features various forms of A"+-trees have been represented and constructed in a unified way. It is shown that all functional programs achieve the same asymptotic running time as their imperative counterparts. (WEN)Available from TIB Hannover: RR 6882(95-03) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekSIGLEDEGerman