Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
An answer to an open problem of Urquhart
Egly U. Theoretical Computer Science198 (1-2):201-209,1998.Type:Article
Date Reviewed: Dec 1 1998

Egly answers a question raised by Urquhart in a 1995 paper [1], where he proves that resolution with limited extension (Rle), a Gentzen system G based on the biconditional ( as the only connective, and G extended by the analytic cut rule (Gacut) can polynomially simulate (p-simulate) each other.

The justification for these p-simulations is that an application of an analytic cut rule can be simulated by the rules for ( and by limited extensions. The question answered in the paper is whether such a p-simulation extends to a Gentzen system with all the usual connectives. The author shows that a p-simulation only exists between Gacut and Rle and that there are no p-simulations between G and Gacut or between G and Rle.

The second section familiarizes readers with the definitions and notations used throughout the paper. The author uses a variant of a sequent calculus, where the form of the proof is not restricted to tree form and the logical axioms are not restricted to the form A+ A for an atom.

The third section presents the proof of the main result.

The paper is well written and concise. The result supplements previous work in the propositional calculus.

Reviewer:  Svetlana Segarceanu Review #: CR121853 (9812-0987)
1) Urquhart, A. The complexity of propositional proofs. Bull. Symb. Logic 1, 4 (1995), 425–467.
Bookmark and Share
  Featured Reviewer  
 
Resolution (I.2.3 ... )
 
 
Proof Theory (F.4.1 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Resolution": Date
On determining the causes of nonunifiability
Cox P. Journal of Logic Programming 4(1): 33-58, 1987. Type: Article
Jun 1 1988
Completeness results for inequality provers
Bledsoe W., Kunen K., Shostak R. Artificial Intelligence 27(3): 255-288, 1985. Type: Article
Mar 1 1987
Unification in datastructure multisets
Büttner W. Journal of Automated Reasoning 2(1): 75-88, 1986. Type: Article
Jul 1 1987
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy