  The paper considers various formalisms based on Automata, Temporal Logic and
Regular Expressions for specifying queries over sequences. Unlike traditional
binary semantics, the paper presents a similarity based semantics for thse
formalisms. More specifically, a distance measure in the range [0,1] is
associated with a sequence, query pair denoting how closely the sequence
satisfies the query. These measures are defined using a spectrum of normed
vector distance measures. Various distance measures based on the syntax and the
traditional semantics of the query are presented. Efficient algorithms for
computing these distance measure are presented. These algorithms can be
employed for retrieval of sequence from a database that closely satisfy a
given.
