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 deÿning 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 e ciently 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 ÿrst order logic (FO). We consider the well-known problems of k-mismatches and k-di erences. Assuming ÿrst 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 show how to adapt the formalisms to allow individual costs for the editing operations, and consider music information retrieval (MIR) as a case study.
We believe that in the general case k-di erences is not expressible in FO(DTC). However, we show that proving this is at least as hard as separating LOGSPACE from NLOGSPACE. On the other hand, we show that if k is ÿxed, the k-di erences problem can be expressed by an FO(DTC) formula.