8
$\begingroup$

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.

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
6
$\begingroup$

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.

[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

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ Thanks a lot for your post :-) but I need a bit more help to understand the big picture of what you propose. I also want to understand the main differences between your post and the one of D. Eppstein (as suggested in the upper comment), here : cstheory.stackexchange.com/questions/1132/… . $\endgroup$
    – Luz
    Apr 19, 2017 at 16:54
  • 1
    $\begingroup$ If I sum up the D.E. (D. Eppstein) method : Given a NFA of size $n$, $1 \leq x \leq n$ and a word of size $w$, D.E. method guarantees a trade-off between a NFA simulation time of $O(w.x^2)$ and a size of $O(x^2.2^{n/x})$ for storing the data structure representing the NFA (though this data structure is not a NFA, it is an array). $\endgroup$
    – Luz
    Apr 19, 2017 at 16:54
  • 1
    $\begingroup$ There are my questions. Given a $k$-width NFA $N$ of size $n$, (1) Is $S=O(\sum\limits_{i=0}^{k}{{n}\choose{i}})$ the maximum size of the DFA resulting from the $k$-powerset construction applied on $N$ ? And (2) is $T=O(w.k)$ the maximum time needed to simulate $N$ ? $\endgroup$
    – Luz
    Apr 19, 2017 at 16:56
  • 1
    $\begingroup$ Additional question if the both previous hypothesis are true. Imagine a usecase where the available space $S$ to determinize $N$ is fixed such that $S=O(\sum\limits_{i=0}^{p}{{n}\choose{i}})$ with $p \leq k$. Then we partially determinize $N$ into $N'$ by applying the $p$-powerset construction on $N$ (since there is enough space to do so). Is $O(w.(k/p))$ the maximum time needed to simulate $N'$ ? $\endgroup$
    – Luz
    Apr 19, 2017 at 16:59
  • $\begingroup$ (1) Yes (2) not sure what you mean by "simulate", but you can deterministically move k tokens in N to see if a word is accepted, so I would say yes (3) Yes, with a ceiling on the k/p $\endgroup$
    – Denis
    Apr 19, 2017 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.