Journal article

Formal Derivation of a Pattern Matching Algorithm

Abstract:: This paper is devoted to the synthesis of a functional version of the Knuth-Morris-Pratt algorithm for pattern matching. This algorithm was first discussed by Knuth; since then formal developments have been given by Dijkstra and Dromey, among many others. The novel aspects of the present treatment are: (i) the result is expressed as a (very short) functional program; and (ii) the derivation makes use of the calculus of lists described by Bird.

Actions

Email

Email this record

Send the bibliographic details of this record to your email address.

Your Email
Please enter the email address that the record information will be sent to.

-
Your message (optional)
Please add any additional information to be included within the email.
Share
Cite

Cite this record

APA Style

Bird, R., Gibbons, J., & Jones, G. (1989). Formal Derivation of a Pattern Matching Algorithm. Science of Computer Programming, 12(2), 93–104.

MLA Style

Bird, R., et al. “Formal Derivation of a Pattern Matching Algorithm.” Science of Computer Programming, vol. 12, no. 2, 1989, pp. 93–104.

Chicago Style

Bird, R., J. Gibbons, and G. Jones. 1989. “Formal Derivation of a Pattern Matching Algorithm.” Science of Computer Programming 12 (2): 93–104.
Print

Authors

+ Bird, R More by this author

Role:: Author

+ Gibbons, J More by this author

Institution:: University of Oxford
Division:: MPLS
Department:: Computer Science
Role:: Author

+ Jones, G More by this author

Role:: Author

Journal:: Science of Computer Programming More from this journal
Volume:: 12
Issue:: 2
Pages:: 93-104
Publication date:: 1989-07-01

UUID:: uuid:8f674df1-775c-4c65-815e-8c449b24aace
Local pid:: cs:2374
Deposit date:: 2015-03-12
ARK identifier:: ark:/29072/ora_8f674df1775c4c65815e8c449b24aace

Terms of use

Copyright date:: 1989

Licence:: Terms and Conditions of Use for Oxford University Research Archive

Views and Downloads

Views and downloads will return soon

If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP