Skip to main content
8 votes
Accepted

Error in Robson's proof about separating strings?

Converting my comment to an answer: This is taken care of in the paragraph just before Theorem 1. If the accepting state is reached at some $v_j$, then we necessarily have $j>i$, and we can compose ...
Tassle's user avatar
  • 881
5 votes

Relationship between size of Boolean functions and DFAs

Complementing the other answers, here are a few research papers that explicitly study the size of (one-way) DFAs that represent Boolean functions in the way the OP describes. Maximum and average state ...
Hermann Gruber's user avatar
5 votes

Relationship between size of Boolean functions and DFAs

Regarding question 3: There are $S^{2S} \cdot 2^S$ different DFAs on $S$ states (fixing the initial state), and so most Boolean functions require $\Omega(2^n/n)$ states. This is the same calculation ...
Yuval Filmus's user avatar
  • 14.5k
5 votes

Relationship between size of Boolean functions and DFAs

Here are are my attempts to answer. I'm not an expert on this subject. Please check all details for yourself. No. Consider $f$ defined by $f(x)=1$ iff $x_1 \ne x_{n/2+1}$ or $x_2 \ne x_{n/2+2}$ or ...
D.W.'s user avatar
  • 12.2k
2 votes
Accepted

What is the current state of the art on exact identification of DFAs with a maximum N states

The last step of the proposed reasoning can be done as described in https://cs.stackexchange.com/questions/48136/testing-two-dfas-generate-the-same-language-by-trying-all-strings-upto-a-certain and in ...
EXPTIME-complete's user avatar
1 vote
Accepted

Counting the different subsets of nodes seen when iterating a subset through a directed graph

The argument in Chrobak’s paper can be applied to this problem as well, with the same bounds. Let $\{D_i:i<k\}$ be the set of strongly connected components of $G$ that contain a cycle (i.e., other ...
Emil Jeřábek's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible