Value Automata with Filters

Abstract

We propose to study value automata with filters, a natural generalization of regular cost automata to nondeterminism. Models such as weighted automata and Parikh automata appear naturally as specializations. Results on the expressiveness of this model offer a general understanding of the behavior of the models that arise as special cases. A landscape of such restrictions is drawn.

arXiv comment8 pages, presented in the short track of NCMA'15, work in progress