Vol. 15 No. 5, © The Author, 2005. Published by Oxford University Press. All rights reserved.
Original Articles |
Logical Consecutions in Intransitive Temporal Linear Logic of Finite Intervals
Department of Computing and Mathematics, Manchester Metropolitan University, All Saints, Oxford Road, Manchester M15 6BH, UK. Email: V.Rybakov{at}mmu.ac.uk
The paper concerns the problem of logical consequence in linear temporal logics in terms of logical consecutions. A logical consecution c is an expression 
1,...,n/
, where all i and are formulas. An informal meaning of c is ‘ is a logical consequence of assumptions 1,...n’. We introduce valid and admissible temporal consecutions and prove that the class of admissible consecutions is a proper extension of the class of all valid consecutions. First we describe the admissible consecutions of the intransitive linear temporal Tomorrow/Yesterday logic TYL defined by intervals of natural numbers in a semantic manner – via consecutions valid on special constructive temporal Kripke/Hintikka models. Then we show that any temporal consecution has a reduced normal form which is given in terms of temporal formulas of temporal degree at most 1. Using this and an enhanced semantic technique we construct an algorithm recognizing consecutions admissible in TYL, i.e. we show that TYL is decidable w.r.t. admissible consecutions.
Keywords: Temporal logic, linear temporal logic, logical consequence, inference, decidability, inference rules, consecutions, admissible rules
Received 11 November 2004.