Paper Info
Title
Computing Maximal Error-detecting Capabilities and Distances of Regular Languages
Abstract
A (combinatorial) channel consists of pairs of words representing all possible input-output channel situations. In a past paper, we formalized the intuitive concept of “largest amount of errors” detectable by a given language L, by defining the maximal error-detecting capabilities of L with respect to a given class of channels, and we showed how to compute all maximal error-detecting capabilities (channels) of a given regular language with respect to the class of rational channels and a class of channels involving only the substitution-error type. In this paper we resolve the problem for channels involving any combination of the basic error types: substitution, insertion, deletion. Moreover, we consider the problem of finding the inverses of these channels, in view of the fact that L is error-detecting for γ if and only if it is error-detecting for the inverse of γ. We also discuss a natural method of reducing the problem of computing (inner) distances of a given regular language L to the problem of computing maximal error-detecting capabilities of L.
Year
DOI
Venue
2010
10.3233/FI-2010-287
Fundam. Inform.
Keywords
Field
DocType
language l,string distance.,error detection,computing maximal error-detecting capabilities,combinatorial channel,rational channel,edit string,basic error type,algorithm,regular language,automaton,largest amount,regular languages,maximal error-detecting capability,maximal,past paper,intuitive concept,possible input-output channel situation,natural method
Discrete mathematics,Inverse,Combinatorics,Algebra,Automaton,Communication channel,Error detection and correction,If and only if,Regular language,String distance,Mathematics
Journal
Volume
Issue
ISSN
101
4
0169-2968
Citations 
PageRank 
References 
7
0.59
6
Authors
2
Name
Order
Citations
PageRank
Stavros Konstantinidis128331.10
Pedro V. Silva214129.42