Boker, Udi ;
Henzinger, Thomas A.
Determinizing DiscountedSum Automata
Abstract
A discountedsum automaton (NDA) is a nondeterministic finite automaton with edge weights, which values a run by the discounted sum of visited edge weights. More precisely, the weight in the ith position of the run is divided by lambda^i, where the discount factor lambda is a fixed rational number greater than 1. Discounted summation is a common and useful measuring scheme, especially for infinite sequences, which reflects the assumption that earlier weights are more important than later weights. Determinizing automata is often essential, for example, in formal verification, where there are polynomial algorithms for comparing two deterministic NDAs, while the equivalence problem for NDAs is not known to be decidable.
Unfortunately, however, discountedsum automata are, in general, not determinizable: it is currently known that for every rational discount factor 1 < lambda < 2, there is an NDA
with lambda (denoted lambdaNDA) that cannot be determinized.
We provide positive news, showing that every NDA with an integral factor is determinizable. We also complete the picture by proving that the integers characterize exactly the discount factors that guarantee determinizability: we show that for every nonintegral rational factor lambda, there is a nondeterminizable lambdaNDA.
Finally, we prove that the class of NDAs with integral discount factors enjoys closure under the algebraic operations min, max, addition, and subtraction, which is not the case for general NDAs nor for deterministic NDAs. This shows that for integral discount factors, the class of NDAs forms an attractive specification formalism in quantitative formal verification. All our results hold equally for automata over finite words and for automata over infinite words.
BibTeX  Entry
@InProceedings{boker_et_al:LIPIcs:2011:3224,
author = {Udi Boker and Thomas A. Henzinger},
title = {{Determinizing DiscountedSum Automata}},
booktitle = {Computer Science Logic (CSL'11)  25th International Workshop/20th Annual Conference of the EACSL},
pages = {8296},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897323},
ISSN = {18688969},
year = {2011},
volume = {12},
editor = {Marc Bezem},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3224},
URN = {urn:nbn:de:0030drops32243},
doi = {10.4230/LIPIcs.CSL.2011.82},
annote = {Keywords: Discountedsum automata, determinization, quantitative verification}
}
31.08.2011
Keywords: 

Discountedsum automata, determinization, quantitative verification 
Seminar: 

Computer Science Logic (CSL'11)  25th International Workshop/20th Annual Conference of the EACSL

Issue date: 

2011 
Date of publication: 

31.08.2011 