Completude e linguagens sensíveis ao contexto.

16

Estou interessado em duas perguntas sobre linguagens sensíveis ao contexto (CSL) e integridade:

  1. Existe uma noção de integridade para CSL e quais idiomas estão completos?
  2. Existem CSL naturais que são NP-completas?

Para 2., certamente posso pensar em linguagens naturais completas de NP que são CSL (como CSL é igual a NSPACE [ ], SAT é uma CSL), mas estou procurando o contrário, ou seja, um contexto gramática sensível que descreve uma linguagem NP-completa.n

np-hardness fl.formal-languages space-bounded Michaël Cadilhac
fonte
2
Vamos ver se entendi (2) corretamente: Seria suficiente escrever uma gramática sensível ao contexto que gere todas as instâncias 3SAT válidas em um alfabeto fixo de conectivos e variáveis ​​SAT?
Evgenij Thorstensen 04/10/10
11
Bem, eu não teria adicionado variáveis ​​SAT como parte do alfabeto (uma codificação binária de seus índices é boa o suficiente), mas isso certamente responderia ao meu segundo ponto!
Michaël Cadilhac
A propósito, você tentou?
Michaël Cadilhac
4
(1) Como você mencionou, é possível escrever um CSG para o 3SAT, mas isso soa semelhante a escrever uma descrição completa de uma máquina de Turing para o problema de fluxo máximo (ou qualquer idioma específico em P); Eu não esperaria que isso desse uma idéia da teoria da complexidade. (Mas, ei, se acontecer de outra forma, ficarei feliz em ouvi-lo.) (2) Geralmente, a noção de gramáticas sensíveis ao contexto e a noção de completude NP não combinam bem porque o conjunto de questões sensíveis ao contexto idiomas não está fechado com reduções de tempo polinomial.
Tsuyoshi Ito
11
Obrigado por esse comentário Tsuyoshi. Na verdade, uma gramática para o 3SAT provavelmente não é o que estou procurando, mas fui com a mesma reação que a sua: se for um pouco fácil / natural, eu estaria interessado. Para o seu (2), um dos meus objetivos é o seguinte: digamos que eu tenho uma classe de idiomas CS fechada por redução do espaço de log e quero mostrar que minha classe não (ou é improvável que) contenha problemas completos de NP, Eu só precisaria mostrar que a linguagem específica do NP-CS completa não está na minha turma, o que poderia ser mais fácil se o idioma for naturalmente CS.
Michaël Cadilhac 10/10

Respostas:

9

Para responder à sua primeira pergunta, uma redutibilidade adequada às suas necessidades é log-lin-reducibility, que é a redutibilidade do espaço de log com a restrição adicional de que o tamanho da cadeia de saída da redução é no máximo linear no tamanho da entrada. Se bem me lembro, o problema de associação para gramáticas sensíveis ao contexto (ou, se você preferir, autômatos delimitados linearmente) é o problema canônico da CSL-complete por redutibilidade de log-lin.

No lado aplicado, o problema da universalidade das expressões regulares (comuns) sobre o alfabeto binário é a redutibilidade de log-lin-redutibilidade completa do CSL. A noção e o resultado da completude são encontrados em Albert R. Meyer e Larry J. Stockmeyer (SWAT 1972) também: Stockmeyer (tese de doutorado, MIT 1974). Para mais informações e resultados semelhantes nessa área, consulte também a pesquisa recente de Holzer e Kutrib (DLT 2010).

EDIT (06/03/2017): Com relação à sua segunda pergunta, a resposta aceita para a pergunta abaixo cita um artigo de Rounds (1973), que constrói um autômato de pilha aninhado unidirecional que reconhece SAT. Embora o SAT não se qualifique como uma CSL "natural", pode valer a pena pesquisar na literatura por outros exemplos de autômatos de pilha aninhados unidirecionais ou gramáticas indexadas.

Gramática sensível ao contexto para SAT?

Hermann Gruber
fonte
Muito obrigado, é isso que eu estava procurando!
Michaël Cadilhac
Para a edição: Fantástico! Obrigado por voltar e completar esta resposta, este é um grande espírito!
Michaël Cadilhac