Descriptional Complexity of Error/Edit Systems

		Lila Kari and Stavros Konstantinidis

Errors appear in a wide range of information processing and transmission 
applications, such as data communications, biological computing, computer 
typesetting, speech recognition, etc. It can be said indeed that errors are 
truly natural phenomena. In this work we introduce error or edit systems
(e-systems, for short), which are formal languages over the alphabet of the 
basic edit operations. Our formalism allows one to model essentially any 
kind of error situations. For certain natural regular e-systems,
we investigate their descriptional complexity in terms of the number 
of states of the automata accepting such systems. This problem is
of interest in its own right as well as in the computation of maximal 
error-correcting capabilities of known languages.


Key words: error models, automata, descriptional complexity, formal languages