Shuffles of Context-Free Languages along Regular Trajectories
Corentin Barloy, Michaël Cadilhac, Kyle Ockerlund · 2026
Read Shuffles of Context-Free Languages along Regular Trajectories by Corentin Barloy, Michaël Cadilhac, Kyle Ockerlund (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-26162.txt.
Introduction
Barloy, Cadilhac, and Ockerlund study when shuffling two context-free languages stays context-free. A shuffle interleaves two words letter by letter, like a scheduler merging tasks. Regular languages are closed under shuffles, but context-free ones are not. The authors restrict shuffles to regular trajectories, which act as scheduling rules. They build tools to prove a given trajectory always breaks the property. For deterministic languages, they find a clean three-way split of trajectories. The work also settles an open question about pushdown stack use.
Catalog record
| CREATOR | Corentin Barloy, Michaël Cadilhac, Kyle Ockerlund |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 120511 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.26162
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Shuffles of Context-Free Languages along Regular Trajectories Corentin Barloy, Michaël Cadilhac, Kyle Ockerlund Abstract In single-core processors, when multiple processes execute concurrently, they are, in practice, intertwined by a scheduler as a single thread of execution. The language-theoretic operation that corresponds to this is the shuffle of two languages: in general, this is defined as the set of words obtained by interleaving words from the first and second language in an arbitrary fashion. It is well known that regular languages are closed under shuffles, while context-free languages (CFL) are not. Following an established line of research, this paper considers shufflings according to regular “trajectories,” that is, subject to scheduling constraints expressed by an automaton. Unsurprisingly, some trajectories, such as “a word from the first language first, then a word from the second,” allow for CFLs to be shuffled into CFLs, while some other trajectories 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. These results are based on intricate expressiveness lemmas for CFLs and DCFLs of independent interest, the latter lemma relying on a recent result of Jančar and Šíma (MFCS’2021). University of [email protected] DePaul University, [email protected] Google, [email protected] \Cref prop:nosimplecflp is due to Georg Zetzsche. We thank Arka Ghosh and Petra Wolf for stimulating discussions on this topic. keywords Context-free languages, shuffles, concurrency ccs Theory of computation Concurrency ccs Theory of computation Grammars and context-free languages † † runningauthor: C. Barloy, M. Cadilhac, K. Ockerlund † † copyright: Corentin Barloy, Michaël Cadilhac, and Kyle Ockerlund To facilitate the reading, we provide a table of contents below. We further provide hyperlinks for navigating between statements in the main text and proofs in the appendix. To go to the proof of a statement, click “ \faArrowDown ” in the left margin, and then click “ \faArrowUp ” to go back to the statement in the main text. 1 Introduction In the theory of concurrency and parallel computation, many composition operations ultimately boil down to a variant of the shuffle operation (see, e.g., [ 14 , 17 , 13 , 7 , 3 , 1 , 16 ] for early examples from the 1970s to the 1990s). The theoretical study of shuffles was thus initiated, starting in the 1970s, as a means of formalizing interactions and synchronization of processes. Types of shuffles. As concurrency may take many forms, theoretical work has turned to restricting the “full” shuffle operation to more constrained interleavings between processes. Bérard [ 2 ] , in particular, introduced literal shuffles , that enforce that the processes strictly alternate — she refers to it as modeling step-lock transmission in single communication channels. Further widening the definition of shuffles, Mateescu et al. [ 11 ] introduced shuffles along a trajectory , where a trajectory is a language of words over \{s,t\} , and such a word indicates in which order the processes are scheduled ( s for the first one, t for the second). For instance, (s+t)^{*} is the trajectory of the full shuffle, and (st)^{*} would force that the two processes strictly alternate, during the same length of time. Shuffles along trajectories generalize many language-theoretic operations, including for example concatenation (trajectory s^{*}t^{*} ). Questions about shuffles. Historically, the most prominent questions about shuffles revolved around closure properties. While regular languages are easily seen to be closed under the full shuffle, Latteux famously showed [ 10 ] , in the late 1970s, that the full shuffle of two CFLs is a CFL if, and only if, one of the two languages is regular. 1 1 1 Let us note here that this only holds if the two languages are over disjoint alphabets, which is a standard assumption we will be making. Shuffling languages over a common alphabet is, in addition to being less natural in most concurrent scenarios, not well behaved: one can show that for any language E\subseteq\Sigma^{*} containing the empty word \varepsilon , with \#\notin\Sigma , the full shuffle of \{w_{1}\#w_{2}\mid w_{1}\in\Sigma^{*}\land w_{2}\in E\} and \{w_{1}\#w_{2}\mid w_{1}\in E\land w_{2}\in\Sigma^{*}\} is simply \Sigma^{*}\#\Sigma^{*}\#\Sigma^{*} . In fact, Ogden et al. [ 14 ] exhibited DCFLs that shuffle into NP-complete languages. On the other hand, Bérard [ 2 ] shows that there are nonregular CFLs which can be shuffled along the trajectory (st)^{*}(s^{*}+t^{*}) into a CFL. She asks in particular if this is also true of the trajectory (s^{*}+t^{*})(st)^{*}(s^{*}+t^{*}) , a question that has been open since then. Mateescu et al. [ 11 ] expand on these results, focusing in particular on regular trajectories (Section 5 therein). They show, for instance, that the shuffle of a CFL and a regular language along a regular trajectory is always CFL. This rugged landscape leaves open an important question: which regular trajectories do preserve context-freeness (in the sense that the shuffle of two CFLs is CFL)? These questions can be seen as variants of — or a preliminary step to — the so-called parallelization problem , which asks, given a nonCFL, whether it is expressible as the shuffle along some trajectory of two CFLs. Crisp answers to these questions would not only clarify the landscape of regular trajectories, but allow to understand when regular schedulers over context-free processes require additional computational power to be seen as a single thread of context-free execution. Contributions. The contributions of this paper follow two broad lines: 1. In \Cref sec:coup, we investigate couplings within PDA: Briefly, two subsections of a word are said to be coupled by a PDA if, for all accepting runs, a symbol is pushed during the first subsection, and popped during the second. We show, relying on some surgery on the runs, that if couplings are rare, then the PDA recognizes a regular language. A strengthening is provided for the case where the PDA, which may itself be nondeterministic, recognizes a deterministic CFL, relying on a deep result of Jančar and Šíma [ 8 ] . The proofs of these lemmas, dubbed the Coupling Lemmas, are provided in \Cref sec:couppda,sec:coupdpda, which can be safely skipped on first reading. We note that these sections are entirely independent of shuffles; they simply provide a toolbox to study how couplings appear. 2. In \Cref sec:shuf, we turn to shufflings proper. We first study how couplings survive a shuffle, leading to two so-called Resilience Lemmas. We then show two salient results: (1) We provide infinite families of trajectories that always shuffle two nonregular CFLs into a nonCFL; and (2) We partition regular trajectories into three categories: CFL ′ \babelhyphen nobreaksafe , under which shuffles of CFLs are always CFLs; DCFL ′ \babelhyphen nobreakhostile , under which shuffles of nonregular DCFLs are always nonCFL; DCFL ′ \babelhyphen nobreakmixed , under which nonregular DCFLs shuffle sometimes into CFLs, sometimes into nonCFLs. We give a decidable characterization of each of these categories. We note that we partially answer Bérard’s open question: we can show that the shuffle along (s^{*}+t^{*})(st)^{*}(s^{*}+t^{*}) never preserves nonregular DCFLs, but we cannot answer the same for CFLs. However, our results also imply that the same is true for the trajectory (st)^{*}(s^{*}+t^{*}) , for