Quantitative automata under probabilistic semantics

Chatterjee K, Henzinger TA, Otop J. 2016. Quantitative automata under probabilistic semantics. Proceedings of the 31st Annual ACM/IEEE Symposium. LICS: Logic in Computer Science, 76–85.

Download (ext.)
OA https://arxiv.org/abs/1604.06764 [Preprint]

DOI
10.1145/2933575.2933588
Conference Paper | Published | English

Scopus indexed
Author
Chatterjee, KrishnenduISTA ; Henzinger, Thomas AISTA ; Otop, JanISTA
Department
Chatterjee Group
Henzinger_Thomas Group
Grant
Quantitative Reactive Modeling
Rigorous Systems Engineering
Wittgenstein Award – Thomas Henzinger
Modern Graph Algorithmic Techniques in Formal Verification
Quantitative Graph Games: Theory and Applications
Efficient Algorithms for Computer Aided Verification
Abstract
Automata with monitor counters, where the transitions do not depend on counter values, and nested weighted automata are two expressive automata-theoretic frameworks for quantitative properties. For a well-studied and wide class of quantitative functions, we establish that automata with monitor counters and nested weighted automata are equivalent. We study for the first time such quantitative automata under probabilistic semantics. We show that several problems that are undecidable for the classical questions of emptiness and universality become decidable under the probabilistic semantics. We present a complete picture of decidability for such automata, and even an almost-complete picture of computational complexity, for the probabilistic questions we consider. © 2016 ACM.
Publishing Year
2016
Date Published
2016-07-05
Proceedings Title
Proceedings of the 31st Annual ACM/IEEE Symposium
Publisher
IEEE
Acknowledgement
This research was funded in part by the European Research Council (ERC) under grant agreement 267989 (QUAREM), by the Austrian Science Fund (FWF) projects S11402-N23 (RiSE) and Z211-N23 (Wittgenstein Award), FWF Grant No P23499- N23, FWF NFN Grant No S114
Page
76 - 85
Conference
LICS: Logic in Computer Science
Conference Location
New York, NY, USA
Conference Date
2016-07-05 – 2016-07-08
IST-REx-ID
1138

Cite this

Chatterjee K, Henzinger TA, Otop J. Quantitative automata under probabilistic semantics. In: Proceedings of the 31st Annual ACM/IEEE Symposium. IEEE; 2016:76-85. doi:10.1145/2933575.2933588
Chatterjee, K., Henzinger, T. A., & Otop, J. (2016). Quantitative automata under probabilistic semantics. In Proceedings of the 31st Annual ACM/IEEE Symposium (pp. 76–85). New York, NY, USA: IEEE. https://doi.org/10.1145/2933575.2933588
Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. “Quantitative Automata under Probabilistic Semantics.” In Proceedings of the 31st Annual ACM/IEEE Symposium, 76–85. IEEE, 2016. https://doi.org/10.1145/2933575.2933588.
K. Chatterjee, T. A. Henzinger, and J. Otop, “Quantitative automata under probabilistic semantics,” in Proceedings of the 31st Annual ACM/IEEE Symposium, New York, NY, USA, 2016, pp. 76–85.
Chatterjee K, Henzinger TA, Otop J. 2016. Quantitative automata under probabilistic semantics. Proceedings of the 31st Annual ACM/IEEE Symposium. LICS: Logic in Computer Science, 76–85.
Chatterjee, Krishnendu, et al. “Quantitative Automata under Probabilistic Semantics.” Proceedings of the 31st Annual ACM/IEEE Symposium, IEEE, 2016, pp. 76–85, doi:10.1145/2933575.2933588.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
URL
https://arxiv.org/abs/1604.06764
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 1604.06764

Search this title in

Google Scholar