Quantitative monitor automata

K. Chatterjee, T.A. Henzinger, J. Otop, in:, Springer, 2016, pp. 23–38.


Conference Paper | Published | English
Series Title
LNCS
Abstract
In this paper we review various automata-theoretic formalisms for expressing quantitative properties. We start with finite-state Boolean automata that express the traditional regular properties. We then consider weighted ω-automata that can measure the average density of events, which finite-state Boolean automata cannot. However, even weighted ω-automata cannot express basic performance properties like average response time. We finally consider two formalisms of weighted ω-automata with monitors, where the monitors are either (a) counters or (b) weighted automata themselves. We present a translation result to establish that these two formalisms are equivalent. Weighted ω-automata with monitors generalize weighted ω-automata, and can express average response time property. They present a natural, robust, and expressive framework for quantitative specifications, with important decidable properties.
Publishing Year
Date Published
2016-08-31
Volume
9837
Page
23 - 38
Conference
SAS: Static Analysis Symposium
Conference Location
Edinburgh, United Kingdom
Conference Date
2016-09-08 – 2016-09-10
IST-REx-ID

Cite this

Chatterjee K, Henzinger TA, Otop J. Quantitative monitor automata. In: Vol 9837. Springer; 2016:23-38. doi:10.1007/978-3-662-53413-7_2
Chatterjee, K., Henzinger, T. A., & Otop, J. (2016). Quantitative monitor automata (Vol. 9837, pp. 23–38). Presented at the SAS: Static Analysis Symposium, Edinburgh, United Kingdom: Springer. https://doi.org/10.1007/978-3-662-53413-7_2
Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. “Quantitative Monitor Automata,” 9837:23–38. Springer, 2016. https://doi.org/10.1007/978-3-662-53413-7_2.
K. Chatterjee, T. A. Henzinger, and J. Otop, “Quantitative monitor automata,” presented at the SAS: Static Analysis Symposium, Edinburgh, United Kingdom, 2016, vol. 9837, pp. 23–38.
Chatterjee K, Henzinger TA, Otop J. 2016. Quantitative monitor automata. SAS: Static Analysis Symposium, LNCS, vol. 9837. 23–38.
Chatterjee, Krishnendu, et al. Quantitative Monitor Automata. Vol. 9837, Springer, 2016, pp. 23–38, doi:10.1007/978-3-662-53413-7_2.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar