®®®® SIIA Público

Título del libro: Proceedings Of The 3rd International Acm Sigplan Conference On Principles And Practice Of Declarative Programming
Título del capítulo: Development reuse and the logic program derivation of two string-matching algorithms

Autores UNAM:
DAVID ARTURO ROSENBLUETH LAGUETTE;
Autores externos:
Idioma:
Año de publicación:
2001
Palabras clave:

Boyer-Moore; Knuth-Morris-Pratt; Program derivation

Resumen:

Program transformation advocates the development of programs by applying a sequence of meaning-preserving rules to a specification, thereby obtaining an implementation. The cost of program development and maintenance decreases if previous, similar derivations can be reused conveniently. Through the string-matching problem, we study the reuse of complete parts of the derivation of an algorithm, in the derivation of another, "similar" algorithm. In particular, we first derive the search stage of a variant of the Boyer-Moore algorithm, and then reuse some "developments" in a derivation of the search stage of the Knuth-Morris-Pratt algorithm. Several advantages result from employing logic programming. First, we get the semantic benefit of having a logical basis. Second, we can easily exploit nondeterminism. Third, we link both derivations by observing that repetitive "deterministic" unfolding (i.e. sequences of unfolding steps that halt when more than one clause would be inferred) is closely related to the preprocessing stage of both algorithms.

Entidades citadas de la UNAM:
Fuente:


ISBN:
158113388X
Editorial:
Association for Computing Machinery (ACM)

Tipo de producto:
Conference Paper



DOI:
10.1145/773184.773190