Existe um DCFL mais difícil?

Greibach notoriamente definida uma linguagem de , o chamado versão não-determinístico de , de tal modo que qualquer CFL é uma imagem inversa de mórfica . Existe uma afirmação semelhante com o DCFL, possivelmente com alguma restrição nos morfismos permitidos? $H$ $D_2$ $H$

(Ver, por exemplo, M. Autebert, J. Berstel e L. Boasson. Linguagens sem contexto e autômatos de empilhamento. Em R. Rozenberg e A. Salomaa, editores, Handbook of Formal Languages, volume I, capítulo 3. Springer Verlag , 1997.)

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

Respostas:

Uma caracterização homomorfismo idêntica da DCFL não parece ser possível. O seguinte é extraído do artigo original de Greibach .

Mostramos que toda linguagem livre de contexto pode ser expressa como ou para um homomorfismo . A afirmação algébrica é: a família das linguagens livres de contexto é a principal AFDL; ... Por outro lado, a família de linguagens deterministas livres de contexto não é a principal AFDL [7]. $h^{-1}(L_0)$ $h^{-1}(L_0-\{e\})$ $h$

O artigo 7 é a versão em conferência do artigo. Na versão da conferência, o Teorema 4.2 afirma que "A família de linguagens determinísticas livres de contexto não é uma AFDL principal".

No entanto, alguma caracterização analógica ainda pode ser possível. Okhotin forneceu caracterizações homomórficas de gramáticas conjuntivas e booleanas. Para a DCFL, o problema parece estar aberto. A seguir, é apresentada a conclusão do artigo de Okhotin (a partir de 2013).

Toda família de idiomas fechados sob homomorfismos inversos pode potencialmente ter um análogo da caracterização homomórfica inversa de Greibach. A questão é: quais são as famílias? Poderia existir para variantes lineares, determinísticas ou inequívocas de gramáticas comuns (sem contexto)? Poderia haver tal caracterização para gramáticas conjuntivas lineares, gramáticas conjuntivas inequívocas, etc.?

Mateus de Oliveira Oliveira
fonte

Obrigado! No entanto, eu sei que o DCFL não é principal; é por isso que estou permitindo que os morfismos sejam restritos, se necessário - posso formular minha pergunta com mais precisão como: qual é a menor classe de funções F para a qual existe uma linguagem H onde F (H) é o conjunto de todos os DCFL - dê ou aceite alguns fechamentos adicionais.

Michaël Cadilhac

Está bem. Eu editei minha resposta. Parece que, para o DCFL, esse é um problema em aberto.

Mateus de Oliveira Oliveira

Curiosamente, eu conheço muito bem o artigo de Okhotin, mas não percebi que ele estava se referindo explicitamente ao problema! Bem, então, não tenho certeza do que fazer aqui; claro, é uma resposta válida no momento , mas deve ser deixada em aberto até que seja resolvida?

Michaël Cadilhac 23/02

Não sei qual é a polícia do site sobre pedir soluções para problemas difíceis. Pessoalmente, se alguém me disser que um problema em que estou interessado está aberto por muitos anos, eu aceitaria a resposta. Minha opinião é que, nesse caso, é mais apropriado visualizar a pergunta como uma solicitação de referência. Mas pode haver pontos de vista divergentes em relação a isso. Eu acho que essa discussão em meta.cstheory pode ser útil meta.cstheory.stackexchange.com/questions/1058/…

Mateus de Oliveira Oliveira

Claro que não me importo que você aceite sua resposta. Na verdade, é uma resposta muito interessante. No entanto, embora a resposta se encaixe no título, ela é muito diferente da pergunta em si, pois as reduções do espaço de log são muito mais poderosas que os 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)}$

Conforme mencionado pelo colaborador Mateus de Oliveira Oliveira, o DCFL não é um AFL principal e não se sabe se existe uma caracterização exata envolvendo o fechamento de um único idioma em algumas operações.

Michaël Cadilhac
fonte

O papel

J.-M. Autebert, Uma nota sobre os cilindros demétricos, Theoretical Computer Science 8 (1979), 395-399

fornece uma prova curta do seguinte resultado (creditado a Greibach) que parece responder à sua pergunta:

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

J.-E. PIN
fonte