É decidível se o comprimento de saída de um transdutor é limitado pelo comprimento de entrada?

10

Os transdutores considerados aqui são aqueles que a Wikipedia chama de transdutores de estado finito . O comportamento de um transdutor , isto é, a relação que ele calcula, é escrito : uma palavra é uma saída para iff .[ T ] y x x [ T ] yT[T]yxx[T]y

Pergunta: O seguinte problema é decidível:

Dado: Um transdutor e uma linguagem regular Decida: Mantém que , uma palavra, implica que?Tx L y x [ T ] y | y | | x |L
xLyx[T]y|y||x|

Estou à procura de análises não triviais / subcasas solucionáveis, redução de problemas conhecidos e / ou referências relacionadas. (agora nem tenho certeza se é decidível em geral ...?)

Motivação: esse problema foi inspirado pela análise / investigação do teorema automatizado de comprovação de problemas da teoria dos números em geral e por um estudo altamente estudado, a conjectura de Collatz , em particular.

vzn
fonte
2
Os transdutores FSM ps (deveriam ter sido mencionados, há muito conhecido) são poderosos o suficiente para calcular iterações únicas das "descrições instantâneas" da TM . portanto, o problema parece possivelmente se relacionar com LBAs e CSLS .
vzn
por você fala do número de saídas na entrada x , certo? Não é o tamanho das saídas; nesse caso, seria bastante direto. |F(x)|x
Michaël Cadilhac
são palavras e | F ( x ) | é o comprimento da palavra "saída". tenho algumas idéias, mas não vejo nada direto no momento, portanto, a pergunta. seu devido presumivelmente não trivial por exemplo, para ε entradas / saídas em algumas transições etcx,F(x)|F(x)|ϵ
vzn
Portanto, você assume implicitamente que seu transdutor é funcional - em termos de notação, não ficou claro para mim :-) Então, o que se segue: Seja um transdutor (possivelmente não determinístico) e L seja uma linguagem comum. Modifique T em um transdutor T ' para verificar se sua entrada está em L e todos os seus estados são alcançáveis ​​e co-alcançáveis. Então | T ( w ) | | w | para todos w L se não houver um ciclo simples no transdutor T TLTTL|T(w)||w|wLTpara as quais a entrada é menor que a saída e algumas propriedades fáceis adicionais nas transições que não aparecem em nenhum SCC.
Michaël Cadilhac
Está bem. para "a entrada é menor que a saída", você quer dizer ao longo do ciclo? acho que vale a pena escrever isso como resposta. havia outra maneira diferente de formular este / problema relacionado com critérios mais rígidos que provavelmente não é (como) fácil, talvez tente novamente ("parte 2 / sequência / acompanhamento") se sua resposta parecer correta. esse problema atual é provavelmente quase um caso especial do problema mais amplo.
vzn

Respostas:

8

O outro colaborador excluiu sua resposta, talvez para me permitir estender meu comentário acima, então aqui está.

Seja um transdutor possivelmente não determinístico e L seja uma linguagem comum. Modifique T em um transdutor T ' que verifique se sua entrada está em L (alterando, por exemplo, o estado definido no produto cartesiano dos conjuntos de estados T e L e modificando a função de transição para que a parte L dos estados é atualizado corretamente, mantendo o comportamento de T. )TLTTLTLLT

Um ramo de é uma sequência ρT de tal modo que ρ 1 ρ 2ρ n + 1 é um caminho aceitar simples em T ' , e cada um C i é um componente fortemente conectado de T cujos estados incluem o destino de ρ i (e a origem de ρ iρ1C1ρ2C2ρnCnρn+1ρ1ρ2ρn+1TCiTρi ) A filial émansase:ρi+1

  1. O comprimento de entrada do caminho é maior do que ou igual ao seu comprimento de saída;ρ1ρ2ρn+1

  2. Para qualquer , qualquer ciclo simples em C i , o comprimento de entrada do ciclo é maior ou igual ao seu comprimento de saída.iCi

Fato: Para qualquer x , y , x [ T ] y implica em | y | | x | ] se todos os ramos são mansos.[x,yx[T]y|y||x| ]

A prova é bastante imediata. Sendo a última propriedade decidível (como o número de ramificações é limitado e o número de ciclos simples também), isso mostra que o problema da questão é decidível.

Michaël Cadilhac
fonte
11
Parece, pela descrição, que é até decidível em NL (daí em P), assumindo que é dado por uma FSA. L
Emil Jerabek
Enviei um aviso (desculpe, não li atentamente seu comentário antes de postar), mas provavelmente você não o recebeu após a exclusão da resposta :-) ... mas agora - como reembolso do tempo - você deve mudar para (e resolva!), este é mais complicado: " Problema em aberto : existe e uma codificação computável S nn1Sn tal que, para todos os , L S nn = L S nn + k ?" :-D :-Dk1LnSn=Ln+kSn
Marzio De Biasi
11
@ EmilJeřábek De fato, é bem claro em co-NL (daí em NL).
Michaël Cadilhac
@MarzioDeBiasi Thanks! Na verdade, eu não vi o seu aviso ☺ vou trabalhar para reembolsar seu tempo quando tiver algum ☺ #
Michaël Cadilhac