Pumping Sequence Families: An Inexpressibility Result for Copyless Cost Register Automata

nexpressibility results are among the most natural questions in automata theory. They are also often some of the most difficult. One of the few reliable tools for proving them are pumping lemmas, but most models are too complex to admit any version of them. We propose a new tool for such proofs, called pumping sequence families. In my talk I will explain this concept and prove a pumping sequence family lemma for copyless cost register automata over Q, a model with no known pumping lemma, allowing for separation between this model and polynomially ambiguous weighted automata.