<p>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.</p>

<p>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&lt;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.</p>

<p>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.</p>

<p>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].</p>

<p>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.</p>

<p>[HP06]  <a href="https://link.springer.com/chapter/10.1007/11874683_26#page-1" rel="nofollow noreferrer">Solving games without determinization</a>, Henzinger, Piterman, in CSL 2006</p>

<p>[BKKS13]  <a href="http://perso.ens-lyon.fr/denis.kuperberg/papers/ICALP13long.pdf" rel="nofollow noreferrer">Nondeterminism in the presence of a diverse or unknown future</a>, Boker, Kuperberg, Kupferman, Skrzypczak, in ICALP 2013</p>

<p>[KS15]   <a href="http://perso.ens-lyon.fr/denis.kuperberg/papers/GFGlong.pdf" rel="nofollow noreferrer">On Determinisation of Good-for-Games Automata</a>, Kuperberg, Skrzypczak, in ICALP 2015</p>

CC BY-SA 3.0
2017-04-19T16:54:33.003Z
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 : https://cstheory.stackexchange.com/questions/1132/are-there-small-machines-which-can-efficiently-match-regular-expressions/1273#1273 .
Luz
CC BY-SA 3.0
2017-04-19T16:54:57.350Z
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).
Luz
CC BY-SA 3.0
2017-04-19T16:56:00.817Z
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$ ?
Luz
CC BY-SA 3.0
2017-04-19T16:59:14.907Z
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'$ ?
Luz
CC BY-SA 3.0
2017-04-19T20:46:26.447Z
(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
Denis
CC BY-SA 3.0
2017-04-19T20:52:01.797Z
Maybe not the correct term, but I was using "simulate" as "reading a word" of size $w$.
Luz
CC BY-SA 3.0
2017-04-19T22:05:54.977Z
If I try to sum it up : putting all together to compare your proposition with the one of D. Eppstein. Let's consider a NFA of size $n$, $1 \leq x \leq n$ and a word of size $w$. Am I correct in saying that : (1) D.E. method guarantees a trade-off between a running time of $O(w.\lceil\frac{n}{x}\rceil^2)$ and a size of $O(\lceil\frac{n}{x}\rceil^2.2^x)$ ? And (2) the trade-off in your method is a running time of $O(w.\lceil\frac{n}{x}\rceil)$ and a size of $O(\sum\limits_{i=0}^{x} {{n}\choose{i}})$ ?
Luz
CC BY-SA 3.0
2017-04-19T22:10:43.380Z
I have still a little doubt about the $\lceil\frac{n}{x}\rceil$ factor... Shouldn't be rather $\lceil\frac{n}{x}\rceil^2$ since there can be a quadratic number of transitions between the $\lceil\frac{n}{x}\rceil$ states considered at each step of a run on the word of size $w$ ? Leading the running time of your method to $O(w.\lceil\frac{n}{x}\rceil^2)$ ?
Luz
CC BY-SA 3.0
2017-04-20T00:23:06.970Z
The point is that the width $k'$ of the $x$-powerset automaton is $\lceil\frac{k}{x}\rceil$. So if the running time is $O(wk')$, we get $O(w\lceil\frac{k}{x}\rceil)$. However if you want to compare it fairly to D.E.'s method, you would need to count the space used for storing the strategy resolving the nondeterminism in order to be able to run the automaton. This would give a total space of $O(\sum_{i=1}^k {n\choose i})$ where $k$ is the width of the original automaton. So might as well do the $k$-determinization, not much interest in doing it partially if you count the strategy storage.
Denis
CC BY-SA 3.0
2017-04-19T15:00:47.697Z
2017-09-27T14:38:07.080Z
2017-09-27T14:38:07.080Z
Denis
<p>Given a NFA $N$ and its equivalent DFA $D$ resulting from the <strong>total determinization</strong> of $N$ (using powerset construction, for example), the following properties hold for $N$, $D$ and for any word $w$ :</p>

<ul>
<li>$N$ reads $w$ in running time at most $O(|w|.|N|^2)$.</li>
<li>$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$).</li>
</ul>

<p>I wonder if there exists some <strong>partial determinization</strong> algorithm that guarantees a trade-off between the size of the result and the running time ?</p>

<p>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|$.</p>

<p>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...</p>

<p>I would really appreciate any references or any answers regarding this problem. Thank you very much, Luz.</p>

CC BY-SA 3.0
2017-04-19T14:31:13.520Z
Is https://cstheory.stackexchange.com/a/1273/236 useful?
Radu GRIGore
CC BY-SA 3.0
2017-04-19T14:41:17.960Z
Wow :-) this is awesome ! Indeed, the post https://cstheory.stackexchange.com/questions/1132/are-there-small-machines-which-can-efficiently-match-regular-expressions/1273#1273 seems to do the job. Thank you very much, I'm going to process the D. Eppstein answer...
Luz
<automata-theory><regular-language><nondeterminism><dfa><nfa>
NFA to DFA Powerset Construction : A Partial determinization algorithm with trade-off between running time and size for the resulting automata?
Luz
# NFA to DFA Powerset Construction : A Partial determinization algorithm with trade-off between running time and size for the resulting automata?

(Asked by: username_0 on 2017-04-19)

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.

**Tags:** automata-theory, regular-language, nondeterminism, dfa, nfa
> **Comments:**
> **username_1**: Is https://cstheory.stackexchange.com/a/1273/236 useful?  
> **username_0**: Wow :-) this is awesome ! Indeed, the post https://cstheory.stackexchange.com/questions/1132/are-there-small-machines-which-can-efficiently-match-regular-expressions/1273#1273 seems to do the job. Thank you very much, I'm going to process the D. Eppstein answer...  

---

## 1 answers

### Answer by username_2 on 2017-04-19. Score: 6 | Accepted answer

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

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](https://link.springer.com/chapter/10.1007/11874683_26#page-1), Henzinger, Piterman, in CSL 2006

[BKKS13] [Nondeterminism in the presence of a diverse or unknown future](http://perso.ens-lyon.fr/denis.kuperberg/papers/ICALP13long.pdf), Boker, Kuperberg, Kupferman, Skrzypczak, in ICALP 2013

[KS15] [On Determinisation of Good-for-Games Automata](http://perso.ens-lyon.fr/denis.kuperberg/papers/GFGlong.pdf), Kuperberg, Skrzypczak, in ICALP 2015

> **Comments:**
> **username_0**: 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 : https://cstheory.stackexchange.com/questions/1132/are-there-small-machines-which-can-efficiently-match-regular-expressions/1273#1273 .  
> **username_0**: 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).  
> **username_0**: 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$ ?  
> **username_0**: 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'$ ?  
> **username_2**: (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  
> **username_0**: Maybe not the correct term, but I was using "simulate" as "reading a word" of size $w$.  
> **username_0**: If I try to sum it up : putting all together to compare your proposition with the one of D. Eppstein. Let's consider a NFA of size $n$, $1 \leq x \leq n$ and a word of size $w$. Am I correct in saying that : (1) D.E. method guarantees a trade-off between a running time of $O(w.\lceil\frac{n}{x}\rceil^2)$ and a size of $O(\lceil\frac{n}{x}\rceil^2.2^x)$ ? And (2) the trade-off in your method is a running time of $O(w.\lceil\frac{n}{x}\rceil)$ and a size of $O(\sum\limits_{i=0}^{x} {{n}\choose{i}})$ ?  
> **username_0**: I have still a little doubt about the $\lceil\frac{n}{x}\rceil$ factor... Shouldn't be rather $\lceil\frac{n}{x}\rceil^2$ since there can be a quadratic number of transitions between the $\lceil\frac{n}{x}\rceil$ states considered at each step of a run on the word of size $w$ ? Leading the running time of your method to $O(w.\lceil\frac{n}{x}\rceil^2)$ ?  
> **username_2**: The point is that the width $k'$ of the $x$-powerset automaton is $\lceil\frac{k}{x}\rceil$. So if the running time is $O(wk')$, we get $O(w\lceil\frac{k}{x}\rceil)$. However if you want to compare it fairly to D.E.'s method, you would need to count the space used for storing the strategy resolving the nondeterminism in order to be able to run the automaton. This would give a total space of $O(\sum_{i=1}^k {n\choose i})$ where $k$ is the width of the original automaton. So might as well do the $k$-determinization, not much interest in doing it partially if you count the strategy storage.  

---

