Finite-state error/edit-systems and difference-measures 
			for languages and words

	L. Kari, S. Konstantinidis, S. Perron, G. Wozniak, J. Xu

Abstract. 

We consider a special type of automaton, the weighted finite-state
e-system (wfse-system), that allows us to describe formally
the combinations of errors (edit operations) that are 
permitted in some information processing application. 
Given two regular languages and a wfse-system we can compute
the set of all edit-strings that can transform a word of the
first language to a word of the second one using only
the edit operations permitted by the given wfse-system.
Each wfse-system can be used to define a measure of the
difference between words and languages.
Our presentation provides a uniform treatment of certain
algorithmic problems pertaining to the differences between
such objects. In particular, we show how to find
the Hamming distance
of a given regular language in quadratic time and how to
compute efficiently the general string to regular-language 
correction problem. Moreover, we discuss an implementation
of our solution to this problem, which uses Grail to
represent automata.