Qual é a complexidade do estado da linguagem de cópia?

Deixe um número ser dado. Considere o seguinte idioma $n$ . $L_n = \{ \; ww \; \vert \; w \in \{0,1\}^{n} \; \}$

Em palavras, é o conjunto de cadeias de cópia de comprimento . $L_n$ $2n$

Considere a seguinte função de complexidade de estado modo que é o número de estados no menor autômato de empilhamento que reconhece . $s$ $s(n)$ $L_n$

Pergunta: Você pode provar formalmente qualquer limite inferior significativo para ? $s(n)$

Minha conjectura: . $s(n) = 2^{\Theta(n)}$

Upperbound conhecido: . $s(n) \leq \mathrm{poly}(n) \cdot 2^{\frac{n}{2}}$

Regras:

(1) O alfabeto da pilha deve ser binário.

(2) A fita de entrada é unidirecional e não pode parar em nenhum caractere de entrada.

fl.formal-languages automata-theory grammars context-free Michael Wehar
fonte

Atualmente, não tenho nenhum limite inferior significativo. Parece-me que você poderá provar um limite inferior para o número de variáveis necessárias para um CFG que reconheça o idioma. Embora eu nem tenha certeza disso.

22615 Michael Wehar

Minha intuição é que, ao enviar caracteres da fita de entrada para a pilha, você se depara com um problema. Se você quiser recuperar esses bits mais tarde, precisará jogar fora todos os bits que empurrou acima dele. Em outras palavras, parece que a pilha não ajuda, porque quanto mais você pressiona, mais você é forçado a esquecer mais tarde.

22715 Michael Wehar

Observação: para os DFA (autômatos sem pilha), é possível provar um limite inferior da complexidade do estado exponencial.

22715 Michael Wehar

Você pode mostrar um limite inferior razoável para o problema mais simples de

{0^{k} 1^{l} 0^{k} 1^{l}}

$\{0^k1^l0^k1^l\}$

András Salamon

Um limite superior mais preciso parece ser

estados.

(n + 3) 2^{n / 2}

$(n+3)2^{n/2}$

András Salamon

Respostas:

A técnica descrita por Yuval:

Existe CFG de tamanho polinomial que descreve essa linguagem finita?

(você também pode ler: Limites mais baixos no tamanho dos CFGs para idiomas finitos específicos )

$G$ $L_n$ $w\in \{0,1\}^n$ $A(w)$ $s(w)$ $ww$ $n/2$ $n$ $p(w)$ $ww$ $n/2$ $w,w'$ $A(w)=A(w')$ $p(w)=p(w')$ $2^{n/2}$ $A(w)$ $p(w)$ $2^{\Theta(n)}$

$2^{\Theta(n)}$ $L_n$

Joseph Stack
fonte

Incrível, obrigado novamente! Eu vejo agora e vou pensar sobre isso para confirmar. :)

Michael Wehar

[n, 2 n]

$[n,2n]$

[n / 2, n]

$[n/2,n]$

(A (w), p (w))

$(A(w),p(w))$

A (w)

$A(w)$

w w

$ww$

p (w)

$p(w)$

Veja também o Teorema 7 em meu artigo: cs.toronto.edu/~yuvalf/CFG-LB.pdf .

Yuval Filmus

@YuvalFilmus Também vale a pena notar que Andras passou um pouco de tempo tentando ajustar os limites superior e inferior. Meu amigo Pepe e eu definimos uma classe geral de linguagens finitas e aplicamos a técnica a elas. Nós nunca escrevemos nada. Se você tiver algum problema relacionado, estaríamos mais do que dispostos a colaborar. Obrigado novamente.

Michael Wehar