<p>Unlike one-way models, intersection of 2-way NFAs is &quot;cheap&quot;:
Given 2-way NFAs <span class="math-container">$A_1,A_2$</span>, you can construct a 2-way NFA <span class="math-container">$B$</span> for their intersection that works as follows: it first behaves like <span class="math-container">$A_1$</span>, and once the accepting state is reached, it resets the head to the left marker (using a single state), and starts at the initial state of <span class="math-container">$A_2$</span>.</p>
<p>This can be easily extended to any number of NFAs, and the construction has linear size.</p>
<p>Thus, the non-emptiness problem for intersection of 2-way NFAs reduces to non-emptiness of a single 2-way NFA. So still PSPACE-complete.</p>

CC BY-SA 4.0
2024-04-18T07:35:57.737Z
2024-04-18T07:35:57.737Z
Shaull
<p>We know that checking the emptiness of intersection of an unbounded number of deterministic finite automata is PSpace-complete, and that just the emptiness problem for a nondeterministic two-way finite state automaton is also PSpace-complete.</p>
<p>Is there anything known about checking the emptiness of intersection of an unbounded number of <em>two-way</em> state automata? Maybe even deterministic ones.</p>
<p>Googling did not give anything. But maybe some hypothesis/connection with other problems/etc.?</p>

<cc.complexity-theory><automata-theory><space-bounded><pspace>
Intersection Non-Emptiness for Two-Way Finite Automata
A. G.
# Intersection Non-Emptiness for Two-Way Finite Automata

(Asked by: username_0 on 2024-04-17)

We know that checking the emptiness of intersection of an unbounded number of deterministic finite automata is PSpace-complete, and that just the emptiness problem for a nondeterministic two-way finite state automaton is also PSpace-complete.

Is there anything known about checking the emptiness of intersection of an unbounded number of *two-way* state automata? Maybe even deterministic ones.

Googling did not give anything. But maybe some hypothesis/connection with other problems/etc.?

**Tags:** cc.complexity-theory, automata-theory, space-bounded, pspace

---

## 1 answers

### Answer by username_1 on 2024-04-18. Score: 6 | Accepted answer

Unlike one-way models, intersection of 2-way NFAs is "cheap":
Given 2-way NFAs $A\_1,A\_2$, you can construct a 2-way NFA $B$ for their intersection that works as follows: it first behaves like $A\_1$, and once the accepting state is reached, it resets the head to the left marker (using a single state), and starts at the initial state of $A\_2$.

This can be easily extended to any number of NFAs, and the construction has linear size.

Thus, the non-emptiness problem for intersection of 2-way NFAs reduces to non-emptiness of a single 2-way NFA. So still PSPACE-complete.


---

