{"action":"closed","number":523,"pull_request":{"url":"https://api.github.com/repos/gapt/gapt/pulls/523","id":72706209,"html_url":"https://github.com/gapt/gapt/pull/523","diff_url":"https://github.com/gapt/gapt/pull/523.diff","patch_url":"https://github.com/gapt/gapt/pull/523.patch","issue_url":"https://api.github.com/repos/gapt/gapt/issues/523","number":523,"state":"closed","locked":false,"title":"[RFC] New resolution calculus","user":{"login":"gebner","id":313929,"avatar_url":"https://avatars.githubusercontent.com/u/313929?v=3","gravatar_id":"","url":"https://api.github.com/users/gebner","html_url":"https://github.com/gebner","followers_url":"https://api.github.com/users/gebner/followers","following_url":"https://api.github.com/users/gebner/following{/other_user}","gists_url":"https://api.github.com/users/gebner/gists{/gist_id}","starred_url":"https://api.github.com/users/gebner/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gebner/subscriptions","organizations_url":"https://api.github.com/users/gebner/orgs","repos_url":"https://api.github.com/users/gebner/repos","events_url":"https://api.github.com/users/gebner/events{/privacy}","received_events_url":"https://api.github.com/users/gebner/received_events","type":"User","site_admin":false},"body":"I do not intend to merge this very soon, at the very least I need to add some documentation.  I highly welcome any comments, criticisms, wishes, etc.!\r\n\r\nOur current resolution calculus has several shortcomings, from my point of view the main ones are the following:\r\n 1. Preprocessing steps, introduced definitions, etc. are not included or represented in the proof.  In order to convert resolution proofs to LK or expansion proofs, we have to pass the original end-sequent, the introduced definitions, and justifications for the input clauses (i.e. projections of the end-sequent) around.  This makes working with resolution proofs cumbersome.\r\n 2. Splitting inferences are handled in an intransparent and confusing way.  In particular, we do not support Vampire's Avatar inferences.\r\n 3. Due to 1., the current resolution calculus is only first-order.  As alluded to in [another pull request](https://github.com/gapt/gapt/pull/521#issuecomment-217735987), it might be a good idea to use the standard calculi for CERESω--this PR might pave the way towards unifying LK/LKsk and Ral/resolution.\r\n\r\nRecently, I had the pleasure of being locked 10 hours inside an airplane during daytime and could thus try out some ideas that fix all three problems in order to pass the time.  The result is the new resolution calculus implementation in this PR.  Features:\r\n * The clausification is completely represented in the calculus.  Similar to higher-order resolution calculi (such as Ral), there are inferences that decompose formulas from the end-sequent into clauses.  This eliminates the mysterious `(cnf, justifications, definitions)` triples that were being passed around.\r\n * Splitting is supported through special rules for Avatar.  (SPASS-style splitting can be simulated as well, this works with the built-in SPASS interface.)   Hence the calculus does not reason about clauses, but A-clauses.  An A-clause is a pair of a clause and a conjunction of ground literals--the \"assertion\".  We write `l_1 ∨ l_2 ∨ ... ∨ l_n  ←  a_1 ∧ ... ∧ a_n` for an A-clause consisting of a clause `l_1 ∨ l_2 ∨ ... ∨ l_n` with assertion `a_1 ∧ ... ∧ a_n`.  An A-clause is interpreted as `a_1 ∧ ... ∧ a_n ⊃ l_1 ∨ l_2 ∨ ... ∨ l_n`.  Inferences such as resolution and paramodulation only operate on the clause part, not the assertion.\r\n * The resolution calculus is higher-order.\r\n * Expansion proof extraction works via a bottom-up expansion tree propagation.\r\n * Escargot is now a bit less sluggish and does Avatar splitting.\r\n\r\nObligatory prooftool screenshot:\r\n```scala\r\nprooftool(Escargot getRobinsonProof hof\"∀x p x ⊃ ∀x p (f x)\")\r\n```\r\n![Sample proof in the new resolution calculus](https://cloud.githubusercontent.com/assets/313929/15822223/bbe74a5a-2bf4-11e6-8c58-892cea65baf8.png)\r\n\r\nTo do:\r\n * When `ResolutionToLKProof` encounters a rule for a propositional connective, it converts the resolution proof to an expansion proof, and the expansion proof to LK.  The missing part is to transform a proof of e.g. `Γ :- a ∧ b` into a proof of `Γ :- a`--this should be possible without introducing a cut, by modifying the inferences that introduces `a ∧ b`.  This is not implemented yet because 1) these are 17 similar transformations that I do not want to write using copy&paste, and 2) our current LK visitor code does not track ancestorship data.\r\n * Splitting elimination.  The conversion of splitting inferences to LK creates Π_1-cuts.  \r\n * `ResolutionToLKProof` uses definition rules.  In some cases these cannot be eliminated easily: for example if CERES plugs in projections at the top which already contain other definitions.  The elimination fails because we cannot selectively eliminate definitions at the moment.\r\n * Documentation.\r\n * Actual proof import from Vampire.\r\n * The old `structuralCNF` clausification procedure that provides projections as justifications is still present.  It has the same functionality as `structuralCNF3`, but the unconditional construction of resolution proofs might cause a performance loss; I still need to test this.","created_at":"2016-06-06T13:09:25Z","updated_at":"2016-06-08T14:43:40Z","closed_at":"2016-06-08T14:43:40Z","merged_at":"2016-06-08T14:43:40Z","merge_commit_sha":"8e5782f7c5ecb44ff887d04e035431c18917970e","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/gapt/gapt/pulls/523/commits","review_comments_url":"https://api.github.com/repos/gapt/gapt/pulls/523/comments","review_comment_url":"https://api.github.com/repos/gapt/gapt/pulls/comments{/number}","comments_url":"https://api.github.com/repos/gapt/gapt/issues/523/comments","statuses_url":"https://api.github.com/repos/gapt/gapt/statuses/8e5782f7c5ecb44ff887d04e035431c18917970e","head":{"label":"gebner:resolution3","ref":"resolution3","sha":"8e5782f7c5ecb44ff887d04e035431c18917970e","user":{"login":"gebner","id":313929,"avatar_url":"https://avatars.githubusercontent.com/u/313929?v=3","gravatar_id":"","url":"https://api.github.com/users/gebner","html_url":"https://github.com/gebner","followers_url":"https://api.github.com/users/gebner/followers","following_url":"https://api.github.com/users/gebner/following{/other_user}","gists_url":"https://api.github.com/users/gebner/gists{/gist_id}","starred_url":"https://api.github.com/users/gebner/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gebner/subscriptions","organizations_url":"https://api.github.com/users/gebner/orgs","repos_url":"https://api.github.com/users/gebner/repos","events_url":"https://api.github.com/users/gebner/events{/privacy}","received_events_url":"https://api.github.com/users/gebner/received_events","type":"User","site_admin":false},"repo":{"id":31465991,"name":"gapt","full_name":"gebner/gapt","owner":{"login":"gebner","id":313929,"avatar_url":"https://avatars.githubusercontent.com/u/313929?v=3","gravatar_id":"","url":"https://api.github.com/users/gebner","html_url":"https://github.com/gebner","followers_url":"https://api.github.com/users/gebner/followers","following_url":"https://api.github.com/users/gebner/following{/other_user}","gists_url":"https://api.github.com/users/gebner/gists{/gist_id}","starred_url":"https://api.github.com/users/gebner/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gebner/subscriptions","organizations_url":"https://api.github.com/users/gebner/orgs","repos_url":"https://api.github.com/users/gebner/repos","events_url":"https://api.github.com/users/gebner/events{/privacy}","received_events_url":"https://api.github.com/users/gebner/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/gebner/gapt","description":"GAPT: General Architecture for Proof Theory","fork":true,"url":"https://api.github.com/repos/gebner/gapt","forks_url":"https://api.github.com/repos/gebner/gapt/forks","keys_url":"https://api.github.com/repos/gebner/gapt/keys{/key_id}","collaborators_url":"https://api.github.com/repos/gebner/gapt/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/gebner/gapt/teams","hooks_url":"https://api.github.com/repos/gebner/gapt/hooks","issue_events_url":"https://api.github.com/repos/gebner/gapt/issues/events{/number}","events_url":"https://api.github.com/repos/gebner/gapt/events","assignees_url":"https://api.github.com/repos/gebner/gapt/assignees{/user}","branches_url":"https://api.github.com/repos/gebner/gapt/branches{/branch}","tags_url":"https://api.github.com/repos/gebner/gapt/tags","blobs_url":"https://api.github.com/repos/gebner/gapt/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/gebner/gapt/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/gebner/gapt/git/refs{/sha}","trees_url":"https://api.github.com/repos/gebner/gapt/git/trees{/sha}","statuses_url":"https://api.github.com/repos/gebner/gapt/statuses/{sha}","languages_url":"https://api.github.com/repos/gebner/gapt/languages","stargazers_url":"https://api.github.com/repos/gebner/gapt/stargazers","contributors_url":"https://api.github.com/repos/gebner/gapt/contributors","subscribers_url":"https://api.github.com/repos/gebner/gapt/subscribers","subscription_url":"https://api.github.com/repos/gebner/gapt/subscription","commits_url":"https://api.github.com/repos/gebner/gapt/commits{/sha}","git_commits_url":"https://api.github.com/repos/gebner/gapt/git/commits{/sha}","comments_url":"https://api.github.com/repos/gebner/gapt/comments{/number}","issue_comment_url":"https://api.github.com/repos/gebner/gapt/issues/comments{/number}","contents_url":"https://api.github.com/repos/gebner/gapt/contents/{+path}","compare_url":"https://api.github.com/repos/gebner/gapt/compare/{base}...{head}","merges_url":"https://api.github.com/repos/gebner/gapt/merges","archive_url":"https://api.github.com/repos/gebner/gapt/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/gebner/gapt/downloads","issues_url":"https://api.github.com/repos/gebner/gapt/issues{/number}","pulls_url":"https://api.github.com/repos/gebner/gapt/pulls{/number}","milestones_url":"https://api.github.com/repos/gebner/gapt/milestones{/number}","notifications_url":"https://api.github.com/repos/gebner/gapt/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/gebner/gapt/labels{/name}","releases_url":"https://api.github.com/repos/gebner/gapt/releases{/id}","deployments_url":"https://api.github.com/repos/gebner/gapt/deployments","created_at":"2015-02-28T15:09:37Z","updated_at":"2015-02-28T15:09:41Z","pushed_at":"2016-06-08T14:37:42Z","git_url":"git://github.com/gebner/gapt.git","ssh_url":"git@github.com:gebner/gapt.git","clone_url":"https://github.com/gebner/gapt.git","svn_url":"https://github.com/gebner/gapt","homepage":"http://www.logic.at/gapt/","size":106743,"stargazers_count":0,"watchers_count":0,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"gapt:master","ref":"master","sha":"c9ae4c718ecbbcc6aab530529dc327c215556376","user":{"login":"gapt","id":10725194,"avatar_url":"https://avatars.githubusercontent.com/u/10725194?v=3","gravatar_id":"","url":"https://api.github.com/users/gapt","html_url":"https://github.com/gapt","followers_url":"https://api.github.com/users/gapt/followers","following_url":"https://api.github.com/users/gapt/following{/other_user}","gists_url":"https://api.github.com/users/gapt/gists{/gist_id}","starred_url":"https://api.github.com/users/gapt/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gapt/subscriptions","organizations_url":"https://api.github.com/users/gapt/orgs","repos_url":"https://api.github.com/users/gapt/repos","events_url":"https://api.github.com/users/gapt/events{/privacy}","received_events_url":"https://api.github.com/users/gapt/received_events","type":"Organization","site_admin":false},"repo":{"id":1971451,"name":"gapt","full_name":"gapt/gapt","owner":{"login":"gapt","id":10725194,"avatar_url":"https://avatars.githubusercontent.com/u/10725194?v=3","gravatar_id":"","url":"https://api.github.com/users/gapt","html_url":"https://github.com/gapt","followers_url":"https://api.github.com/users/gapt/followers","following_url":"https://api.github.com/users/gapt/following{/other_user}","gists_url":"https://api.github.com/users/gapt/gists{/gist_id}","starred_url":"https://api.github.com/users/gapt/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gapt/subscriptions","organizations_url":"https://api.github.com/users/gapt/orgs","repos_url":"https://api.github.com/users/gapt/repos","events_url":"https://api.github.com/users/gapt/events{/privacy}","received_events_url":"https://api.github.com/users/gapt/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/gapt/gapt","description":"GAPT: General Architecture for Proof Theory","fork":false,"url":"https://api.github.com/repos/gapt/gapt","forks_url":"https://api.github.com/repos/gapt/gapt/forks","keys_url":"https://api.github.com/repos/gapt/gapt/keys{/key_id}","collaborators_url":"https://api.github.com/repos/gapt/gapt/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/gapt/gapt/teams","hooks_url":"https://api.github.com/repos/gapt/gapt/hooks","issue_events_url":"https://api.github.com/repos/gapt/gapt/issues/events{/number}","events_url":"https://api.github.com/repos/gapt/gapt/events","assignees_url":"https://api.github.com/repos/gapt/gapt/assignees{/user}","branches_url":"https://api.github.com/repos/gapt/gapt/branches{/branch}","tags_url":"https://api.github.com/repos/gapt/gapt/tags","blobs_url":"https://api.github.com/repos/gapt/gapt/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/gapt/gapt/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/gapt/gapt/git/refs{/sha}","trees_url":"https://api.github.com/repos/gapt/gapt/git/trees{/sha}","statuses_url":"https://api.github.com/repos/gapt/gapt/statuses/{sha}","languages_url":"https://api.github.com/repos/gapt/gapt/languages","stargazers_url":"https://api.github.com/repos/gapt/gapt/stargazers","contributors_url":"https://api.github.com/repos/gapt/gapt/contributors","subscribers_url":"https://api.github.com/repos/gapt/gapt/subscribers","subscription_url":"https://api.github.com/repos/gapt/gapt/subscription","commits_url":"https://api.github.com/repos/gapt/gapt/commits{/sha}","git_commits_url":"https://api.github.com/repos/gapt/gapt/git/commits{/sha}","comments_url":"https://api.github.com/repos/gapt/gapt/comments{/number}","issue_comment_url":"https://api.github.com/repos/gapt/gapt/issues/comments{/number}","contents_url":"https://api.github.com/repos/gapt/gapt/contents/{+path}","compare_url":"https://api.github.com/repos/gapt/gapt/compare/{base}...{head}","merges_url":"https://api.github.com/repos/gapt/gapt/merges","archive_url":"https://api.github.com/repos/gapt/gapt/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/gapt/gapt/downloads","issues_url":"https://api.github.com/repos/gapt/gapt/issues{/number}","pulls_url":"https://api.github.com/repos/gapt/gapt/pulls{/number}","milestones_url":"https://api.github.com/repos/gapt/gapt/milestones{/number}","notifications_url":"https://api.github.com/repos/gapt/gapt/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/gapt/gapt/labels{/name}","releases_url":"https://api.github.com/repos/gapt/gapt/releases{/id}","deployments_url":"https://api.github.com/repos/gapt/gapt/deployments","created_at":"2011-06-29T09:15:16Z","updated_at":"2016-05-25T16:56:25Z","pushed_at":"2016-06-08T14:43:39Z","git_url":"git://github.com/gapt/gapt.git","ssh_url":"git@github.com:gapt/gapt.git","clone_url":"https://github.com/gapt/gapt.git","svn_url":"https://github.com/gapt/gapt","homepage":"https://logic.at/gapt/","size":116372,"stargazers_count":22,"watchers_count":22,"language":"Scala","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":12,"mirror_url":null,"open_issues_count":29,"forks":12,"open_issues":29,"watchers":22,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/gapt/gapt/pulls/523"},"html":{"href":"https://github.com/gapt/gapt/pull/523"},"issue":{"href":"https://api.github.com/repos/gapt/gapt/issues/523"},"comments":{"href":"https://api.github.com/repos/gapt/gapt/issues/523/comments"},"review_comments":{"href":"https://api.github.com/repos/gapt/gapt/pulls/523/comments"},"review_comment":{"href":"https://api.github.com/repos/gapt/gapt/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/gapt/gapt/pulls/523/commits"},"statuses":{"href":"https://api.github.com/repos/gapt/gapt/statuses/8e5782f7c5ecb44ff887d04e035431c18917970e"}},"merged":true,"mergeable":null,"mergeable_state":"unknown","merged_by":{"login":"gebner","id":313929,"avatar_url":"https://avatars.githubusercontent.com/u/313929?v=3","gravatar_id":"","url":"https://api.github.com/users/gebner","html_url":"https://github.com/gebner","followers_url":"https://api.github.com/users/gebner/followers","following_url":"https://api.github.com/users/gebner/following{/other_user}","gists_url":"https://api.github.com/users/gebner/gists{/gist_id}","starred_url":"https://api.github.com/users/gebner/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gebner/subscriptions","organizations_url":"https://api.github.com/users/gebner/orgs","repos_url":"https://api.github.com/users/gebner/repos","events_url":"https://api.github.com/users/gebner/events{/privacy}","received_events_url":"https://api.github.com/users/gebner/received_events","type":"User","site_admin":false},"comments":3,"review_comments":0,"commits":44,"additions":3615,"deletions":1795,"changed_files":75}}
{"actor":{"display_login":"gebner"}}