## Paper: Approximate Pattern Matching is Expressible in Transitive Closure Logic (at LICS 2000)

*Winner of the Test-of-Time Award in 2020***Kjell Lemström Lauri Hella**

### Abstract

A sartorial query language facilitates the formulation of queries to a (string) database. One step towards an implementation of such a query language can be taken by defining a logical formalism expressing a known solution for the particular problem at hand. The simplicity of the logic is a desired property, because the simpler the logic that the query language is based on, the more efficiently it can be implemented. We introduce a logical formalism for expressing approximate pattern matching. The formalism uses properties of the dynamic programming approach; a minimizing path of a dynamic programming table is expressed by using a formula in an extension of first-order logic (FO). We consider the well-known problems of k mismatches and k differences. Assuming first that k is given as a part of the input, those problems are expressed by using deterministic transitive closure logic (FO(DTC)) and transitive closure logic (FO(TC)), respectively. We believe that in the general case the k differences is not expressible in FO(DTC), and show that solving this question in the affirmative is at least as hard as separating LOGSPACE from NLOGSPACE. We show, however, that if k is fixed, the k difference problem can be expressed by an FO(DTC) formula.

### BibTeX

@InProceedings{LemstrmHella-ApproximatePatternM, author = {Kjell Lemström and Lauri Hella}, title = {Approximate Pattern Matching is Expressible in Transitive Closure Logic}, booktitle = {Proceedings of the Fifteenth Annual IEEE Symposium on Logic in Computer Science (LICS 2000)}, year = {2000}, month = {June}, pages = {157--167}, location = {Santa Barbara, CA, USA}, publisher = {IEEE Computer Society Press} }