| Summary: | Regular cost functions have been introduced recently as an extension to the
notion of regular languages with counting capabilities, which retains strong
closure, equivalence, and decidability properties. The specificity of cost
functions is that exact values are not considered, but only estimated. In this
paper, we define an extension of Linear Temporal Logic (LTL) over finite words
to describe cost functions. We give an explicit translation from this new logic
to two dual form of cost automata, and we show that the natural decision
problems for this logic are PSPACE-complete, as it is the case in the classical
setting. We then algebraically characterize the expressive power of this logic,
using a new syntactic congruence for cost functions introduced in this paper.
|
|---|