Com que rapidez podemos decidir se um DFA é mínimo?

Minimizando autómatos finitos determinista (AFDs) é um problema que tem sido bem estudada na literatura, e vários algoritmos foram propostos para resolver o seguinte problema: Dado um DFA , calcular um mínimo DFA correspondente aceite a mesma linguagem como . A maioria desses algoritmos é executada em tempo polinomial. $\mathscr{A}$ $\mathscr{A}$

No entanto, gostaria de saber se a variante de decisão desse problema - "dado um DFA , é mínimo?" - pode ser resolvido com mais eficiência do que realmente computando o autômato mínimo. Obviamente, isso também pode ser feito com eficiência, executando, por exemplo, o algoritmo de refinamento de partição de Hopcroft e depois decidindo se todas as partições contêm exatamente um estado. $\mathscr{A}$ $\mathscr{A}$

Como Yuval Filmus sugere em sua resposta , a variante de decidibilidade pode ser resolvida mais rapidamente, possivelmente usando os algoritmos padrão. Infelizmente, não consigo ver como (espero não estar perdendo um ponto óbvio aqui).

Yuval aponta nos comentários aqui que os algoritmos mais conhecidos (como o acima) são executados no tempo para alfabetos de tamanho constante. Portanto, não estou interessado apenas em ganhos assintoticamente significativos em tempo de execução, pois eles parecem bastante improváveis. O que mais me incomoda é que não consigo imaginar nenhum "atalho" que possa ser extraído do fato de estarmos interessados apenas em uma resposta do tipo sim-não-resposta - nem mesmo um atalho que permita economizar uma quantidade de tempo assintoticamente desprezível. Eu sinto que todo algoritmo sensato que decide a minimalidade de um DFA precisaria realmente minimizar o DFA e ver se alguma coisa muda durante o processo. $\mathcal{O}(n \log n)$

algorithms formal-languages finite-automata Cornelius Brand
fonte

O algoritmo de Hopcroft já é executado em tempo quaseilinear, portanto não há muito espaço para melhorias.

Yuval Filmus

Sim, editei minha pergunta para que ela refletisse esse fato. @YuvalFilmus

Cornelius Brand

Acredito que o algoritmo de minimização do DFA mais rápido conhecido ainda seja este . É mais rápido do que qualquer algoritmo publicado antes de 2008, executando em

, em que

é o número de transições.

O (n + m \log n)

$O(n+m \log n)$

m

$m$

Juho

me parece improvável que o problema de decisão seja equivalente em complexidade ao problema de minimização, o primeiro parece possivelmente mais difícil porque envolve testar a equivalência do DFA que não é trivial. portanto, parece que a complexidade do problema de decisão é o máximo de "testes de minimização ou equivalência". e qual é a complexidade do teste de equivalência?

vzn 03/03

@vzn Supondo que você quis dizer "[...] que não é trivial": não precisa necessariamente, pois, por exemplo, o procedimento que dei na minha pergunta evita o teste de equivalência. No entanto, também acho que o problema não é mais fácil do que minimizar.

Marca Cornelius

Pode não ser exatamente o tipo de resposta que você está procurando, mas desde que você perguntou sobre problemas de decisão, pensei que você poderia estar interessado na complexidade do problema. É -completo. $\mathsf{NL}$

Agora, o que significa para um DFA ser mínimo? Existem duas propriedades:

Cada estado é alcançável: $\forall q \in Q \; \exists w \in \Sigma^*$ $q$ $s$ $w$ $s \rightarrow_w q$
$\forall q,r \in Q$ $q \neq r$ $\exists w \in \Sigma^*$ $q \rightarrow_w s$ $r \rightarrow_w t$ $|\{s,t\} \cap F| = 1$ $s,t$

$x \rightarrow_w y$ $\mathsf{L}$ $w$ $\forall$ $\exists$ $\mathsf{NL}$

$\mathsf{NL}$ $s$ $t$ $\mathsf{NL}$

$\mathsf{NL} \subseteq \mathsf{L}^2$ $n$

Artem Kaznatcheev
fonte

isso parece melhorar o espaço, mas não a complexidade do tempo?

vzn

Eu concordo com o vzn. Embora eu goste desta resposta, ainda estou interessado em idéias que estão mais intimamente relacionadas à pergunta original.

Cornelius Marca

N L

$\mathsf{NL}$

P

$\mathsf{P}$

Com que rapidez podemos decidir se um DFA é mínimo?

Respostas: