Source-linked AI summary
Solution to Bucher's density problem for context-free languages
Rastko Maslic, Jeffrey Shallit
TL;DR
Bucher asked whether context-free languages L ⊆ U with infinite difference always admit a context-free intermediate K that leaves both differences infinite; this paper proves they do not. It constructs an infinite D with context-free complement that regular languages cannot split into two infinite parts, then uses a grammar argument to transfer that obstruction to K. The result holds with L and U over a binary alphabet.
Problem
Bucher asked whether context-free L ⊆ U with infinite U \ L must contain a context-free K for which both K \ L and U \ K are infinite.
Source: §1.1 · pp. 1–2Method
The paper constructs an infinite D with context-free complement that regular languages cannot split into two infinite parts, then uses a grammar argument to relate any intermediate K to a regular language.
Source: §3 · p. 6, §4.4 · p. 11, §5.2 · p. 14Results
Every context-free K between the constructed binary context-free L and U has finite K \ L or finite U \ K, although U \ L is infinite.
Source: §1.1 · p. 2, §6 · p. 15Takeaways & Limitations
The construction gives a negative answer to Bucher’s question, including for endpoints over a binary alphabet.
Source: §1.1 · p. 2The formula-testing automaton assumes identical copies; a separate machine must detect disagreements between them.
Source: §3 · p. 7
Abstract
from arXiv · showhide
In 1980 Bucher asked whether, given context-free languages $L\subseteq U$ with $U\setminus L$ infinite, there must be a context-free language $K$ between them for which both $K\setminus L$ and $U\setminus K$ are infinite. We give a negative answer. We first construct an infinite language $D$ with context-free complement such that, for every regular language $R$, either $D\cap R$ or $D\setminus R$ is finite. The words of $D$ encode computations of factorials; repetition of letters ensures that each finite automaton either accepts all but finitely many words of $D$ or rejects all but finitely many words of $D$, while a one-counter automaton recognizes errors in the encodings. We then construct $L$ and $U$ from the complement of $D$. A grammar argument shows that any context-free intermediate language $K$ would divide $D$ in the same way as some regular language. This proves the required impossibility. Both $L$ and $U$ can be taken over a binary alphabet.
1 Bucher’s problem and the main theorem
Bucher’s question asks whether a context-free language can always lie strictly between two context-free languages with infinite difference; the paper proves that it cannot. The proof constructs an infinite language that regular languages cannot split into two infinite parts, then uses a grammar argument to transfer that property to context-free intermediates.
1.3 Earlier work
- Earlier work left the context-free case open; Bucher had affirmative answers for regular, recursive, and deterministic context-sensitive languages.The problem arose in connection with density questions in grammatical similarity.Source: §1.1 · pp. 1–2
1.1 The original question
- Every context-free intermediate K has either finite K \ L or finite U \ K, even when L and U are binary context-free languages with infinite difference.This gives a negative answer to Bucher’s question.Source: §1.1 · p. 2
1.2 Outline of the proof
- The proof constructs an infinite D such that every regular R leaves either D ∩ R or D \ R finite, then uses this property to rule out an infinite split by K.A grammar argument makes K agree with a suitable regular language on the relevant words.Source: §1.2 · pp. 2–3
2 Extracting a regular language from a grammar
The section extracts a regular language from a context-free grammar for an intermediate language. This lets the authors express the two gaps around that intermediate language as images of a regular split of D.
Extracting a regular language from a grammar
- A context-free intermediate K ⊆ U_A yields a regular R ⊆ Σ* whose membership decisions match K on words w#wR indexed by D.The grammar argument extends a marked-palindrome consequence of an earlier characterization.Source: §2 · p. 4
- Variables are classified by whether their derived words contain zero or one separator, and off-path variables in a parse tree for w#wR must each derive only one terminal word.Otherwise substitution would create a word outside both the diagonal language and A#AR, contradicting K ⊆ U_A.Source: §2 · p. 4
- Replacing zero-separator variables by fixed words yields a grammar with productions X → uYv or X → u#v, which defines a regular language R.The finite graph of these productions becomes a finite automaton; accepting paths correspond to grammar derivations.Source: §2 · pp. 4–5
- For the constructed languages, K \ L = Δ(D ∩ R) and U \ K = Δ(D \ R), so the property of D makes one difference finite while Δ(D) remains infinite.The map w ↦ w#wR is injective, preserving the infinitude of D in its image.Source: §2 · p. 5
3 Testing equations with one counter
The section describes one-counter automata for testing linear conditions used to recognize incorrect computation encodings. Repetition of identical blocks lets one counter evaluate fixed Boolean formulas, while a separate test detects disagreement between copies.
Testing equations with one counter
- A one-counter automaton combines finite-state control with a nonnegative counter, and its accepted languages are context-free.Finite unions and intersections with regular languages are also handled by these automata.Source: §3 · p. 6
- Fixed integer coefficients let the counter track a linear expression in block lengths, so its sign tests a fixed linear equality or inequality.The coefficients are built into the automaton rather than supplied in the input.Source: §3 · p. 6
- With r identical copies of the encoded blocks and r at least the number of comparisons, the automaton can evaluate a fixed Boolean formula by testing one comparison per copy.It stores each truth value in finite control and empties the counter between tests.Source: §3 · pp. 6–7
- The formula-testing machine does not check that the copies are identical; a separate machine detects disagreements, and the error languages are combined by finite union.This avoids requiring closure under intersections of arbitrary context-free languages.Source: §3 · p. 7
4 Encoding computations
The paper encodes computations as repeated-letter blocks whose lengths represent configurations, then uses fixed arithmetic tests to characterize valid computation words. One-counter automata can recognize exactly the words that fail those tests.
4.1 The programs to be encoded
- Programs have finite control and nonnegative integer registers; instructions test register conditions, apply simultaneous affine updates, and may be padded with idle steps after halting.One instruction application counts as one step regardless of register sizes.Source: §4.1 · p. 7
4.2 Words representing steps and computations
- Each computation step is encoded by blocks whose lengths represent the old and new configurations, recovered by dividing by a common multiplier and subtracting one.Repeating each step encoding r times provides copies for testing several equations about that step.Source: §4.2 · p. 8
- A nondeterministic one-counter automaton recognizes the complement of the encoded computation language, with every block length a positive multiple of the represented output.The encoding uses the same output value as the number of records and the multiplier for block lengths.Source: §4.2 · p. 8
4.3 Writing the tests in terms of block lengths
- Four fixed Boolean formulas test nonnegative coordinates, initial and final configurations, and permitted transitions; r agreeing copies let a one-counter automaton evaluate them.The formulas are written in block lengths using fixed integer coefficients.Source: §4.3 · p. 9
4.4 Conditions for a word to encode a computation
- A word encodes a computation exactly when it has the required record format and satisfies the copy, multiplier, step-link, formula, and equation conditions.The induction proving the characterization shows that the initial and instruction equations force represented register values to be integers.Source: §4.4 · pp. 10–11
4.5 Recognizing the words that fail these conditions
- A finite union of one-counter error tests accepts every word outside the computation language and no valid encoded computation.The tests check format, equalities, formulas, and equations using additions and subtractions of input block lengths.Source: §4.5 · pp. 11–12
5 Factorial computations and finite automata
A fixed register program computes factorials, producing a unique halting computation for each n ≥ 4 whose length is less than n!. Its encodings form an infinite language with context-free complement, while every regular language accepts or rejects all but finitely many of them.
5.1 A fixed program for factorials
- For each n ≥ 4, the program has a unique computation halting with output n!, and its step count t_n is less than n!.In state C, the program maintains f = i!; state R multiplies by repeated addition.Source: §5.1 · p. 13
- Padding each factorial computation to n! steps yields distinct words forming an infinite language D whose complement is context-free.The encodings use the multiplier n! for their repeated-letter block lengths.Source: §5.1 · p. 14
5.2 Why finite automata eventually give the same answer
- A map on q states has equal powers at q! and kq! steps, which underlies the eventual uniform acceptance or rejection of the encoded words.The proof applies this finite-state fact to the letter transitions of a deterministic automaton.Source: §5.2 · p. 14
- For every regular language R, either D ∩ R or D \ R is finite.For a q-state automaton, sufficiently large n make each block length a multiple of q!, so its effect stabilizes across the words w_n.Source: §5.2 · p. 14
6 Proof of the main theorem
The proof first obtains the main theorem’s languages over a twelve-letter alphabet, then recodes them over a binary alphabet. The recoding preserves context-freeness and the infinite difference, so a context-free intermediate language would contradict Proposition 3.
6 Proof of the main theorem
- The proof constructs L and U from A and D, establishing the theorem’s properties over a twelve-letter alphabet.Here A is context-free and D is infinite.Source: §6 · p. 15
- Mapping each of the twelve symbols to a distinct four-bit word gives an injective homomorphism h.The map assigns four-bit binary expansions to a_j for 0 ≤ j ≤ 10 and maps # to 1011.Source: §6 · p. 15
- Because h is injective and context-free languages are closed under homomorphism, h(L) and h(U) are context-free and their difference remains infinite.h(U) \ h(L) = h(U \ L).Source: §6 · p. 15
- Any context-free intermediate K′ would induce a context-free K between L and U with both differences infinite, contradicting Proposition 3.The proof uses inverse homomorphism to obtain K = h−1(K′).Source: §6 · p. 15
7 Declaration of AI usage
The authors describe the LLM’s role in developing the paper and state that they take responsibility for its claims.
7 Declaration of AI usage
- The authors say most of the paper’s ideas were obtained by LLM GPT 6 Astra.The first author initially obtained a proof with the LLM.Source: §7 · p. 15
- Astra repeatedly modified the initial proof while following suggestions from the second author.Source: §7 · p. 15
- The second author rewrote some text, and the authors take full responsibility for all claims.Source: §7 · p. 15