Quais são os isomorfismos apropriados entre linguagens formais?

Uma linguagem formal $L$ sobre um alfabeto é um subconjunto de , ou seja, um conjunto de palavras sobre esse alfabeto. Duas linguagens formais e são iguais, se os conjuntos correspondentes forem extensionalmente iguais como subconjuntos de . Pode-se usar linguagens na teoria da complexidade para formalizar o conceito de "problema". Alguém poderia reclamar que a igualdade extensional "em geral" é indecidível, mas acredito que isso seria equivocado.Σ * L L $\Sigma$$\Sigma^*$$L$$L'$$L\cup L'$

Estou pensando no seguinte problema há algum tempo: Dois idiomas e sobre alfabetos e (onde , , e$L$$L'$$\Sigma=\{a,b\}$$\Sigma'=\{c,d\}$$a$$b$$c$$d$são letras distintas) nunca podem ser iguais, mesmo que descrevam "exatamente" o mesmo "problema". Mas eles devem ser isomórficos, se realmente descreverem "exatamente" o mesmo "problema". O que eu gostaria de saber são possíveis noções de isomorfismo apropriadas para a teoria da complexidade. Inicialmente, pensei que um "tradutor" computacionalmente fraco, como uma máquina de estado finito, pudesse ser usado para definir os isomorfismos permitidos, mas isso já parece desmoronar para traduções sintáticas triviais entre fórmulas lógicas equivalentes. (Veja, por exemplo, esta tabela com a definição sintática do duplo na lógica linear$A^\bot$ .)

Hoje tive a seguinte idéia: Uma definição da linguagem correspondente a um "problema de decisão" geralmente tem duas partes: (1) uma codificação das instâncias de problemas permitidas como seqüências finitas de símbolos e (2) uma definição do " aceitas "instâncias de problemas que pertencem ao idioma. Se a verificação de se uma determinada sequência finita de símbolos é uma codificação de uma instância de problema permitida já exige uma máquina computacionalmente mais forte que uma máquina de estado finito, essa máquina mais forte também deve ser usada para a definição dos isomorfismos permitidos.

Perguntas: Essa linha de raciocínio tem alguma chance de "resolver" meu problema? Meu problema já foi resolvido, para que eu apenas precise ler as referências corretas? Meu próprio problema faz algum sentido ou isso é tão equivocado quanto reclamar da indecidibilidade da igualdade extensional?

Editar (ainda não foi uma resposta) notei que "(1) Uma codificação das instâncias de problemas permitidas como seqüências finitas de símbolos" já contém a suposição (oculta) de uma entrada normalizada. Sem essa suposição, duas seqüências finitas diferentes podem corresponder à mesma instância do problema. Em vez de verificar se uma determinada sequência finita é válida, a verificação pode produzir uma entrada normalizada (e mapear seqüências inválidas para uma sequência especial).

Essa configuração tem a vantagem de que a máquina que faz a verificação / normalização já está equipada com meios para transformar cadeias finitas em outras cadeias finitas. A máquina permitida (classe de complexidade) para esta tarefa poderia fazer parte da definição do problema, e os morfismos (iso) usariam a mesma máquina (classe de complexidade). (A sugestão de "reduções polivalentes e múltiplas" do comentário de Raphael seria, de fato, uma possibilidade para problemas em .)$\mathsf{P}$

Uma desvantagem é que essa forma de especificação pode ser apropriada apenas para máquinas determinísticas. Máquinas não determinísticas podem exigir maneiras mais flexíveis de especificar / decidir se duas seqüências de entrada correspondem à mesma instância do problema.

Meu problema já foi resolvido, para que eu apenas precise ler as referências corretas?

A teoria da família abstrata de línguas é relevante. Por exemplo, os morfismos definidos pelos transdutores de estado finito levam à família dos cones . A curta palestra sobre ICM de Eilenberg, de 1970, explica muito bem essa estrutura, consulte também o capítulo 11 "Propriedades de fechamento de famílias de idiomas", de Introdução à teoria de autômatos, idiomas e computação (1ª ed.) Por J. Hopcroft e J. Ullman, de 1979. No entanto, , apenas linguagens não determinísticas se encaixam nessa estrutura ¹ . No final, o livro Theory of codes de J. Berstel e D. Perrin, de 1985, me ajudou a encontrar soluções razoáveis ​​para o meu problema. Códigos e autômatospor J. Berstel, D. Perrin e C. Reutenauer de 2009 é uma revisão importante deste livro com uma cobertura muito mais ampla.

Essa linha de raciocínio tem alguma chance de "resolver" meu problema? Meu problema em si faz algum sentido ou isso é tão equivocado quanto ...?

A suposição de que existe uma categoria correta para modelar isomorfismos entre linguagens para "formalizar o conceito de um problema" é equivocada. Existem muitas categorias diferentes que podem ser interessantes no contexto das linguagens formais.

Aqui estão três categorias interessantes relacionadas a muitas reduções, que serão referidas como total , parcial e relacional . Os objetos das categorias são pares de um alfabeto finito Σ e um idioma L ⊂ Σ ∗ de palavras sobre Σ . Para o total , os morfismos entre o objeto de origem ( Σ , L ) e o objeto de destino ( Σ ′ , L ′ ) são funções totais $(\Sigma, L)$$\Sigma$$L\subset\Sigma^*$$\Sigma$$(\Sigma, L)$$(\Sigma', L')$ com L = f - 1 ( G ' ) . Paraparcial, os morphisms são funções parciais f : Σ * → Σ ' * com L = f - 1 ( L ' ) , onde duas funções parciais de f , g são considerados iguais (como morphisms), se f ( x ) = g ( x $f : \Sigma^* \to \Sigma'^*$$L=f^{-1}(L')$$f : \Sigma^* \to \Sigma'^*$$L=f^{-1}(L')$$f$$g$$f(x)=g(x)$para todos os . Para relacional , as relações são morphisms R ⊂ Σ * × Σ ' * com L = R - 1 ( L ' ) , e quaisquer dois morphisms entre a mesma origem e de destino são considerados iguais. O conjunto de funções ou relações permitidas pode ser restrito a vários "tradutores" simples para obter categorias com isomorfismos interessantes.$x\in L$$R\subset \Sigma^* \times \Sigma'^*$$L=R^{-1}(L')$

• Os homomorfismos monóides de a Σ ′ ∗ dão uma categoria total muito básica . Os isomorfismos desta categoria são basicamente apenas as bijeções entre Σ e Σ ′ . Qualquer família razoável de idiomas deve respeitar melhor esses isomorfismos, ou seja, ser fechada sob homomorfismos inversos.$\Sigma^*$$\Sigma'^*$$\Sigma$$\Sigma'$
• As funções parciais definidas pelos tradutores determinísticos de máquinas de Turing no espaço de log determinam uma categoria parcial bastante natural . É capaz de realizar muitas transformações sintáticas triviais (como aplicar as leis de De Morgan para mover negações para os átomos), inclui o morfismo definido pelos transdutores funcionais de estado finito ¹ e também pode classificar. Ainda assim, ele não identificará duas linguagens completamente não relacionadas como isomórficas, porque a igualdade da composição de dois morfismos com um morfismo de identidade é um requisito muito mais forte do que apenas a existência de muitas reduções em ambas as direções.
• As relações definidas pelos tradutores de máquina de Turing não-determinísticos no espaço de log fornecem uma categoria relacional interessante . O SAT é isomórfico para o HORNSAT nesta categoria, mas é uma questão em aberto se a TAUTOLOGY ou qualquer outro problema de co-NP completo é isomórfico para o HORNSAT.

Duas línguas e L ' sobre alfabetos Σ = { a , b } e Σ ' = { c , d } (onde a , b , c e d são letras distintas) nunca pode ser igual, mesmo se eles descrevem "exatamente" o mesmo problema." Mas eles devem ser isomórficos, se realmente descreverem "exatamente" o mesmo "problema".$L$$L'$$\Sigma=\{a,b\}$$\Sigma'=\{c,d\}$$a$$b$$c$$d$

A categoria total muito básica descrita acima resolve esse problema.

O problema torna-se mais interessante se "exatamente o mesmo" é substituído por "quase o mesmo para a maioria dos fins práticos": Let ser uma linguagem sobre Σ = { L , C , A , G } e deixar L ' ser a língua mais Σ ′ = { 0 , 1 } obtido de L pela substituição U → 00 , C → 01 , A → 10 e G → $L$$\Sigma=\{U,C,A,G\}$$L'$$\Sigma'=\{0,1\}$$L$$U \to 00$$C \to 01$$A \to 10$$G \to 11$. Observe que em qualquer categoria total , e L ′ não são isomórficos para L = Σ ∗ . O mesmo seria válido para categorias parciais , se a parte "onde duas funções parciais f , g forem consideradas iguais (como morfismos) se f ( x ) = g ( x ) para todos os x ∈ L " fossem omitidos da definição.$L$$L'$$L=\Sigma^*$$f$$g$$f(x)=g(x)$$x\in L$

A categoria parcial bastante natural descrita acima é suficiente para tornar e L ′ isomórficos. Seria bom ter uma categoria mais básica (ou seja, mais restritiva) que as torne isomórficas. As seguintes categorias (sucessivamente mais restritivas) parecem razoáveis ​​para mim:$L$$L'$

• As funções parciais realizadas por transdutores de estado finito inequívocos ^{2, em} que o único estado de aceitação é o estado inicial. Os isomorfismos dessa categoria parcial são (um subconjunto das) bijeções entre códigos de comprimento variável reconhecíveis .
• As funções parciais realizadas pelos transdutores determinísticos de estado finito, onde o único estado de aceitação é o estado inicial. Os isomorfismos dessa categoria parcial são (um subconjunto das) bijeções entre códigos de prefixo .
• As funções parciais são realizadas simultaneamente por um transdutor determinístico para a frente e para trás, onde o único estado de aceitação é o estado inicial. Os isomorfismos dessa categoria parcial são (um subconjunto das) bijeções entre os códigos bifix .
• Restrições adicionais das funções parciais, de modo que os isomorfismos sejam (um subconjunto das) bijeções entre códigos de bloco, também podem fazer sentido.

Pode-se usar linguagens na teoria da complexidade para formalizar o conceito de "problema".

Mesmo antes de aprender sobre a teoria das categorias, me perguntei se havia maneiras "mais fiéis" de formalizar o conceito de "problema". Depois de me familiarizar com a teoria das categorias, às vezes tentei encontrar soluções possíveis, mas sempre desistia rapidamente do primeiro obstáculo (porque ninguém se importa). Sei que Yuri Gurevich resolveu algumas questões relacionadas, mas suas soluções são praticamente aplicáveis, enquanto eu procurava mais por algo agradável e abstrato, independente da aplicabilidade prática.

A maior parte do meu tempo livre nas últimas três semanas foi finalmente fazer algum progresso nesse problema. Na maioria das vezes, passava o tempo encontrando problemas irritantes nas possíveis soluções que eu tinha em mente. O sentido de progredir surgiu da leitura de livros e artigos (antigos) e da aprendizagem de muitos conceitos e fatos básicos sobre transdutores e conjuntos racionais. Finalmente, aprendi as noções de código de prefixo e código bifixo (anteriormente código de biprefixo no livro de Berstel), o que me permitiu apresentar as ^três categorias razoáveis descritas acima.

Pode ser difícil apreciar essas categorias (relacionadas ao código), sem ter visto alguns problemas das categorias mais óbvias. Uma questão geral é que o fechamento sob composição pode dificultar a definição de uma classe bem restrita de funções parciais. Outra questão está relacionada ao fato de que a adição de uma (ou multiplicação por uma constante) é uma "função fácil de calcular" se os dígitos do número forem fornecidos em ordem low-endian, mas não se os dígitos forem fornecidos em caracteres grandes. ordem endian.

_$O(n)$$O(1)$

2 _{Um transdutor de estado finito inequívoco é um transdutor de estado finito não determinístico com no máximo um caminho de aceitação para cada entrada. Ele realiza uma função parcial, portanto, também é um transdutor de estado finito funcional. É decidível se um determinado transdutor de estado finito é inequívoco.}

_{$R\subset \Sigma^* \times \Sigma'^*$$L=R^{-1}(L')-R^{-1}(\Sigma'^*-L')$, e quaisquer dois morfismos entre a mesma origem e destino são considerados iguais.}