PAVERI FONTANA GABRIELE | Cycle: XXXV |
Section: Computer Science and Engineering
Advisor: ROSSI MATTEO GIOVANNI
Tutor: BARESI LUCIANO
Major Research topic:
Decidable fragments of first-order Metric Temporal Logic.
Abstract:
Temporal logics is the standard descriptive formalism adopted in literature for the formal specification of time-dependent systems.
Although computer systems are inherently discrete-time objects, their application to real-time control and monitoring often requires to deal with a continuous notion of time. For this reason, several descriptive models have been developed which support a continuous-time semantics, most notably Metric Temporal Logic (MTL). Unfortunately, in general, verification of continuous-time temporal logics is not as well supported as for discrete time.Moreover, the mainstream of theoretical studies on temporal logics has mostly been restricted to the propositional case. The reason is clear: most first-order temporal logics that are useful in computer science are not even decidable. Nevertheless, some decidability results for suitable fragments of first-order temporal logics have been obtained, thus opening the way for further studies [1]. The main issue with first-order temporal logics is that, even when decidability results are available for a certain fragment, there is often no actual implementation of a decision procedure for it. This drammatically limits the utility of such formalisms in verification.
Our work is focused on defining decidable fragments of first order MTL, aiming at also providing effective decision procedures for them. The idea is to exploit and extend an existing complete and effective verification tool for propositional MITL (a syntactic fragment of MTL) [2].
Essential bibliography
[1] I. Hodkinson, F. Wolter, M. Zakharyaschev, “Decidable fragments of first-order temporal logics”, Annals of Pure and Applied Logic 106 (2000) 85-134.
[2] M.M. Bersani, M. Rossi, P. San Pietro, “An SMT-based approach to satisfiability checking of MITL”, Information and Computation 245 (2015) 72-97.
Although computer systems are inherently discrete-time objects, their application to real-time control and monitoring often requires to deal with a continuous notion of time. For this reason, several descriptive models have been developed which support a continuous-time semantics, most notably Metric Temporal Logic (MTL). Unfortunately, in general, verification of continuous-time temporal logics is not as well supported as for discrete time.Moreover, the mainstream of theoretical studies on temporal logics has mostly been restricted to the propositional case. The reason is clear: most first-order temporal logics that are useful in computer science are not even decidable. Nevertheless, some decidability results for suitable fragments of first-order temporal logics have been obtained, thus opening the way for further studies [1]. The main issue with first-order temporal logics is that, even when decidability results are available for a certain fragment, there is often no actual implementation of a decision procedure for it. This drammatically limits the utility of such formalisms in verification.
Our work is focused on defining decidable fragments of first order MTL, aiming at also providing effective decision procedures for them. The idea is to exploit and extend an existing complete and effective verification tool for propositional MITL (a syntactic fragment of MTL) [2].
Essential bibliography
[1] I. Hodkinson, F. Wolter, M. Zakharyaschev, “Decidable fragments of first-order temporal logics”, Annals of Pure and Applied Logic 106 (2000) 85-134.
[2] M.M. Bersani, M. Rossi, P. San Pietro, “An SMT-based approach to satisfiability checking of MITL”, Information and Computation 245 (2015) 72-97.
Cookies
We serve cookies. If you think that's ok, just click "Accept all". You can also choose what kind of cookies you want by clicking "Settings".
Read our cookie policy
Cookies
Choose what kind of cookies to accept. Your choice will be saved for one year.
Read our cookie policy
-
Necessary
These cookies are not optional. They are needed for the website to function. -
Statistics
In order for us to improve the website's functionality and structure, based on how the website is used. -
Experience
In order for our website to perform as well as possible during your visit. If you refuse these cookies, some functionality will disappear from the website. -
Marketing
By sharing your interests and behavior as you visit our site, you increase the chance of seeing personalized content and offers.