Imaginamos que um conjunto de dados (palavras) pertencentes a uma linguagem L são transmitidos atra
Imaginamos que um conjunto de dados (palavras) pertencentes a uma linguagem L são transmitidos atraves de um canal de comunicação com possíveis erros. Formalmente, o canal e definido por um conjunto de pares de palavras que representam os possíveis input/output. Se assumirmos que o canal considerado garante que nenhuma palavra u de L pode ser recebida como sendo uma outra palavra de L, dizemos que L detecta erros para o canal em questão. Apresentaremos a conclusão do trabalho iniciado em 2006 com Stavros Konstantinidis (Saint Mary's University) com o objectivo de avaliar o potencial de detecção de erros de uma linguagem racional relativamente a canais naturalmente associados aos modelos de erro mais comuns. Em particular, conseguimos que alguns resultados que eram válidos apenas para substituições (cf. distância de Hamming) fossem generalizados para combinações dos tipos de erro considerados na distância de Lewenshtein (substituições, inserções e supressões).

Date and Venue

Start Date
Venue
Sala 0.05 – DMP/FCUP

Speaker

Pedro Silva
(FCUP / CMUP)

Area

Semigroups, Automata and Languages