Regular Functions, Cost Register Automata, and Generalized Min-Cost Problems

Details Regular Functions, Cost Register Automata, and Generalized Min-Cost Problems Regular Functions, Cost Register Automata, and Generalized Min-Cost Problems

2011-11-02

arxiv.org/abs/1111.0670v2

Computer Science

Formal Languages and Automata Theory

ICALP12 submission, technical report/extended version. 33 pages+title page

Scientific paper

Motivated by the successful application of the theory of regular languages to formal verification of finite-state systems, there is a renewed interest in developing a theory of analyzable functions from strings to numerical values that can provide a foundation for analyzing {\em quantitative} properties of finite-state systems. In this paper, we propose a deterministic model for associating costs with strings that is parameterized by operations of interest (such as addition, scaling, and $\min$), a notion of {\em regularity} that provides a yardstick to measure expressiveness, and study decision problems and theoretical properties of resulting classes of cost functions. Our definition of regularity relies on the theory of string-to-tree transducers, and allows associating costs with events that are conditional upon regular properties of future events. Our model of {\em cost register automata} allows computation of regular functions using multiple "write-only" registers whose values can be combined using the allowed set of operations. We show that classical shortest-path algorithms as well as algorithms designed for computing {\em discounted costs}, can be adopted for solving the min-cost problems for the more general classes of functions specified in our model. Cost register automata with $\min$ and increment give a deterministic model that is equivalent to {\em weighted automata}, an extensively studied nondeterministic model, and this connection results in new insights and new open problems.

Affiliated with

Also associated with

No associations

Rating

Regular Functions, Cost Register Automata, and Generalized Min-Cost Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Regular Functions, Cost Register Automata, and Generalized Min-Cost Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Regular Functions, Cost Register Automata, and Generalized Min-Cost Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-700447