Oxford Journals
tools journals homepage advanced search contact help
Journal of Logic and Computation: Current Issue
 
home
browse
current
etoc
authors
subinfo
subscribers
samples

OUP > Journals > Computing/Engineer. & Mathematics/Stats. > Journal of Logic and Computation

Journal of Logic and Computation

Volume 12, Issue 6, December 2002: pp. 955-992

Space-efficient Decision Procedures for Three Interpolable Propositional Intermediate Logics

Guido Fiorino1

1Dipartimento di Scienze dell'Informazione, Universita' degli Studi di Milano, Italy.E-mail: fiorino@dsi.unimi.it

In this paper we present duplication-free tableau calculi for three propositional intermediate interpolable logics, namely the logic characterized by rooted Kripke models with depth two at most, the logic characterized by rooted Kripke models with two final elements at most and depth two at most and the logic characterized by rooted Kripke models with a final element at most (also known as Jankov Logic). Using such calculi we define a O(n)-SPACE decision procedure for the second logic and a O(n log n)-SPACE decision procedure for each of the other two logics.

Keywords: Tableau systems; intermediate logics; decision procedures

Table of Contents   Full-Text PDF (319 KB)

Oxford University Press
Published by Oxford University Press
Copyright ©Oxford University Press 2003
Print ISSN: 0955-792X  Online ISSN: 1465-363X.
Oxford University Press Privacy Policy and Legal Statement