Computing Maximal Error-detecting Capabilities and Distances of Regular Languages

• Type: Article in International Scientific Journal
• Date: 2010

Authors

Stavros Konstantinidis (Author) Other; Pedro V. Silva (Author) FCUP

Journal

Title: Fundamenta Informaticae

Vol. 101 No. 4

Pages: 257-270

ISSN: 0169-2968

Publisher: IOS PRESS

Indexing

ISI Web of Knowledge - 7 Citations

ISI Web of Science

Scopus - 7 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-003-B0Q

DOI: 10.3233/fi-2010-287

Abstract (EN): 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 gamma if and only if it is error-detecting for the inverse of gamma. 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 14