Showing 2026Show all
2 papers · 1 filter
cs.CC2026
Complexity of Consistency Testing for the Release-Acquire Semantics
R. Govind, S. Krishna, Sanchari Sil +1
In a seminal work, Gibbons and Korach studied the complexity of deciding whether an observed sequence of reads and writes of a multi-threaded program admits a sequentially consiste…
cs.FL2026
A Myhill-Nerode Characterization and Active Learning for One-Clock Timed Automata
Kyveli Doveri, Pierre Ganty, B. Srivathsan
We present a Myhill-Nerode style characterization for languages recognized by one-clock deterministic timed automata (1-DTA). Although there is only one clock, distinct automata ma…