# Tag Info

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 ...
• 10.8k
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 ...
• 12.2k
Accepted

• 2,174

### 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 ...
• 17.9k
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 ...
• 6,545
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 ...
• 2,778

### 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. ...
• 6,545
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 ...
• 8,903
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 ...
• 3,707
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, ...
• 5,656
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 ...
• 10.8k

### 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
• 1,225
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$ ...