Kyle Ockerlund

dblp:433/0686 · DBLP profile ↗
← Back
1ranked-venue papers
0as first author
1since 2021 · last 2026
—ORCID · unresolved

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 1 · 1 since 2021

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Theoretical computer science
1 paper
Automata and formal languages · 75% Combinatorics and discrete mathematics · 25%

Topics — the 3 heaviest of 4, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Combinatorics and discrete mathematics
card shuffling
1.012026
Shuffles of Context-Free Languages Along Regular Trajectories · ICALP 2026
Automata and formal languages
context-free languages
1.012026
Shuffles of Context-Free Languages Along Regular Trajectories · ICALP 2026
Automata and formal languages
pushdown automata
1.012026
Shuffles of Context-Free Languages Along Regular Trajectories · ICALP 2026

Methods — techniques the papers use, named apart from their topics

language theory · 1.0determinism · 1.0
YearPublicationVenuePosition
2026 Shuffles of Context-Free Languages Along Regular Trajectories
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. 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.
Corentin Barloy, Michaël Cadilhac, Kyle Ockerlund
ICALP3