Skip to main content
10 votes
Accepted

Can we efficiently enumerate the words accepted by a DFA by order of increasing weight?

EDIT: Added Lemma 2 which covers all cases asked about. Lemma 1. Given a DFA with alphabet $\{0,1\}$ and an integer $n$, it is possible to enumerate all length-$n$ words in the language of the DFA, ...
Neal Young's user avatar
  • 10.8k
9 votes
Accepted

Is DFA language inclusion decidable in quasi-linear time?

EDIT: the question has an answer by Michael Wehar. A better than quadratic running time contradicts the strong exponential time hypothesis. https://cstheory.stackexchange.com/a/29166/2367 ORIGINAL ...
Hermann Gruber's user avatar
8 votes
Accepted

Number of minimal DFAs of size at most $m$?

According to Ishigami Y., Tani S. (1993) The VC-dimension of finite automata with $n$ states, http://link.springer.com/chapter/10.1007/3-540-57370-4_58 , the VC-dimension of the concept class of $n$-...
Aryeh's user avatar
  • 10.6k
8 votes

Is there a well-defined division operation on finite automata?

Take a look at this MFCS 2013 paper, which studies compositionality in automata. Perhaps it will help.
Shaull's user avatar
  • 5,656
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
7 votes
Accepted

Complexity of DFA intersection in this specific case?

The precise bound is $2^n$. The lower bound was given in the comments: the state complexity of $A^*a_1A^* \cap \dotsm \cap A^*a_nA^*$ is $2^n$. For the upper bound, it suffices to observe that if $B$ ...
J.-E. Pin's user avatar
  • 4,841
6 votes
Accepted

Bounds on this Strategy for Separating Words

The second section of Robson's "Separating strings with small automata" proves $F(n) = O((n \log n)^{1/2})$. The string sequence $(10^n)^n$ gives a lower bound of $\Omega(n^{1/2})$. If the ...
acupoftea's user avatar
  • 176
6 votes
Accepted

Separating words with random DFAs

It appears, via code, that if you take a random string $x$ and then form $y$ by flipping only the first bit of $x$, then a random DFA on $n/5$ states fails to separate $x,y$ with high probability. So, ...
mathworker21's user avatar
6 votes

NFA to 2DFA: what are the upper and lower bounds?

The recent survey Two-Way Finite Automata: Old and Recent Results by Pighizzini states in the introduction: The costs of the simulations of 1NFAs by 2DFAs and of 2NFAs by 2DFAs are still unknown. ...
Hermann Gruber's user avatar
6 votes
Accepted

NFA to DFA Powerset Construction : A Partial determinization algorithm with trade-off between running time and size for the resulting automata?

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 ...
Denis's user avatar
  • 8,903
5 votes
Accepted

Automata : Language Containment, Minimality & Graph Homomorphism

For inclusion, using your condition that non-final states can be mapped to final states does not work. Consider for instance that $A$ is a rejecting sink $p_0$, and $B$ is the minimal automaton for ...
Denis's user avatar
  • 8,903
5 votes
Accepted

Oncina-Garcia RPNI algorithm for learning DFAs

The algorithm is named RPNI, not RNPI. Given that the language generating the inputs is regular and that enough examples are given (the characteristic set), the algorithm returns the canonical (i.e., ...
Roman Manevich's user avatar
5 votes
Accepted

Finite Automata with succinct representation of chains of states

This is a very partial answer, but I have some ideas: Clearly the union of NSAs can be taken without any blowup - just use the nondeterministic union of the initial states. As for determinization, ...
Shaull's user avatar
  • 5,656
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
5 votes

Random Cerny Conjecture

I think this problem has little to do with Cerny's conjecture. There the problem is to find a word that works for every pair of states. Here it is enough to show that the word will work whp. for any ...
domotorp's user avatar
  • 14k
5 votes

2DFA to 1DFA - Converting two way deterministic finite automata to one way deterministic finite automata

Kozen presents a constructive proof of the equivalence of 1dfa and 2dfa in a chapter of his book titled "Automata and Computability". If I recall correctly, it is a standard argument and the ...
Taylor Dohmen's user avatar
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
4 votes
Accepted

2DFA to 1DFA - Converting two way deterministic finite automata to one way deterministic finite automata

First, a warning: this will involve exponential $(2^{n \log n})$ blowup in the number of states (see here). However, if your application is fine with computing the states of the DFA "on the fly" then ...
Caleb Stanford's user avatar
4 votes

Is there a well-defined division operation on finite automata?

Lets give some obvious way to recover one "factor" of the product automaton. If $\mathcal A_i = (Q_i, \delta_i, q_{0i}, F_i), i = 1,2$ and $\mathcal A = \mathcal A_1 \times \mathcal A_2$ denotes the ...
StefanH's user avatar
  • 2,077
4 votes

Number of minimal DFAs of size at most $m$?

(NB: the upper bound given in the accepted answer is better or equal to the one given here) An upper bound is proposed in this paper given in one of the previous comments: “On the number of distinct ...
Luz's user avatar
  • 427
3 votes

Finite Automata with succinct representation of chains of states

A model that seems somewhat relevant is capacitated automata: http://www.cs.huji.ac.il/~ornak/publications/fsttcs14b.pdf
Guy's user avatar
  • 1,215
3 votes
Accepted

How to check if a the language represented by a DFA is finite

The language accepted by a deterministic finite automata is infinite if and only if there exists some cycle on some path from which a final state is reachable. If you minimize your automaton, then ...
StefanH's user avatar
  • 2,077
3 votes
Accepted

Is Bayes optimal RL of a finite set of DFAs feasible?

Even determining whether there is a policy which always succeeds is NP-complete, by a reduction from constructing optimal decision trees (Hyafil and Rivest, Constructing Optimal Binary Decision Trees ...
zeb's user avatar
  • 376
2 votes

Separating words and graph isomorphism

I hadn't thought about the Separating Words problem before, but based on looking at the Robson paper referenced in the linked answer, I don't immediately see how techniques from GI would apply. At a ...
Joshua Grochow's user avatar
2 votes

Can we efficiently enumerate the words accepted by a DFA by order of increasing weight?

After discussing it further with a3nm, I propose an algorithm that is different than Neal's algorithm and works in a more general setting. The approach gives polynomial delay algorithm but it uses ...
holf's user avatar
  • 2,174
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
1 vote

I have to make a dfa over the alphabet Σ = { 0, 1, 2 } of strings that end with the same digit twice; e.g., strings that end in 00, 11, 22

this forum is meant for research level questions. Your question seems to be an exercise to a first course on formal languages and would fit more in the following forum https://cs.stackexchange.com/ ...
Louis's user avatar
  • 775
1 vote

A conjecture related to the Cerny conjecture - counterexample/reference request

I found a partial answer to question 2. The same idea is discussed in the last 10 minutes of this lecture.
Kaarel Hänni's user avatar

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