242 views

Is DFA language inclusion decidable in quasi-linear time? [duplicate]

Given two DFAs $A_1$ and $A_2$, we want to decide whether $\mathcal{L}(A_1) \subseteq \mathcal{L}(A_2)$. Of course, one can compute whether $\mathcal{L}(A_1) \cap \mathcal{L}(A_2) = \mathcal{L}(A_1)$. ...
• 135
9k views

Are there any open problems left about DFAs?

After studying deterministic finite state automata (DFA) in undergrad, I felt they are extremely well understood. My question is whether there is something we still don't understand about them. I don'...
2k views

Problems that can be used to show polynomial-time hardness results

When designing an algorithm for a new problem, if I can't find a polynomial time algorithm after a while, I might try to prove it is NP-hard instead. If I succeed, I've explained why I couldn't find ...
• 13.7k
3k views

Proving lower bounds by proving upper bounds

The recent breakthrough circuit complexity lower-bound result of Ryan Williams provides a proof technique that uses upper-bound result to prove complexity lower-bounds. Suresh Venkat in his answer to ...
1k views

What are the relationships between those hypotheses in Fine-Grained Complexity Theory?

Complexity theory, through such concepts as NP-completeness, distinguishes between computational problems that have relatively efficient solutions and those that are intractable. "Fine-grained" ...
670 views

Intersection non-emptiness problem over regular expressions and NFA

The intersection non-emptiness problem is defined as follows: Given a list of deterministic finite automata as input, the goal is to determine whether or not their associated regular languages have a ...
• 1,049
328 views

Two DFA intersection emptiness connections to SETH & L vs P

(re "fine grained complexity") Wehar has proved that Two DFA intersection emptiness in $O(n^{2-\epsilon})$ time → SETH false. does anyone see any particular key proof difficulty, challenge, ...
• 11k
254 views

What are some problems in $P$ which have lower bounds assuming that $P \neq NP$ or the ETH?

Last year I had watched this talk online about problems in $P$ for which an algorithm which runs in some subclass of $P$, say in subquadratic time, would imply $P = NP$, or violate the ETH (...
• 1,572
255 views

DFSA and NFSA intersection problem

Given $k$ deterministic FSAs of $n$ states the intersection of their languages is empty is decidable in $n^{o(k)}$ time is an open problem. For unbounded $k$ it is known the problem is $PSPACE$ ...
• 13k
76 views

Updating (minimal) DFA incrementally

Is there algorithm to incrementally update (minimal) DFA? Namely, having relatively large minimized DFA I want to update it incrementally using union and sudtraction with other (relatively small, ...
• 421