Determinando recursos de máquinas de estado min-heap (ou outras exóticas)

44

Veja o final deste post para obter alguns esclarecimentos sobre as definições de autômatos de min-heap.

Pode-se imaginar o uso de uma variedade de estruturas de dados para armazenar informações para uso por máquinas de estado. Por exemplo, autômatos push-down armazenam informações em uma pilha e as máquinas de Turing usam uma fita. As máquinas de estado que usam filas e aquelas que usam duas pilhas ou fitas múltiplas mostraram ser equivalentes em potência às máquinas de Turing.

Imagine uma máquina min-heap. Funciona exatamente como um autômato push-down, com as seguintes exceções:

  1. Em vez de examinar a última coisa que você adicionou ao heap, apenas o menor elemento (com a ordem definida por máquina) atualmente no heap.
  2. Em vez de remover a última coisa que você adicionou ao heap, você só pode remover um dos menores elementos (com a ordem definida por máquina) atualmente no heap.
  3. Em vez de adicionar um elemento à parte superior do heap, você pode adicionar apenas um elemento ao heap, com sua posição sendo determinada de acordo com os outros elementos no heap (com a ordem definida por máquina).

Esta máquina pode aceitar todos os idiomas comuns, simplesmente não usando o heap. Ele também pode aceitar o idioma adicionando 's ao heap, e remover 's da pilha quando lê 's. Pode aceitar uma variedade de outras linguagens sem contexto. No entanto, ele não pode aceitar, por exemplo, (declarado sem prova). EDIT: ou pode? Acho que não, mas já fiquei surpreso antes, e tenho certeza de que ficarei surpreso quando minhas suposições continuarem me fazendo um ... bem.{anbn{a,b}n0}aab{w{a,b}w=wR}

Ele pode aceitar qualquer linguagem sensível ao contexto ou completa de Turing?

De maneira mais geral, que pesquisa, se houver alguma, foi realizada nessa direção? Que resultados existem, se houver? Também estou interessado em outras variedades de máquinas de estado exóticas, possivelmente aquelas que usam outras estruturas de dados para armazenamento ou vários tipos de restrições de acesso (por exemplo, como os LBAs são TMs restritos). Referências são apreciadas. Peço desculpas antecipadamente se esta pergunta está demonstrando ignorância.


Definição formal:

Fornecemos aqui algumas definições mais detalhadas de autômatos de min-heap, a fim de esclarecer uma discussão mais aprofundada em questões que fazem referência a este material.

Definimos um autômato de heap não-determinístico tipo 1 como uma tupla de 7 que ...

(Q,q0,A,Σ,Γ,Z0,δ)
  1. Q é um conjunto de estados finito e não vazio;
  2. q0Q é o estado inicial;
  3. AQ é o conjunto de estados que aceitam;
  4. Σ é um alfabeto de entrada finito e não vazio;
  5. γ Γ w ( γ ) N w ( γ 1 ) = w ( γ 2 )Γ é um alfabeto de entrada finito e não vazio, em que o peso de um símbolo , , é tal que ;γΓw(γ)Nw(γ1)=w(γ2)γ1=γ2
  6. Z0Γ é o símbolo especial da parte inferior da pilha;
  7. δ:Q×(Σ{ϵ})×(Γ{Z0})P(Q×Γ) é a função de transição.

A função de transição funciona assumindo um heap inicialmente vazio que consiste apenas em . A função de transição pode adicionar à pilha uma coleção arbitrária (finita, mas possivelmente vazia ou com repetições) de elementos . Como alternativa, a função de transição pode remover uma instância do elemento com o menor peso de todos os elementos restantes na pilha (ou seja, o elemento na parte superior da pilha). A função de transição pode usar apenas a instância do símbolo mais alto (ou seja, de peso mínimo) para determinar qualquer transição.γ 1 , y 2 , . . . , γ kΓ γ w ( γ )Z0γ1,γ2,...,γkΓγw(γ)

Além disso, defina um autômato min-heap determinístico do tipo 1 como um autômato min-heap não-determinístico do tipo 1 que satisfaça a seguinte propriedade: para todas as seqüências de caracteres modo que e , .| x | = n σ Σ | δ n + 1 ( q 0 , x σ y , Z 0 ) | 1xσyΣ|x|=nσΣ|δn+1(q0,xσy,Z0)|1

Defina também um autômato de pilha mínima não-determinística tipo 2 exatamente o mesmo que um autômato de pilha mínima não-determinística tipo 1, exceto as seguintes alterações:

  1. γ Γ w ( γ ) N w ( γ 1 ) = w ( γ 2 ) γ 1 = γ 2Γ é um alfabeto de entrada finito e não vazio, em que o peso de um símbolo , , é tal que não implica necessariamente ; em outras palavras, diferentes símbolos de heap podem ter o mesmo peso.γΓw(γ)Nw(γ1)=w(γ2)γ1=γ2
  2. Quando instâncias de símbolos de heap distintos com o mesmo peso são adicionadas ao heap, sua ordem relativa é preservada de acordo com uma ordem de pilha do tipo LIFO (último a entrar, primeiro a sair).

Agradecemos a Raphael por apontar essa definição mais natural, que captura (e amplia) as linguagens sem contexto.


Alguns resultados demonstrados até agora:

  1. O autômato de pilha mínima do tipo 1 reconhece um conjunto de idiomas que não é um subconjunto nem um superconjunto dos idiomas sem contexto. [ 1 , 2 ]
  2. Os autômatos de heap mínimo do tipo 2, por sua definição, reconhecem um conjunto de idiomas que é um superconjunto adequado das linguagens sem contexto, bem como um superconjunto adequado dos idiomas aceitos pelos autômatos de heap min do tipo 1.
  3. Os idiomas aceitos pelos autômatos de pilha mínima tipo 1 parecem estar fechados sob a união, concatenação e estrela Kleene, mas não sob complementação [ 1 ], interseção ou diferença;
  4. Os idiomas aceitos pelos autômatos de pilha mínima não-determinística do tipo 1 parecem ser um superconjunto adequado de idiomas aceitos pelos autômatos de pilha mínima determinística do tipo 1.

Pode haver alguns outros resultados que eu perdi. Mais resultados estão (possivelmente) a caminho.


Perguntas de acompanhamento

  1. Fechamento sob reversão? -- Abrir
  2. Encerramento sob complementação? -- Não!
  3. O não determinismo aumenta o poder? -- Sim?
  4. O do tipo 2? HALCSL-- Abrir
  5. A adição de pilhas aumenta a potência do tipo 1? - para (?) k > 2HAL1HAL2=HALkk>2
  6. A adição de uma pilha aumenta a potência do tipo 1? -- Abrir
Patrick87
fonte
1
Ótima pergunta, a propósito. Estou tentado a procurar um lema de bombeamento para esses autômatos.
Raphael
@ Rafael: Eu acho que você pode usar a minha prova (atualizada) para esse lema: qualquer idioma para o qual você precise "lembrar" mais do que uma quantidade linear de informações em alguma substring para corresponder a uma subsequente corretamente não pode ser analisado por autômatos de min-heap. Não tenho certeza se é possível um verdadeiro lema no estilo de bombeamento - ele também pode acabar sendo um caso especial do meu lema.
Alex-Brink
@AlextenBrink Como combinações de números de símbolos de heap podem ser usadas para codificar coisas, não tenho certeza se um limite linear é suficiente.
Raphael

Respostas:

25

Você pode reconhecer a linguagem canônica não isenta de contexto (mas sensível ao contexto) com esse tipo de máquina de estado. O ponto crucial é que você adicionar fichas para a pilha para cada caráter, e ao analisar os caracteres, você adiciona os tokens 'maiores' para a pilha, para que eles só acabam no fundo do poço quando você ter analisado todos os personagens.a b b{anbncn | n1}abb

Símbolos heap são e , onde . Nós consumimos todos os símbolos na entrada e adicionar símbolo para a pilha. Se encontrarmos um , alternamos as estratégias: para cada que encontramos subsequentemente, removemos a do heap e adicionamos ao heap. Quando encontramos um , deveríamos ter ficado sem s para remover e, em seguida, para cada na entrada restante, removemos um do heap. Se o heap estiver vazio no final, a sequência estará no idioma. Obviamente, rejeitamos se algo der errado.b a < b a a b b a b c a c baba<baabbabcacb

Atualizar:

A linguagem não pode ser reconhecido pelos autômatos de min-heap. Suponha que tenhamos um autômato min-heap que possa reconhecer o . Observamos o 'estado' em que o autômato está depois de ler (a primeira parte da entrada, então é o próximo). O único estado que temos são o conteúdo da pilha e o estado particular do autômato que se encontra. Isto significa que depois de reconhecer , este necessidades 'estado' para manter informações suficientes para corresponder .EPAL={wwR|w{a,b}}EPALwwRwwR

Em particular, a fim de fazer isso, deve haver possível diferente 'do estado (onde ), uma vez que existem palavras possíveis que consistem de e caracteres. Como há apenas um número finito de estados e apenas um número finito de caracteres de heap, isso implica que existe alguma palavra para a qual o heap contém um número exponencial de algum caractere de heap, digamos .2nn=|w|2nabwx

Primeiro, provamos o teorema dos autômatos determinísticos de minheap e, em seguida, estendemos essa prova aos autômatos não determinísticos de minheap. Em particular, autômatos determinísticos que reconhecem alguma linguagem não se colocarão em um loop infinito, que é uma propriedade útil.

Devemos provar que o heap pode conter apenas no máximo um número de tokens de heap lineares no número de caracteres lidos na entrada. Isso exclui imediatamente que aparece um número exponencial de vezes no heap, o que completa a prova de que o não pode ser reconhecido pelos autômatos de min-heap.xEPAL

Como temos apenas um número finito de estados em nosso autômato e como um autômato determinístico não se coloca em um loop infinito, ao ler um sinal de entrada, ele adicionará no máximo um número constante de caracteres de heap no heap. Da mesma forma, ao consumir algum símbolo de heap , ele só pode adicionar no máximo um número constante de caracteres de heap estritamente maiores que e só pode diminuir o número de símbolos na pilha (caso contrário, obtemos um loop infinito).yyy

Portanto, consumir símbolos de heap pode causar um (enorme) acúmulo de símbolos de heap maiores, mas como há apenas um número constante de tipos diferentes de símbolos de heap, esse é apenas um número constante, não dependente de . Isso implica que o número de símbolos de heap é no máximo algumas vezes (grandes) constantes do número de símbolos de entrada lidos até o momento. Isso completa a prova para o caso determinístico.n

No caso não determinístico, a prova é semelhante, mas um pouco mais complicada: em vez de adicionar no máximo algum número constante de tokens de heap ao heap, ele adiciona um número arbitrário de tokens de heap ao heap. No entanto, o ponto crucial é que esse número não depende de . Em particular, se pudermos obter de maneira não determinística exatamente os símbolos de heap corretos após reconhecer (certo para reconhecer ), também poderemos escolher de forma não determinística os símbolos de heap que correspondam a alguma outra palavra e, assim, reconhece , contradizendo assim que o autômato min-heap reconhece exatamente .nwwRwwwREPAL

Atualização 3: tornarei o último argumento (sobre não determinismo) rigoroso. Pelo argumento acima, deve existir um conjunto infinito de palavraspara que para cada, após reconhecer, o heap contenha elementos( note que podemos falar sobrepois temos um conjunto infinito de palavras). Como não podemos colocar tantos elementos no heap por meios determinísticos, devemos ter algum tipo de loop no qual escolhemos, de maneira não determinística, adicionar mais elementos ao heap (sem consumir entrada) e depois optamos por sair desse loop, e devemos ter atravessado esse loopvezes.W{a,b}wWwω(|w|)O(f(|w|))ω(1)

Tomar o conjunto de todas essas ansas utilizados por . Como existem apenas estados , o tamanho deste conjunto é e o conjunto de todos os seus subconjuntos também é . Agora observe que a parte 'determinística' dos caminhos de execução só pode contribuir para dos tokens, o que significa que muito do número exponencial de palavras diferentes deve ter caminhos de execução cujas partes 'determinísticas' contribuem da mesma forma. tokens para a pilha. Em particular, a única maneira de obter mais tokens é usando os loops identificados acima.WO(1)O(1)O(1)O(|w|)

Combinando essas observações, isso significa que deve haver duas palavras distintas em , e digamos, cuja parte 'determinística' dos caminhos de execução contribui com os mesmos tokens para o heap, e que são diferenciadas ao fazer parte de um subconjunto dos loops acima um número diferente de vezes, mas que usam o mesmo subconjunto de loops (lembre-se de que existem apenas desses loops).Ww1w2O(1)

Agora podemos mostrar que também pode ser reconhecido pelo autômato min-heap: seguimos o caminho de execução de como acima, mas percorremos os loops o mesmo número de vezes que o caminho de execução de percorre. Isso preenche o min-heap com tokens, de forma que seja aceito como sufixo, completando assim a prova.w1w2w1w2w2

Atualização 2:

Apenas me ocorreu que o acima exposto significa que podemos simular um autômato de min-heap determinístico usando apenas espaço logarítmico: mantemos um contador para cada tipo de caractere na min-heap. Como mostrado acima, esse contador será no máximo e, portanto, pode ser armazenado usando apenas espaço (pois há apenas um número constante desses contadores). Isso nos dá:O(n)O(logn)

DHALL

HALNL

onde é o conjunto de idiomas reconhecidos por alguns autômatos determinísticos de min-heap.DHAL

Alex ten Brink
fonte
1
+1 para uma excelente visão, parece que você entendeu meu significado completamente. Estou certo em minha avaliação de que essas máquinas não podem reconhecer palíndromos? Como a ordem dos símbolos adicionados não é preservada, não parece possível.
precisa saber é o seguinte
@ Patrick87: Eu estou pensando sobre esse problema agora :)
Alex ten Brink
@Raphael Observação muito legal sobre máquinas de Turing com restrições de recursos logarítmicos, vocês dois fizeram um trabalho fantástico ao investigar esses autômatos. Você sabe, eu meio que joguei o autômato min-heap fora como um exemplo do que eu estava interessado, mas parece ter sido bem recebido. Que outras perguntas podem ser respondidas sobre esses autômatos? DHAL = HAL? Quais são as propriedades de fechamento do HAL? Vale a pena explorar outras explorações? Se sim, devem permanecer aqui ou ser colocadas em uma nova pergunta? Mais uma vez obrigado pelas excelentes ideias.
precisa saber é o seguinte
1
@ Rafael: Eu fiz essa parte completamente rigorosa. Você está certo de que deve ser suficientemente grande - encarei alguns detalhes à esquerda e à direita. n
Alex ten Brink
1
@ Rafael: De fato, ele faz. , então pelo teorema da hierarquia de espaço e algumas inclusões. CSL=NLINSPACEDHALCSL
Alex-Brink
19

Aqui está o que (acreditamos) sabemos:

  • HALCFL (tipo 1, tipo 2)
  • CFLHAL (tipo 1)
  • CFLHAL (tipo 2, por definição)
  • CSLHAL (tipo 1, tipo 2)

Veja detalhes e outras notas abaixo.


HALCFL

Esta parte da resposta está relacionada ao tipo 1 e ao tipo 2.

Um autômato de pilha mínima (HA) com alfabeto de pilha finito e totalmente ordenado aceita .L={anbncnnN}CSLCFL

Pressupostos: Semelhante ao PDA, nossa função de transição consome o símbolo mais importante de heap e grava de volta um número arbitrário de símbolos de heap. O heap contém inicialmente um símbolo distinto que é maior que todos os outros símbolos de heap.$

Seja um autômato de comA=(Q,ΣI,ΣH,,q0,QF)

  • Q={q0,q1,q2,qf} o conjunto de estados
  • ΣI={a,b,c} o alfabeto de entrada.
  • ΣH=a,b,$ o alfabeto da pilha com a ordem .a<b<$
  • QF={qf}
  •  (Q×ΣI×ΣH)×(Q×ΣH) com
    • (q0,a,σ)(q0,aσ) para todosσΣH
    • (q0,b,a)(q1,b)
    • (q1,b,a)(q1,b)
    • (q1,c,b)(q2,ε)
    • (q2,c,b)(q2,ε)
    • (q2,c,$)(qf,ε)

O autômato escreve um para a pilha para cada na entrada. Quando um ocorre, ele consome como muitos como tem havido , escrever um para a pilha para cada encontrados . Isso não atrapalha a contagem, porque o heap mantém convenientemente no topo. Só depois de tudo são tomadas a partir da pilha são aceito; somente depois que tantos como (e com isso ) forem encontrados, aceitará com heap vazio e estado final.aabbabbaaccbaA

Portanto, .L(A)=L


CFLHAL

Esta parte da resposta refere-se apenas ao tipo 1.

Considere o mesmo conjunto de palindromes e assumir que existe HA com .EPAL={wwRw{a,b}}AL(A)=L

Conjectura: encontramos com ede modo que esteja no mesmo estado e tenha o mesmo conteúdo de heap depois de ler e , respectivamente. Como aceita e , também aceita (e ), que é uma contradição para .w1,w2{a,b}w1w2|w1|=|w2|Aw1w2Aw1w1Rw2w2Rw1w2REPALw2w1RL(A)=EPAL


CSLHAL

Esta parte da resposta está relacionada ao tipo 1 e ao tipo 2.

O mesmo raciocínio usado em (para o tipo 1) pode ser usado para mostrar que a linguagem sensível ao contexto não está em . { w w w { a , b } } H A LEPAL{www{a,b}}HAL


HAL?CSL

Isso ainda está aberto para o tipo 1 e o tipo 2.


Factoids adicionais

O HA parece ser ortogonal a um subconjunto das linguagens levemente sensíveis ao contexto aceitas pelo Embedded Pushdown Automata : Embora o HA possa simular um número limitado de pilhas empilhadas, ele não pode simular arbitrariamente muitos (como o EPA). No entanto, o HA pode acessar os principais símbolos das pilhas que atualmente não estão na parte superior (que a EPA não pode).

Rafael
fonte
+1, excelente resposta. Essencialmente equivalente ao método de Brink, certo? Ainda assim, o rigor e a precisão são excelentes. Você pensou se essas máquinas podem aceitar todas as lâmpadas fluorescentes compactas? Parece impossível, uma vez que as informações do pedido são perdidas pela pilha ...
Patrick87 7/12
É a mesma ideia que Alex teve, sim. Ainda bem que você pode obter algo com isso, no entanto. Eu adicionei uma idéia para a outra direção, mas há uma (enorme?) Lacuna. Precisa pensar sobre isso com a cabeça limpa amanhã e talvez roubar alguns colegas.
Raphael
Sinto que deveria ter incluído uma prova de correção para ganhar créditos extras por rigor. ;) Não deve ser muito difícil por indução sobre , eu acho. n
Raphael
O esquema de prova que você rotula como uma conjectura é o que eu tinha em mente, e acho isso bastante convincente ... também, e esse é um ponto técnico menor, acho que você está usando a linguagem dos palíndromos de tamanho uniforme, nem todos palíndromos ... embora a prova certamente funcione de qualquer maneira (observe que também funciona para palíndromos simples, portanto o HAL não é tão forte quanto os DPDAs, outro resultado).
precisa saber é o seguinte
@ Patrick87 O problema é que pode haver mais configurações possíveis após a leitura de símbolos do que HA , em particular se houver permissão para -transitions que colocam símbolos na pilha. εnε
Raphael