Timeline for Maximal minimal DFA for some language of n-bit strings
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 22, 2021 at 4:05 | vote | accept | ShyPerson | ||
| May 20, 2021 at 2:45 | comment | added | ShyPerson | @D.W. Many thanks again for all your help! | |
| May 19, 2021 at 22:15 | comment | added | D.W.♦ | Here's a construction that might get close to the right asymptotics: let $\Sigma=\{0,1\}^{\lg n}$; there's an isomorphism $\Sigma^{n/\lg n} \to \{0,1\}^n$; then consider the language of all words $w$ over $\Sigma^{n/\lg n}$ such that at least one $s \in \Sigma$ does not appear in $w$, i.e., $L=\{w \in \Sigma^{n/\lg n} \mid \exists s \in \Sigma . w \in (\Sigma \setminus \{s\})^{n/\lg n}\}$. Then by cs.stackexchange.com/q/3381/755, the minimal DFA for $L$ has at least $2^{n/\lg n}$ states. It's easy to see that $x \le n \cdot 2^n$ states. | |
| May 19, 2021 at 21:21 | answer | added | Yuval Filmus | timeline score: 3 | |
| May 19, 2021 at 20:55 | comment | added | D.W.♦ | That helped a ton! Thank you. | |
| May 19, 2021 at 20:54 | history | reopened |
ShyPerson D.W.♦ |
||
| May 19, 2021 at 20:54 | history | edited | D.W.♦ | CC BY-SA 4.0 |
Improve Latex and English wording.
|
| May 19, 2021 at 20:49 | comment | added | ShyPerson | @D.W. Thanks for your ongoing help and patience with this question. I've substantially rewritten the question to make things more precise. To address your specific questions: "over" is formalized by set $A$. $A$ also addresses your first two questions. Your third question is addressed by set $S$. Your final question is addressed by $min(M)$ in the notation section. Please let me know what other improvements I can make so this question can be reopened. Many thanks | |
| May 19, 2021 at 20:48 | history | edited | ShyPerson | CC BY-SA 4.0 |
Very substantial rewrite to address questions
|
| May 12, 2021 at 3:27 | review | Reopen votes | |||
| May 19, 2021 at 21:04 | |||||
| May 12, 2021 at 3:15 | history | edited | ShyPerson | CC BY-SA 4.0 |
Correction: added "all" to specify the strings covered by the automaton
|
| May 12, 2021 at 3:05 | history | edited | ShyPerson | CC BY-SA 4.0 |
Tried to address the objections.
|
| May 12, 2021 at 1:54 | history | closed | D.W.♦ | Needs details or clarity | |
| May 12, 2021 at 1:27 | history | asked | ShyPerson | CC BY-SA 4.0 |