Intersection DFA dans l'espace sub-quadratique?

L'intersection de deux DFA (minimes) avec n états peut être calculée en utilisant O (n ² ) temps et espace. Ceci est optimal en général, car le DFA résultant (minimal) peut avoir n ² états. Cependant, si le DFA minimal résultant a z états, où z = O (n), peut-il être calculé dans l'espace n ^2-eps , pour un eps constant> 0? Je serais intéressé par un tel résultat même pour le cas spécial où les DFA d'entrée sont acycliques.

La réponse est oui sans aucune exigence sur la taille de l'automate. Il peut être calculé dans l' espace $O(\log^2 n)$ même pour $k$ DFA où $k$ est une constante.

Soit ( i ∈ [ k ] ) soient k DFA. Nous montrons que, compte tenu ⟨ A 1 , ... , A k ⟩ , le calcul du DFA minimal reconnaissant L ( A 1 ) ∩ ⋯ ∩ L ( A k ) peut être fait en $A_i = (Q_i, \Sigma_i, \delta_i, z_i, F_i)$$i \in [k])$$k$$\langle A_1, \ldots, A_k \rangle$$\text{L}(A_1) \cap \cdots \cap\text{L}(A_k)$ espace. Nous prouvons d'abord quelques résultats techniques.$O(\log^2 n)$

Définition 1 : Soit deux états puis q ≡ r ssi ∀ w ∈ Σ ∗ , q . w ∈ F ⇔ r . w ∈ $q, r$$q \equiv r$$\forall w \in \Sigma^*$$q . w \in F \Leftrightarrow r . w \in F$

Nous considérons maintenant l'automate donné par la construction classique du produit cartésien. Que q = ( q 1 , ... , q k ) et r = ( r 1 , ... , r k ) soit des états de A .$A$$q = (q_1, \ldots, q_k)$$r = (r_1, \ldots, r_k)$$A$

Lemme 1 : Décider si est en NL.$q \equiv r$

Preuve (esquisse): Nous montrons que le test de l'inéquivalence est en NL et utilisons NL = coNL. Devinez un mot (une lettre à la fois) tel que q . w est un état final et r . w ne l'est pas. Ceci peut être réalisé en calculant q i . w , r i . w dans l'espace logarithmique pour i ∈ [ k ] et en utilisant le fait que q est final ssi q i ∈ F $w \in \Sigma^*$$q . w$$r . w$$q_i . w, r_i . w$$i \in [k]$$q$ . On peut montrer que q ≢ r implique l'existence d'un w de poly-taille.$q_i \in F_i \, \forall i \in [k]$$q \not\equiv r$$w$

Lemme 2 : Décider si est (in) accessible est en NL.$q$

Preuve (esquisse): devinez (poly-taille) les chemins de à q i ( i ∈ [ k ] ).$z_i$$q_i$$i \in [k]$

Définition 2 : Considérons les états de dans l'ordre lexicographique. Définissez s ( 1 ) comme étant le premier état accessible et s ( i ) le premier état accessible suivant s ( i - 1 ) qui n'est équivalent à aucun état précédent. Nous définissons c ( q ) comme l'unique i tel que q ≡ s ( i ) .$A$$s(1)$$s(i)$$s(i-1)$$c(q)$$i$$q \equiv s(i)$

Lemme 3 : peut être calculé dans l' espace O ( log 2 n ) .$s(i)$$O(\log^2 n)$

Preuve (esquisse): la définition 2 donne un algorithme. Nous utilisons compteurs pour parcourir les états. Soit j ← 0 et q l'état actuel. À chaque état, nous utilisons le lemme 2 pour vérifier si q est accessible. Si c'est le cas, nous bouclons sur tous les états précédents et nous vérifions si l'un d'eux est équivalent à q . S'il n'y en a pas, on incrémente j et on sort q si j = i . Sinon, nous stockons q comme étant s ( j ) et nous continuons. Étant donné que nous ne stockons qu'un nombre constant de compteurs et que nos tests peuvent être effectués en $k$$j \leftarrow 0$$q$$q$$q$$j$$q$$j = i$$q$$s(j)$ , ceci complète la preuve.$\text{NL} \subseteq \text{DSPACE}(\log^2 n)$

Corollaire 1 : peut être calculé dans l' espace O ( log 2 n ) .$c(q)$$O(\log^2 n)$

Théorème : La minimisation de peut être effectuée dans l' espace O ( log 2 n ) .$A$$O(\log^2 n)$

Preuve (esquisse): Soit être le plus grand i tel que s ( i ) soit défini (c'est-à-dire le nombre de classes de ≡ ). Nous donnons un algorithme produisant un automate A ′ = ( Q ′ , Σ , δ ′ , z ′ , F ′ ) où$1 \leq m \leq |Q_0| \cdots |Q_1|$$i$$s(i)$$\equiv$$A' = (Q', \Sigma, \delta', z', F')$

• ;$Q' = \lbrace s(i) : i \in [m] \rbrace$
• ;$F' = \lbrace q \in Q' : q_i \in F_i \, \forall i \in [k] \rbrace$
• où q = ( z 0 , … , z k ) .$z' = s(c(q))$$q = (z_0, \ldots, z_k)$

Nous montrons maintenant comment calculer . Pour chaque i ∈ [ m ] , a ∈ Σ , calculez q ← s ( i ) . a et sortir la transition ( s ( i ) , a , s ( c ( q ) ) ) . Par le lemme 3 et le corollaire 1, cet algorithme s'exécute dans l' espace O ( log 2 n ) . On peut vérifier que A $\delta'$$i \in [m], a \in \Sigma$$q \leftarrow s(i) . a$$\left(s(i), a, s(c(q))\right)$$O(\log^2 n)$$A'$est minimale et .$\text{L}(A') = \text{L}(A)$

Dick Lipton et ses collègues ont récemment travaillé sur ce problème, et Lipton en a parlé ici:

http://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/

It appears that doing better than O(n^2) is open even for the very-special case of determining if the DFA intersection defines the empty language.
The paper gives complexity consequences that would result from a much-improved algorithm handling not just 2 DFAs in the intersection, but larger numbers as well.

Si vous disposez de k DFA (k fait partie de l'entrée) et que vous souhaitez savoir si leur intersection est vide, ce problème est PSPACE-complete en général:

Dexter Kozen: limites inférieures pour les systèmes de preuve naturels FOCS 1977: 254-266

Peut-être que si vous étudiez attentivement cette preuve (et les constructions similaires de Lipton et de ses co-auteurs), vous pourriez trouver une sorte d'espace limite inférieure même pour k fixe.

Given two automata $A$, $B$ accepting finite languages (acyclic automata), the state complexity of $L(A) \cap L(B)$ is in $\Theta(|A| \cdot |B|)$ (1). This result also holds for unary DFAs (not necessarily acyclic) (2). However, you seem to be talking about the space required to compute the intersection of two automata. I don't see how the classic construction using the Cartesian product uses $O(n^2)$ space. All you need is a constant number of counters of logarithmic size. When you compute the transition function for the new state $(q,r)$ you only have to scan the input without looking to any previously generated data.

Perhaps you want to output the minimal automaton? If this is the case, then I have no clue whether it can be achieved. The state complexity of the intersection for finite languages doesn't seem encouraging. However, unary DFAs have the same state complexity and I think it can be achieved with such automata. By using results from (2), you can get the exact size of the automaton recognizing the intersection. This size is described by the length of the tail and the cycle, thus the transition function can be easily computed with very few space since the structure is entirely described by those two sizes. Then, all you have to do is to generate the set of final states. Let $n$ be the number of states in the resulting automaton, then for all $1 \leq i \leq n$, state $i$ est un état final ssi $a^i$ est accepté par les deux $A$ et $B$. Ce test peut être effectué avec peu d'espace.