Completitud y lenguajes sensibles al contexto.

16

Me interesan dos preguntas sobre los lenguajes sensibles al contexto (CSL) y la integridad:

  1. ¿Existe una noción de integridad para CSL y qué idiomas están completos?
  2. ¿Hay CSL naturales que son NP completas?

Para 2., ciertamente puedo pensar en lenguajes NP-completos naturales que son CSL (como CSL es igual a NSPACE [ ], SAT es un CSL), pero estoy buscando lo contrario, es decir, un contexto- gramática sensible que describe un lenguaje NP-completo.norte

np-hardness fl.formal-languages space-bounded Michaël Cadilhac
fuente
2
Veamos si entiendo (2) correctamente: ¿Sería suficiente escribir una gramática sensible al contexto que genere todas las instancias válidas de 3SAT sobre un alfabeto fijo de conectivas y variables SAT?
Evgenij Thorstensen
1
Bueno, no habría agregado variables SAT como parte del alfabeto (una codificación binaria de sus índices es lo suficientemente buena), ¡pero eso ciertamente respondería a mi segundo punto!
Michaël Cadilhac
Por cierto, ¿lo intentaste?
Michaël Cadilhac
44
(1) Como mencionó, es posible escribir un CSG para 3SAT, pero eso suena similar a escribir una descripción completa de una máquina Turing para el problema de flujo máximo (o cualquier lenguaje específico en P); No esperaría que dé una idea de la teoría de la complejidad. (Pero bueno, si resulta lo contrario, estaré encantado de escucharlo). (2) En general, la noción de gramáticas sensibles al contexto y la noción de completitud NP no van bien juntas porque el conjunto de sensibles al contexto idiomas no está cerrado bajo reducciones de tiempo polinomial.
Tsuyoshi Ito
1
Gracias por ese comentario Tsuyoshi. De hecho, una gramática para 3SAT probablemente no sea lo que estoy buscando, pero tomé la misma reacción que la suya: si es algo fácil / natural, me interesaría. Para su (2), uno de mis objetivos es el siguiente: digamos que tengo una clase de lenguajes CS cerrados por reducción de espacio de registro, y quiero mostrar que mi clase no contiene (o es poco probable que) contenga problemas NP-completos, Solo tendría que mostrar que el lenguaje específico de CS NP-completo no está en mi clase, lo que podría ser más fácil si el lenguaje es naturalmente CS.
Michaël Cadilhac

Respuestas:

9

Para responder a su primera pregunta, una reducibilidad que se ajuste a sus necesidades es log-lin-reducibility, que es la reducibilidad de espacio de registro con la restricción adicional de que el tamaño de la cadena de salida de la reducción es como máximo lineal en el tamaño de la entrada. Si no recuerdo mal, el problema de la membresía para las gramáticas sensibles al contexto (o, si lo desea, autómatas con límites lineales) es el problema canónico CSL-complete wrt log-lin reducibility.

En el lado aplicado, el problema de universalidad de las expresiones regulares (ordinarias) sobre el alfabeto binario, es CSL-complete wrt log-lin-reducibility. La noción y el resultado completo se encuentran en Albert R. Meyer y Larry J. Stockmeyer (SWAT 1972) también: Stockmeyer (tesis doctoral, MIT 1974). Para obtener más antecedentes y resultados similares en esa área, consulte también la encuesta reciente de Holzer y Kutrib (DLT 2010).

EDITAR (2017/03/06): Con respecto a su segunda pregunta, la respuesta aceptada a la pregunta a continuación cita un artículo de Rounds (1973), que construye un autómata de pila anidada unidireccional que reconoce SAT. Si bien el SAT no calificará como CSL "natural", podría valer la pena buscar en la literatura otros ejemplos de autómatas de pila anidada unidireccional o gramáticas indexadas.

Gramática sensible al contexto para SAT?

Hermann Gruber
fuente
¡Muchas gracias, esto es lo que estaba buscando!
Michaël Cadilhac
Para la edición: ¡Fantástico! Gracias por volver allí y completar esta respuesta, ¡este es un gran espíritu!
Michaël Cadilhac