residual-counts-and-access.tex

% Options for packages loaded elsewhere
\PassOptionsToPackage{unicode}{hyperref}
\PassOptionsToPackage{hyphens}{url}
\PassOptionsToPackage{dvipsnames,svgnames,x11names}{xcolor}
%
\documentclass[
  11pt,
]{article}
\usepackage{amsmath,amssymb}
\usepackage{iftex}
\ifPDFTeX
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
  \usepackage{textcomp} % provide euro and other symbols
\else % if luatex or xetex
  \usepackage{unicode-math} % this also loads fontspec
  \defaultfontfeatures{Scale=MatchLowercase}
  \defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
\fi
\usepackage{lmodern}
\ifPDFTeX\else
  % xetex/luatex font selection
\fi
% Use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
\IfFileExists{microtype.sty}{% use microtype if available
  \usepackage[]{microtype}
  \UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\makeatletter
\@ifundefined{KOMAClassName}{% if non-KOMA class
  \IfFileExists{parskip.sty}{%
    \usepackage{parskip}
  }{% else
    \setlength{\parindent}{0pt}
    \setlength{\parskip}{6pt plus 2pt minus 1pt}}
}{% if KOMA class
  \KOMAoptions{parskip=half}}
\makeatother
\usepackage{xcolor}
\usepackage[margin=0.9in]{geometry}
\usepackage{color}
\usepackage{fancyvrb}
\newcommand{\VerbBar}{|}
\newcommand{\VERB}{\Verb[commandchars=\\\{\}]}
\DefineVerbatimEnvironment{Highlighting}{Verbatim}{commandchars=\\\{\}}
% Add ',fontsize=\small' for more characters per line
\newenvironment{Shaded}{}{}
\newcommand{\AlertTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
\newcommand{\AnnotationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\AttributeTok}[1]{\textcolor[rgb]{0.49,0.56,0.16}{#1}}
\newcommand{\BaseNTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\BuiltInTok}[1]{\textcolor[rgb]{0.00,0.50,0.00}{#1}}
\newcommand{\CharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\CommentTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textit{#1}}}
\newcommand{\CommentVarTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\ConstantTok}[1]{\textcolor[rgb]{0.53,0.00,0.00}{#1}}
\newcommand{\ControlFlowTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
\newcommand{\DataTypeTok}[1]{\textcolor[rgb]{0.56,0.13,0.00}{#1}}
\newcommand{\DecValTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\DocumentationTok}[1]{\textcolor[rgb]{0.73,0.13,0.13}{\textit{#1}}}
\newcommand{\ErrorTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
\newcommand{\ExtensionTok}[1]{#1}
\newcommand{\FloatTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\FunctionTok}[1]{\textcolor[rgb]{0.02,0.16,0.49}{#1}}
\newcommand{\ImportTok}[1]{\textcolor[rgb]{0.00,0.50,0.00}{\textbf{#1}}}
\newcommand{\InformationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\KeywordTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
\newcommand{\NormalTok}[1]{#1}
\newcommand{\OperatorTok}[1]{\textcolor[rgb]{0.40,0.40,0.40}{#1}}
\newcommand{\OtherTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{#1}}
\newcommand{\PreprocessorTok}[1]{\textcolor[rgb]{0.74,0.48,0.00}{#1}}
\newcommand{\RegionMarkerTok}[1]{#1}
\newcommand{\SpecialCharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\SpecialStringTok}[1]{\textcolor[rgb]{0.73,0.40,0.53}{#1}}
\newcommand{\StringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\VariableTok}[1]{\textcolor[rgb]{0.10,0.09,0.49}{#1}}
\newcommand{\VerbatimStringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\WarningTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\usepackage{longtable,booktabs,array}
\usepackage{calc} % for calculating minipage widths
% Correct order of tables after \paragraph or \subparagraph
\usepackage{etoolbox}
\makeatletter
\patchcmd\longtable{\par}{\if@noskipsec\mbox{}\fi\par}{}{}
\makeatother
% Allow footnotes in longtable head/foot
\IfFileExists{footnotehyper.sty}{\usepackage{footnotehyper}}{\usepackage{footnote}}
\makesavenoteenv{longtable}
\setlength{\emergencystretch}{3em} % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{-\maxdimen} % remove section numbering
\ifLuaTeX
\usepackage[bidi=basic]{babel}
\else
\usepackage[bidi=default]{babel}
\fi
\babelprovide[main,import]{english}
% get rid of language-specific shorthands (see #6817):
\let\LanguageShortHands\languageshorthands
\def\languageshorthands#1{}
\ifLuaTeX
  \usepackage{selnolig}  % disable illegal ligatures
\fi
\IfFileExists{bookmark.sty}{\usepackage{bookmark}}{\usepackage{hyperref}}
\IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
\urlstyle{same}
\hypersetup{
  pdftitle={Remembering information and reaching it},
  pdfauthor={FPRD Lab · Research directed by Joshua Gay},
  pdflang={en},
  colorlinks=true,
  linkcolor={blue},
  filecolor={Maroon},
  citecolor={Blue},
  urlcolor={blue},
  pdfcreator={LaTeX via pandoc}}

\title{Remembering information and reaching it}
\usepackage{etoolbox}
\makeatletter
\providecommand{\subtitle}[1]{% add subtitle to \maketitle
  \apptocmd{\@title}{\par {\large #1 \par}}{}{}
}
\makeatother
\subtitle{Research note extending Kim--Park's PEG separation}
\author{FPRD Lab · Research directed by Joshua Gay}
\date{5 September 2026 · Revision 4}

\begin{document}
\maketitle

\hypertarget{the-grammar-for-our-non-peg-language}{%
\subsection{The grammar for our non-PEG
language}\label{the-grammar-for-our-non-peg-language}}

This research note extends Kim--Park's explicit separation {[}1{]}. It
follows their lower-bound strategy and adapts their recursive parity
rules; novelty of the extensions is not established. The grammar below
uses a tree address to select one record. Its start symbol is
\texttt{A}; \texttt{epsilon} denotes the empty string.

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{A  {-}\textgreater{} 0 A t | 1 A T t | \# P1 [}
\NormalTok{T  {-}\textgreater{} T T t | ] B [}
\NormalTok{B  {-}\textgreater{} B 0 | B 1 | 0 | 1}
\NormalTok{R  {-}\textgreater{} R t | R [ | R ] | R 0 | R 1 | epsilon}

\NormalTok{P0 {-}\textgreater{} $ R ] | 0 P0 0 | 1 P0 0 | 0 P0 1 | 1 P1 1}
\NormalTok{P1 {-}\textgreater{}         0 P1 0 | 1 P1 0 | 0 P1 1 | 1 P0 1}
\end{Highlighting}
\end{Shaded}

Call its language \(L\). \textbf{This grammar is unambiguous, and no
ordinary PEG recognizes \(L\)}, using Ko's lower bound and the
Loff--Moreira--Reis PEG--scaffolding theorem. The proof is given below
in Proposition 1 and Corollary 6.

The proof studies the reversed language \(U=L^R\), whose records arrive
before its query. The grammar printed here reverses every right-hand
side of the grammar for \(U\) in Proposition 1; thus \(L=U^R\).
Reversing derivation trees preserves unambiguity.

\protect\hypertarget{abstract}{}{}

\hypertarget{question-contribution-and-dependencies}{%
\subsection{A question that arrives too
late}\label{question-contribution-and-dependencies}}

Suppose you are given a collection of records. Each record is a row of
zeros and ones. You can study the records and organize them however you
like. Next, another row of bits arrives, one bit at a time. Finally,
someone names a record and asks: \textbf{in how many positions do that
record and the new row both have a one---is that number odd or even?}

For example, take the record \texttt{1011} and the arriving row
\texttt{1101}. They both have a one in the first and fourth positions.
The answer is even, or zero. With the record \texttt{1001} and arriving
row \texttt{1000}, there is one such position. The answer is odd, or
one. This calculation is called an \emph{inner product over the
two-element field}: multiply corresponding bits and add modulo two.

If the question names the record in advance, maintain one running parity
bit. If it names the record only at the end, that strategy no longer
suffices. Storing the arriving row still takes only one write per bit,
but answering an arbitrary record's question may require consulting much
of it. Maintaining every record's answer during the updates moves the
work earlier. Can a more ingenious organization avoid both costs?

This note connects that data-structure question to a question about
grammars. Along the way we prove a limitation of one tempting way to
classify recognition problems. Two families of instances can have the
same number of distinguishable futures at every stage we measure,
including after any initial update prefix has been fixed, while their
access costs differ. The amount of information distinguished by future
answers does not determine the cost of maintaining and consulting that
information.

Our construction also gives an unambiguous context-free language outside
ordinary parsing expression grammars, using Ko's lower bound and the
PEG--scaffolding theorem described below. The residual-count identities
themselves need neither external theorem.

\hypertarget{fords-question-and-why-ambiguity-does-not-settle-it}{%
\subsection{Ford's question, and why ambiguity does not settle
it}\label{fords-question-and-why-ambiguity-does-not-settle-it}}

A context-free grammar describes strings by recursive construction
rules. A familiar example is

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{S {-}\textgreater{} ( S ) S | epsilon}
\end{Highlighting}
\end{Shaded}

which generates balanced parentheses. A parsing expression grammar, or
PEG, instead prescribes recognition operations. Its alternatives are
ordered: a successful earlier alternative commits the parser at that
choice. This changes what a rule means, even when its written form
resembles a context-free rule.

Bryan Ford introduced the PEG framework in his 2004 paper {[}4{]}. He
explained its practical appeal for describing syntax and established
that PEGs can express languages beyond the context-free class. The other
direction resisted proof: \textbf{is there a context-free language that
no PEG recognizes?} Failure of one attempted PEG would not answer this.
A language can have many grammars, so the question asks us to exclude
every possible PEG for one language.

The distinction is particularly interesting for an \emph{unambiguous}
context-free language: one that has a context-free grammar giving every
accepted word exactly one parse tree. A unique parse does not
automatically provide a PEG. It says how many successful derivations
exist, not how a recognizer can find the successful choices as input
arrives.

Kim and Park {[}1, Section 4.3, equation (3){]} already give an explicit
grammar for a linear context-free language whose reversal is outside
PEG. Their construction supplies the separation asked for by Ford. This
note follows their lower-bound strategy and adapts their grammar: the
eight recursive parity rules for \texttt{P0} and \texttt{P1} are the
same, up to ordering, while the base case and surrounding
record-selection rules change. Here a tree path selects at most one
leaf, giving a proof of unambiguity. We also compare families with
matching residual counts and different access costs. These are
extensions within their approach; their novelty in the literature has
not been established. The simulation below is proved directly, but it
uses the same Ko lower bound and does not constitute an independent
method of resolving Ford's question.

\hypertarget{what-ko-contributes}{%
\subsection{What Ko contributes}\label{what-ko-contributes}}

Young Kun Ko studies dynamic data structures: information is prepared,
updates arrive, and later queries must be answered {[}2{]}. His lower
bound applies in the \emph{cell-probe model}. Memory consists of cells
holding words of a specified size. Reading or writing a cell costs one
probe; computation using the values already read is free. Giving
computation away makes an impossibility result in this model especially
useful: it rules out clever encodings and arithmetic tricks as well as
straightforward implementations.

The consequence we need concerns an arbitrary matrix with \(n^2\)
records of \(n\) bits each. With words of \(\Theta(\log n)\) bits and
polynomially many memory cells, an exact deterministic data structure
cannot process each arriving coordinate in \(O(1)\) probes and answer
the final, previously unknown record query in \(O(\log n)\) probes. Ko's
Theorem 1.1 and the coordinate-update accounting in his Section 3 supply
that consequence. We call it \textbf{K} below. Ko's proof is an external
premise; our contribution here includes checking the interface and
proving our own reduction to it.

Why should a grammar face a memory-access restriction? Loff, Moreira,
and Reis give the bridge {[}3, Theorem 16{]}. They introduce a
\emph{scaffolding automaton}, which reads one input symbol at a time and
appends one node to a permanent graph. The machine can inspect only a
fixed-size neighborhood of its latest node. Old information persists,
but reaching it takes navigation. Their characterization is

\[L\in\mathsf{PEG}\quad\Longleftrightarrow\quad L^R\in\mathsf{SCA}.\]

The superscript \(R\) reverses every word in a language. Thus, to
exclude a PEG for \(U^R\), we can exclude a scaffold for \(U\). Our
direct simulation shows that a scaffold for our record-and-query
language would violate K. The reversal is part of the theorem, not a
convenient change of convention.

\hypertarget{what-a-residual-tells-us}{%
\subsection{What a residual tells us}\label{what-a-residual-tells-us}}

After a prefix \(u\) has arrived, its \emph{residual} is the set of
suffixes that would finish an accepted word:

\[\rho_L(u)=u^{-1}L=\{z:uz\in L\}.\]

Think of it as the complete answer sheet for every possible
continuation. If two prefixes have different answer sheets, a
deterministic recognizer must distinguish them. Otherwise it would give
the same answer to a continuation that should distinguish them.

Here is a small example. Store two bits \(x_1,x_2\), and allow three
final questions: ask for \(x_1\), for \(x_2\), or for their parity
\(x_1\oplus x_2\). The four possible updates give these answer sheets:

\begin{longtable}[]{@{}lrrr@{}}
\toprule\noalign{}
Update & First bit & Second bit & Parity \\
\midrule\noalign{}
\endhead
\bottomrule\noalign{}
\endlastfoot
\texttt{00} & 0 & 0 & 0 \\
\texttt{01} & 0 & 1 & 1 \\
\texttt{10} & 1 & 0 & 1 \\
\texttt{11} & 1 & 1 & 0 \\
\end{longtable}

There are four distinct residuals. This is \textbf{not the size of one
residual}. Each residual consists of the questions answered one; in this
example the residual for \texttt{00} is empty, while each other residual
contains two questions. We count different answer sheets as the update
varies.

Four possibilities require two bits to distinguish. But this count does
not tell us what memory operations maintain the answer sheet, or how
much of it a particular query must consult. Our theorem makes that
distinction exact for an unbounded family. It compares canonical
instances inside one language, not the global residual growth of two
different languages.

\hypertarget{a-language-with-a-uniquely-selected-leaf}{%
\subsection{A language with a uniquely selected
leaf}\label{a-language-with-a-uniquely-selected-leaf}}

Let \(D=\{\mathtt t,\mathtt{[},\mathtt{]},0,1\}\), with additional
delimiters \texttt{\$} and \texttt{\#}. A complete binary tree has
prefix encoding

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{T {-}\textgreater{} t T T | [ B ]}
\NormalTok{B {-}\textgreater{} 0 B | 1 B | 0 | 1.}
\end{Highlighting}
\end{Shaded}

Thus \texttt{t} introduces an internal node, and \texttt{{[}s{]}} a leaf
with a nonempty binary payload. These encodings are self-delimiting.
Pending child slots start at one, increase by one on an internal node,
and decrease by one after a leaf. The first return to zero uniquely
identifies the end of a complete tree.

For an arbitrary data word \(a\in D^*\) and path \(p\in\{0,1\}^*\),
start at the beginning of \(a\). Each path bit requires a \texttt{t}. A
zero descends immediately into the left child; a one skips exactly one
complete tree and then descends into the right child. After all path
bits, require a leaf \texttt{{[}s{]}}. If this succeeds, write \(s_p\)
for its payload and put \(p\in P(a)\).

Each path selects at most one leaf. The set \(P(a)\) is finite, since
each path step consumes a \texttt{t}. The data after the selected leaf
is unrestricted. We do not require the whole data word to be a complete
tree. For example, \texttt{t{[}1{]}\$1\#0} will be accepted although its
unvisited right subtree is missing.

The membership condition is

\[U=\{a\mathtt\$x\mathtt\#p^R:
 p\in P(a),\ |s_p|=|x|,\ \langle s_p^R,x\rangle=1\}.\]

All inner products and ranks in this note are over \(\mathbb F_2\). The
query is a reversed path: the last query bit determines the first tree
branch. The payload is reversed in the parity comparison for the same
nested-matching reason.

\hypertarget{proposition-1.-an-unambiguous-grammar}{%
\subsubsection{Why every accepted word has one
parse}\label{proposition-1.-an-unambiguous-grammar}}

\textbf{Proposition 1.}

The following CFG, with start symbol \(A\), generates exactly \(U\) and
is unambiguous. Its recursive \texttt{P0} and \texttt{P1} rules are
adapted from Kim--Park {[}1, equation (3){]}; the tree-addressed
selection and parity base case give the language used here.

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{A  {-}\textgreater{} t A 0 | t T A 1 | [ P1 \#}
\NormalTok{T  {-}\textgreater{} t T T | [ B ]}
\NormalTok{B  {-}\textgreater{} 0 B | 1 B | 0 | 1}
\NormalTok{R  {-}\textgreater{} t R | [ R | ] R | 0 R | 1 R | epsilon}

\NormalTok{P0 {-}\textgreater{} ] R $ | 0 P0 0 | 0 P0 1 | 1 P0 0 | 1 P1 1}
\NormalTok{P1 {-}\textgreater{}         0 P1 0 | 0 P1 1 | 1 P1 0 | 1 P0 1}
\end{Highlighting}
\end{Shaded}

\emph{Proof.} For \(r\in\{0,1\}\), induction gives

\[L(P_r)=\{s\mathtt{]}z\mathtt\$x:
z\in D^*,\ |s|=|x|,\ \langle s^R,x\rangle=r\}.\]

The only terminal base is \(P_0\to\mathtt{]}R\mathtt\$\). A production
\(P_r\to bP_c e\) is present precisely when \(r=c\oplus be\). It adds a
payload bit on the left and an update bit on the right, changing the
parity by \(be\). Since \(P_1\) has no terminal base, an accepting
derivation has nonempty payload and update vector.

The two recursive \(A\)-productions respectively descend left and skip a
complete left subtree before descending right. Appending the path bit on
the right produces \(p^R\). The base \(A\to\mathtt{[}P_1\mathtt\#\)
enforces parity one at the selected leaf. This proves equality with
\(U\).

To prove unambiguity, fix a terminal word. Its delimiters determine the
data, update, and query fields. An empty query forces the base
\(A\)-production; otherwise the last query bit forces the outer
recursive production. A skipped tree has a unique boundary and
derivation. At the selected leaf, the first closing bracket fixes the
payload, while \texttt{\$} fixes the ignored tail. Each
\(P_r\)-production is determined by the first payload bit and last
update bit. Finally \(R\) derives each tail uniquely. Induction leaves
at most one derivation tree. \(\square\)

Reversing all production right-hand sides mirrors derivation trees
bijectively. In particular, \(U^R\) is also an unambiguous CFL.
Proposition 8 below proves that neither language is linear context-free.

\hypertarget{exact-full-residuals}{%
\subsection{Counting all possible futures}\label{exact-full-residuals}}

The formulas in this section concern full residuals in \(U\), not a
promised subset of continuations.

\hypertarget{proposition-2.-residual-rank-at-an-arbitrary-update-cut}{%
\subsubsection{Proposition 2. Residual rank at an arbitrary update
cut}\label{proposition-2.-residual-rank-at-an-arbitrary-update-cut}}

Fix any \(a\in D^*\) and update length \(j\geq0\). For each accessible
leaf \(p\in P(a)\), let \(b_p=s_p^R\) and \(\ell_p=|b_p|\). Let
\(M_j(a)\) contain the first \(j\) coordinates of every row \(b_p\) with
\(\ell_p\geq j\). Then

\[\rho_U(a\mathtt\$v)=\left\{
y\mathtt\#p^R:
\begin{array}{l}
p\in P(a),\quad \ell_p\geq j,\quad |y|=\ell_p-j,\\
\langle b_p[1:j],v\rangle+
\langle b_p[j+1:\ell_p],y\rangle=1
\end{array}\right\}.\]

Consequently, across all \(v\in\mathbb F_2^j\), the number of residuals
is \(2^{\operatorname{rank}M_j(a)}\).

\emph{Proof.} Every accepting continuation must finish the binary update
field, then supply \texttt{\#} and a successful reversed path. Length
equality and a split inner product give the formula. Two update prefixes
\(v,v'\) have the same residual exactly when \(M_j(a)(v+v')=0\). If a
row distinguishes them, choose its path and an all-zero remaining
update: the acceptance values differ. Rank-nullity gives the count. A
matrix without rows has rank zero and gives the single empty residual.
\(\square\)

Now fix a binary matrix \(M\) of width \(d\geq1\) and \(m=2^h\) rows,
numbered from zero. Let \(\tau(M)\) be the complete balanced prefix tree
with leaf \(i\) equal to \([M_i^R]\). Write \(\operatorname{code}_h(i)\)
for the \(h\)-bit root-to-leaf address. Then

\[\tau(M)\mathtt\$y\mathtt\#\operatorname{code}_h(i)^R\in U
\quad\Longleftrightarrow\quad\langle M_i,y\rangle=1.\]

For a query prefix \(r\), \(|r|\leq h\), define its cylinder

\[I(r)=\{i:\operatorname{code}_h(i)^R\text{ begins with }r\}.\]

This is one residue class modulo \(2^{|r|}\): the query reveals
low-order index bits first. If \(\operatorname{code}_h(i)^R=rz_i\), the
full residual after \(\tau(M)\mathtt\$y\mathtt\#r\) is exactly

\[\{z_i:i\in I(r),\ (My)_i=1\}.\]

The remaining suffixes are distinct, so this residual identifies the
answer vector on \(I(r)\). No other continuations are possible: all leaf
lengths equal \(d\), and all successful addresses have length \(h\).

\hypertarget{proposition-3.-conditional-residual-counts-and-probabilities}{%
\subsubsection{Proposition 3. Conditional residual counts and
probabilities}\label{proposition-3.-conditional-residual-counts-and-probabilities}}

Define the update counts

\[u_M(j)=|\{\rho_U(\tau(M)\mathtt\$v):v\in\mathbb F_2^j\}|,
\qquad 0\leq j\leq d.\]

For any fixed update prefix \(v\in\mathbb F_2^j\) and query prefix
\(r\), define

\[Q_M(v,r)=|\{\rho_U(\tau(M)\mathtt\$vz\mathtt\#r):
 z\in\mathbb F_2^{d-j}\}|.\]

Then

\[u_M(j)=2^{\operatorname{rank}M[:,1:j]},\qquad
Q_M(v,r)=2^{\operatorname{rank}M[I(r),j+1:d]}.\]

Under a uniform choice of \(z\), these latter residuals are
equiprobable. If the indicated rank is \(s\), each occurs with
probability \(2^{-s}\) and has \(2^{d-j-s}\) completions.

\emph{Proof.} The first formula is Proposition 2. For the second, the
possible answer vectors on \(I(r)\) form the affine image

\[M[I(r),1:j]v+M[I(r),j+1:d]\,z.\]

Its size is \(2^s\). Every fibre is a translate of the kernel and has
size \(2^{d-j-s}\). The distinct suffixes identify the answer vector
with the full residual. \(\square\)

Taking \(j=0\) gives the residual count across all update vectors at
every query prefix. Taking \(j=d\) gives count one: the update word is
then completely fixed. The sole residual need not be the same in two
compared instances.

\hypertarget{matching-every-profile-with-a-terminal-marker}{%
\subsection{How to hide a hard query inside matching
counts}\label{matching-every-profile-with-a-terminal-marker}}

The next construction adds \emph{guard records}: questions that expose
individual update bits. Their job is to make the number of
distinguishable answer sheets the same in both families. A final extra
update bit, the \emph{marker}, keeps that equality true even after
earlier update bits have been fixed.

Consider just one cluster with two data bits \(x_1,x_2\) and final
marker \(b\). In the hard cluster, the distinguished question asks for
\(x_1\oplus x_2\oplus b\). In the easy cluster, it asks for \(b\). Both
also contain guard questions for \(x_1\) and \(x_2\), plus a question
whose answer is always zero.

\begin{longtable}[]{@{}
  >{\raggedright\arraybackslash}p{(\columnwidth - 4\tabcolsep) * \real{0.3333}}
  >{\raggedright\arraybackslash}p{(\columnwidth - 4\tabcolsep) * \real{0.3333}}
  >{\raggedright\arraybackslash}p{(\columnwidth - 4\tabcolsep) * \real{0.3333}}@{}}
\toprule\noalign{}
\begin{minipage}[b]{\linewidth}\raggedright
Update \(x_1x_2b\)
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
Hard answers: distinguished, two guards, zero
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
Easy answers: distinguished, two guards, zero
\end{minipage} \\
\midrule\noalign{}
\endhead
\bottomrule\noalign{}
\endlastfoot
\texttt{000} & \texttt{0000} & \texttt{0000} \\
\texttt{001} & \texttt{1000} & \texttt{1000} \\
\texttt{010} & \texttt{1010} & \texttt{0010} \\
\texttt{011} & \texttt{0010} & \texttt{1010} \\
\texttt{100} & \texttt{1100} & \texttt{0100} \\
\texttt{101} & \texttt{0100} & \texttt{1100} \\
\texttt{110} & \texttt{0110} & \texttt{0110} \\
\texttt{111} & \texttt{1110} & \texttt{1110} \\
\end{longtable}

Both columns contain eight different answer sheets, each appearing once.
The guards reveal the data bits; after those are known, the
distinguished answer reveals the marker. The hard question has changed
which update produces an answer sheet without changing the number of
sheets.

This example alone is not a lower bound: two bits are easy to handle.
For arbitrary record length, however, the distinguished questions
contain an arbitrary matrix of inner products. We must also arrange the
record addresses carefully. Early query bits select an original record
while leaving its entire cluster available; later bits select a position
within that cluster. The formal row indexing below achieves precisely
this.

Putting the marker last matters. When we fix an initial part of the
update, the marker remains free until all the data bits have arrived. It
therefore contributes an independent dimension whenever the
distinguished record is still among the possible questions. If we
instead fixed the marker first, the distinguished question could
collapse or depend on the data matrix in a way the easy question does
not.

\hypertarget{theorem-4.-matching-conditional-profiles}{%
\subsubsection{The exact matching
statement}\label{theorem-4.-matching-conditional-profiles}}

\textbf{Theorem 4.}

For every \(n\geq1\) and \(A\in\mathbb F_2^{n^2\times n}\), there are
matrices \(H(A)\) and \(E_n\), both of width \(d=n+1\) and with the same
\(m=\Theta(n^3)\) rows, such that:

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\tightlist
\item
  \(u_{H(A)}(j)=u_{E_n}(j)=2^j\) for every \(0\leq j\leq d\).
\item
  \(Q_{H(A)}(v,r)=Q_{E_n}(v,r)\) for every update prefix \(v\) and every
  query prefix \(r\).
\item
  Under uniform completions of \(v\), the two distributions on residuals
  have the same multiset of probabilities.
\item
  The continuation problem for \(E_n\) has constant update and query
  probe cost. The family \(H(A)\) contains arbitrary Multiphase Inner
  Product with constant overhead.
\end{enumerate}

Consequently, under K, these matching profiles do not determine whether
constant updates and logarithmic queries are attainable.

\emph{Construction.} Put

\[N=2^{\lceil\log_2(n^2)\rceil},\qquad
G=2^{\lceil\log_2(n+1)\rceil},\qquad m=NG.\]

Pad \(A\) with zero rows to \(N\) rows. Index the new rows as \(i+Nc\),
where \(0\leq i<N\) and \(0\leq c<G\). Define

\[H(A)_{i+Nc}=\begin{cases}
(A_i,1),&c=0,\\
(e_c,0),&1\leq c\leq n,\\
0,&n<c<G,
\end{cases}\]

where \(e_c\) is the \(c\)th basis vector of \(\mathbb F_2^n\). Replace
every distinguished row \((A_i,1)\) by \((0^n,1)\) to obtain \(E_n\).
The marker is the \textbf{last} update coordinate. This placement is
what gives the conditional strengthening.

\emph{Update counts.} The guard rows contain a basis for the first \(n\)
columns. Adding the marker column raises the rank once more, since a
distinguished row has marker one and guards have marker zero. Every
initial \(j\) columns have rank \(j\), in both matrices. Proposition 3
gives assertion 1.

\emph{Query counts after any fixed update prefix.} Write \(a=\log_2N\)
and fix \(r\).

If \(|r|\leq a\), its cylinder leaves the cluster coordinate \(c\)
completely unrestricted. It contains an entire cluster and therefore all
guard rows and a distinguished row. For every \(j\), the selected rows
restricted to columns \(j+1,\ldots,d\) have full rank \(d-j\) in both
matrices.

If \(|r|=a+t\), the query fixes one \(i\) and a residue class \(C_r\) of
cluster positions modulo \(2^t\). For \(j\leq n\), the surviving guards
with \(j<c\leq n\) remain distinct basis rows; guards with \(c\leq j\)
restrict to zero. If \(0\in C_r\), the distinguished row adds precisely
one dimension because its final marker is still one. If \(0\notin C_r\),
the selected rows are identical. Thus the rank in either matrix is

\[|\{c\in C_r:j<c\leq n\}|+\mathbf1_{\{0\in C_r\}},\qquad j\leq n.\]

For \(j=d\), no columns remain and both ranks are zero. Proposition 3
proves assertions 2 and 3, including the endpoints and every query
branch.

\emph{Easy access.} Write the update as \(y=(x,b)\). Store each arriving
coordinate. Given index \(i+Nc\), return \(b\) if \(c=0\), return
\(x_c\) if \(1\leq c\leq n\), and otherwise return zero. This costs one
write per update and at most one read per query. Arithmetic on the given
index is free in the cell-probe model.

\emph{Embedded hard problem.} Given \(A\), preprocess \(H(A)\). Supply
\(y=(x,0)\) and query row \(i\) with cluster position zero. The answer
is exactly \(\langle A_i,x\rangle\). The fixed final zero can be
processed with the last coordinate update, at constant overhead. The
transformation uses polynomial space, \(d=n+1\) update symbols, and
\(\log_2m+1=O(\log n)\) query symbols. Hence excluded costs for
Multiphase Inner Product would follow from the same costs for the whole
hard family. \(\square\)

The lower bound is worst-case over the family: particular matrices such
as \(A=0\) are easy. A single algorithm must handle arbitrary \(A\),
with the preprocessing information stored in its charged memory. A
different uncharged program hardwired for each matrix is not the model
under comparison.

\hypertarget{what-the-theorem-forgets-and-what-it-preserves}{%
\subsubsection{What the theorem forgets, and what it
preserves}\label{what-the-theorem-forgets-and-what-it-preserves}}

The profiles preserve the number of distinct full residuals, including
after any initial update prefix has been fixed. They also preserve the
entropy and the multiset of residual probabilities under uniform
completions. They do not preserve the residual sets themselves, their
labels, or their transition maps.

For example, let \(n=1\) and \(A=[1]\). On update \(y=10\), the
distinguished hard row answers one and the easy row answers zero. After
its complete query, the residuals are respectively \(\{\varepsilon\}\)
and \(\varnothing\), although both conditional counts are one.
Conditioning instead on a fixed \textbf{final} marker value while
varying the preceding data is not covered by the prefix-conditioning
theorem.

No claim is made that the easy canonical family itself forms a CFL, or
that its cell-probe algorithm has a fixed-locality scaffold
implementation. The theorem compares the precisely defined continuation
problems embedded in \(U\). It does not rule out classification using
richer residual structure.

\hypertarget{direct-simulation-and-the-unambiguous-non-peg-consequence}{%
\subsection{From a scaffold to a forbidden data
structure}\label{direct-simulation-and-the-unambiguous-non-peg-consequence}}

\hypertarget{proposition-5.-from-a-fixed-scaffold-to-cheap-probes}{%
\subsubsection{Proposition 5. From a fixed scaffold to cheap
probes}\label{proposition-5.-from-a-fixed-scaffold-to-cheap-probes}}

If a fixed scaffolding automaton recognizes \(U\), then Multiphase Inner
Product admits the costs excluded by K.

\emph{Proof.} Let the automaton have outdegree \(b\), inspection radius
\(k\), a finite node-label alphabet, and finite control. Index its nodes
by creation time. A node is a constant number of words containing its
label and outgoing pointers. A constant-size memory header stores the
control state, current top, and next free node index. All state
surviving between operations is in charged memory.

One input symbol reads that header and follows every relevant path of
length at most \(k\) from the top. Even if visits are repeated, this
accesses at most a constant multiple of

\[1+b+b^2+\cdots+b^k\]

node fields. The fixed transition table is evaluated for free. Its new
node refers only to permitted inspected endpoints, itself, or absent
pointers. Writing its fields and the header uses a constant number of
further probes. Self-pointers and repeated endpoints cause no difficulty
because the inspection depth is fixed. The simulation supplies exactly
the prescribed labelled neighbourhood to the transition table.

During preprocessing, simulate the automaton on \(\tau(H(A))\mathtt\$\).
This depends only on \(A\) and \(n\). Process the bits of \(x\) one at a
time; with the last bit also process the fixed marker zero. Each update
uses constantly many probes. After index \(i\) is revealed, simulate
\texttt{\#} followed by its reversed \(h\)-bit address, and return the
automaton's accepting-state bit. There are \(h+1=O(\log n)\) query
symbols.

The balanced tree has \(m-1\) internal nodes and \(m\) leaves of length
\(d+2\), hence

\[|\tau(H(A))|=m(d+3)-1=O(n^4).\]

All node addresses therefore fit in logarithmic words and the memory is
polynomial. The update algorithms receive no queried row for free. The
query arrives after all data updates. If a read-only final query is
required, simulated writes can be kept in an operation-local overlay,
since no later operation needs them. Correctness follows from the
encoding equivalence and Theorem 4. \(\square\)

This simulation excludes arbitrary fixed scaffolding automata,
regardless of their internal summaries, sharing, or preprocessing
strategy. It is not a lower bound against one proposed data
representation. The proof is included here in full, while its
methodological source remains {[}1{]}.

\hypertarget{corollary-6.-an-unambiguous-cfl-outside-peg}{%
\subsubsection{Corollary 6. An unambiguous CFL outside
PEG}\label{corollary-6.-an-unambiguous-cfl-outside-peg}}

Under K, \(U\notin\mathsf{SCA}\) and

\[U^R\in\mathsf{UCFL}\setminus\mathsf{PEG}.\]

\emph{Proof.} Proposition 5 contradicts K if \(U\) has an SCA.
Proposition 1 gives the unambiguous grammar for \(U^R\), and {[}3,
Theorem 16{]} converts a hypothetical PEG for \(U^R\) into an SCA for
\(U\). \(\square\)

We have not proved whether \(U\) itself has a PEG. In particular, this
paper does not fill both asymmetric PEG/reversal categories within UCFL.

\hypertarget{corollary-7.-failure-in-both-orientations}{%
\subsubsection{Corollary 7. Failure in both
orientations}\label{corollary-7.-failure-in-both-orientations}}

Under K, \(V=U\cup U^R\) is a self-reversing unambiguous CFL in neither
PEG nor SCA.

\emph{Proof.} Words of \(U\) start with \texttt{t} or \texttt{{[}}.
Words of \(U^R\) start with a bit, or with \texttt{\#} when the path is
empty. The languages are disjoint, so a new start symbol joining their
unambiguous grammars remains unambiguous. Also \(V^R=V\).

The regular filter selecting first symbols \(0,1,\mathtt\#\) extracts
exactly \(U^R\). If \(V\) had a PEG, intersection with that regular
language would give a PEG for \(U^R\), contrary to Corollary 6. This
regular-intersection closure follows directly by an anchored PEG test
for the filter followed by the original recognizer {[}4{]}.
Self-reversal and {[}3{]} also exclude SCA membership. \(\square\)

\hypertarget{failed-conversions-and-finite-evidence}{%
\subsection{Failed conversions and finite
evidence}\label{failed-conversions-and-finite-evidence}}

Unambiguity of a CFG does not justify treating its alternatives as PEG
ordered choices. For the grammar in Proposition 1, prioritizing
\texttt{t\ A\ 0} before \texttt{t\ T\ A\ 1} rejects the valid word

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{t[1]t[1][1]$1\#01}
\end{Highlighting}
\end{Shaded}

Prioritizing the right alternative rejects

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{tt[1][1][1]$1\#10}
\end{Highlighting}
\end{Shaded}

An end-of-input guard inside each outer alternative still fails on
nested instances: respectively \texttt{tt{[}1{]}t{[}1{]}{[}1{]}\$1\#010}
and \texttt{t{[}0{]}tt{[}1{]}{[}1{]}{[}1{]}\$1\#101}. A nested call can
commit before its caller checks the caller's trailing path bit. These
counterexamples reject particular conversions; they are not proofs that
\(U\notin\mathsf{PEG}\).

The accompanying original checker implements a CFG derivation counter
and a separate semantic traversal. Its earlier run covered malformed
data, ignored tails, varied tree depths, canonical encodings, and
mutations. The new checker focuses on Theorem 4: it checks all binary
\(4\times2\) input matrices, both \(1\times1\) matrices, and larger
deterministic examples. It also forms actual residual answer signatures
through the semantic recognizer and checks the conditional fibre
multiplicities. All checks passed.

The tests corroborate index reversal, marker placement, rank formulas,
and the explicit failures. Universal unambiguity, nonlinearity, and
asymptotic lower bounds are supported by proofs, not by enumerating
finite cases. The companion audit records the precise scope and
reproduction commands.

\hypertarget{the-witness-is-not-linear-context-free}{%
\subsection{The witness is not linear
context-free}\label{the-witness-is-not-linear-context-free}}

\hypertarget{proposition-8.-nonlinearity-of-the-language}{%
\subsubsection{Proposition 8. Nonlinearity of the
language}\label{proposition-8.-nonlinearity-of-the-language}}

Neither \(U\) nor \(U^R\) is linear context-free.

\emph{Proof.} Intersect \(U\) with the regular language described by

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{t (t | [0])* [1] $ 1 \# 1.}
\end{Highlighting}
\end{Shaded}

The final query takes one right turn. A word in the intersection is
therefore exactly \(t e[1]\mathtt\$1\mathtt\#1\), where \(e\) is a
complete prefix tree whose leaves are all \texttt{{[}0{]}}. The selected
\texttt{{[}1{]}} is the unique such leaf and the regular restriction
allows no tail after it.

Apply the homomorphism sending \texttt{t} to \(a\), \texttt{0} to \(b\),
and all other symbols to \(\varepsilon\). Its image is \(aE\), where
\(E\to aEE\mid b\). These are precisely the nonempty words with total
\(a\)-minus-\(b\) balance zero and strictly positive balance at every
nonempty proper prefix.

The linear-language pumping lemma {[}5, Lemma 6{]} gives a constant
\(P\) and, for each sufficiently long word, a factorization \(uvwxy\)
with \(|uvxy|\leq P\), \(|vx|>0\), and \(uv^iwx^iy\) in the language for
every \(i\geq0\).

Choose \(N>P\) and

\[z=a^{N+1}b^Na^Nb^{N+1}\in aE.\]

The bounded end factors force \(v\) to contain only initial \(a\)'s and
\(x\) only final \(b\)'s. Put \(r=|v|\), \(s=|x|\). Pumping down with
\(r\ne s\) destroys total balance. If \(r=s\), both are positive, and
the prefix through the first \(b\)-block has balance \(1-r\leq0\), with
a nonempty second \(a\)-block still following. This also leaves \(aE\).
Thus \(aE\) is not linear.

Regular intersection and homomorphism preserve linearity: one can
annotate the single nonterminal by DFA entry/exit states, and replace
its terminal contexts by their homomorphic images. Hence linearity of
\(U\) would contradict that of its extracted image. Reversal also
preserves the one-nonterminal production property, so \(U^R\) is not
linear either. \(\square\)

\hypertarget{what-remains-to-classify}{%
\subsection{What remains to classify}\label{what-remains-to-classify}}

The theorem isolates a loss of information in the proposed classifier.
Counts retain quotient sizes while discarding how individual update
coordinates and query branches act on those quotients. Equal size, equal
conditional size, and equal residual-probability multisets leave room
for different access costs.

A stronger classification must retain enough structure to ask whether
one representation supports all required updates and late queries within
the available local work. Passing the present obstruction does not imply
SCA or PEG membership. An intrinsic scaffold obstruction independent of
cell-probe lower bounds remains open. So do a PEG construction for \(U\)
and a witness retaining both linearity and unambiguity.

The reusable contribution is the terminal-marker construction and its
exact comparison inside an explicit UCFL. Rank-nullity, pumping, and the
external lower bound retain their established provenance. The resulting
separation is a focused obstruction to cardinality-based classification,
not a classification of all CFLs.

\hypertarget{references}{%
\subsection{References}\label{references}}

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Jungyeom Kim and Jihyeok Park. \emph{Separating Parsing Expression
  Grammars using Cell-Probe Lower Bounds}. arXiv:2608.29592v1, 2026.
  \href{https://arxiv.org/html/2608.29592v1}{Article}. Methodological
  source for the late-query strategy.
\item
  Young Kun Ko. \emph{An \(\Omega((\log n/\log\log n)^2)\) Cell-Probe
  Lower Bound for Dynamic Boolean Data Structures}. arXiv:2603.25914v1,
  2026, Theorem 1.1 and Section 3.
  \href{https://arxiv.org/html/2603.25914v1}{Article}. External
  lower-bound premise; source inspected 5 September 2026.
\item
  Bruno Loff, Nelma Moreira, and Rogério Reis. \emph{The computational
  power of parsing expression grammars}. Journal of Computer and System
  Sciences \textbf{111} (2020), 1--21.
  \href{https://doi.org/10.1016/j.jcss.2020.01.001}{DOI};
  \href{https://arxiv.org/pdf/1902.08272}{author version, Theorem 16}.
\item
  Bryan Ford. \emph{Parsing Expression Grammars: A Recognition-Based
  Syntactic Foundation}. POPL 2004, 111--122.
  \href{https://bford.info/pub/lang/peg.pdf}{Paper};
  \href{https://doi.org/10.1145/964001.964011}{DOI}.
\item
  Géza Horváth and Benedek Nagy. \emph{Pumping lemmas for linear and
  nonlinear context-free languages}. Acta Universitatis Sapientiae,
  Informatica \textbf{2}(2) (2010), 194--209.
  \href{https://arxiv.org/pdf/1012.0023}{Paper}, Lemma 6.
\end{enumerate}

\end{document}