On algorithmic properties of propositional inconsistency-adaptive logics

Sergei P. Odintsov, Stanislav O. Speranski

DOI: http://dx.doi.org/10.12775/LLP.2012.011


The present paper is devoted to computational aspects of propositional inconsistency-adaptive logics. In particular, we prove (relativized versions of) some principal results on computational complexity of derivability in such logics, namely in cases of CLuNr and CLuNm , i.e., CLuN supplied with the reliability strategy and the minimal abnormality strategy, respectively.


inconsistency-adaptive logics; non-monotonic logic; dynamic reasoning; reliability strategy; minimal abnormality strategy; computational complexity; expressiveness

Full Text:



Batens, D., “Inconsistency-adaptive logics’;, pages 445–472 in: E. Orłowska (ed.), Logic at Work. Essays dedicated to the memory of Helena Rasiowa, Springer, Heidelberg, New York, 1999,

Batens, D.,“A general characterization of adaptive logics”, Logique et Analyse 173–174–175 (2001): 45–68.

Batens, D., “A procedural criterion for final derivability in inconsistency-adaptive logics”, Journal of Applied Logic 3 (2005): 221–250.

Batens, D. “Adaptive logics and dynamic proofs”, manuscript, available at http://logica.ugent.be/adlog/book.html

Horsten, L., and P. Welch, “The undecidability of propositional adaptive logic”, Synthese 158 (2007): 41–60.

Smorynski, C., Self-reference and Modal Logic, Springer, Berlin, 1985.

Verdee, P.,“Adaptive logics using the minimal abnormality strategy are Π1 1-complex”, Synthese 167 (2009): 93–104.

Verdee, P., “A proof procedure for adaptive logics”, to appear in Logical Journal of IGPL.

ISSN: 1425-3305 (print version)

ISSN: 2300-9802 (electronic version)

Partnerzy platformy czasopism