Weak Cost Register Automata are Still Powerful
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