Automatically assigned DDC number: 00633

Manually assigned DDC number: 006332

Number of references: 4

Title: Negation and Proof by Contradiction in Access-Limited Logic

Author:

Author:

Subject: J. M. Crawford,B. J. Kuipers Negation and Proof by Contradiction in Access-Limited Logic

Description: Access-Limited Logic (ALL) is a language for knowledge representation which formalizes the access limitations inherent in a network structured knowledge-base. Where a deductive method such as resolution would retrieve all assertions that satisfy a given pattern, an access-limited logic retrieves all assertions reachable by following an available access path. In this paper, we extend previous work to include negation, disjunction, and the ability to make assumptions and reason by contradiction. We show that the extended ALL neg remains Socratically Complete (thus guaranteeing that for any fact which is a logical consequence of the knowledgebase, there exists a series of preliminary queries and assumptions after which a query of the fact will succeed) and computationally tractable. We show further that the key factor determining the computational difficulty of finding such a series of preliminary queries and assumptions is the depth of assumption nesting. We thus demonstrate the existenc...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1994-06-23

Pubyear: 1991

Format: ps

Identifier: http://citeseer.ist.psu.edu/148022.html

Source: ftp://ftp.cs.utexas.edu/pub/qsim/papers/Crawford+Kuipers-AAAI91.ps.Z

Language: en

Relation:

Relation:

Relation:

Relation:

Rights: unrestricted

Graph

<?xml   version="1.0"   encoding="UTF-8"?>

<references_metadata>

      <rec   ID="/111217.html"   Type="inproceedings"   CiteSeer_Book="Proceedings   of   the   Eighth   National   Conference   on   Artificial   Intelligence"   CiteSeer_Volume=""   Title="{QPC}:   a   Compiler   From   Physical   Models   Into   Qualitative   Differential   Equations,">

            <identifier   Org="ISBN:0262061422"   Paper_ID="/111217.html"   Extracted="0262061422"   DDC="530/.011"   Normalized_DDC="530011"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:026251057X"   Paper_ID="/111217.html"   Extracted="026251057X"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:0262510634"   Paper_ID="/111217.html"   Extracted="0262510634"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:0262510715"   Paper_ID="/111217.html"   Extracted="0262510715"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:0262511126"   Paper_ID="/111217.html"   Extracted="0262511126"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:0262521865"   Paper_ID="/111217.html"   Extracted="0262521865"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:0262611023"   Paper_ID="/111217.html"   Extracted="0262611023"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:0816907072"   Paper_ID="/111217.html"   Extracted="0816907072"   DDC="660/.2815"   Normalized_DDC="6602815"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:0818629053"   Paper_ID="/111217.html"   Extracted="0818629053"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:1558603778"   Paper_ID="/111217.html"   Extracted="1558603778"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:1558604804"   Paper_ID="/111217.html"   Extracted="1558604804"   />

            <identifier   Org="ISBN:3211825797"   Paper_ID="/111217.html"   Extracted="3211825797"   />

            <identifier   Org="ISBN:3540555773"   Paper_ID="/111217.html"   Extracted="3540555773"   DDC="003"   Normalized_DDC="003"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:3540573224"   Paper_ID="/111217.html"   Extracted="3540573224"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.08333333333333333"   />

      </rec>

      <rec   ID="/120778.html"   Type="incollection"   CiteSeer_Book="KR89   Principles   of   Knowledge   Representation   and   Reasoning"   CiteSeer_Volume=""   Title="Towards   a   Theory   of   Access-Limited   Logic   for   Knowledge   Representation,">

            <identifier   Org="ISBN:0262061570"   Paper_ID="/120778.html"   Extracted="0262061570"   DDC="004.2/1"   Normalized_DDC="00421"   Normalized_Weight="0.14285714285714285"   />

            <identifier   Org="ISBN:0262510596"   Paper_ID="/120778.html"   Extracted="0262510596"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.14285714285714285"   />

            <identifier   Org="ISBN:0262510987"   Paper_ID="/120778.html"   Extracted="0262510987"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.14285714285714285"   />

            <identifier   Org="ISBN:0262611023"   Paper_ID="/120778.html"   Extracted="0262611023"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.14285714285714285"   />

            <identifier   Org="ISBN:0780300335"   Paper_ID="/120778.html"   Extracted="0780300335"   DDC="621.381"   Normalized_DDC="621381"   Normalized_Weight="0.14285714285714285"   />

            <identifier   Org="ISBN:0780304942"   Paper_ID="/120778.html"   Extracted="0780304942"   />

            <identifier   Org="ISBN:0818620463"   Paper_ID="/120778.html"   Extracted="0818620463"   />

            <identifier   Org="ISBN:0818673133"   Paper_ID="/120778.html"   Extracted="0818673133"   />

            <identifier   Org="ISBN:0879426888"   Paper_ID="/120778.html"   Extracted="0879426888"   />

            <identifier   Org="ISBN:0897913825"   Paper_ID="/120778.html"   Extracted="0897913825"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.14285714285714285"   />

            <identifier   Org="ISBN:1558600884"   Paper_ID="/120778.html"   Extracted="1558600884"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.14285714285714285"   />

      </rec>

      <rec   ID="/98622.html"   Type="phdthesis"   CiteSeer_Book=""   CiteSeer_Volume=""   Title="Access-Limited   Logic---{A}   Language   for   Knowledge   Representation,">

            <identifier   Org="ISBN:0262510596"   Paper_ID="/98622.html"   Extracted="0262510596"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:0262611023"   Paper_ID="/98622.html"   Extracted="0262611023"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:0471768146"   Paper_ID="/98622.html"   Extracted="0471768146"   DDC="004.67/8"   Normalized_DDC="004678"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:0521650585"   Paper_ID="/98622.html"   Extracted="0521650585"   DDC="401/.41"   Normalized_DDC="40141"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:079239416X"   Paper_ID="/98622.html"   Extracted="079239416X"   DDC="006.3/5"   Normalized_DDC="00635"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:0897919084"   Paper_ID="/98622.html"   Extracted="0897919084"   />

            <identifier   Org="ISBN:2884491287"   Paper_ID="/98622.html"   Extracted="2884491287"   DDC="620.0028563"   Normalized_DDC="6200028563"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:3540633081"   Paper_ID="/98622.html"   Extracted="3540633081"   DDC="006.3/32"   Normalized_DDC="006332"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:3540660127"   Paper_ID="/98622.html"   Extracted="3540660127"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:905199074X"   Paper_ID="/98622.html"   Extracted="905199074X"   DDC="418/.02/0285"   Normalized_DDC="418020285"   Normalized_Weight="0.1111111111111111"   />

      </rec>

      <rec   ID="/225437.html"   Type="inproceedings"   CiteSeer_Book="Proceedings   of   IJCAI89   10th   International   Joint   Conference   on   Artificial   Intelligence"   CiteSeer_Volume=""   Title="Vivid   knowledge   and   tractable   reasoning:   preliminary   report,">

            <identifier   Org="ISBN:0080420125"   Paper_ID="/225437.html"   Extracted="0080420125"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:0262510596"   Paper_ID="/225437.html"   Extracted="0262510596"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:0262510634"   Paper_ID="/225437.html"   Extracted="0262510634"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:0262700670"   Paper_ID="/225437.html"   Extracted="0262700670"   DDC="153"   Normalized_DDC="153"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:0387569790"   Paper_ID="/225437.html"   Extracted="0387569790"   DDC="006.3/3/015115"   Normalized_DDC="00633015115"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:0444887717"   Paper_ID="/225437.html"   Extracted="0444887717"   />

            <identifier   Org="ISBN:0471139408"   Paper_ID="/225437.html"   Extracted="0471139408"   />

            <identifier   Org="ISBN:0521410150"   Paper_ID="/225437.html"   Extracted="0521410150"   DDC="410/.285"   Normalized_DDC="410285"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:0780337573"   Paper_ID="/225437.html"   Extracted="0780337573"   />

            <identifier   Org="ISBN:0792334329"   Paper_ID="/225437.html"   Extracted="0792334329"   DDC="401"   Normalized_DDC="401"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:0818621362"   Paper_ID="/225437.html"   Extracted="0818621362"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:0824727193"   Paper_ID="/225437.html"   Extracted="0824727193"   />

            <identifier   Org="ISBN:0835229777"   Paper_ID="/225437.html"   Extracted="0835229777"   />

            <identifier   Org="ISBN:0929280474"   Paper_ID="/225437.html"   Extracted="0929280474"   />

            <identifier   Org="ISBN:1558600949"   Paper_ID="/225437.html"   Extracted="1558600949"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.1111111111111111"   />

      </rec>

      <rec   ID="SELF"   Type="SELF"   CiteSeer_Book="SELF"   CiteSeer_Volume="SELF"   Title="Negation   and   Proof   by   Contradiction   in   Access-Limited   Logic">

            <identifier   Org="ISBN:0262510596"   Paper_ID="SELF"   Extracted="0262510596"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.3333333333333333"   />

            <identifier   Org="ISBN:0471768146"   Paper_ID="SELF"   Extracted="0471768146"   DDC="004.67/8"   Normalized_DDC="004678"   Normalized_Weight="0.3333333333333333"   />

            <identifier   Org="ISBN:0897919084"   Paper_ID="SELF"   Extracted="0897919084"   />

            <identifier   Org="ISBN:3540753869"   Paper_ID="SELF"   Extracted="3540753869"   DDC="629.892"   Normalized_DDC="629892"   Normalized_Weight="0.3333333333333333"   />

      </rec>

</references_metadata>