ALTERNATIVE AXIOMATICS AND COMPLEXITY OF DELIBERATIVE STIT THEORIES
ALTERNATIVE AXIOMATICS AND COMPLEXITY OF DELIBERATIVE STIT THEORIES
复制标题
另类公理学和深思熟虑的 STIT 理论的复杂性
DOI：
10.1007/s10992-007-9078-7
复制
发表时间：
2007
影响因子：
1.5
通讯作者：
N. Troquard
中科院分区：
文献类型：
--
作者：
P. Balbiani;A. Herzig;N. Troquard
我们提出了两个替代徐的公理化的Chellas的STIT。第一个简化了它的介绍，也提供了另一种公理化的审议STIT。第二种观点认为，历史必然性算子可以被定义为代理算子的缩写，从而可以从切拉斯的STIT逻辑中排除。第二个公理化也使我们能够建立，没有时间运营商的STIT公式的可满足性决定的问题是NP-完全的单智能体的情况下，是NEXPTIME-完全的多智能体的情况下，无论是审议和Chellas的STIT。
We propose two alternatives to Xu’s axiomatization of Chellas’s STIT. The first one simplifies its presentation, and also provides an alternative axiomatization of the deliberative STIT. The second one starts from the idea that the historic necessity operator can be defined as an abbreviation of operators of agency, and can thus be eliminated from the logic of Chellas’s STIT. The second axiomatization also allows us to establish that the problem of deciding the satisfiability of a STIT formula without temporal operators is NP-complete in the single-agent case, and is NEXPTIME-complete in the multiagent case, both for the deliberative and Chellas’s STIT.