6 papers
Deterministic Suffix-reading Automata
R Keerthan, B Srivathsan, R Venkatesh +1
We introduce deterministic suffix-reading automata (DSA), a new automaton model over finite words. Transitions in a DSA are labeled with words. From a state, a DSA triggers an outg…
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…
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…
Simplifying imperfect recall games
Hugo Gimbert, Soumyajit Paul, B. Srivathsan
In games with imperfect recall, players may forget the sequence of decisions they made in the past. When players also forget whether they have already encountered their current dec…
Deterministic Suffix-reading Automata
R Keerthan, B Srivathsan, R Venkatesh +1
We introduce deterministic suffix-reading automata (DSA), a new automaton model over finite words. Transitions in a DSA are labeled with words. From a state, a DSA triggers an outg…
A Myhill-Nerode style Characterization for Timed Automata With Integer Resets
Kyveli Doveri, Pierre Ganty, B. Srivathsan
The well-known Nerode equivalence for finite words plays a fundamental role in our understanding of the class of regular languages. The equivalence leads to the Myhill-Nerode theor…