Shuffles of Context-Free Languages along Regular Trajectories

Corentin Barloy; Kyle Ockerlund; Micha\"el Cadilhac

arxiv: 2603.26162 · v2 · pith:NKAY3YMSnew · submitted 2026-03-27 · 💻 cs.FL

Shuffles of Context-Free Languages along Regular Trajectories

Corentin Barloy , Micha\"el Cadilhac , Kyle Ockerlund This is my paper

Pith reviewed 2026-05-14 23:23 UTC · model grok-4.3

classification 💻 cs.FL

keywords context-free languagesshuffleregular trajectoriespushdown automatadeterministic context-free languagesclosure propertiesinterleaving

0 comments

The pith

Regular trajectories can force the shuffle of any two nonregular context-free languages to leave the context-free class.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops criteria for regular trajectories that guarantee the interleaving of two context-free languages produces a non-context-free result whenever both inputs are nonregular. It supplies lemmas on the stack operations required by pushdown automata to accept nonregular languages and uses those to build explicit counterexamples for bad trajectories. For deterministic context-free languages the same approach yields a clean three-way split of trajectories according to whether their shuffles stay deterministic context-free, become context-free but nondeterministic, or leave the context-free class altogether. The work also shows that a known result for deterministic languages does not extend to the general case, requiring separate arguments for each.

Core claim

Regular trajectories admit a robust test that identifies those under which any shuffle of two nonregular context-free languages is itself non-context-free; the test rests on stack-invocation patterns that every accepting pushdown automaton for a nonregular language must exhibit. For deterministic context-free languages the trajectories partition into three families: those whose shuffles remain deterministic context-free, those whose shuffles are context-free but not deterministic, and those whose shuffles are not context-free.

What carries the argument

Lemmata that characterize the necessary stack pushes and pops performed by any pushdown automaton accepting a nonregular context-free language or deterministic context-free language.

If this is right

Trajectories satisfying the paper's syntactic conditions always map pairs of nonregular CFLs to non-CFLs.
DCFL trajectories divide cleanly into three classes according to the language family produced by their shuffles.
The Jančar-Šima result on deterministic languages cannot be lifted to arbitrary CFLs, so separate machinery is required for the two settings.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The classification supplies a practical check that a scheduler designer could run on a given interleaving policy to decide whether it risks generating non-context-free behavior from simple input processes.
Because the non-generalization result is proved by counterexample, it points to a concrete difference in how nondeterminism interacts with stack discipline under arbitrary versus deterministic acceptance.
The same stack-pattern technique may be reusable for other language families whose acceptance requires auxiliary memory, such as linear languages or certain tree languages.

Load-bearing premise

The stack-usage patterns described in the lemmas are unavoidable for every pushdown automaton that accepts a nonregular language.

What would settle it

An explicit regular trajectory together with two concrete nonregular context-free languages whose shuffle along that trajectory is still context-free would refute the claimed toolset.

read the original abstract

In single-core processors, concurrency requires that multiple processes be interleaved into a single thread of execution by a scheduler. The language-theoretic operation that corresponds to this is the shuffle of two languages: the set of words obtained by interleaving a word from each language in an arbitrary, letter-wise fashion. It is well known that regular languages are closed under shuffles, while context-free languages (CFLs) are not. Following an established line of research, this paper considers shuffles according to regular ``trajectories,'' that is, subject to scheduling constraints expressed by an automaton. Unsurprisingly, some trajectories allow for CFLs to be shuffled into CFLs (e.g., simple concatenation of the two words), while others do not. This paper provides a robust toolset to show that a given trajectory would always shuffle two nonregular CFLs into a nonCFL. In the case of deterministic CFLs (DCFLs), a salient trichotomy of trajectories depending on how they shuffle DCFLs is provided. Notably, these results are based on lemmata of independent interest regarding how pushdown automata (PDA) must invoke the stack when accepting a nonregular CFL or DCFL. The latter case relies on a recent result of Jan\v{c}ar and \v{S}\'ima (MFCS'2021); answering an open question therein, it is demonstrated that said result cannot be generalized to arbitrary CFLs, leading to dedicated machinery for both cases.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives concrete lemmata on PDA stack usage that let you prove many regular trajectories force non-closure when shuffling non-regular CFLs, plus a trichotomy for the deterministic case.

read the letter

The main new material is a toolkit of lemmata that characterize how pushdown automata must call on their stacks to accept non-regular CFLs. The authors use these to show that for a range of regular trajectories the shuffle of two such languages falls outside the CFLs. For deterministic CFLs they add a clean three-way split of trajectories according to whether the shuffle stays deterministic context-free, becomes context-free but not deterministic, or leaves the CFLs entirely. They also show why the 2021 Jančar-Šima result on deterministic cases does not extend to general CFLs and supply separate arguments instead. That directly answers an open question left in the earlier paper. The constructions look useful for anyone who needs to settle closure questions under constrained interleaving, which comes up in scheduling and concurrency models. The stack-invocation properties are the load-bearing part. If they miss some accepting runs, the non-closure claims for arbitrary CFLs would not go through. The abstract indicates the proofs are self-contained once the lemmata are granted, but a referee would still have to verify that the stack-height and invocation rules cover every case. The citation pattern is appropriate; the work builds directly on the 2021 result without circularity. This is for people already working in automata theory who want practical tools rather than high-level existence arguments. It is worth sending out for peer review. The results are focused and the machinery is new enough to deserve checking.

Referee Report

2 major / 2 minor

Summary. The manuscript studies shuffles of context-free languages (CFLs) and deterministic CFLs (DCFLs) along regular trajectories. It develops lemmata on pushdown-automaton stack invocations to establish a toolset proving that certain trajectories always map pairs of nonregular CFLs to non-CFLs; for DCFLs it supplies a trichotomy classifying trajectories by their effect on DCFL shuffles. The DCFL results rest on Jančar and Šima (MFCS 2021), which the paper shows does not generalize to arbitrary CFLs, necessitating separate machinery.

Significance. If the stack-invocation lemmata are correct, the work supplies a concrete methodological advance for proving non-closure under constrained shuffle operations, extending the line of research on trajectory-controlled interleaving. The DCFL trichotomy offers a clean classification with potential for further applications, and the negative result on generalization of the 2021 theorem is a useful clarification. These contributions would be of interest to the formal-language community.

major comments (2)

[Section on stack-invocation lemmata (likely §3–4)] The section presenting the PDA stack-invocation lemmata for nonregular CFLs: these lemmata are load-bearing for the central claim that certain trajectories force non-CFL shuffles; the manuscript supplies only a high-level outline without complete derivations or exhaustive case analysis, so it is impossible to confirm that every accepting computation satisfies the claimed height and invocation properties.
[Section on DCFL trichotomy (likely §5)] The DCFL trichotomy section: the application of Jančar and Šima (MFCS 2021) is stated to hold without generalization issues, yet the paper separately demonstrates failure for general CFLs; an explicit statement of the precise conditions under which the trichotomy applies (including any restrictions on the trajectory automaton) is required to ensure the classification is exhaustive.

minor comments (2)

[Abstract] Abstract: the three classes of the DCFL trichotomy are alluded to but never named or briefly characterized; adding one sentence defining them would improve immediate readability.
[Preliminaries] Notation and examples: a concrete small automaton illustrating a regular trajectory (e.g., a simple periodic scheduler) would help readers connect the formal definition to the later theorems.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments. We address the major comments point by point below.

read point-by-point responses

Referee: [Section on stack-invocation lemmata (likely §3–4)] The section presenting the PDA stack-invocation lemmata for nonregular CFLs: these lemmata are load-bearing for the central claim that certain trajectories force non-CFL shuffles; the manuscript supplies only a high-level outline without complete derivations or exhaustive case analysis, so it is impossible to confirm that every accepting computation satisfies the claimed height and invocation properties.

Authors: We agree that the current version presents the stack-invocation lemmata at a high level. In the revision we will supply complete derivations together with an exhaustive case analysis of accepting PDA computations, explicitly verifying the claimed bounds on stack height and the number of stack invocations for every path. This will render the lemmata fully verifiable and strengthen the non-closure arguments that rely on them. revision: yes
Referee: [Section on DCFL trichotomy (likely §5)] The DCFL trichotomy section: the application of Jančar and Šima (MFCS 2021) is stated to hold without generalization issues, yet the paper separately demonstrates failure for general CFLs; an explicit statement of the precise conditions under which the trichotomy applies (including any restrictions on the trajectory automaton) is required to ensure the classification is exhaustive.

Authors: We will insert a dedicated paragraph that states the precise conditions under which the trichotomy holds: it applies exactly when the input languages are deterministic context-free and the trajectory automaton is deterministic and complete. We will also note the explicit restrictions on the trajectory automaton that are inherited from Jančar and Šima (MFCS 2021) and contrast them with the counter-examples showing that the same statement fails for nondeterministic CFLs. This will make the scope of the classification exhaustive and unambiguous. revision: yes

Circularity Check

0 steps flagged

No significant circularity; new lemmata and external citation are independent

full rationale

The paper's central toolset and DCFL trichotomy rest on newly introduced lemmata characterizing necessary stack usage by PDAs for nonregular CFLs and DCFLs. These lemmata are presented as results of independent interest. The deterministic case additionally invokes an external result of Jančar and Šima (MFCS'2021) from different authors; the paper explicitly shows this result fails to generalize to arbitrary CFLs and supplies dedicated machinery instead. No equation or claim reduces by construction to a fitted parameter, self-definition, or self-citation chain. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

The paper rests on standard automata theory and one external result; no free parameters or invented entities are introduced.

axioms (3)

standard math Standard properties of pushdown automata, regular languages, and closure operations
Invoked throughout the development of the toolset and trichotomy.
domain assumption Stack-invocation behavior of PDAs for nonregular CFLs and DCFLs as per cited lemmata
Central to both the general toolset and the DCFL trichotomy.
domain assumption Result of Jančar and Šima (MFCS'2021) on deterministic pushdown automata
Used directly for the DCFL case; the paper shows it does not extend to general CFLs.

pith-pipeline@v0.9.0 · 5568 in / 1334 out tokens · 29298 ms · 2026-05-14T23:23:18.890085+00:00 · methodology

Shuffles of Context-Free Languages along Regular Trajectories

Core claim

What carries the argument

If this is right

Where Pith is reading between the lines

Load-bearing premise

What would settle it

discussion (0)