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 quantitative properties of finitestate 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 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 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 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 weighted automata, an extensively studied nondeterministic model, and this connection results in new insights and new open problems.
Streaming tree transducers @cite_34 (STTs), introduced by two of the co-authors in this paper are a new formalism for expressing MSO-definable tree-to-tree and string-to-tree transductions. In comparison to some of the transducer models discussed above, STTs have distinguishing features that make them desirable as a canonical model for specifying regular or MSO-definable transductions: (1) STTs produce the output in linear time by performing a single pass over the input, (2) they preserve desirable properties such as closure under sequential composition and regular look-ahead, and (3) they have good algorithmic properties such as decidability of functional equivalence.
@cite_34
2949841359
Two well-known formalisms for the specification and computation of tree transductions are compared: the mso graph transducer and the attributed tree transducer with look-ahead, respectively. The mso graph transducer, restricted to trees, uses monadic second order logic to define the output tree in terms of the input tree. The attributed tree transducer is an attribute grammar in which all attributes are trees; it is preceded by a look-ahead phase in which all attributes have finitely many values. The main result is that these formalisms are equivalent, i.e., that the attributed tree transducer with look-ahead is an appropriate implementation model for the tree transductions that are specifiable in mso logic. This result holds for mso graph transducers that produce trees with shared subtrees. If no sharing is allowed, the attributed tree transducer satisfies the single use restriction.