Decision problems for additive regular functions

We introduce cost register automata (CRA) -- this is a deterministic model to associate costs with strings that is parametrized by operations of interest (such as addition, scaling, and minimum), and a notion of regularity that provides a yardstick to measure expressiveness. Our notion of regularity relies on the notion of string-to-tree transducers, and allows associating costs with events that are conditioned on regular properties of future events. CRAs compute regular functions using multiple write-only registers whose values can be combined using the allowed set of operations. We then discuss various analysis problems associated with CRAs and regular functions, including the decidability of equivalance and containment, register and state minimization, and Angluin-style learning of cost functions.

Authors

• Rajeev Alur University of Pennsylvania
• Mukund Raghothaman

Keywords

No keywords are indexed for this paper.