Skip to main content
14 votes
Accepted

Complexity of NFA cofiniteness

Lemma 1. Determining whether a given NFA is cofinite is PSPACE-hard. Proof. The proof is by an easy reduction from the PSPACE-complete problem of determining whether a given NFA is universal. The ...
Neal Young's user avatar
  • 10.8k
11 votes
Accepted

Determining if a word of specific length exists that is not accepted by a NFA

Your problem is NP-hard, by reduction from 3SAT. Let $\varphi$ be a 3SAT formula with $m$ clauses and on the $n$ variables $x_1,\dots,x_n$. Construct a NFA over the alphabet $\Sigma=\{0,1\}$ as ...
D.W.'s user avatar
  • 12.2k
10 votes
Accepted

Converting 2-ambiguous NFA to unambiguous NFA

I think that this is in fact not possible, thanks to the (recent and difficult!) ICALP'22 results of Göös et al.. They show that there are UFAs $A_1$ and $A_2$ with $n$ states such that the language $...
a3nm's user avatar
  • 9,677
8 votes
Accepted

Containment problem of an acyclic NFA in an NFA

This is coNP-hard even if $B$ is also acyclic. Let $D = \bigvee_{i=1}^m T_i$ be a DNF on variables $x_1, \dots, x_n$. We can easily contruct an NFA $B$ accepting exactly the satisfying assignment of $...
holf's user avatar
  • 2,174
8 votes

Complexity of NFA cofiniteness

Since the other answer makes it sound as if it were not obvious, let me point out that the problem is computable in PSPACE. First, we observe: Lemma. For any NFA $A$ with $n$ states, the following ...
Emil Jeřábek's user avatar
7 votes
Accepted

The complexity of conversion from a regular expression to a nondeterminsitic automata and back after changing initial and final states

As observed in the proof of Theorem 6 (later dubbed the "Star Height Lemma") of Gruber/Holzer ICALP 2008, when converting a regular expression into an $\varepsilon$-NFA, then the underlying ...
Hermann Gruber's user avatar
7 votes
Accepted

Does a given regular language contain an infinite prefix-free subset?

Your problem can be solved in polynomial time. To begin, convert the given NFA to an equivalent NFA with the following additional properties: There are no epsilon transitions All states are ...
Mikhail Rudoy'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

What class of languages is recognized by finite-state automata with $k$ heads?

This model is one of the standard models in automata theory and it has been examined by some researchers. The references given in the first comment are very good starting points. When the head is ...
Abuzer Yakaryilmaz'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
3 votes
Accepted

Deciding whether a 2nfa halts on every input on every branch

Lemma 1. $H_{\textsf{2nfa}}$ is decidable. Proof. Decide it as follows. Given as input a two-way non-deterministic finite automaton $M_{\textsf{2nfa}}$: Convert $M_{\textsf{2nfa}}$ into a two-way ...
Neal Young's user avatar
  • 10.8k
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,225
3 votes

Determining if a word of specific length exists that is not accepted by a NFA

In the following paper, a regular expression $r$ over some alphabet $\Sigma$ is constructed that accepts the set $INVALC_{M,w}$ of invalid computations of a deterministic in-place Turing machine $M$ ...
Hermann Gruber's user avatar
2 votes

Does a given regular language contain an infinite prefix-free subset?

Definitions Definition 1: Let $S$ be a set of words. We say that $S$ is nicely infinite prefix-free (made up name for the purpose of this answer) if there are words $u_0,\dots,u_n,\dots $ and $v_1,\...
xavierm02's user avatar
  • 556
2 votes

Is there an algorithm for minimizing an NFA with respect to bisimilarity rather than language equivalence?

Yes, see for example here: Johanna Högberg, Andreas Maletti, Jonathan May, Backward and forward bisimulation minimization of tree automata, Theoretical Computer Science 410(37), 2009, pp. 3539-3552, ...
Hermann Gruber's user avatar
2 votes
Accepted

Are regular expressions polynomially decomposable?

The answer to my question turned out to be positive, which follows from a translation from regular expressions to automata and back. Check the answer of Hermann Gruber to my previous POST.
Bartosz Bednarczyk'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