Bounded Model Checking of Dense-Timed Deontic Interpreted Systems: A Satisfiability Modulo Theories Approach
Source abstract
Abstract
Automated verification through the analysis of system models is often recommended to evaluate the correctness of safety-critical systems. Failures in such systems can have serious effects on both individuals and hardware. Historically, many automated verification techniques, including model checking, have been proposed and used to ensure the reliable development of real-time multi-agent systems (RTMASs). This paper investigates the use of Satisfiability Modulo Theories-based bounded model checking (SMT-based BMC) for the existential fragment of deontic epistemic metric temporal logic (EMTLKD), interpreted on models generated by dense-timed deontic interpreted systems (DTDISs). Specifically, we address the translation of the existential model checking problem for EMTLKD into the existential model checking problem for a variant of a deontic epistemic linear temporal logic (ELTLKDq). Additionally, we present an SMT-based BMC approach tailored for ELTLKDq and illustrate its effectiveness using a faulty train controller system as a representative example. Our approach is particularly applicable to engineering domains requiring high-assurance verification, such as railway control, autonomous vehicle coordination, and industrial automation. By formally verifying both timing and compliance constraints, our method supports engineers and system designers in developing more reliable and certifiable safety-critical systems before deployment.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Formal Methods in Verification · Security and Verification in Computing
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Mathematics and Computer Science, Faculty of Science and Technology, Jan Dlugosz University in Czestochowa, Armii Krajowej 13/15, 42-200 Czestochowa, Poland
Department of Computer Science, Częstochowa University of Technology, ul. J. H. Dąbrowskiego 73, 42-200 Czestochowa, Poland
Faculty of Telecommunications, Computer Science and Electrical Engineering, Bydgoszcz University of Science and Technology, S. Kaliskiego 7, 85-796 Bydgoszcz, Poland
References (42)
Show source-provided references
1. Wooldridge, M. (2009). An Introduction to Multi-Agent Systems, John Wiley & Sons. [2nd ed.].
2. Penczek, W., and Półrola, A. (2006). Advances in Verification of Time Petri Nets and Timed Automata: A Temporal Logic Approach, Springer. Studies in Computational Intelligence.10.1007/978-3-540-32870-4 ↗
3. Fagin, R., Halpern, J.Y., Moses, Y., and Vardi, M.Y. (1995). Reasoning About Knowledge, MIT Press.10.7551/mitpress/5803.001.0001 ↗
4. A formalisation of violation, error recovery, and enforcement in the bit transmission problem10.1016/j.jal.2004.01.005 ↗
5. SAT-based Bounded Model Checking for Weighted Deontic Interpreted Systems10.3233/FI-2016-1310 ↗
6. Checking EMTLK Properties of Timed Interpreted Systems Via Bounded Model Checking10.1007/s11225-015-9637-9 ↗
7. Zbrzezny, A.M., Zbrzezny, A., and Woźna-Szcześniak, B. (2022). SMT-based BMC for Dense Timed Interpreted Systems and EMTLK Properties. Proceedings of the 14th International Conference on Agents and Artificial Intelligence—Volume 1: ICAART. INSTICC, SciTePress.10.5220/0010882100003116 ↗
8. Pnueli, A. (November, January 31). The Temporal Logic of Programs. Proceedings of the 18th Annual Symposium on Foundations of Computer Science, Providence, RI, USA.
9. Specifying Real-Time Properties with Metric Temporal Logic10.1007/BF01995674 ↗
10. A Theory of Timed Automata10.1016/0304-3975(94)90010-8 ↗
11. Model-checking Timed Temporal Logics10.1016/j.entcs.2009.02.044 ↗
12. Tomorrow and All our Yesterdays: MTL Satisfiability over the Integers
13. On the Expressiveness and Monitoring of Metric Temporal Logic
14. Bounded satisfiability checking of metric temporal logic specifications10.1145/2491509.2491514 ↗
15. Clarke, E., Grumberg, O., and Peled, D. (1999). Model Checking, The MIT Press.
16. Manna, Z., and Pnueli, A. (1992). The Temporal Logic of Reactive and Concurrent Systems, Springer.10.1007/978-1-4612-0931-7 ↗
17. McMillan, K. (1993). Symbolic Model Checking: An Approach to the State Explosion Problem, Kluwer Academic Publishers.10.1007/978-1-4615-3190-6 ↗
18. Bryant, R. (1995, January 5–9). Binary Decision Diagrams and Beyond: Enabling Technologies for Formal Verification. Proceedings of the International Conference on Computer-Aided Design (ICCAD’95), San Jose, CA, USA.
19. Automatic verification of multi-agent systems by model checking via OBDDs10.1016/j.jal.2005.12.010 ↗
20. Biere, A., Cimatti, A., Clarke, E., Fujita, M., and Zhu, Y. (1999, January 21–25). Symbolic Model Checking Using SAT Procedures Instead of BDDs. Proceedings of the ACM/IEEE Design Automation Conference (DAC’99), New Orleans, LA, USA.10.1145/309847.309942 ↗
21. Bounded Model Checking for the Universal Fragment of CTL
22. Verifying Epistemic Properties of Multi-Agent Systems via Bounded Model Checking
23. BDD- versus SAT-based bounded model checking for the existential fragment of linear temporal logic with knowledge: Algorithms and their performance10.1007/s10458-013-9232-2 ↗
24. Bounded Model Checking for Knowledge and Real Time10.1016/j.artint.2007.05.005 ↗
25. The BMC method for the existential part of RTCTLK and interleaved interpreted systems
26. Zbrzezny, A.M., and Zbrzezny, A. (November, January 28). SAT-Based BMC Approach to Verifying Real-Time Properties of Multi-Agent Systems. Proceedings of the 15th IEEE/ACS International Conference on Computer Systems and Applications, AICCSA, Aqaba, Jordan.
27. SAT-based BMC for Deontic Metric Temporal Logic and Deontic Interleaved Interpreted Systems
28. Biere, A., Heule, M., van Maaren, H., and Walsh, T. (2009). Handbook of Satisfiability: Volume 185 Frontiers in Artificial Intelligence and Applications, IOS Press.
29. Bounded model checking of software using SMT solvers instead of SAT solvers10.1007/s10009-008-0091-0 ↗
30. Improved SMT-Based Bounded Model Checking for Real-Time Systems
31. SMT-based Searching for k-quasi-optimal Runs in Weighted Timed Automata10.3233/FI-2017-1527 ↗
32. Zbrzezny, A.M., Woźna-Szcześniak, B., and Zbrzezny, A. (2015). SMT-Based Bounded Model Checking for Weighted Epistemic ECTL. Progress in Artificial Intelligence: 17th Portuguese Conference on Artificial Intelligence, EPIA 2015, Proceedings, Springer.10.1007/978-3-319-23485-4_65 ↗
33. Checking WECTLK Properties of Timed Real-Weighted Interpreted Systems via SMT-Based Bounded Model Checking
34. Simple Bounded MTLK Model Checking for Timed Interpreted Systems
35. Safe adaptive learning algorithm with neural network implementation for control of nonlinear safety-critical system10.1002/rnc.6452 ↗
36. Wang, J., Qin, C., Qiao, X., Zhang, D., Zhang, Z., Shang, Z., and Zhu, H. (2022). Constrained Optimal Control for Nonlinear Multi-Input Safety-Critical Systems with Time-Varying Safety Constraints. Mathematics, 10.10.3390/math10152744 ↗
37. Event-Triggered Safe Control for the Zero-Sum Game of Nonlinear Safety-Critical Systems With Input Saturation10.1109/ACCESS.2022.3166473 ↗
38. On-the-Fly Controller Synthesis for Discrete and Dense-Time Systems
39. Deontic Interpreted Systems10.1023/A:1026176900459 ↗
40. Model Checking in Dense Real-Time10.1006/inco.1993.1024 ↗
41. Symbolic Model Checking without BDDs
42. A new translation from ECTL* to SAT10.3233/FI-2012-768 ↗