Skip to main content

Weak Cost Register Automata are Still Powerful

Michaël Cadilhac ( University of Oxford )

 In this fairly technical talk, I will show that the
equivalence problem for copyless cost register automata is
undecidable, disproving a conjecture of Alur et. al from 2012. “Cost
register automata” simply means automata equipped with nonnegative
integer registers where each transition induces an update expressed
using increments and minimums; the automaton outputs a specific
register on acceptance. Further, “copyless” means that each register
is used at most once in the update functions, for each transition. The
constructions focus on simulating counter machines with zero-tests: we
will see that a copyless cost register automaton can “check” that an
input string is a correct execution of a counter machine.
Joint work with S. Almagor, F. Mazowiecki and G. A. Pérez.
Full paper: arXiv:1804.06336

Share this: