<p>In general, a DFA <span class="math-container">$P(A)$</span> resulting from the powerset construction of an <span class="math-container">$m$</span>-states NFA <span class="math-container">$A$</span> may have <span class="math-container">$2^m$</span> states, and a simple path traversing all these states is often there.</p>
<p>However, I cannot find in the literature (nor on my own) conditions under which simple paths in the <span class="math-container">$P(A)$</span> remain short, <em>i.e.</em> polynomial in <span class="math-container">$m$</span>. For example, is there any structural property of NFAs (such as low cycle rank, unambiguity, or others) which guarantees every simple path in the DFA has polynomial length?</p>
<p>And what if I look at simple paths in the <em>minimal</em> DFA recognizing <span class="math-container">$L(A)$</span>, instead of <span class="math-container">$P(A)$</span>?</p>

CC BY-SA 4.0
2024-08-08T08:54:57.800Z
There exists an $(n + 1)$-state UFA with cycle rank 1 for the language $1\Sigma^{n-1}$. This language always has a simple path of length $2^n$ (given by an order $n$ de Bruijn sequence) in any corresponding DFA, constructed using the powerset construction or otherwise.
1001
CC BY-SA 4.0
2024-08-08T15:12:50.790Z
Thanks! Maybe I don't get your example. For the language $1\Sigma^{n-1}$, why is a DFA with $n+1$ states not enough?
Nicola Gigante
CC BY-SA 4.0
2024-08-09T17:26:59.277Z
Sorry, I meant $\Sigma^*1\Sigma^{n-1}$ in which case you need to keep track of the last $n$ characters.
1001
CC BY-SA 4.0
2024-08-09T20:21:20.203Z
Thanks, this makes perfect sense now!
Nicola Gigante
<reference-request><automata-theory>
Bounds on the length of simple paths in DFAs resulting from the powerset construction of an NFA
Nicola Gigante
# Bounds on the length of simple paths in DFAs resulting from the powerset construction of an NFA

(Asked by: username_0 on 2024-08-06)

In general, a DFA $P(A)$ resulting from the powerset construction of an $m$-states NFA $A$ may have $2^m$ states, and a simple path traversing all these states is often there.

However, I cannot find in the literature (nor on my own) conditions under which simple paths in the $P(A)$ remain short, *i.e.* polynomial in $m$. For example, is there any structural property of NFAs (such as low cycle rank, unambiguity, or others) which guarantees every simple path in the DFA has polynomial length?

And what if I look at simple paths in the *minimal* DFA recognizing $L(A)$, instead of $P(A)$?

**Tags:** reference-request, automata-theory

> **Comments:**
> **username_1**: There exists an $(n + 1)$-state UFA with cycle rank 1 for the language $1\Sigma^{n-1}$. This language always has a simple path of length $2^n$ (given by an order $n$ de Bruijn sequence) in any corresponding DFA, constructed using the powerset construction or otherwise.  
> **username_0**: Thanks! Maybe I don't get your example. For the language $1\Sigma^{n-1}$, why is a DFA with $n+1$ states not enough?  
> **username_1**: Sorry, I meant $\Sigma^*1\Sigma^{n-1}$ in which case you need to keep track of the last $n$ characters.  
> **username_0**: Thanks, this makes perfect sense now!  

---

## 0 answers

