A Calculus and Complexity Bound for Minimal Conditional Logic | SpringerLink
Skip to main content
Springer Nature Link
Log in

A Calculus and Complexity Bound for Minimal Conditional Logic

  • Conference paper
  • First Online:
Theoretical Computer Science (ICTCS 2001)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2202))

Included in the following conference series:

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. C. Boutilier, Conditional logics of normality: a modal approach. Artificial Intelligence, 68:87–154, 1994.

    Article  MATH  MathSciNet  Google Scholar 

  2. B. F. Chellas, Basic Conditional logics, J. of Philosophical Logic, 4:133–153,1975.

    Article  MATH  MathSciNet  Google Scholar 

  3. G. Crocco and L. Fariñas del Cerro, Structure, Consequence relation and Logic, volume 4, pages 239–259. Oxford University Press, 1992.

    Google Scholar 

  4. G. Crocco, L. Fariñas del Cerro, and A. Herzig, Conditionals: From philosophy to computer science, Oxford University Press, Studies in Logic and Computation, 1995.

    Google Scholar 

  5. G. Crocco and P. Lamarre, On the Connection between Non-Monotonic Inference Systems and Conditional Logics, In B. Nebel and E. Sandewall, editors, Principles of Knowledge Representation and Reasoning: Proceedings of the 3rd International Conference, pages 565–571, 1992.

    Google Scholar 

  6. J. P. Delgrande, A first-order conditional logic for prototypical properties. Artificial Intelligence, (33):105–130, 1987.

    Google Scholar 

  7. H. C. M. de Swart, 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–20, 1983.

    Article  MATH  MathSciNet  Google Scholar 

  8. M. Fitting, Proof methods for Modal and Intuitionistic Logic, vol 169 of Synthese library, D. Reidel, Dordrecht, 1983.

    Google Scholar 

  9. N. Friedman and J. Halpern, On the complexity of conditional logics. In Principles of Knowledge Representation and Reasoning: Proceedings of the 4th International Conference, KR’94, pages 202–213.

    Google Scholar 

  10. N. Friedman and J. Halpern. Belief Revision: A critique, J. of Logic, Language and Information, 8(4): 401–420, 1999.

    Article  MATH  MathSciNet  Google Scholar 

  11. D. M. Gabbay, Labelled Deductive Systems (vol I), Oxford Logic Guides, Oxford University Press, 1996.

    Google Scholar 

  12. D. M. Gabbay L. Giordano, A. Martelli, N. Olivetti and M. L. Sapino, Conditional Reasoning in Logic Programming. J. of Logic Programming 44(1-3):37–74, 2000.

    Article  MATH  MathSciNet  Google Scholar 

  13. I. P. Gent, A sequent or tableaux-style system for Lewis’s counterfactual logic VC. Notre Dame j. of Formal Logic, 33(3): 369–382, 1992.

    Article  MATH  MathSciNet  Google Scholar 

  14. M. L. Ginsberg. Counterfactuals. Artificial Intelligence, 30(2):35–79, 1986.

    Article  MATH  MathSciNet  Google Scholar 

  15. L. Giordano, V. Gliozzi and N. Olivetti, A conditional logic for belief revision. In Proc. European Workshop on Logics in Artificial Intelligence JELIA 98, Springer LNAI 1489, pp. 294–308, 1998.

    Google Scholar 

  16. L. Giordano, V. Gliozzi, and N. Olivetti. Iterated Belief Revision and Conditional Logic. Studia Logica, to appear, 2001.

    Google Scholar 

  17. A. Artosi, G. Governatori, and A. Rotolo: A Labelled Tableau Calculus for Nonmonotonic (Cumulative) Consequence Relations. In Proc.of TABLEAUX 2000, LNCS 1847, pp. 82–97, 2000

    Google Scholar 

  18. G. Grahne, Updates and Counterfactuals, in Journal of Logic and Computation, Vol 8 No.1:87–117, 1998.

    Article  MATH  MathSciNet  Google Scholar 

  19. C. Groeneboer and James Delgrande, A general approach for determining the validity of commonsense assertions using conditional logics. International Journal of Intelligent Systems, (5):505–520, 1990.

    Google Scholar 

  20. J. Hudelmaier, An O(n log n)-space decision procedure for intuitionistic propositional logic. Journal of Logic and Computation, 3, 63–75, 1993.

    Article  MATH  MathSciNet  Google Scholar 

  21. Sarit Kraus, Daniel Lehmann, and Menachem Magidor. Nonmonotonic reasoning, preferential models and cumulative logics. Artificial Intelligence, 44:167–202, 1990.

    Article  MATH  MathSciNet  Google Scholar 

  22. P. Lamarre. A tableaux prover for conditional logics. In Principles of Knowledge Representation and Reasoning: Proceedings of the 4th International Conference, KR’94, pages 572–580.

    Google Scholar 

  23. D. Lewis, Counterfactuals. Basil Blackwell Ltd, 1973.

    Google Scholar 

  24. D. Nute, Topics in Conditional Logic, Reidel, Dordrecht, 1980.

    MATH  Google Scholar 

  25. N. Olivetti and C. Schwind, Analytic Tableaux for Conditional Logics, Technical Report, University of Torino, 2000.

    Google Scholar 

  26. C. B. Schwind, Causality in Action Theories. Electronic Articles in Computer and Information Science, Vol. 3 (1999), section A, pp. 27–50.

    MathSciNet  Google Scholar 

  27. R. Stalnaker, A Theory of Conditionals, in N. Rescher (ed.), Studies in Logical Theory, American Philosophical Quarterly, Monograph Series no.2, Blackwell, Oxford: 98–112, 1968.

    Google Scholar 

  28. L. Viganò, Labelled Non-classical Logics. Kluwer Academic Publishers, Dordrecht, 2000.

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Informatica, Università di Torino, Italy

    Nicola Olivetti

  2. Faculté des Sciences de Luminy, LIM, Marseille, France

    Camilla B. Schwind

Authors
  1. Nicola Olivetti
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Camilla B. Schwind
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

Copyright information

© 2001 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Olivetti, N., Schwind, C.B. (2001). A Calculus and Complexity Bound for Minimal Conditional Logic. In: Theoretical Computer Science. ICTCS 2001. Lecture Notes in Computer Science, vol 2202. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45446-2_25

Download citation

  • DOI: https://doi.org/10.1007/3-540-45446-2_25

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-42672-1

  • Online ISBN: 978-3-540-45446-5

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation