Given a NFA $N$ and its equivalent DFA $D$ resulting from the total determinization of $N$ (using powerset construction, for example), the following properties hold for $N$, $D$ and for any word $w$ :$N$ reads $w$ in running time at most $O(|w|.|N|^2)$.$D$ reads $w$ in running time at most $O(|w|)$ and its size may be $O(2^{|N|})$ (in number of states needed to represent $D$).I wonder if there exists some partial determinization algorithm that guarantees a trade-off between the size of the result and the running time ?For example, this partial determinization algorithm could turn an NFA into a partially deterministic automata $D'$ such that $D'$ guarantees that the word $w$ is read in $O(|w|.|N|^x)$ where $0 \leq x \leq 2$ without exceeding the size $|D'| \leq 2^{f(x)}$ where $f(x)$ is a continuous decreasing function defined on the range $[0, 2]$ such that $f(0)=|N|$ and $f(2)=log |N|$.I did not find any method to partially determinize a NFA in such a way. In all papers : either determinization is avoided because the NFA is too large, either determinization is full and the NFA is turned into a DFA (with a possible exponential blowup). There is no compromise...I would really appreciate any references or any answers regarding this problem. Thank you very much, Luz.
NFA to DFA Powerset Construction : A Partial determinization algorithm with trade-off between running time and size for the resulting automata?
automata theory;regular language;nondeterminism;dfa;nfa
The paper [HP06] is in the spirit of your idea, although in a different direction, in the context of infinite words.It can be adapted more easily to finite words.In the powerset construction, we simultaneously keep track of all possible runs of the $n$-state automaton, by moving around $n$ tokens.  But we could decide to follow only $k<n$ runs, and do a partial powerset construction.In general this will yield a non-deterministic automaton, that is not really more useful than the original one.But it could be that building $k$ runs with a certain deterministic strategy is always enough to obtain an accepting one, if one exists. Think for instance of a big automaton where the only non-determinism is to guess whether the last letter is an $a$ or a $b$, and then branching towards two deterministic automata. Then two tokens suffice, and a $2$-powerset construction works, where subsets have size at most $2$, i.e. the resulting automaton has $\dfrac{n(n+1)}{2}$ states.We can define the width of a non-deterministic automaton as the number of tokens needed to deterministically build an accepting run. The powerset construction actually assumes that we are in the worst case, i.e. width equal to number of states.The case where the width is $1$ corresponds to the notion of good-for-games (GFG) automaton, introduced in [HP06], and further studied in [BKKS13,KS15].We have that a NFA has width at most $k$ if and only if its $k$-powerset construction is GFG.On finite words, it is in P to detect whether an automaton is GFG, and in this case it actually means that it is deterministic with some additional useless transitions. This means we could increment $k$ until the resulting $k$-powerset construction is GFG, prune the useless transitions, and we get a deterministic automaton. This corresponds to emphasizing space-saving, since instead of building the big deterministic automaton and then minimizing it, we try to approach it from below, hoping we won't have to do the full powerset construction.The construction in [HP06] is similar, except that even when reaching $k=n$, the automaton they build is not deterministic but GFG, which is good enough for many contexts (like synthesis).[HP06]  Solving games without determinization, Henzinger, Piterman, in CSL 2006[BKKS13]  Nondeterminism in the presence of a diverse or unknown future, Boker, Kuperberg, Kupferman, Skrzypczak, in ICALP 2013[KS15]   On Determinisation of Good-for-Games Automata, Kuperberg, Skrzypczak, in ICALP 2015