ISSN 2071-8594

Russian academy of sciences


Gennady Osipov

G.S. Plesniewicz, Nguyen Thi Minh Vu. Deduction Algorithms for some Extensions of Allen’s Interval Logic


Allen’s interval logic language and the languages whose statements are Boolean combinations of Allen’s logic statements, possibly, with metric information are considered. Some deduction algorithms for the languages are presented. The algorithms are based on the analytical tableaux methods.


Temporal logics, Allen’s interval logic, Analytical tableaux method, Deduction algorithms.

PP. 75-88.


1. Allen J.A. Maintaining knowledge about temporal intervals // Communications of the ACM, 20(11), 1983. – P. 832-843.
2. Allen J.A. Planning as temporal reasoning // Proceedings of the 2nd International Conference on Principles of Knowledge Representation and Reasoning, 1991. – P. 3-14.
3. Allen J.A., Hayes P.I. Common-sense theory of time // Proceedings of the 9th International Joint Conference on Artificial Intelligence, 1985. – P. 528-531.
4. Allen J.A., Koomen J.A. Planning using a temporal word model // Proceedings of the 8th International Joint Conference on Artificial Intelligence, 1983. – P. 741-747.
5. Brunner K., Metcalf G. (eds.) Automatic reasoning with analytic tableaux and related Methods, LNAI 6793, 2011. – P. 279.
6. Koubarakis M. Tractable Disjunctions of Linear Constraints // Proceedings of the 2nd International Conference on Principles and Practice of Constraint Programming (CP96), LNCS 1118. – P. 297-307.
7. Litman, D., Allen, J.A Plan Recognition Model for Subdialogues in Conversation // Cognitive Science, 11(2), 1987. – P. 163-200.
8. Vilain M., Kautz H. Constraint Propagation Algorithms for Temporal Reasoning //Proceedings of the 5th Conference on Artificial Intelligence, 1986. P. 377-382.
9. Plesnevich G.S., Nguen Tkhi Min Vu, Karabekov B.S. Algoritm deduktsii dlya buleva rasshirenii intervalnoy logiki Allena // Integrirovannye modeli i myagkie vychisleniya v iskusstvennom intellekte. Sbornik nauchnykh trudov VIII-y Mezhdunarodnoy nauchno-prakticheskoy konferentsii (Kolomna, 18-20 maya 2015g.). – M.: Fizmatlit, 2015. – S. 181-189.
10. Dechter R., Meiri I., Pearl J. Temporal constraint networks // Artificial Intelligence, 45(1), 1991. – P. 61-95.
11. Shostak R. Deciding linear inequalities by computing loop residues // Journal of the ACM, 28(4), 1981. – P. 769-779.