Computing Maximal Error-detecting Capabilities and Distances of Regular Languages

• Tipo: Artigo em Revista Científica Internacional
• Data: 2010

Autores

Stavros Konstantinidis (Autor) Outra; Pedro V. Silva (Autor) FCUP

Revista

Título: Fundamenta Informaticae

Vol. 101 Nº 4

Páginas: 257-270

ISSN: 0169-2968

Editora: IOS PRESS

Indexação

ISI Web of Knowledge - 7 Citações

ISI Web of Science

Scopus - 7 Citações

Classificação Científica

FOS: Ciências exactas e naturais > Ciências da computação e da informação

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 14