Construção do Powerset de NFA para DFA: um algoritmo de determinação parcial com compromisso entre tempo de execução e tamanho dos autômatos resultantes?

Dado um NFA $N$ e seu equivalente DFA $D$ resultante da determinação total de $N$ (usando a construção do conjunto de potências, por exemplo), as seguintes propriedades são válidas para $N$ , $D$ e para qualquer palavra $w$ :

$N$ lê $w$ em tempo de execução, no máximo, $O(|w|.|N|^2)$ .
$D$ lê $w$ em tempo de execução no máximo $O(|w|)$ e seu tamanho pode ser $O(2^{|N|})$ (no número de estados necessários para representar $D$ ).

Gostaria de saber se existe algum algoritmo de determinação parcial que garanta uma troca entre o tamanho do resultado e o tempo de execução?

Por exemplo, esse algoritmo de determinação parcial pode transformar um NFA em um autômato parcialmente determinístico $D'$ modo que $D'$ garanta que a palavra $w$ seja lida em $O(|w|.|N|^x)$ que $0 \leq x \leq 2$ sem exceder a tamanho $|D'| \leq 2^{f(x)}$ que $f(x)$ é uma função decrescente contínua definida na faixa $[0, 2]$ tal que $f(0)=|N|$ e $f(2)=log |N|$ .

Não encontrei nenhum método para determinar parcialmente um NFA dessa maneira. Em todos os trabalhos: qualquer determinação é evitada porque o NFA é muito grande, a determinação está cheia e o NFA é transformado em um DFA (com uma possível explosão exponencial). Não há compromisso ...

Eu realmente aprecio quaisquer referências ou respostas sobre esse problema. Muito obrigado, Luz.

automata-theory regular-language nondeterminism dfa nfa Luz
fonte

Cstheory.stackexchange.com/a/1273/236 é útil?

Radu GRIGORE

Uau :-) isso é incrível! De fato, o post cstheory.stackexchange.com/questions/1132/… parece fazer o trabalho. Muito obrigado, eu vou processar a resposta D. Eppstein ...

Luz

Respostas:

O artigo [HP06] está no espírito da sua ideia, embora em uma direção diferente, no contexto de palavras infinitas. Pode ser adaptado mais facilmente a palavras finitas.

$n$ $n$ $k<n$

$k$ $a$ $b$ $2$ $2$ $\dfrac{n(n+1)}{2}$

$1$

$k$ $k$ $k$ $k$

[HP06] Resolvendo jogos sem determinação , Henzinger, Piterman, na CSL 2006

[BKKS13] Não determinismo na presença de um futuro diverso ou desconhecido , Boker, Kuperberg, Kupferman, Skrzypczak, na ICALP 2013

[KS15] Sobre a determinação de autômatos para jogos , Kuperberg, Skrzypczak, na ICALP 2015

Denis
fonte

Muito obrigado pelo seu post :-) mas preciso de um pouco mais de ajuda para entender o panorama geral do que você propõe. Também quero entender as principais diferenças entre o seu post e o de D. Eppstein (conforme sugerido no comentário superior), aqui: cstheory.stackexchange.com/questions/1132/… .

Luz

n

$n$

1 \leq x \leq n

$1 \leq x \leq n$

w

$w$

O (w . x^{2})

$O(w.x^2)$

O (x^{2} {.2}^{n / x})

$O(x^2.2^{n/x})$

k

$k$

N

$N$

n

$n$

S = O (\sum_{i = 0}^{k} (\binom{n}{i}))

$S=O(\sum\limits_{i=0}^{k}{{n}\choose{i}})$

k

$k$

N

$N$

T = O (w . k)

$T=O(w.k)$

N

$N$

Pergunta adicional se as duas hipóteses anteriores são verdadeiras. Imagine um caso de uso em que o espaço disponível para determinar seja fixo, de modo que com . Em seguida, determinamos parcialmente em aplicando a construção poweret em (já que há espaço suficiente para isso). É a duração máxima necessária para simular ?

S

$S$

N

$N$

S = O (\sum_{i = 0}^{p} (\binom{n}{i}))

$S=O(\sum\limits_{i=0}^{p}{{n}\choose{i}})$

p \leq k

$p \leq k$

N

$N$

N^{'}

$N'$

p

$p$

N

$N$

O (w . (k / p))

$O(w.(k/p))$

N^{'}

$N'$

Luz

(1) Sim (2) não sabe ao certo o que você quer dizer com "simular", mas é possível mover deterministicamente k tokens em N para ver se uma palavra é aceita, então eu diria que sim (3) Sim, com um teto no k / p

Denis