<p>We define extensions of <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\textbf{CTL}\)</EquationSource> </InlineEquation> and <b>TCTL</b> with strategic operators, called Strategic <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\textbf{CTL}\)</EquationSource> </InlineEquation> (<b>SCTL</b>) and Strategic <b>TCTL</b> (<b>STCTL</b>), respectively. For each of the above logics we give a synchronous and asynchronous semantics, i.e. <b>STCTL</b> is interpreted over networks of extended Timed Automata (TA) that either make synchronous moves or synchronise via joint actions. We consider several semantics regarding information: imperfect (i) and perfect (I), and recall: imperfect (r) and perfect (R). We prove that <b>SCTL</b> is more expressive than <b>ATL</b> for all semantics,and this holds for the timed versions as well. Moreover, the model checking problem for <b>SCTL</b><InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(_{{\textbf {ir}}}\)</EquationSource> </InlineEquation> is of the same complexity as for <b>ATL</b><InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(_{{\textbf {ir}}}\)</EquationSource> </InlineEquation>, the model checking problem for <b>STCTL</b><InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(_{{\textbf {iR}}}\)</EquationSource> </InlineEquation> is of the same complexity as for <b>TCTL</b>, while for <b>STCTL</b><InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(_{{\textbf {iR}}}\)</EquationSource> </InlineEquation> it is undecidable as for <b>ATL</b><InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(_{{\textbf {iR}}}\)</EquationSource> </InlineEquation>. The above results suggest to use <b>SCTL</b><InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(_{{\textbf {ir}}}\)</EquationSource> </InlineEquation> and <b>STCTL</b><InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(_{{\textbf {ir}}}\)</EquationSource> </InlineEquation> in practical applications. Therefore, we use the tool IMITATOR to support model checking of <b>STCTL</b><InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(_{{\textbf {ir}}}\)</EquationSource> </InlineEquation>.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Strategic (timed) computation tree logic

  • Jaime Arias,
  • Wojciech Jamroga,
  • Wojciech Penczek,
  • Laure Petrucci,
  • Teofil Sidoruk

摘要

We define extensions of \(\textbf{CTL}\) and TCTL with strategic operators, called Strategic \(\textbf{CTL}\) (SCTL) and Strategic TCTL (STCTL), respectively. For each of the above logics we give a synchronous and asynchronous semantics, i.e. STCTL is interpreted over networks of extended Timed Automata (TA) that either make synchronous moves or synchronise via joint actions. We consider several semantics regarding information: imperfect (i) and perfect (I), and recall: imperfect (r) and perfect (R). We prove that SCTL is more expressive than ATL for all semantics,and this holds for the timed versions as well. Moreover, the model checking problem for SCTL \(_{{\textbf {ir}}}\) is of the same complexity as for ATL \(_{{\textbf {ir}}}\) , the model checking problem for STCTL \(_{{\textbf {iR}}}\) is of the same complexity as for TCTL, while for STCTL \(_{{\textbf {iR}}}\) it is undecidable as for ATL \(_{{\textbf {iR}}}\) . The above results suggest to use SCTL \(_{{\textbf {ir}}}\) and STCTL \(_{{\textbf {ir}}}\) in practical applications. Therefore, we use the tool IMITATOR to support model checking of STCTL \(_{{\textbf {ir}}}\) .