|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
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.