A Formal Theory of Contraction

Neil Tennant

in Changes of Mind

Published in print June 2012 | ISBN: 9780199655755
Published online September 2012 | e-ISBN: 9780191742125 | DOI:
A Formal Theory of Contraction

More Like This

Show all results sharing this subject:

  • Philosophy of Mathematics and Logic


Show Summary Details


This is the heart of the formal theory. Mathematically rigorous definitions are provided of all the formal notions that have been gently introduced in the earlier discussion. The main data type of a step is defined, and the central concept of a dependency network is defined in terms of steps. The concept of a minimally mutilating contraction can then be explicated. Interest in the computational complexity of the contraction problem is motivated by thoroughly surveying known results about the (sometimes horrendous) complexities of various other decision problems of a logical nature. This is in order to provide a context within which the complexity results for contraction should strike the reader as both interesting and welcome. The contraction problem is rigorously characterized, including the hard version that involves the (now precisely explicated) desideratum of minimal mutilation. The simplest version of the contraction problem is shown to be NP-complete; the harder version, involving minimal mutilation, is shown to be at just the next level up in the so-called polynomial hierarchy

Keywords: step; dependency network; minimal mutilation; contraction; computational complexity; decision problem; NP-complete

Chapter.  17737 words. 

Subjects: Philosophy of Mathematics and Logic

Full text: subscription required

How to subscribe Recommend to my Librarian

Buy this work at Oxford University Press »

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.