% =====================================================================
% Rewritten edition of the exponential two-way deterministic state
% lower bound for one-way liveness.  Section order: introduction,
% matching algebra, rank-loss bound, machine-to-diagram encoding,
% separation.  The two original typos ("end{lem\nma}" and
% "initia\nlly") are not present.
% =====================================================================
\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{lmodern}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{microtype}
\usepackage[margin=1.05in]{geometry}
\usepackage{enumitem}
\usepackage{xcolor}
\PassOptionsToPackage{hyphens}{url}
\usepackage{hyperref}
\hypersetup{colorlinks=true,linkcolor=blue!45!black,citecolor=blue!45!black,urlcolor=blue!45!black,pdftitle={An exponential two-way deterministic state lower bound for one-way liveness},pdfauthor={OpenAI}}
\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\D}[1]{\mathcal D_{#1}}
\newcommand{\R}[1]{\mathcal R_{#1}}
\newcommand{\Id}[1]{I_{#1}}
\newcommand{\id}{\mathbf 1}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\rank}{rank}
\newcommand{\Lfun}{L}
\newcommand{\OWL}{\mathsf{OWL}}
\newcommand{\eps}{\varepsilon}
\setlist[enumerate]{itemsep=0.35em,topsep=0.5em}
\setlength{\emergencystretch}{2em}
\allowdisplaybreaks[1]

\title{An exponential two-way deterministic state lower bound for one-way liveness}
\author{OpenAI}
\date{September 25, 2026}

\begin{document}
\maketitle

\begin{abstract}
\noindent
One-way liveness on $h$ points accepts a word of binary relations when
the ordered product of the relations is nonempty. It has a nondeterministic
automaton with $h+3$ states and no left moves. We prove that every
equivalent $s$-state two-way deterministic automaton satisfies
$4(s+2)^2 \ge 2^{\lfloor (h-2)/31 \rfloor}$, even if the target is
allowed to use partial transitions, stay moves, and nonaccepting infinite
computations. Over the growing family of these languages, no polynomial
bound can relate $s$ to the source state count; already for one-way
nondeterministic sources, two-way determinism is exponentially more
expensive than two-way nondeterminism in the number of states. The
alphabet is finite for each $h$.
\end{abstract}

\section{Introduction}

Two-way deterministic finite automata (2DFAs) recognize exactly the
same languages as ordinary one-way finite automata (Rabin--Scott,
Shepherdson). The state counts, though, can be vastly different: a
two-way machine can reread its input, so it can move information out
of the finite state and into the head position. The natural question
is whether this is always cheap. If every two-way nondeterministic
automaton had an equivalent two-way deterministic one with only
polynomially many more states, nondeterministic head motion would be
inexpensive in the sense of finite control.

\paragraph{The witness language.}
Sakoda and Sipser gave a clean witness for this question. Fix a set $H$
with $|H| = h$. A \emph{binary relation} on $H$ is a subset of
$H \times H$. Let $\R{H}$ be the set of all binary relations on $H$,
viewed as a monoid (a set with an associative product and an identity)
under composition
\[
 (x,z) \in AB \iff \exists\, y \in H,\ (x,y) \in A \text{ and } (y,z) \in B,
\]
with identity $\Id{H} = \{(x,x) : x \in H\}$. A word
$R_1 \cdots R_\ell$ over the alphabet $\Sigma = \R{H}$ is \emph{live}
if $R_1 \cdots R_\ell \ne \varnothing$. \emph{One-way liveness} is the
language
\[
 \OWL_h = \{\, w \in \Sigma^* : \text{the ordered product of } w \text{ is nonempty} \,\}.
\]
The empty word belongs to $\OWL_h$ because the empty product is $\Id{H}$.

The language is a natural stand-in for nondeterministic path finding:
nonemptiness of a product says that some sequence of intermediate
vertices connects one end of the word to the other. The alphabet is
rich enough that each pair $(x,y)$ can be singled out by two extra
context letters --- the singleton identities at $x$ and at $y$. So
recognizing $\OWL_h$ forces the automaton to remember enough of the
visited path to answer queries like ``is $(x,y)$ in the product?''.
This is exactly where finite control is expensive. Sakoda and Sipser
proved that every two-way nondeterministic automaton over a finite
alphabet can be simulated by a small automaton for some $\OWL_h$; any
superpolynomial lower bound against $\OWL_h$ for two-way deterministic
targets therefore lifts to the general problem.

\paragraph{The source machine.}
Recognizing $\OWL_h$ is easy nondeterministically. Use $h$ path states
$1, \dots, h$ to guess the witness path. Start at the left endmarker
in an extra bookkeeping state and step right into any path state. On a
letter $R$, the machine moves from path state $p$ to path state $q$ by
a right move whenever $(p,q) \in R$. On the right endmarker the machine
enters an accepting state by a stay move. A third state catches missing
moves and rejects forever. This uses $h+3$ states, never moves left,
and needs no work tape.

\paragraph{Main result.}
The nontrivial direction is the deterministic lower bound.

\begin{theorem}[Main]
\label{thm:main}
For every integer $h \ge 2$, the language $\OWL_h$ is recognized by a
nondeterministic automaton with $h+3$ states that uses no left moves.
Every equivalent deterministic two-way automaton with $s$ states
satisfies
\begin{equation}
\label{eq:main-bound}
 4(s+2)^2 \ge 2^{\lfloor (h-2)/31 \rfloor}.
\end{equation}
If an initially accepting configuration counts as acceptance, $s+2$
in \eqref{eq:main-bound} may be replaced by $s+1$.
\end{theorem}

The bound is exponential in $h$. Writing $n = h+3$, the deterministic
side needs at least $2^{(1/2) \lfloor (n-5)/31 \rfloor - 1} - 2$ states,
which outgrows any fixed polynomial. Hence no pair of constants
$(C, c)$ can bound a two-way deterministic simulation by $C n^c$:

\begin{corollary}
\label{cor:no-polynomial}
There are no absolute constants $C, c > 0$ such that every $n$-state
two-way nondeterministic automaton over every finite alphabet has an
equivalent two-way deterministic automaton with at most $C n^c$ states.
\end{corollary}

\begin{proof}
Take the family $\OWL_h$ and the nondeterministic automaton of
Theorem~\ref{thm:main} with $n = h+3$ states. Every deterministic
equivalent has at least $2^{(1/2) \lfloor (n-5)/31 \rfloor - 1} - 2$
states. For large $n$ this expression exceeds $C n^c$ for every fixed
$C, c$. For each $h$ the alphabet $\R{H}$ is finite (of size $2^{h^2}$),
so the family satisfies the hypotheses of the corollary's universal
quantifier.
\end{proof}

\paragraph{Why a naive approach fails.}
The target is a two-way deterministic machine whose running time may be
unbounded, whose transitions may be partial, and whose head may make
arbitrarily many reversals. Each input symbol is a full relation with
up to $h^2$ entries, and the machine has only $s$ states to remember
them all. The interesting case is a cell whose contents have to be
sampled from both directions. Any encoding that stores the entire
neighborhood of a cell in the state uses a huge alphabet and loses the
bound; we need a construction in which each symbol of the input carries
exactly its own information and nothing more.

\paragraph{The two halves of the proof.}
Our proof splits into two independent constructions.

\begin{enumerate}[label=(\arabic*)]
\item \emph{Direct encoding.} From any $s$-state two-way deterministic
machine we build, uniformly, a family of matching diagrams
$\eta(a) \in \D{k}$ indexed by the symbols of the alphabet, with
$k \le 4(s+2)^2$. Each $\eta(a)$ depends only on the symbol $a$.
The machine accepts a word exactly when the composed diagram
$\eta(\vdash) \eta(a_1) \cdots \eta(a_\ell) \eta(\dashv)$ pairs a
specific left test port (port $1$ or port $2$ of Section~\ref{sec:machines})
to a specific right test port. Theorem~\ref{thm:machine-diagrams}
proves this.

\item \emph{Algebraic lower bound.} If an identity-containing submonoid
$S \subseteq \D{k}$ admits a unital surjection $\phi \colon S \to \R{H}$
(a multiplicative map that sends the identity of $S$ to $\Id{H}$ and
hits every relation), then $k \ge 2^{\lfloor (h-2)/31 \rfloor}$. This is
Corollary~\ref{cor:divisor-degree}, proved by an inductive rank-loss
argument (Theorem~\ref{thm:rank-loss}).
\end{enumerate}

The two halves meet in Section~\ref{sec:separation}. From the direct
encoding of a machine recognizing $\OWL_h$, a syntactic
argument (Lemma~\ref{lem:syntactic-quotient}) produces the unital
surjection $S \to \R{[h]}$ demanded by the algebraic half. The algebraic
bound then forces the degree $k \ge 2^{\lfloor (h-2)/31 \rfloor}$, and
since $k$ is essentially the square of the state count, the state bound
follows.

\paragraph{Reader's guide.}
Sections~\ref{sec:matching} and~\ref{sec:rank} are pure algebra: they
define matching diagrams, prove the corner-reduction lemma, and prove
the rank-loss lower bound of Theorem~\ref{thm:rank-loss} and
Corollary~\ref{cor:divisor-degree}. Section~\ref{sec:machines} performs
the encoding of Theorem~\ref{thm:machine-diagrams}. Section~\ref{sec:separation}
combines everything into Theorem~\ref{thm:main}. A reader who wants only
the result can read this introduction and Section~\ref{sec:separation}.
A reader who wants the algebra can start at Definition~\ref{def:matching}
and proceed linearly.

\paragraph{Related results.}
Earlier exponential separations restrict the motion of the target.
Sipser proved an exponential bound for sweeping automata, whose head
changes direction only at an endmarker. Kapoutsis extended this to
deterministic targets with sublinearly many reversals. Neither covers
unrestricted two-way motion. Quadratic lower bounds against unrestricted
two-way deterministic targets already occur in Chrobak's work on unary
languages, and in Adeogun--Kapoutsis's quadratic analysis of $\OWL_h$.
Kapoutsis also proved the optimal order $\Theta(h^2 / \log h)$ for the
promise restriction of $\OWL_h$ to words of exactly three relation
letters. Our target here is $2^{\Theta(h)}$.

On the algebraic side, the matching diagrams form the Brauer diagram
monoid, whose matchings underlie Brauer's centralizer algebras. Their
monoid structure and transversal rank have been analysed by Auinger
and by East and Gray. The corner construction $e \D{m} e \to \D{r}$
and its minimum-rank selection are the standard local-monoid tools
from finite semigroup theory (Pin). The amplification is new: $32$
conjugates of one idempotent contribute $256$ successive additions of
distinct relation pairs, all charged to a single rank-loss budget.

A companion paper analyses the complementary state complexity of two-way
nondeterministic \emph{complementation}, with bound $\tfrac12 \cdot
2^{\lfloor (h-2)/127 \rfloor} - 1$. The present paper establishes the
deterministic lower bound directly via matching diagrams. Both results
concern state succinctness over growing alphabets; neither yields a
uniform logarithmic-space separation or a bound measured in transition
table size.

\section{Matching diagrams and relation corners}
\label{sec:matching}

This section develops the algebra used in the rank argument. We
introduce the monoid $\D{m}$ of matching diagrams, quantify what a
diagram remembers with \emph{rank} and \emph{support}, reduce the
corner of an idempotent to a matching monoid of smaller degree, and
realize corners of the relation monoid inside the matching monoid.

Throughout, all monoid products are in \emph{path order}: in a
product $ab$, the factor $a$ is placed to the left of the factor $b$,
and composition flows left to right. A homomorphism is \emph{unital}
when it preserves the designated identity elements.

\subsection{Matching diagrams}

Picture $m$ positions along the left edge of a card and $m$ along the
right, numbered $1, \dots, m$ on each side. A \emph{matching diagram of
degree $m$} is a rule that pairs up all $2m$ positions, with no
position left unpaired. Draw each pair as a curve; crossings between
curves carry no meaning, so two diagrams that pair the same positions
are the same diagram. Only the pairing matters.

Write $\D{m}$ for the set of all such matchings. The small counts are
$\D{0}$ with one element, $\D{1}$ with one, $\D{2}$ with three, and
$\D{3}$ with fifteen; in general $|\D{m}| = (2m-1)!! = 1 \cdot 3
\cdot 5 \cdots (2m-1)$.

Two diagrams of degree $m$ are multiplied by \emph{gluing}: place $a$
to the left of $b$, identify the right ports of $a$ with the left
ports of $b$ that carry the same label, then read off the resulting
pairing of the outer ports.

\begin{definition}[Multiplication in $\D{m}$]
\label{def:matching}
For $a, b \in \D{m}$, form a finite multigraph as follows. Its vertices
# ^C interrupted by user!