patternMinor
Is $2^{1+\sqrt{mn}}$ an upper bound for the size of the DFA resulting from the determinisation of n DFAs of size m
Viewed 0 times
fromdfaboundthesizesqrtresultingdfasfordeterminisation
Problem
(all automata sizes are expressed in number of states in this question)
There exist NFAs of size $n$ for which the smallest DFA recognizing the same language is of size at least $2^n$.
Let $\Sigma$ be a vocabulary, and let's consider $n$ regular languages $L_i \subseteq \Sigma^*$ respectively recognized by $n$ DFAs $D_i=\{Q_i, q^0_i, F_i , \delta_i \}$ whose size are bounded by $m$.
We consider the epsilon-free NFA $N$ built by merging the $n$ DFAs such as $N=\{Q=\bigcup Q_i, q^0, F=\bigcup F_i , \delta \}$ where $\delta = \bigcup \delta_i$ with the additional constraint that $\forall \sigma \in \Sigma \, \delta(q^0, \sigma) = \{q | \delta_i(q_i^0, \sigma)=q \, \, 0 \leq i \leq n \}$ (note that in $N$ the $q^0_i$ are not anymore initial states since there is a unique initial state $q^0$).
Let $D_N$ be the DFA resulting from the powerset construction of $N$ and $D_N^M$ be the DFA resulting from the minimisation of $D_N$.
Is the size of $D_N^M$ at most $2^{1+\sqrt{mn}}$ ?
An equivalent question is : let $L \subseteq \Sigma^*$ be the language resulting from the union of the $n$ regular languages $L_i$, is the size of the smallest DFA recognizing $L$ always below $2^{1+\sqrt{mn}}$ ?
I would appreciate if possible, some papers related to this problem or a proof/counter-example.
Many thanks, Luz
There exist NFAs of size $n$ for which the smallest DFA recognizing the same language is of size at least $2^n$.
Let $\Sigma$ be a vocabulary, and let's consider $n$ regular languages $L_i \subseteq \Sigma^*$ respectively recognized by $n$ DFAs $D_i=\{Q_i, q^0_i, F_i , \delta_i \}$ whose size are bounded by $m$.
We consider the epsilon-free NFA $N$ built by merging the $n$ DFAs such as $N=\{Q=\bigcup Q_i, q^0, F=\bigcup F_i , \delta \}$ where $\delta = \bigcup \delta_i$ with the additional constraint that $\forall \sigma \in \Sigma \, \delta(q^0, \sigma) = \{q | \delta_i(q_i^0, \sigma)=q \, \, 0 \leq i \leq n \}$ (note that in $N$ the $q^0_i$ are not anymore initial states since there is a unique initial state $q^0$).
Let $D_N$ be the DFA resulting from the powerset construction of $N$ and $D_N^M$ be the DFA resulting from the minimisation of $D_N$.
Is the size of $D_N^M$ at most $2^{1+\sqrt{mn}}$ ?
An equivalent question is : let $L \subseteq \Sigma^*$ be the language resulting from the union of the $n$ regular languages $L_i$, is the size of the smallest DFA recognizing $L$ always below $2^{1+\sqrt{mn}}$ ?
I would appreciate if possible, some papers related to this problem or a proof/counter-example.
Many thanks, Luz
Solution
No. Asymptotically, the size can be as large as $\sim m^n$.
Let $p_1,\dots,p_n$ denote the $n$ largest prime numbers that are at most $m$. Let
$$L_i = \{x : x \not\equiv 0 \pmod{p_i}\},$$
where we assume the number $x$ is expressed in unary. Then $L = L_1 \cup \dots \cup L_n$ has the form
$$L = \{x : x \not\equiv 0 \pmod q\},$$
where $q = p_1 \times \dots \times p_n$.
Note that, with this construction, each $L_i$ has a DFA of size at most $m$ (in particular, of size $p_i$). However, the minimal DFA for $L$ has size $q$, which is close to $m^n$. In particular, the size of the minimal DFA for $L$ is asymptotically larger than $2^{1 + \sqrt{mn}}$ (as a function of $n$, treating $m$ as fixed).
Let $p_1,\dots,p_n$ denote the $n$ largest prime numbers that are at most $m$. Let
$$L_i = \{x : x \not\equiv 0 \pmod{p_i}\},$$
where we assume the number $x$ is expressed in unary. Then $L = L_1 \cup \dots \cup L_n$ has the form
$$L = \{x : x \not\equiv 0 \pmod q\},$$
where $q = p_1 \times \dots \times p_n$.
Note that, with this construction, each $L_i$ has a DFA of size at most $m$ (in particular, of size $p_i$). However, the minimal DFA for $L$ has size $q$, which is close to $m^n$. In particular, the size of the minimal DFA for $L$ is asymptotically larger than $2^{1 + \sqrt{mn}}$ (as a function of $n$, treating $m$ as fixed).
Context
StackExchange Computer Science Q#70415, answer score: 4
Revisions (0)
No revisions yet.