Problemas com o LogDCFL

16

LogCFL é o conjunto de todos os idiomas com espaço de log redutível para um idioma sem contexto. Da mesma forma, LogDCFL é o conjunto de todos os idiomas com espaço de log redutível para um idioma sem contexto determinístico. Consulte este artigo da Wikipedia para alguns problemas naturais completos do LogCFL. Existem vários outros problemas interessantes completos do LogCFL. Não foi possível encontrar nenhum problema natural com o LogDCFL. Nomeie qualquer problema completo com LogDCFL natural.

Shiva Kintali
fonte
Por curiosidade, posso perguntar por que você está interessado no LogDCFL?
Michaël Cadilhac
Estou interessado em computação limitada por espaço em geral e tentando entender o LogDCFL.
Shiva Kintali

Respostas:

12

O idioma a seguir é um pequeno ajuste do normal do LogCFL completo, para que ele seja completo do LogDCFL. A prova pode ser encontrada na complexidade da fita de línguas determinísticas, livre de contexto, de Sudborough.

Seja e T = { [ , ] , | } . O seguinte linguagem sobre Σ T é LogDCFL-completo. L consiste em palavras w 0 [ ( 1 l 1 | ( 2 r 1 ] …… [ ( 1 l n | ( 2Σ={(1 1,(2,)1 1,)2}T={[,],|}ΣTeu , onde w 0 , l i , r i Σ * tal que existe w 1 ,..., w n com w i = ( 1 l i ou w i = ( 2 R i para todos osi1e w 0 w 1 w n está entre parênteses.

W0 0[(1 1eu1 1|(2r1 1]...[(1 1eun|(2rn]
W0 0,euEu,rEuΣW1 1,...,WnWEu=(1 1euEuWEu=(2rEuEu1 1W0 0W1 1...Wn
Michaël Cadilhac
fonte