Decidability via mosaics for bundled Ockhamist logic

被引：0

作者：

Gatto, Alberto ^{[1
]}

机构：

[1] Imperial Coll London, Dept Comp, London, England

来源：

2015 22nd International Symposium on Temporal Representation and Reasoning (TIME) | 2015年

关键词：

Ockhamist logic; decidability; mosaics; complexity; double exponential time; TIME;

D O I：

10.1109/TIME.2015.10

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We adapt the 'mosaics' technique of Reynolds 1997 (in turn an adaption of Nemeti 1986) achieving decidability for the (non local) Ockhamist logic of (upward endless) bundled trees. We produce a double exponential time procedure, thus improving the complexity upper bound of the problem - so far relying on the non elementary procedure of the Rabin's Theorem (Burgess 1979).

引用

页码：131 / 139

页数：9

共 20 条

[1]

[Anonymous], 1994, Temporal Logic. Mathematical Foundations and Computational Aspects

[2]

[Anonymous], 1995, Temporal Logic: From Ancient Ideas to Artificial Intelligence

[3]

[Anonymous], 1968, THESIS

[4] LOGIC AND TIME [J].