3 papers
cs.PL2026
Verifying Sequential Consistency under Bounded Preemptions
R. Govind, S. Krishna, Sanchari Sil +1
Gibbons and Korach studied a fundamental problem in 1997: given an observed sequence of reads and writes of a multi-threaded program, does there exist an interleaving which is sequ…
cs.FL2025
Reversible Pebble Transducers
Luc Dartois, Paul Gastin, L. Germerie Guizouarn +1
Deterministic two-way transducers with pebbles (aka pebble transducers) capture the class of polyregular functions, which extend the string-to-string regular functions allowing pol…
cs.FL2024
Reversible Transducers over Infinite Words
Luc Dartois, Paul Gastin, Loïc Germerie Guizouarn +2
Deterministic two-way transducers capture the class of regular functions. The efficiency of composing two-way transducers has a direct implication in algorithmic problems related t…