Distância entre idiomas regulares

13

Eu quero definir uma noção de "proximidade" entre duas linguagens regulares de palavras finitas em (e / ou palavras infinitas em Σ w ). A idéia básica é que queremos que dois idiomas estejam próximos se eles não diferirem em muitas palavras. Também poderíamos usar a distância de edição de alguma maneira ... Não foi possível encontrar boas referências sobre esse problema.ΣΣω

Não chamo de distância, porque não exijo que todos os axiomas de distância sejam verdadeiros (embora não sejam ruins se forem).

d(eu,K)=lim supn|eunΔKn||eunKn|
eunKneuKΣnΔ

Essa "distância" é estudada? Existem referências sobre o assunto (possivelmente com opções alternativas para a função de distância)? Qualquer ajuda ou ponteiro seria apreciada, obrigado.

Denis
fonte

Respostas:

11

Como você talvez já saiba, uma métrica comum para palavras é a métrica Cantor, definida como:

d(eu,k)={0 0E se eu=k2-nOnde n=min{EuN|euEukEu}

Grosso modo, se uma string é uma sequência de eventos, a distância entre duas strings é , onde é a primeira vez que diferem. Isso pode ser elevado para uma métrica em idiomas (não vazios) usando a métrica Hausdorff. (Se você permitir seqüências infinitas, também precisará garantir que os idiomas estejam completos em Cauchy.) 2-nn

Essa métrica aparece muito na verificação. A primeira referência a isso que eu conheço é Alpern e Schneider 1985, Definindo a Viver . (Desculpe pela ausência de um link, mas não consegui encontrar uma cópia online.)

Jean-Eric Pin escreveu um artigo de pesquisa, Profinite Methods in Automata Theory , no qual ele examina algumas métricas mais gerais e também faz algumas conexões com a dualidade de Stone.

Neel Krishnaswami
fonte
Obrigado, eu estava ciente da métrica Cantor, mas não do seu uso para definir a métrica Hausdorff, isso parece perfeitamente correto.
Denis