¿Existe un DCFL más difícil?

Greibach famoso definido un lenguaje de , la denominada versión no determinista de , tal que cualquier CFL es una imagen mórfica inversa de . ¿Existe una declaración similar con DCFL, posiblemente con alguna restricción en los morfismos permitidos? $H$ $D_2$ $H$

(Véase, por ejemplo, M. Autebert, J. Berstel y L. Boasson. Lenguajes libres de contexto y autómatas pushdown. En R. Rozenberg y A. Salomaa, editores, Manual de idiomas formales, volumen I, capítulo 3. Springer Verlag , 1997.)

fl.formal-languages open-problem context-free nondeterminism hard-instances Michaël Cadilhac
fuente

Respuestas:

Una caracterización de homomorfismo idéntica de DCFL no parece ser posible. Lo siguiente se extrae del documento original de Greibach .

$h^{-1}(L_0)$ $h^{-1}(L_0-\{e\})$ $h$

El documento 7 es la versión de conferencia del documento. En la versión de la conferencia, el Teorema 4.2 establece que "La familia de lenguajes deterministas sin contexto no es un AFDL principal".

Sin embargo, aún puede ser posible alguna caracterización analógica. Okhotin proporcionó caracterizaciones homomórficas de gramáticas conjuntivas y booleanas. Para DCFL, el problema parece estar abierto. La siguiente es la conclusión del artículo de Okhotin (de 2013).

Cada familia de lenguas cerradas bajo homomorfismos inversos puede tener un análogo de la caracterización homomórfica inversa de Greibach. La pregunta es, ¿qué familias lo tienen? ¿Podría existir para variantes lineales, deterministas o inequívocas de gramáticas ordinarias (sin contexto)? ¿Podría haber tal caracterización para las gramáticas conjuntivas lineales, las gramáticas conjuntivas inequívocas, etc.?

Mateus de Oliveira Oliveira
fuente

¡Gracias! Sin embargo, sé que los DCFL no son principales; es por eso que estoy permitiendo que se restrinjan los morfismos si es necesario: puedo formular mi pregunta con mayor precisión como: ¿cuál es la clase más pequeña de funciones F para la cual hay un lenguaje H donde F (H) es el conjunto de todos los DCFL? - Dar o tomar algunos cierres adicionales.

Michaël Cadilhac

Okay. Edité mi respuesta. Parece que para DCFL este es un problema abierto.

Mateus de Oliveira Oliveira

Curiosamente, conozco muy bien el artículo de Okhotin, ¡pero no me di cuenta de que se refería explícitamente al problema! Pues bien, no estoy seguro de qué hacer aquí; claro, es una respuesta válida por el momento , pero ¿debería dejarse abierta hasta que se resuelva?

Michaël Cadilhac

No sé cuál es la policía del sitio acerca de pedir soluciones para problemas abiertos. Personalmente, si alguien me señalara que un problema que me interesa está abierto durante muchos años, entonces aceptaría la respuesta. Mi opinión es que en este caso es más apropiado ver la pregunta como una solicitud de referencia. Pero puede haber puntos de vista divergentes con relación a esto. Creo que esta discusión en meta.cstheory podría ser útil meta.cstheory.stackexchange.com/questions/1058/…

Mateus de Oliveira Oliveira

Por supuesto, no me importa que aceptes tu respuesta. De hecho, es una respuesta muy interesante. Sin embargo, aunque la respuesta se ajusta al título, es muy diferente de la pregunta en sí, ya que las reducciones de espacio de registro son mucho más poderosas que los homomorfismos.

Mateus de Oliveira Oliveira

$L_0^{(2)}$ $\{a, \bar{a}, b, \bar{b}, \#, [, ]\}$

γ_{0} [\bar{a} γ_{a}^{(1)} # \bar{b} γ_{b}^{(1)}] \dots [\bar{a} γ_{a}^{(k)} # \bar{b} γ_{b}^{(k)}],

$\gamma_0\;[\bar{a}\gamma_a^{(1)}\#\bar{b}\gamma_b^{(1)}]\;\cdots\; [\bar{a}\gamma_a^{(k)}\#\bar{b}\gamma_b^{(k)}]\enspace,$

$\gamma_0, \gamma_a^{(i)}, \gamma_b^{(i)}$ $\{a, \bar{a}, b, \bar{b}\}$ $w_1w_2\cdots w_k \in \{a, b\}^k$ $\gamma_0 \; \bar{w_1}\gamma_{w_1}^{(1)} \cdots \bar{w_k}\gamma_{w_k}^{(k)}$

$L_0^{(2)}$ $L_0^{(2)}$ $L_0^{(2)}$

Como mencionó el colaborador Mateus de Oliveira Oliveira, DCFL no es una AFL principal, y se desconoce si existe una caracterización exacta que implique el cierre de un solo idioma en algunas operaciones.

Michaël Cadilhac
fuente

El papel

J.-M. Autebert, Une note sur le cylindre des langages déterministes, Theoretical Computer Science 8 (1979), 395-399

da una breve prueba del siguiente resultado (acreditado a Greibach) que parece responder a su pregunta:

$L$ $C$ $h$ $R$ $C = h^{-1}(L)\cap R$

J.-E. Alfiler
fuente