Earlier Version

Nested weighted automata

K. Chatterjee, T.A. Henzinger, J. Otop, Nested Weighted Automata, IST Austria, 2014.

OA 573.46 KB

Technical Report | Published | English
Series Title
IST Austria Technical Report
Recently there has been a significant effort to add quantitative properties in formal verification and synthesis. While weighted automata over finite and infinite words provide a natural and flexible framework to express quantitative properties, perhaps surprisingly, several basic system properties such as average response time cannot be expressed with weighted automata. In this work, we introduce nested weighted automata as a new formalism for expressing important quantitative properties such as average response time. We establish an almost complete decidability picture for the basic decision problems for nested weighted automata, and illustrate its applicability in several domains.
Publishing Year
Date Published

Cite this

Chatterjee K, Henzinger TA, Otop J. Nested Weighted Automata. IST Austria; 2014. doi:10.15479/AT:IST-2014-170-v1-1
Chatterjee, K., Henzinger, T. A., & Otop, J. (2014). Nested weighted automata. IST Austria. https://doi.org/10.15479/AT:IST-2014-170-v1-1
Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. Nested Weighted Automata. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-170-v1-1.
K. Chatterjee, T. A. Henzinger, and J. Otop, Nested weighted automata. IST Austria, 2014.
Chatterjee K, Henzinger TA, Otop J. 2014. Nested weighted automata, IST Austria, 27p.
Chatterjee, Krishnendu, et al. Nested Weighted Automata. IST Austria, 2014, doi:10.15479/AT:IST-2014-170-v1-1.
Main File(s)
File Name
Access Level
OA Open Access
Last Uploaded

Material in IST:
Later Version
Later Version
Later Version


Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar