TY - JOUR
T1 - Adequacy and complete axiomatization for Timed Modal Logic
AU - Jaziri, Samy
AU - Larsen, Kim G.
AU - Mardare, Radu
AU - Xue, Bingtian
PY - 2014/10/29
Y1 - 2014/10/29
N2 - In this paper we develop the metatheory for Timed Modal Logic (TML), which is the modal logic used for the analysis of timed transition systems (TTSs). We solve a series of long-standing open problems related to TML. Firstly, we prove that TML enjoys the Hennessy-Milner property and solve one of the open questions in the field. Secondly, we prove that the set of validities are not recursively enumerable. Nevertheless, we develop a strongly-complete proof system for TML. Since the logic is not compact, the proof system contains infinitary rules, but only with countable sets of instances. Thus, we can involve topological results regarding Stone spaces, such as the Rasiowa-Sikorski lemma, to complete the proofs.
AB - In this paper we develop the metatheory for Timed Modal Logic (TML), which is the modal logic used for the analysis of timed transition systems (TTSs). We solve a series of long-standing open problems related to TML. Firstly, we prove that TML enjoys the Hennessy-Milner property and solve one of the open questions in the field. Secondly, we prove that the set of validities are not recursively enumerable. Nevertheless, we develop a strongly-complete proof system for TML. Since the logic is not compact, the proof system contains infinitary rules, but only with countable sets of instances. Thus, we can involve topological results regarding Stone spaces, such as the Rasiowa-Sikorski lemma, to complete the proofs.
KW - complete axiomatization
KW - non-compact modal logics
KW - timed modal logic
UR - http://www.scopus.com/inward/record.url?scp=84908389448&partnerID=8YFLogxK
U2 - 10.1016/j.entcs.2014.10.011
DO - 10.1016/j.entcs.2014.10.011
M3 - Article
AN - SCOPUS:84908389448
SN - 1571-0661
VL - 308
SP - 183
EP - 210
JO - Electronic Notes in Theoretical Computer Science
JF - Electronic Notes in Theoretical Computer Science
ER -