Theory-contraction is NP-Complete
| Abstract | I investigate the problem of contracting a dependency-network with respect to any of its nodes. The resulting contraction must not contain the node in question, but must also be a minimal mutilation of the original network. Identifying successful and minimally mutilating contractions of dependencynetworks is non-trivial, especially when non-well-founded networks are to be taken into account. I prove that the contraction problem is NP-complete.1.. | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | No categories specified (fix it) | |||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,709 |
| External links |
  Try with proxy. |
| Through your library | Only published papers are available at libraries |
Similar books and articlesDennis Dieks (1984). The “Reality” of the Lorentz Contraction. Journal for General Philosophy of Science 15 (2):330-342.
Greg Restall (1993). How to Bereally Contraction Free. Studia Logica 52 (3):381 - 391.
Sven Ove Hansson (1994). Kernel Contraction. Journal of Symbolic Logic 59 (3):845-859.
Wolfgang Spohn & Matthias Hild (2008). The Measurement of Ranks and the Laws of Iterated Contraction. Artificial Intelligence 172:1195-1218.
Sven Ove Hansson (2008). Specified Meet Contraction. Erkenntnis 69 (1):31 - 54.
Neil Tennant (2005). Contracting Intuitionistic Theories. Studia Logica 80 (2-3):369 - 391.
Raghav Ramachandran, Abhaya C. Nayak & Mehmet A. Orgun (2012). Three Approaches to Iterated Belief Contraction. Journal of Philosophical Logic 41 (1):115-142.
André Fuhrmann & Sven Ove Hansson (1994). A Survey of Multiple Contractions. Journal of Logic, Language and Information 3 (1):39-75.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2009-01-28Total downloads1 ( #275,053 of 549,700 )Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
