Title A calculus and complexity bound for minimal conditional logic
Authors Nicola Olivetti, dipartimento di Informatica, Universita'di Torino, Italia
Camilla Schwind, LIM, Faculte'de Sciences de Luminy, Marseille, France
Main Fields 4. computational complexity
20. theory of knowledge bases
Other Main Fields automated deduction
logics for artificial intelligence
Abstract + Keywords In this paper, we introduce a cut-free sequent calculus 
for minimal conditional logic CK and three extensions of it: 
namely, with ID, MP and both of them. 
The calculus uses labels and transition formulas and 
can be used to prove decidability and space complexity bounds 
for the respective logics. As a first result, we show that CK can be 
decided in O(n log n) space.