Proceedings

Formal Grammars as Models of Logic Derivations

Download BibTeX Cite

Proceedings of the Fifth International Joint Conference on Artificial Intelligence. Theorem Proving. Pages 544-550.

© 1977 International Joint Conferences on Artificial Intelligence

Abstract

Context-free attribute grammars are proposed as derivational models for proofs in the predicate calculus. The new representation is developed and its correspondence to resolution-based clause interconnectivity graphs is established. The new representation may be used to transform a predicate calculus characterization of a problem into a regular algebra characterization of the solutions. The new representation can be used to simplify the search for proofs. It allows us to express and derive predicate calculus proofs as a constraining function that serves as a filter to the set of candidate proofs that ignore the arguments to predicates. The effect of this is to separate the underlying propositional structure from the re- . strictions imposed by the required unifications. While previous theorem proving methods have been able to enumerate all proofs of a theorem, the method reported here is unique in being able to characterize all proofs of some theorems, representing even an infinite set of proofs with a finite formula. This work has implications for proof theory as well as providing a useful tool in the analysis of programs specified in logic.

  1. Chang, c.L. and R.C.T. Lee, S~bolic Logic and Mechanical Theorem Proving, Academ1c Press, New York, 1973.
  2. Hopcroft, J. and J. Ullman, Formal Languages and Their Relation to Automata, Addison-Wesley, Menlo Park, 1969.
  3. Robinson, J.A., "A machine-oriented logic based on the resolution principle", JACM 12, l(Jan,l965).
  4. Sickel, S. ,"A search technique for clause interconnectivity graphs", IEEE Transactions on Computers. Aug. 1976.
  5. Sickel, S., "Completeness of clause inter- connectivity graphs", Technical Rpt., University of California, Santa Cruz, 1977.
  6. Sickel, S., "A 1 inguistic approach to automatic theorem proving", CSCSI/SCEIO Summer Conference Proceedings, 1976.
  7. Sickel, S., "A proof description language for first-order predicate calculus", Technical Rpt., University of California, Santa Cruz, 1977. TheoreM Prnvln~-3: Sickel

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards