Parikh Automata: Theme and Variations on Tame Register Testing

Parikh automata and their variants focus on equipping automata with integer registers that only get tested at the end of the execution.  The original model, introduced by Klaedtke and Rueß in 2003, amounts to treating the registers separately, with updates of the form "x := x + constant", and checking whether their final values verify a simple formula.  From this, a wealth of related models has been introduced and studied: deterministic, unambiguous, with affine updates, with updates depending on the letter read, etc.  In this talk, I will review some of these variants and present old and new results on their interrelationships and intrinsic properties.  Links with algebraic automata theory, formal power series, circuit complexity, and logic will spice up the presentation, to the taste of the audience.

Joint works with Alain Finkel, Pierre McKenzie, and Andreas Krebs.