Founding agency: National Science Centre (NCN), Poland
Funding subtype: SONATA 8
Duration: 07.2015 - 10.2018
Abstract:
The goal of this project is to advance weighted automata techniques motivated by
the need of expressing natural quantitative properties.
We divide the goal into three tasks with different levels of abstraction,
from the most theoretical to the most applied task:
classification of quantitative properties w.r.t. the computational complexity of their verification problems,
development of new weighted automata models, which express natural quantitative properties, and
construction of efficient algorithms for the verification problems on weighted automata.
Investigators:
Jan Otop, Principal Investigator
Jakub Michaliszyn
Publications:
Krishnendu Chatterjee, Thomas A. Henzinger, Jan Otop: Computing Average Response Time. Principles of Modeling 2018
Jakub Michaliszyn, Jan Otop: Non-deterministic Weighted Automata on Random Words. CONCUR 2018
Krishnendu Chatterjee, Thomas A. Henzinger, Rasmus Ibsen-Jensen, Jan Otop: Edit Distance for Pushdown Automata. Logical Methods in Computer Science 13(3)
Krishnendu Chatterjee, Thomas A. Henzinger, Jan Otop: Nested Weighted Automata. ACM TOCL 18(4): 31
Thomas A. Henzinger, Jan Otop: Model measuring for discrete and hybrid systems. Nonlinear Analysis: Hybrid Systems 23
Krishnendu Chatterjee, Thomas A. Henzinger, Jan Otop: Bidirectional Nested Weighted Automata. CONCUR 2017
Jakub Michaliszyn, Jan Otop: Average Stack Cost of Büchi Pushdown Automata. FSTTCS 2017
Krishnendu Chatterjee, Thomas A. Henzinger, Jan Otop: Quantitative Automata under Probabilistic Semantics. LICS 2016
Krishnendu Chatterjee, Thomas A. Henzinger, Jan Otop: Nested Weighted Limit-Average Automata of Bounded Width. MFCS 2016
Krishnendu Chatterjee, Thomas A. Henzinger, Jan Otop: Quantitative Monitor Automata. SAS 2016
Thomas A. Henzinger, Jan Otop, Roopsha Samanta: Lipschitz Robustness of Timed I/O Systems. VMCAI 2016