Formal Grammars as Models of Logic Derivations
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.
- Chang, c.L. and R.C.T. Lee, S~bolic Logic and Mechanical Theorem Proving, Academ1c Press, New York, 1973.
- Hopcroft, J. and J. Ullman, Formal Languages and Their Relation to Automata, Addison-Wesley, Menlo Park, 1969.
- Robinson, J.A., "A machine-oriented logic based on the resolution principle", JACM 12, l(Jan,l965).
- Sickel, S. ,"A search technique for clause interconnectivity graphs", IEEE Transactions on Computers. Aug. 1976.
- Sickel, S., "Completeness of clause inter- connectivity graphs", Technical Rpt., University of California, Santa Cruz, 1977.
- Sickel, S., "A 1 inguistic approach to automatic theorem proving", CSCSI/SCEIO Summer Conference Proceedings, 1976.
- 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.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1. Introduction
This section gives definitions of clause interconnectivity graphs and context-free grammars. The definitions have been extended where needed to express the additional structure treated in this paper. A more detailed description of clause interconnectivity graphs is given by Sickel[4]. Common definitions in theorem proving used here are given by Chang and Lee[l].
A substitution e is a set of ordered pairs [tl/xl, t2/x2, ... tn/xn] where each ti is an arbi trary term and each xi is a distinct variable. For an arbitrary literal L, Le denotes the literal L with all occurrences of xi replaced by ti for l~i~n. Similiar definitions apply for terms te,
and clauses ce.
A directed substitution is given by esl s 2 where e is a substitution [tl/xl, ... ,tn/xn], and sl and s2 form a partitioning of the variables of e. For example, [f(y)/x, g(a)/z](x)(y,z) is a directed substitution.
A variant a .. of a directed substitution 1 ,J
8 1 2 is a substitution derived from e in which s s . each variable y E sl is replaced by yi in e, .and each variable z E s2 is replaced by zj in e. Variant a. replaces only variables from s·l; var1 · - iant a . replaces only variables from s2. a -,J -.- = e.
Given a set of clauses that are variable dis joint, we can construct a clause interconnectivity ~ (CIG). A CIG is a quadruple:
<Nodes, Edges, Subst, Clause> where Nodes is a set of graph nodes, one for each literal in each clause. Even if two literals in _separate clauses are identical, they cor respond to different nodes.
~ is a symmetric relation between pairs Ofim)des such that <A,B> E Edges iff the lit erals associated with nodes A and B have op posite signs and unifiable atoms. We write A<>B if <A,B> E Edges and A<+>B if either A<>B or if 3C,D such that A<>C, C E Clause(D) but C~D, and D<+>B.
Subst is a mapping: Ed~es + Directed Substi ~ tut1ons such that Subst(<A,B>)=esl s 2 where e
is a most general unifier of the atoms of the literals associated with nodes A and B, sl is the set of variables appearing in both A and e, and s2 is the set of variables appearing in both B and e. In the ground case, Subst maps to the empty substitution. .
Clause is a mapping: Nodes+ Powerset(Nodes). Clause partitions the nodes so that literals in the same clause have corresponding nodes in the same partition.
The start clauses are one or more clause par titions wh1ch may be chosen arbitrarily. Us ually they are the clauses representing the negation of the theorem to be proved. Residual literals is a mapping: Nodes + Powerset(Nodes) where Residual_literals(B) = Clause(B) - {B}.
For example, Figure 1 shows a simple CIG. Throughout the discussion of this example we refer to nodes by the literals they represent. If two or more literals were identical, it would be neces sary to distinguish between them. For this example:
Nodes = the set of circled literals
Edges= {<A,B>I A and Bare connec!ed by an eQ9e of the graph}_. I.e., {<A(x), A(y)>, <A(y), A(x)>, etc.}
A(x)<+>C(g(u)) since A(x).<>A(y), A(y) E Cl&use(C(g(y) }land C(g(y) )<>C(g(u)). Intuitively P<+>Q means that from P we can get to Q by first traversing an edge and then alternating between selecting a residual of the destination and from there traversing an edge, etc.
Subst maps each edge to a_directed substitu tion, e~., Subst(<A(x), A{y)>)=[x/y](x)(y)' Subst(<A(y), A(x)>)=[x/y](y)(x)' etc.
Undirected substitutions are shown on the un directed edges of the figure.
Clause maps each node to the set of nodes in the same clause, e.~., Clause(A(f(z))) = {A(f(z)), C(g(u)), D(w)}.
Residual literals maps a node to the other nodes in-the same clause, e.g., Residual_literals(A(f(z))) ~ {C(g(u)), D(w)}.

f.igur~ 1: A CIG for clauses {A(x) B(f(x)), ~(y) C(g(y)l, D(b), A(f(z)) C(g.{_u)) D(w), B(f(f(a))) E(g(e)) F(a), E(v), F(a)}.
Continuing with the definitions,
Unifying composition (~) is a mapping: SubstitutionsxSubstitutions + Substitutions where aOB = y such that y is a most general unifier satisfying, for an arbitrary term t,
If no such y exists, a0B is undefined. 0 is commutative and associative, i.e.,
a0B ~ BOa
a0(B0y) = (aGB)0y Composition of substitutions is normally de fined in the context of applying substitutions sequentially. However, for this application we are looking for evidence that substitutions are compatible. Here, substitutions may be applied in any order; therefore they must be commutative and associative.
Suppose we have a sequence of edges ei=<Ai,Bi> l~i~n, such that Al = Bn and for l~i<n, A(i+l) E Residual literals(Bi), and for i1j Ai t Clause(Aj). Then the sequence leads from node Al back to itself (i.e., Al<+>Al) without visiting any other clause more than once. The base node is Al. If the substitutions along ~way allow us to use the same instance of Al at both ends of the sequence (i.e., if a = Subst(el) 0Subst(e2)0 ... OSubst(en) is defined) then m is called a merge loop. Sub(m), the substitution of the loo~, is the directed substitution asl s 2 such t at sl is the list of variables from the clause of base node Al and s2 is the list of all other variables ap pearing in the loop.
For a merge loop <Al ,81>, <A2,B2>, ... <An,Bn> the undeleted residuals = {L! L E Residual_ literals(Bk) -{A(k+l)} where l ~~n-1}.
In order to find proofs, we must find ways to delete all literals in a start clause. If a CIG is a tree to begin with, then it models a proof in which the root is the start clause. However, if the CIG is not a tree, then it must be made into one. For example,

The definitions for deletion tree and solution tree do that tran.sformation, along with checking for substitution consistency.
A deletion tree for node N, denoted T(N) is:
a) a finite tree
- (i) having root N
- (ii) where N has a single child L such that <N,L> E Edges
- (iii) and L has k children T(Ll), ... T(Lk) where Residual literals(L) = {Ll, ... ,Lk} -
- (iv) and Sub(T(N)) = Subst(<N,L>) .0 -,J Sub.(T(Ll))0 ... OSub.(T(Lk)) is J J defined where j is an integer not used beforet, and where Sub.(T(N)) = Sub(T(N)) with all pre~iously unsub scripted variables now subscripted with i. The subscripts are used to distinguish between different occur rences of the variables.
Note: if k=O, then L is a leaf.
b) a finite tree
- (i) having root N
- (ii) where N has a single child m such that m is a merge loop with base node N
- (iii) and m has k children T(Ll), ... T(Lk) where {Ll, ... Lk} are the undeleted residuals of m
- (iv) and Sub(T(N)) = Sub(m) .0Subj· (T(Ll)) -,J 0 ... 0Sub/T(Lk)) is defined where j is an integer that has not been used ~~~~r~.~tnd where Subi(T(N)) is as in
Note: if k=O, then m is a leaf.
t The reason for this condition is to guarantee that subtrees T(Ll) ... T(Lk) do not have common renaming constants. The choice of j is by a global function similar to GENSYM in LISP.
- derived only by means of a) and b).
A solution tree, Ts(C}, for a CIG Cis a tree such that: --
- (i) it has root "·"
- (ii} and "·" has as children deletion trees for all the literals of a start clause {ll, ... ,lk}.
- (iii) and Sub(Ts(C)) = Subj(T(ll)) c ... G
Subj(T(lk)) is defined where j is an integer that has not been used before.
Again, consider the example in Fi9ure 1. The s~quence <A(x), A(y)>, <C(g(y)), C(g(u))>, <A(f(z)), A(x)> is a merge loop. The base node is A(x). The substitution of the loop is
[f(z)/x, f(z)/y, f(z)/u](x)(u,y,z)· U(w) is the
only undeleted residual. For the start clause {A(x), B(f(x))}, Figure 2 shows the solution tree for this example.

Figure 2: The only solution tree for Figure 1 with start clause {A(x),B(f(x))} Nonempty substitutions of the subtrees are denoted at the roots.
A context-free grammar is a quadruple: <Nonterminals, Terminals, Productions, Start symbol> in which
- Nonterminals, Terminals and Productions are finite sets
- Nonterminals n Terminals = ~
- ~P E Productions, p is of the form: N + sl s2 ... sk for any finite k where N E Nonterminals for l~i~k. si E Nonterminals U Terminals. N is known as the left-hand side (l.h.s.) and sl ... sk as the right hand side (r.h.s) of the production p.
- Start symbol E Nonterminals.
If we always use upper case latin letters to denote nonterminals and never to denote terminals, and restrict the start symbol to be "S", then the production set will fully specify the grammar. We sometimes use this shortcut notation.
For any set of characters C, the set of all strings of those characters is denoted C*. E.g., for the above grammar, T* equals all strings made up only of symbols 0, 1, 2. The empty string, a string consisting of no symbols, is denoted £. £ E T* for all T.
If a and e are strings of symbols and there exists a production A+ Bl ... Bn and by replacing a single occurrence of symbol A in a by the string Bl ... Bn we get B, then we say a= e. In the preceding grammar, OA2 = 01A2. If a and e are strings such that for finite n~l
a= el = e2 = ... =en= e. then we say a can be de rived from e and denote it a~e. A special case of this definition is that a~. S ~ 0111112 in the previous grammar.
The language l(G) of a context-free grammar G = <N,T,P,S> is the set of all terminal strings derivable from G, i.e., {x! ~ E T* and S ~ x}.
- A tree is a derivation tree[2] . for G if:
- Every node has a label which is inN U T.
- The label of the root is S.
- If a node s has at least one descendant, and s has label A, then A must be in N.
- If nodes sl, s2, ... ,sk are the direct de scendants of node s, in order from the left, with labels Al, ... ,Ak respectively, then A+ Al ·A2 ... Ak must be a production in P.
Denote by D(A) a derivation tree for a string de rivable from nonterminal A.
2. CIG's to Grammars
Grammars provide concise representations for very rich sets of objects. For example, all com putable functions are grammatically describable. The functions that we are interested in are the ones that take statements of theorems as input and produce proofs of those theorems as output. This paper attacks that problem by transforming the in~ put into a grammar that will generate exactly the set of proofs to the theorem.
Ground case. In the ground case, all substitutions are empty and are therefore all mutually compatible. Ignoring substitutions simplifies the problem so we will start here. From a ground case CIG:
- C = <Nodes, Edges, Subst, Clause>,
- construct a context-free grammar G. let
- G = <Nodes U {S}, Edges, P, S> where S I Nodes U Edges. P consists of:
- S + ll ... lk for each starting clause {ll, ... lk}.
- B + eCl ... Ck for each edge e=<B,C> and Residual literals(C)={Cl, ... Ck}.
- B + mll.~.lk for each merge loop m and where ll ... lk are the undeleted residuals of m.
For example, consider the ground case CIG of Fig ure 3. The edges of Figure 3 are named a-d and the nodes A-G for purposes of exposition. let the start clause be {A,B} and let e' denote edge <Y,X> if e denotes edge <X,Y>. Edges are directed to designate in which direction the label applies.

Then G is:
<{S,A,B,C,D,E,F,G}, {a,b,c,d}, P, S> where P is:
S -+ A B
A. -+ abc (a merge loop)
A -+ a D
A -+ c' F
B ..,. d C .... a' B
D -+ b E
E -+ c B
F -+ b' C
G .... d I A
L(G) = {abcdd, c'b'a'dd, abed}.
A derivation tree for abcdd is shown in Figure 4.

(i) derivation tree
Figure 4: Trees for abcdd
The string abcdd corresponds to the proof in which the sequence of resolutions corresponding to edges a, b, c, d, d are performed as shown in Fig ure 4(ii). A-G are merely labels, not the literals themselves. _Bec~use ed~es rep~esent complementary pairs, · A .~ C ~ E, D ~ F, B ~ G; dashed lines con nect these pairs in the proof for the convenience of the reader. Each edge traversed is denoted at the corresponding resolution step, also for con venience.
Thm 1. For the ground case, the set of deletion trees for node N of CIG C is equivalent to the set of derivation trees for strings derivable from non terminal N using the productions of the grammar G derived from C.
Proof The proof is by induction on the depth of the trees. Both cases contain a basis step as an in stance. There are two operations for constructing each of the deletion trees and derivation trees. We shall show that the two pair correspond. The first production for G does not apply since we have no way of generating S from any other nonterminal. Part a COnstruction rule a for deletion trees corresponds to production rule b of grammars constructed from CIG's. Figure 5 shows the cor responding constructions.

Figure 5: A corresponding pair of construction rules for de letion and derivation trees.
For k=O, it is clear that L, as a child of N, can be mapped onto <N,L> and vice versa. For k>O, we assume that if T(Li) is equivalent to D(Li) for l~i~k then Figure 5(i) is equivalent to Figure 5(ii). The only transformations to be made are ~etween L and <N,L> and a simple tree reshaping. Part b Construction rule b for deletion trees corresponds to production rule c of grammars con structed from CIG's. Figure 6 shows the corres ponding constructions.

Figure 6: A corresponding pair of construction rules for de letion and derivation trees
For k=O the two trees are identical. For k>O, we assume that if T(Li) is equivalent to D(Li) for l ~ i~k then Figure 6(i) is equivalent to Figure 6(ii) with the only required transformations being a simple tree reshaping.
From parts a and b we conclude that for any deletion tree we can construct a corresponding derivation tree and vice versa. Q.E.D.
Thm 2 For the ground case, the set of solution trees of a CIG is equivalent to the set of deri vation trees for the language of the grammar G constructed from the CIG.
Proof Figure 7 shows the form of solution trees and derivation trees for L(G). For each Li, l ~i~k, we can construct equivalent T(Li) and D(Li). It is therefore trivial to show that for any solution tree we can construct an equivalent derivation tree from S.


Thm 3 Every proof by resolution of the unsatisfi ability of a setS of ground clauses can be mapped onto an element in the language L(G) where G is the grammar constructed from the CIG C construc ted from S.
Proof Any proof by resolution of the unsatisfi ability of Scan be mapped onto a solution tree for C, [5]. By Thm 2 we know that every solution tree for C can be mapped onto a derivation tree of an element of G. Every derivation tree can be mapped onto the element of L(G) that consists of the leaves of the tree in the same left-to-right order.
Thm 4 (Soundness) Suppose G is the grammar deriv ea-Trom CIG C, derived in turn from the set of clauses S. If L(G) is non-empt¥, then S is unsat isfiable and any element of L(G) can be mapped onto a proof of the unsatisfiability of S.
Proof Suppose L(G) contains some string s. Every member of L(G) has a derivation tree that describes the process of deriving s. Let d be a derivation tree for s. From Thm 2 we can map d onto a solu tion tree of C. That solution tree maps onto a proof by resolution of the unsatisfiability of S, l5].
Thm 5 (Completeness) If a set S of clauses is unsatisfiable then the language L(G) is nonempty and any element of L(G) can be used to construct a proof of the unsatisfiability of S.
Proof Assume S unsatisfiable. Then there exists a refutation r of S by resolution[3]. By Thm 3 we know that r can be mapped onto an element s of L(G) and L(G) must therefore be nonempty. Further more, by Thm 4, s can be used to find a proof of the unsatisfiability of S.
Note: The terminals making up the string s are edge names. · Those edge names may be used to represent resolution steps that collectively will generate the empty clause.
General case In deriving a string in a context free language, any production may be applied when ever the current, derived string contains the non terminal that is the l.h.s. of that production. We shall ·now define a similar type of grammar in which application of productions is further re stricted.
A context-free attribute grammar is a context free grammar in which the productions are replaced by production-attribute pairs: (P,A) where P is a production and A is a predicate. When applying a production the corresponding attribute must be true.
E.g., G = <{S}, {0,1}, P_A, S> where P A consists of the two elements:
p
- S + OSl
A
derived string is of length
- less than or equal to 6
- S + 01 True
Then L(G) = {01, 0011, 000111, 00001111}
The method for constructing a grammar in the general case is basically the same as that in the ground case except that we add attributes to .the productions. Each attribute corresponds to the substitution that must be made at that st~p and its compatibility with the substitutions that have al ready been made in the derivation.
Assume a given CIG. Find all merge loops. Now construct a context-free attribute grammar, <Nonterminals, Terminals, P A, S> where:
S is a new symbol, i.e-:, S I Nodes U Edges Nonterminals = {S} U {Nil N E Nodes, i>O} Terminals = Edges
P A= (P,A)
- 1) PisS+ Ll .... Lk. for each start clause (Ll, ... ,Lk)~ A is Jtrue. The empty substi tution is the substitution of the newly de rived string, or
- P is B. + e Cl. ... Ck . where e = <B,C> E 1 J J Edges; Residual literals(C) = {Cl ·.. Ck} A is true iff BT = B()a.j is defined where . 1 B denotes the accumulated substitution of the current, derived string and a= Subst(e). B' is the substitution of the newly derived string, or
- Pis B.+ m Ll .... Lk. where m is a merge . 1 J J loop, (Ll, ... Lk) are the undeleted literals of m. A is as in case 2 except that a = Sub(m).
The indexing of the nonterminals is used to keep track of different copies of the same variable. If more than one instance of a clause is used in the proof then the variables in those clauses must be distinguishable. We assume that variables in different clauses already have different names, so that the only po~sible ambiguity arises from mult1ple 1nstances ot a ~1ven clause.
Product1on-attn bute pairs are really temp lates.t If nonterminal Bh appears in a derived string, then we may use the template
where n is an integer constant not previously used t The number of production templates is finite, but the number of actual productions obtainable will be infinite. It would have been possible, however, to limit ourselves to a finite set of productions and nonterminals by complicating the attributes.
as a nonterminal subscript. This production may now be applied to the derived strings if the attribute of the production is true, i.e., if substitution(s)0 ahn is defined.
For example, consider the CIG C of Figure 8. Again, if e is edge <X,Y> let e1 denote <Y,X>; if Subst(e) = asl s 2 then Subst(e 1 ) = a 52 sl. The grammar constructed from Cis G = <{S,A,B,C,D,E,F, G,H,I,J}, {1 ,2,3,4,5,1 1 ,21 ,3 1 ,41 ,51},P A,S> where p A: - p A: true if 8 1 = 8 Oa defined

Figure 8: A CIG with variable lists attached to clause partitions
L(G) equals the single element set {23451}.
The productions in our constructed attribute grammar tell us how to generate strings, their corresponding derivation trees and associated sub stitutions, top-down. In order to prove the com pleteness theorem for the general case, we need to defin~ the bottom-up construction of substitutions of derivation trees. The following is such a def inition. Proof of equivalence of this to the orig inal definition is simple and left to the reader.
For the derivation tree shown in Fig. 9(i), Sub(D(B . )) = Subst(e) .. 0Sub(D(Cl.)) 0 ... 0 1 1 ,J . J Sub(D(Ckj)).
For the derivation tree shown in Fig. 9(ii), Sub(D(B . )) = Sub(m) .. 0Sub(D(Ll.))0 ... 0 1 1 ,J J Sub(D(Lkj)).
For the derivation tree shown in Fig. 9(iii), Sub(D(S)) = Sub(D(Llj))0 ... (0Sub(D(Lkj)).

Thm 6. (General case, Completeness and Soundness) ~et of solution trees of a CIG is equivalent to the set of derivation trees for the language of the attribute grammar constructed from the CIG.
Proof Consider first the ground structure, i.e. theiCIG without substitutions and the grammar with the attributes ignored. In this case, productions enjoy unrestricted use. Looking only at the ground structure, we are reduced to the situation of thms 1 and 2. Therefore the ground structure of the two are equivalent. The general case puts restrictions on those ground structures. What we need to show is that the restrictions allow the equivalent structures to be admitted at the gener a 1 1 evel.
For the same case breakdown as before, we shall show that the structures the two systems ad mit are equivalent and have equivalent substitu tions. The proof will be by induction on the depth of the trees. The basic steps are the spec ial instances of cases 1 and 2 in which k=O.

Assume by the induction hypothesis that T(Ll), ... , T(Lk) and D(Ll), ... ,D(Lk) are admitted by their respective systems, and that Sub(T(Lh)) = Sub(D(Lhj)) with a possible change of variables for 1~ h~ k. Then let
a = Sub(T(N)) =
Subst(<N,L>) .QSub.(T(Ll))O ... OSub.(T(Lk))
- ,J
~ = Sub(D(Ni)) =
Subst( <N,L>) i ,j 0 Sub(D(Ll j) )0 ... 0Sub(D(Lkj)).
For 1~ h~ k, all variables in Sub(D(Lhj)) are subscripted since every substitution applied un der the grammar is fully subscripted; furthermore, all variables of Lh. are subscripted by j. All variables of Sub(T(fh)) are subscripted except for those in Lh, since by the definition of dele-
J
J
tion tree, before forming Sub(T(Lh)) we subscript all unsubscripted variables. Subj(T(Lh)) then equals Sub(T(Lh)) with all variables of Lh now sub scripted. Therefore, if by the induction hypothe sis, Sub(D(Lhj)) equals Sub(T(Lh)) up to a change, cv, of variables, then Sub(D(Lh.)) equals J Subj(T(Lh)) up to cv', which is equal to cv minus the changes involving unsubscripted variables.
Therefore, Sub(D(N)) and Sub(T(N)) are either both or neither defined, and Sub(D(N)) = Sub(T(N)) with cv' plus change in Sub(T(N)) the unsubscripted variables x of N to X;·

Cl = Sub(T(N)) = Sub(m) .GSub.(T(Ll))O ... OSub . (t(Lk)) and - ,J J J S = Sub(D(N)) = Sub(m) i ,j o Sub(D(L 1)) 0 ... OSub(D(Lkj)) Sub(D(Lhj)) = Subj{T(Lh)) with change cv' for l ~h~ k as in Case 1. Therefore Sub(D(N)) and Sub(T(N)) are either both or neither defined, and Sub(D(N)) = Sub(T(N)) with cv' plus change in Sub(T(N)) the unsubscripted variables x of m to xi.
Case 3 //\

Cl = Sub(Ts(C)) = Subj(T(Ll))O ... OSub/T(Lk)) and S = Sub(D(S)) = Sub(D(Ll.))O ... OSub(D(Lk.)) J J Sub(D(Lh.)) = Sub.(T(Lh)) with change cv' for . J J l~~k as in Case 1. Therefore Sub(D(S)) and Sub(Ts(C)) are either both or neither defined, and
Sub(D(S)) = Sub(Ts(C)) with change cv'.
3. Grammar G to .Language L(G)
In the theorem proving application just des cribed, a context-free grammar is defined whose language represents proofs of a theorem. A des cription of that language is a description of the set of objects we desire. We describe a concise, closed form and discuss how to derive it.
In the case of regular grammars (a special case of context-free grammars), we can describe the generatable language as a regular expression. Re ular ex ressions are defined as follows:
- a Every terminal symbol is a regular expression.
- If A and B are regular expressions, then (A), AlB, AB, and A* are also.
- No sequence of symbols not satisfying a) or b) above is a regular expression.
Parentheses are used to enclose subexpressions, "AlB" is used to denote the choice of A or B, "AB" to denote concatenation of regular expressions A and B, and "A*" denotes that A is repeated zero or more times.
E.G. for grammar G:
L(G) is represented by the regular expression 0* 1 1 1* (213), i.e. any element of L(G) consists of zero or more "O"'s followed by two or more "1'" s followed by either a "2" or a "3".
Context-free grammars sometimes generate languages that are not representable by reguiar expressions. For example, grammar:
generates language: (n e )n, ~o. i.e. all strings that consist of zero or more open parens followed by "e" followed by the same number of close parens as open parens. There is no way to express
(n e )n strictly as a regular expression since the
only repetition operator, "*", does not carry a
count that can be matched. E.g., (*e)* would
allow "(((e)". In order to eliminate this dif
ficulty, we add to the regular expression notation
the positive integer exponent. We define a reg
ular algebra R that admits the following expres
sions:
- Every terminal symbol is in R.
- If A andnB are in R, then (A), AlB, AB, A* and A are in R.
- No sequence not satisfying a) or b) is in R. The addition of exponents is essential since the inherent power of context-free grammars allows balanced bracketing of expressions. Some context free grammars naturally create expressions in R. Several simple operations can be used to generate the expression in those cases.
- Back-substitution. If for any nonterminal A all productions having A as the l.h.s. have no nonterminals on the r.h.s., then replace all ref erences to A by the alternative terminal strings or expressions in R that A derives. Then remove all productions having A as the l.h.s .. E.g.,
- Simple recursion. If for any nonterminal A the only productions having A as the l.h.s. are of the form:

(type 1) A-+ ti, l ~i~n or
where ti, li, and ri represent expressions in R,
- A* (ltl. .. 11 k)* (ttl ... ltn) (r'1 1 .. ·lrj)*. Replace every reference to A in other productions
by this expression representing strings derivable from A. Eliminate all productions having A as the l.h.s.. E.g., A _. A 0
- Internal recursion. If for any nonterminal A, the only productions having A as the l.h.s. are of the form:
(type 1) A_. ti, l~i~n
(type 2) A_. 1 A r
where ti, 1 and r represent expressions in R, where nsl, and there is a single production of type 2, then A i5 1 n ( t 1 I ... I tn) rn.
Replace A as before and eliminate the above pro ductions. E.g.,
The above three replacement rules will not suffice for all context-free grammars. For example the grammar G:
has language (012)* a (113)* such that the number of O's equals the number of 1 's. We cannot, strictly speaking, represent that by our regular algebra. However we can loosen the ordering re striction on the r.h.s. of productions since the r.h.s.'s represent subgoals to be solved and the order is unimportant. This allows us to represent the language as (01 12)* a 3*. A later paper will discuss this ordering relaxation and double recur sion, e.g. A_. 0 A 1 A.
Loosening the ordering restriction also allows the elimination of some redundancy. The first grammar derived from a CIG that appears in this paper generates the following language: {abcdd, c'b'a'dd, abed, cbad}. Allowing reordering and representing edges <X,Y> and <Y,X> similarly, then the set reduces to {abcdd, abed}. For further discussion of minimizing the set representing the proof schemata, see [7].
4. Conclusions
We have described a method that represents proofs in predicate logic by a formal language. This language includes the full set of proofs for a given . theorem. If we can describe the language with a regular algebra then we have a closed form for a possibly infinite set of proofs. This rep resentation gives an analysis of the flow of the derivation. This analysis can be used on programs specified in logic to describe required execution flow of the program that leads to termination with the proper result.
The regular algebra representation can also be used to .analyze the values that variables may have if the derivation is to terminate. In the logic program application, this analysis will be used to clarify the possible values of input and output variables, i.e. the domain and range of the function computed by the program.
Studies are underway to apply this regular algebra representation of logic specifications. Some of the areas presently being considered are:
- program synthesis
- plan formation
- question-answering
- machine learning.
@inproceedings{ijcai1977p125,
title = {Formal Grammars as Models of Logic Derivations},
author = {Sickel, Sharon},
booktitle = {Proceedings of the Fifth International Joint Conference on
Artificial Intelligence, {IJCAI-77}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Raj Reddy},
pages = {544--550},
year = {1977},
note = {Theorem Proving},
url = {https://ijcai.org/proceedings/1977/125},
}
TY - CPAPER TI - Formal Grammars as Models of Logic Derivations AU - Sickel, Sharon T2 - Proceedings of the Fifth International Joint Conference on Artificial Intelligence, IJCAI-77 PB - International Joint Conferences on Artificial Intelligence PY - 1977 SP - 544 EP - 550 UR - https://ijcai.org/proceedings/1977/125 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: