DocumentCode :
2221793
Title :
Approximate pattern matching is expressible in transitive closure logic
Author :
Lemström, Kjell ; Hella, Lauri
Author_Institution :
Dept. of Comput. Sci., Helsinki Univ., Finland
fYear :
2000
fDate :
2000
Firstpage :
157
Lastpage :
167
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 differences problem can be expressed by an FO(DTC)formula
Keywords :
computational complexity; database theory; dynamic programming; formal logic; pattern matching; query languages; set theory; string matching; LOGSPACE; NLOGSPACE; approximate pattern matching; deterministic transitive closure logic; dynamic programming approach; dynamic programming table; first-order logic; logic simplicity; logical formalism; minimizing path; query formulation; sartorial query language; string database; Computer science; Database languages; Dynamic programming; Image databases; Image retrieval; Logic programming; Mathematics; Multimedia databases; Music information retrieval; Pattern matching;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Logic in Computer Science, 2000. Proceedings. 15th Annual IEEE Symposium on
Conference_Location :
Santa Barbara, CA
ISSN :
1043-6871
Print_ISBN :
0-7695-0725-5
Type :
conf
DOI :
10.1109/LICS.2000.855764
Filename :
855764
Link To Document :
بازگشت