Jump to ContentJump to Main Navigation
Changes of MindAn Essay on Rational Belief Revision$
Users without a subscription are not able to see the full content.

Neil Tennant

Print publication date: 2012

Print ISBN-13: 9780199655755

Published to Oxford Scholarship Online: September 2012

DOI: 10.1093/acprof:oso/9780199655755.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (www.oxfordscholarship.com). (c) Copyright Oxford University Press, 2017. All Rights Reserved. Under the terms of the licence agreement, an individual user may print out a PDF of a single chapter of a monograph in OSO for personal use (for details see http://www.oxfordscholarship.com/page/privacy-policy).date: 19 November 2017

A Formal Theory of Contraction

A Formal Theory of Contraction

Chapter:
(p.95) Chapter 4 A Formal Theory of Contraction
Source:
Changes of Mind
Author(s):

Neil Tennant

Publisher:
Oxford University Press
DOI:10.1093/acprof:oso/9780199655755.003.0004

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

Oxford Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.

Please, subscribe or login to access full text content.

If you think you should have access to this title, please contact your librarian.

To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us .