DFA intersection in subquadratic space? The intersection of two (minimal) DFAs with n states can be computed using O(n2) time and space. This is optimal in general, since the resulting (minimal) DFA may have n2 states. However, if the resulting minimal DFA has z states, where z=O(n), can it be computed in space n2-eps, for some constant eps>0? I would be interested in such a result even for the special case where the input DFAs are acyclic.
The answer is yes without any requirement on the size of the automaton. It can be computed in $O(\log^2 n)$ space even for $k$ DFAs where $k$ is a constant.

Let $A_i = (Q_i, \Sigma_i, \delta_i, z_i, F_i)$  ($i \in [k])$ be $k$ DFAs. We show that, given $\langle A_1, \ldots, A_k \rangle$, computing the minimal DFA recognizing $\text{L}(A_1) \cap \cdots \cap\text{L}(A_k)$ can be done in $O(\log^2 n)$ space. We first prove some technical results.

Definition 1: Let $q, r$ be two states then $q \equiv r$ iff $\forall w \in \Sigma^*$, $q . w \in F \Leftrightarrow r . w \in F$ 

We now consider the automaton $A$ given by the classical cartesian product construction. Let $q = (q_1, \ldots, q_k)$ and $r = (r_1, \ldots, r_k)$ be states of $A$.

Lemma 1: Deciding whether $q \equiv r$ is in NL.

Proof (sketch): We show that testing inequivalence is in NL and use NL = coNL. Guess a word $w \in \Sigma^*$ (one letter at the time) such that $q . w$ is a final state and $r . w$ isn't. This can be achieved by computing $q_i . w, r_i . w$ in log-space for $i \in [k]$ and using the fact that $q$ is final iff $q_i \in F_i \, \forall i \in [k]$. It can be shown that $q \not\equiv r$ implies the existence of a $w$ of poly-size.

Lemma 2: Deciding whether $q$ is (in)accessible is in NL.

Proof (sketch): Guess (poly-size) paths from $z_i$ to $q_i$ ($i \in [k]$).

Definition 2: Consider the states of $A$ in lexicographical order. Define $s(1)$ as being the first accessible state and $s(i)$ the first accessible state following $s(i-1)$ which isn't equivalent to any previous state. We define $c(q)$ as the unique $i$ such that $q \equiv s(i)$.

Lemma 3: $s(i)$ can be computed in $O(\log^2 n)$ space.

Proof (sketch): Definition 2 yields an algorithm. We use $k$ counters to iterate over the states. Let $j \leftarrow 0$ and $q$ be the current state. At each state, we use lemma 2 to verify if $q$ is accessible. If it is, we loop on every previous states and we verify if any of them is equivalent to $q$. If there isn't any, we increment $j$ and output $q$ if $j = i$. Otherwise, we store $q$ as being $s(j)$ and we continue. Since we only store a constant number of counters and our tests can be carried out in $\text{NL} \subseteq \text{DSPACE}(\log^2 n)$, this completes the proof.

Corollary 1: $c(q)$ can be computed in $O(\log^2 n)$ space.

Theorem: Minimizing $A$ can be done in $O(\log^2 n)$ space.

Proof (sketch): Let $1 \leq m \leq |Q_0| \cdots |Q_1|$ be the largest $i$ such that $s(i)$ is defined (ie. the number of classes of $\equiv$). We give an algorithm outputting an automaton $A' = (Q', \Sigma, \delta', z', F')$ where


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


We now show how to compute $\delta'$. For every $i \in [m], a \in \Sigma$, compute $q \leftarrow s(i) . a$ and output the transition $\left(s(i), a, s(c(q))\right)$. By lemma 3 and corollary 1, this algorithm runs in $O(\log^2 n)$ space. It can be checked that $A'$ is minimal and $\text{L}(A') = \text{L}(A)$.