2026/03/27 by Corentin Barloy, Michaël Cadilhac, Kyle Ockerlund · 1 voice
Computer Science · #Embedded Systems Design Techniques #Interconnection Networks and Systems #Lemma (botany) #Parallel Computing and Optimization Techniques #Regular language #Salient #Set (abstract data type) #Trichotomy (philosophy) #Word (group theory) #cs.FL
paper · pdf · open access · doi:10.48550/arxiv.2603.26162
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2026/03/27 · arxiv published 2026/03/27 · openalex created_date 2026/03/31 · arxiv updated 2026/05/12 · openalex updated_date 2026/07/28
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čar and Šíma (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.