Abstract
Nested sequent calculi are a useful generalization of ordinary sequent calculi, where sequents are allowed to occur within sequents. Nested sequent calculi have been profitably employed in the area of (multi)-modal logic to obtain analytic and modular proof systems for these logics. In this work, we extend the realm of nested sequents by providing nested sequent calculi for the basic conditional logic CK and some of its significant extensions. The calculi are internal (a sequent can be directly translated into a formula), cut-free and analytic. Moreover, they can be used to design (sometimes optimal) decision procedures for the respective logics, and to obtain complexity upper bounds. Our calculi are an argument in favour of nested sequent calculi for modal logics and alike, showing their versatility and power.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alenda, R., Olivetti, N., Pozzato, G.L.: Nested sequents for Conditional Logics: preliminary results, Technical Report (2012), http://www.di.unito.it/~pozzato/termcso.pdf
Artosi, A., Governatori, G., Rotolo, A.: Labelled tableaux for non-monotonic reasoning: Cumulative consequence relations. Journal of Logic and Computation 12(6), 1027–1060 (2002)
Baltag, A., Smets, S.: The logic of conditional doxastic actions. Texts in Logic and Games, Special Issue on New Perspectives on Games and Interaction 4, 9–31 (2008)
Board, O.: Dynamic interactive epistemology. Games and Economic Behavior 49(1), 49–80 (2004)
Boutilier, C.: Conditional logics of normality: a modal approach. Artificial Intelligence 68(1), 87–154 (1994)
Brünnler, K.: Deep sequent systems for modal logic. Archive for Mathematical Logic 48(6), 551–577 (2009), http://www.iam.unibe.ch/~kai/Papers/2009dssml.pdf
Brünnler, K.: Nested sequents (2010), habilitation Thesis, http://arxiv.org/pdf/1004.1845
Fitting, M.: Prefixed tableaus and nested sequents. Annals of Pure Applied Logic 163(3), 291–313 (2012)
Gent, I.P.: A sequent or tableaux-style system for lewis’s counterfactual logic vc. Notre Dame Journal of Formal Logic 33(3), 369–382 (1992)
Ginsberg, M.L.: Counterfactuals. Artificial Intelligence 30(1), 35–79 (1986)
Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: Analytic Tableaux Calculi for KLM Logics of Nonmonotonic Reasoning. ACM Trans. Comput. Logic 10(3) (2009)
Giordano, L., Gliozzi, V., Olivetti, N.: Weak AGM postulates and strong ramsey test: A logical formalization. Artificial Intelligence 168(1-2), 1–37 (2005)
Giordano, L., Gliozzi, V., Olivetti, N., Schwind, C.: Tableau calculus for preference-based conditional logics: Pcl and its extensions. ACM Trans. Comput. Logic 10(3) (2009)
Grahne, G.: Updates and counterfactuals. Journal of Logic and Computation 8(1), 87–117 (1998)
Kraus, S., Lehmann, D., Magidor, M.: Nonmonotonic reasoning, preferential models and cumulative logics. Artificial Intelligence 44(1-2), 167–207 (1990)
Lewis, D.: Counterfactuals. Basil Blackwell Ltd. (1973)
Nute, D.: Topics in conditional logic. Reidel, Dordrecht (1980)
Olivetti, N., Pozzato, G.L., Schwind, C.B.: A Sequent Calculus and a Theorem Prover for Standard Conditional Logics. ACM Trans. Comput. Logic 8(4) (2007)
Pattinson, D., Schröder, L.: Generic modal cut elimination applied to conditional logics. Logical Methods in Computer Science 7(1) (2011)
Schröder, L., Pattinson, D., Hausmann, D.: Optimal tableaux for conditional logics with cautious monotonicity. In: ECAI. pp. 707–712 (2010)
de Swart, H.C.M.: A gentzen- or beth-type system, a practical decision procedure and a constructive completeness proof for the counterfactual logics vc and vcs. Journal of Symbolic Logic 48(1), 1–20 (1983)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Alenda, R., Olivetti, N., Pozzato, G.L. (2012). Nested Sequent Calculi for Conditional Logics. In: del Cerro, L.F., Herzig, A., Mengin, J. (eds) Logics in Artificial Intelligence. JELIA 2012. Lecture Notes in Computer Science(), vol 7519. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33353-8_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-33353-8_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33352-1
Online ISBN: 978-3-642-33353-8
eBook Packages: Computer ScienceComputer Science (R0)