Web Grammars
Proceedings of the First International Joint Conference on Artificial Intelligence. Linguistic and Contextual Methods in Pattern Recognition. Pages 609-620.
© 1969 International Joint Conferences on Artificial Intelligence
Abstract
Classes of "phrase-structure grammars" are defined whose "languages" consist, not of strings of symbols, but of directed graphs with symbols at their vertices ("webs"). Examples of such "web grammars" are given, having languages consisting of trees, of two-terminal series-parallel networks, and of "triangular" networks. It is shown that if the graphs permitted in a "context-sensitive" web grammar are required to be acyclic, and the parsing rules are assumed to be graph homomorphisms, then any subgraph which is parsed by a rule must be "convex", and any rule is a composite of rules each of which parses a subgraph having just two points.
- W. F. Miller and A. C. Shaw, Linguistic methods in picture processing -a sur vey, Proc. Fall Joint Computer Conf., December 1968 , 279-290.
- J. Feder, Linguistic specificatio n and analy sis of classes of line patterns, Ph.D. Dissertation, Department of Electrical Engineering, New York University, January 1 969 .
- R. A. Kirsch, Computer interpreta- tion of English text and picture patterns, I.E.E.E. Trans. EC -1 3 , August 1964, 363-376.
- J. L. Pfaltz, Convexity in graphs: Mathematical preliminaries to a theory of graph grammars, AD673420 , July 1968 (abridged ve rsions of parts of this report hav e been accepted for publication in the Journal of Combinatorial Theory and the Proceedings of the American Mathematical Society).
- S.-Y. Kuroda, Classes of languages and linear-bounded automata, Info. Control 7, June 1964, 207-223.
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.
John L. Pfaltz
Azriel Rosenfeld
Computer Science Center University of Maryland College Park, Maryland
Classes of "phrase-structure grammars" are defined whose "languages" consist, not of strings of symbols, but of directed graphs with symbols at their vertices ("webs"). Examples of such "web grammars" are given, having languages consisting of trees, of two-terminal series-parallel networks, and of "triangular" networks. It is shown that if the graphs permitted in a "context-sensitive" web grammar are required to be acyclic, and the parsing rules are assumed to be graph homomorphisms, then any sub graph which is parsed by a rule must be "convex", and any rule is a composite of rules each of which parses a subgraph having just two points.
Foreword
Since the early 1960's, considerable effort has been devoted to the problem of developing formal "picture languages" whose "sentences" are lictures of various types. This work (see for a recent sur vey) can be thought of as generalizing the concepts and methods of mathematical linguistics from conventional languages, in which sentences are strings formed by concatenating symbols, to "languages" in which "sentences" are formed by combining symbols in more general ways. The pre sent paper describes a method of defining "languages" whose "sentences" are directed graphs with symbols at their vertices. The writers are indebted to R. A. Kirsch and D. E. Knuth for suggest ing this area of research. The support of the Information Systems Branch, Office of Naval Research, under Contract Nonr-5144(00), is gratefully acknowledged.
Graphs and Webs
A directed graph G is an ordered pair (PG,EG), where
- PG is a finite set, whose ele-· ments (denoted oy lower-case letters) are called the points
- of G
- is a finite set of ordered pairs of elements of PG, which are called the edges of G.
We say that there is an edge from p to q if (p,q) is in EG; we say that there is a loop at p if (p,p) is in EG. A string (a~ ··· ,an) can be regarded as a directed graph, in which the set of points is [a 1 , ·.. ,an}, and the set of edges is
[ (al, a 2), (a2 , a3), .·· , (an-1· an) 1.
H = (PH,EH) is called a subgraph of G (PG,EG) if
PH is a subset of PG EH consists of just those pairs in EG whose terms are both in H
Thus any subset P of PG defines a unique subgraph, which we call the subgraph on P.
Two points p,q of the graph G are said to be connected if there exists a sequence of points p = Po·Pl·····Pn = q such that either (pi-l'Pi) or (pi,Pi-1) is in EG, 1 ~ i ~ n. A subgraph is called connected if every pair of its points is connected. The set of points of G which are connected to any given point of G is called a connected component of G. Readi ly, the connected subgraphs of a string are just its substrings; these are the subgraphs defined on sets of consecutive points of the string.
By a path of length n (where n ~ O) from p to q in the graph G is meant a sequence of points p = p 0 ,p 1 , ... ,pn q such that pi-l I Pi and (Pi-l·Pi) is in EG' 1 ~ i ~ n. [Note that, in contrast to the definition of "connected", here the edges must all go in the same direction7 the requirement that consecutive points be distinct is needed in order to be able to speak meaningfully about the length of the path. A sequence in which the edges need not be in the same direction is sometimes called a~.] A path of length ~ 2 from a point to itself is called a cycle7 note that by this definition, a loop is not a cycle. A graph in which there exist no cycles is called acyclic. Readily, any string is acyclic.
A point of a directed graph is called a least point, if there is a path from it to every other point7 a greatest point, if there is a path from every other point to it. A point is called minimal, if there is no path from any other point to it7 maximal, if there is no path from it to any other point. Readily, in an acyclic graph there can be at most one least point and one greatest point, since if there were two, they would be on a cycle.
The terminology "least", "greatest", "minimal" and "maximal" can be justified if we look at graphs from the point of view of relations. In any graph G, the set of edges EG can be thought of as defining a relation on the set of points PG (indeed, by definition, a relation R on a set S is just a set of ordered pairs of elements of S). By the transitive closure R of the relation R is meant the set of pairs (x,y) of elements of S such that there exist x = x 0 ,x 1 , ··· ,xn = y, n ~ 0, for which (xi_ 1 ,xi) is in R, 1 ~ i ~ n. Note that if n = 0, the last part of the requirement is vacuous -- in other words, if y = x, we automatically have (x,x) in R, so that ~ is always reflexive7 and readily, R is transitive, i.e. if (x,y) and (y,z) are in R, so is (x, z).
Given any graph G, let TIG be the relation on PG consisting of the set of pairs (p,q) for which there is a path from p to q. Readily, TIG is just the transitive closure of EG. Moreover, let G be acyclic7 it is easily seen that this is equivalent to saying that for any p,q in PG, if there are paths from both p to q and q to p, then we must have p = q. In other words, G is acyclic if and only if the relation TIG is weakly antisymmetr~ and since it is reflexive and transitive, this makes it a partial order relation . [In particular, if G is a string, TIG is a total order relation, since for e very pair of distinct points (ai,aj) we evidently have either (ai,aj) or (aj,ai) in TIG, depending on whether i < j or j < i. This last observation shows that acyclic graphs are a natural generaliza tion of strings.]
Let V be a finite set, which we shall call the vocabulary (or "alphabet") 7 the elements of V will be called symbols. By a V-labelling of the graph G will be meant a function A from PG into V. By a web W over the vocabulary V will be meant an ordered pair (G,A), where G is a graph and A is a V-labelling of G. Note that since a string is a special case of a graph, a string of symbols from V is a special case of a web over V.
If G' is a subgraph of G and A is a V-labelling of G, then the restriction A' of A toG' is a V-labelling of G'7 we say that W' = (G',A') is a subweb of W = (G,A).
Web Grammars
In a conventional phrase-structure "string grammar", rewriting rules of the form a := 6 are used to replace one string by another. Such a rule is com pletely determined by specifying the pair of strings (a,S) 7 any string w = ~a~ which contains a as a substring can then be immediately rewritten as ~e'f . The definition of "rewriting rules" for webs is more complicated7 if we want to replace the subweb a of the web w by another subweb e, it is necessary to specify how to "embed" B in w in place of a. This can be done in many different ways7 for example, one can specify that there be edges between given points of e and any points of w - a having various properties (e.g., having given labels, having given numbers of incoming or out going edges, being on edges to or from particular points of a in the original w, etc. etc.) Any' such specification of the edges between e and its "host web" will be called an embedding of e.
Formally, we can now define a web rewriting rule as a triple (a, 8 ,E), where a and e are webs, and E is an embedding of e. It is important to emphasi ze that the definition of an embedding must not depend on the host web w, since we want to be able to re place a by S in any web containing a as a subweb . Thus any properties of points of the host web which are used in defining the embedding must be well defined for an arbitrary w. Note that in string grammars, the same (implicit) embedding is used for all rewriting rules a := S, name ly "Put 'edges' from the symbol of the host s tring which just preceded a to the leftmost symbol of S. and from the rightmost symbol of 8 to the symbol of the host string which just followed a".
By a web grammar Q we shall mean a triple of the form (V,I ,R), where Vis a vocabulary; I is a set of "initial" webs; and R is a set of web rewriting rules. As usual, we assume that V con sists of two disjoint parts, a "non terminal vocabulary" VN and a '"terminal vocabulary" VT. By the language .Cq of the web grammar Q we mean the set of webs which can be derived from the initial webs by repeated application of the rewriting rules, and whose labels all belong to VT.
The following is a very simple example of a web grammar:
v = [A,a,b,c} (where we have denoted the elements of VN by capital letters, those of VT by lower case letters) ;
I consists of the one-point web with label A;
R consists of the following rules:


c
where for both rules, the embedding is E = ( (p, a) \ (p,A) an edge in the host web}.
It is easily verified that the language of this grammar is just the set of all webs of the form Some less triv ial examples will be given in later sections.

An important special case of a web grammar is that in which the terminal vocabulary consists of only a single symbol. In this case, every point of every web in the language has the same label, so that we can ignore the labels and identify the webs with their under lying graphs. This type of web grammar will be called a graph grammar, and its language will be called a graph language. [In the string case too one can restrict consideration to strings involving only a single symbol; this is still a nontrivial case, since not every set of natural numbers can be the set of lengths of the strings in a one-symbol string language if the sets I and R are required to be finite.]
The general definitions of a web rewriting rule and a web grammar which have been given above are too broad to be of much practical use (just as, analogously, there is little that one can say about string grammars in which arbi trary string rewriting rules are allowed). However, one can define special types of web grammars which are analogous to the various important types of string grammars -- in particular, to context sensitive and context-free string grammars .
We shall call the web rewriting rule (a , S,E) context-sensitive if there exists a point a of a such that ry - [a} is a subweb of 8 -- in other words, the rule "rewrites" only a single point of ex and all edges between points of the host web and points of ex - [a} are in E. In particular, the rule (ex , S,E) will be called context-free if ex has only a sin gle point; note that in this case the definition of a context-sensitive rule is triv ially satisfied, since ex - [ a } is empty. It is readily verified that context-sensitive (-free) string rewriting rules, if we regard them as web rewriting rules, satisfy these defini tions.
A web grammar will be called cont~ sensitive (-free) if all its rewriting rules are context-sensitive (-free). The simple example of a web grammar which was given above is context-free, since only one-point webs are rewritten. Other examples of both context-free and context sensitive web grammars will be given in
the next two sections.
It is instructive to compare our definition of a web grammar with the definition of a "plex grammar" given by Feder2. We can think of Feder's NAPEs ("n-attaching-point entities") as webs in which one point is labelled with the name of the NAPE, and the others with the identifiers of its attaching points. Feder's "joint lists", which describe how sets of NAPEs are interconnected, corre pond to the edges (which need not be directed) internal to the subwebs ct and B in a web rewriting rule; while his "tie point list" corresponds to the embedding E of B in the host web. (He also makes use of a "tie point list" for a , so that he can allow the rewriting rule to be applied only if the edges between ct and the host web satisfy given conditions.) Feder's system can be regarded as a generalization of Shaw's (e.g.,l); Shaw deals only with entities having just two attaching points ("head" and "tail"). Thus the web grammars defined in this paper -- if their webs are regarded as embedded in the plane -- can be thought of as equivalent to a general class of "picture grammars".
Examples of Context-Free Web Languages: Trees and Two-Terminal Series-Parallel Networks
In this section we give context-free graph grammars for two important classes of directed graphs: directed trees with least points, and directed two-terminal series-parallel networks (without multiple edges) .
By a directed tree is meant a con nected directed graph whose number of edges is just one less than its number of points. It can be shown that a directed graph with least point is a directed tree if and only if there is a unigue path from the least point to each point.
Theorem 3.1 The following context-free graph grammar has as its language the set of all directed trees which have
least elements:
R consists of the following rules:
Proof: We first verify that the webs generated by this grammar all have least point and all have one fewer edges than points. This is clea~ if the initial web was ~ , since none of the rules apply to it. Similarly, the initial web ~ has these properties; we proceed by induction on the number of times that the rules are applied to it. Readily, under any application of a rule, the "a" in the initial web remains the least point, since if there was a path from it to every point before the rule was applied, the definition of the embedding insures that there is still a path from it to every point afterwards. Finally, it is easily verified that each rule always adds the same number of edges as it does polnts, so that the former number always re
mains one less than the latter.
Conversely, we shall show that any directed tree G with least point can be generated by the grammar. Note first that in any such G, if t is a point such that the path from the least point to t is as long as possible, then t is maximal; so that G always has a maximal point. We shall show that, given any maximal point p, G can be generated in such a way that the last rule used is R 3 , applied to p to change its label from A to a. This is clear if G has only one or two points; we proceed by induction on the number of its points.
Let r be a point of G such that the path from the least point to it is as l ong as possible, and let q be the next-to-last point on this path, so that (q,r) is an edge. Suppose first that there is no s I r such that (q,s} is a lso an edge; then in the subgraph of G from which r has been omitted, q is a maximal element, so that by induc tion hypothesis this subgraph can be generated by the grammar in such a way that the last rule used is R3 , applied to change the label of q from A to a. But then we can obtain G itself by first applying R1 to q to "attach" r to it, and then applying R3 to change the label of r from A to a.
Finally, suppose that there ~ other points r = rl, r2, ·.· ,rk, k ~ 2, such that (q,ri) is an edge. Then by induction hypothesis, we can generate the subgraph from which these points have been omitted, and in which q is evidently a maximal element. To obtain G, we then simply replace the final application of R3 to q by an application of R 1 , followed by k - 1 applications of R2 , followed by k
applications of R 3 .//
It is not difficult to show that if we r eplace I i'n the above grammar by [ 1}.}, we obtain as language the set of all "forests" of such trees -- in other words, directed graphs each of whose connected components is such a tree.
It is well known that trees have a natural string repre sentation as nests of paren theses. Now the string language consisting of nests of parentheses can be accepted by a pushdown automaton, but not by a finite-state automaton; thus its grammar is context free, but not finite-state. In contrast, the simple context-free grammar given in Section 2 evidently is finite state. It would be of interest to define and study classes of automata which would be "equiv alent" to the various classes of web grammars -- context-free, context-sensitive , etc. - considered in this paper.
The set of directed two-terminal series-parallel networks can be defined as the set of directed graphs having least and greatest points which can be "derived" from the graph ~ by repeated ly performing the following operations:
- Serial composition: Let G1 and G 2 be TTSPN's with least and greatest points xl,yl and x 2 ,y 2 , respectively; then their serial composition is the graph G for which s

In short: Gs is obtained by identifying x 2 with y 1 . Readily, Gs has x 1 as least point and y 2 as greatest point.
- Parallel composition: Similarly, the parallel composition Gp of G 1 and G 2 is defined by

In short: Gp is obtained by identifying x 2 with x and y 2 with y 1 ; readily, it fias x 1 and y 1 as least and greatest points.
It can be shown that a directed graph G with distinct least and greatest points x,y is a TTSPN if and only if any two given points p and q of G always appear in the same order on any walk (="undi rected path") from x to y which passes through them.
A directed graph is called a basis ~if whenever (r,s) and (s,t) are edges, (r,t) is not an edge. It is called semi-transitive if whenever (r,t) is an edge, then (r,s) and (s,t) are edges for any point s on any path from r to t. (In both of these definitions, we assume that r,s,t are all distinct.) We shall call G basic if it is both a basis graph and semi-transitive. Readily, G is basic if and only if whenever there is a path of length ~2 from p to q, there is no edge from p to q. All of these pro perties evidently pass to subgraphs.
Theorem 3.2 The following context-free graph grammar has as its language the set of all basic TTSPN's:
R consists of the rules
* We have attached subscripts to the two A's to avoid having to write "E is the set of edges from p to the point of S which is the first term of an edge, for all p such that there was an edge from p to the sole point of ~ in the host web, together with the set of edges to p from the point of 8 which ... "; the A's are still the same label.
Proof: It is easily verified, using induction, that any web generated by this grammar is basic, has least and greatest points and has the "unique order" property, making it a basic TTSPN. Conversely, if G is a basic TTSPN having six or fewer points, it is readily generated by the grammar; we proceed by induction on the number n ~ 7 of points in G.
Since G is a TTSPN, it is the com position (serial or parallel) of two TTSPN's, call them G 1 and G 2 , which are basic since they are subgraphs of G, and at least one of which, say G 1 , has n1 ~ 4 points. By induction hypothe sis, G 1 is generated by the grammar; and since each application of a rewriting rule adds at most one point, there is a step Gi in a "derivation" of G 1 from a A a at which there are exactly n 1 - 1 ~ 3 points., By the first part of the proof, G 1 is a basic TTSPN. Let G' be the· web obtained by composing Gi (rather than G 1 ) with G 2 ; thus G' is a TTSPN, and readily it is basic since G is. Since G' has n - 1 points, by induction hypothesis it is generated by the grammar; and if we now apply to it the same sequence of rewriting rules which was used to get G1 from Gi, we clearly obtain G. / /
Context-Sensitive Web Languages: "Triangles"
In this section we describe a context-sensitive web grammar which gen erates "directed triangles" of the form

(Note that these are directed graphs, not really triangles; but there is a natural way of "embedding" them in the plane - as in the . above picture -- so that the points of the graph coincide with the points of a triangle. The grammar given below should be compared to the right-triangle grammar given by Kirsch 3 .)
v = (B,z,z*,w,w*,x,a,b,c,w,x,y,z1


R consists of the rules

(where the embedding of the "new" vertex, labelled W, is as shown; the other vertices in the rewritten web are attached in the same way as were the corresponding vertices before the rewriting -- and similarly in the remaining rules)



(i.e., w* is simply relabeled w)




Readily, at any stage in the deriva tion of a terminal web using this gram mar, exactly one of the rules can be applied. The grammar changes the initial z to z*, and builds up a "column" of w* 's, topped by a W, "on top" of it. When the column reaches the proper height, its top and next-to-top points become labelled y and w, and the w*·s are then successively changed tow's until the bottom is reached. At this point, the z* can be changed to a z and a new Z (or a B) added "to the right" of it. If a Z is added, the process repeats; if a B (or if we started with the initial web hav ing the B instead of the Z) , the grammar changes it to a b and builds up a column of x's, topped by an X, on top of it, until the proper height is reached, at which the label c is used. Note that in each of these rules, only a single vertex is rewritten, so that this is indeed a context-sensitive web grammar.
The following interesting variation on the above grammar generates truncated "Pascal's triangles" having the binomial coefficients as labels. [This grammar requires an "unbounded" vocabulary, and makes use of rules in which the label of a "new" point is obtained by adding up the labels of neighboring "old" points.]
v (B,z,z*, positive integers, primed positive integers, and starred positive integers } (where the primed and starred integers are understood to be non terminal)

R consists of the following rules (where the letters h,i,j,k,m,n,r, s,t stand for arbitrary positive integers) :

a*

(provided i f 1)




| Rule Contextual condition | Embedd i ng: | |
|---|---|---|
| (Rl) T t := | NONE | L(t) = L(T) |
| (R2) T Tl T L := - | (T) contains no points having non- terminal labels | L(T 1 ) L(T) |
| (R3) .1 Tl a := | NONE | L(A) L(T') L(l ) ( 1 } L(T 1 ) r:; a a |

A
Here again, starred integers are built up on top of the B (or Z) , topped by a primed integer, until the proper height is reached, at which point the stars are successively removed and the B changed t o a 1 (or the Z changed to 1 and another Z added) ·
In both of the above grammars, "con texts" are used which involve more than just the immediate "neighbors" of the point being rewritten -- that is, more than just the points having edges betwee n them and the rewritten point. We can obtain a grammar using only such "imme diate contexts" if we "hang" an extra point from the "bottoms" of the triangles (which, incidentally makes the "triangles" TTSPN 1 s). For conciseness, we use the following notation in describing the embeddings: L(x) = the set of points joined by edges to x; R(x) = the set of points to which x is joined by an edge.


R consists of the following rules (where we have described, rather than drawing, the contexts of the points which are rewritten) :
[Note: In rules (R 3 -R 9 ), R(X} = T for all X in the right members]
Acyclic Web Languages
In all of the examples given earlier, the web languages consist entirely of acyclic webs. [As indicated earlier, from the point of view of rela tions, acyclic graphs are a natural generalization of strings, since the "path" relation on a string is a total order relation, while on an acyclic graph it is a partial order relation.] In this section we show that for such languages, if we impose a certain natural restriction on the types of embeddings which are allowed, we can give a simple graph-theoretic characterization of the S·ubwebs which can result from rewriting a single point. We can also show that any such subweb can be ob tained by repeatedly rewriting one-point subwebs as one- or two-point subwebs; note that all the rewriting rules in our examples were indeed of this form.
The subgraph H of the graph G is called 4 convex in G if any path between two points of H lies completely in H.
Proposition 5.1 G is acyclic if and only if every subgraph on a single point is convex in G.
Proof: Evidently, in any graph, a sub graph on a single point is convex if the point does not lie on a cycle.//
Readily, the convex subgraphs of a string are just its substrings.
Let G and G' be graphs. A mapping ~ from PG onto PG' is called a ~ homomorphism if
- (p, q) in EG implies ( ~ (p) , ~ ( q) ) in EG,
- (p' ,q') in EG' implies (a, b) in EG for some a,b such that
Proposition 5.2 A homomorphic preimage of a convex subgraph is convex.
Proof; Let cp: PG ~ PG' be a homomor phism, let H' be convex in G', and suppose that there were a path in G between two points p~,p2 of cp-~(H') which contained a po~nt q not ~n cp-l(H'). Then there would be a path in G' between the points cp(p 1 ) and cp(p2) of H' containing the point cp(q), which is not in H', contradicting the convex
ity of H' ./I
Readily, a homomorphic image or preimage of a string need not be a string.
Let sA~ := sS~ be a context sensitive string rewriting rule which "expands" the single point A into the substring S. When we use this rule in reverse, to "parse" sentences in the string language, we are "contracting" the substring S into a single point. It is easily verified that if we regard the strings in question as graphs, this "contraction" defines a graph homomor phism of the original string onto the rewritten string. This observation suggests that in context-sensitive web grammars too, where the rewriting rules expand points into subwebs, it is natural to require that the corresponding "contractions" be graph homomorphisms. If we impose this requirement, and also require that the web be acyclic both before and after the contraction -- which is certainly true in the string case - we shall show immediately below that the subwebs into which points are expanded must always be convex.
To see what is implied when we require that the contraction of a sub graph onto a point be a graph homomor phism, let G be a graph, and define the left (right) neighborhood of the subgraph H of G as the set of points of G not in H from (to) which there is an edge to (from) a point of H. Let cp be a function from G onto G' which is one-to-one, and edge-preserving outside H, and which maps H onto a single point p' (where if there is an edge in H, there is a loop at p'). Then readily, cp is a homomorphism if and only if it preserves left and right neighborhoods -- in other words, if the neighborhoods of the subgraph on [p'} in G' are just the images of the neighbor hoods of H in G. [Note that if G is acyclic, the left and right neighborhoods of any one-point subgraph must be dis joint. In the string case, the left (right) neighborhood of a substring is evidently just the point immediately to the left (right) of its leftmost (rightmost) element.] Thus requiring that the reverse of a web rewriting rule be a homomorphism is equivalent to requiring that the embedding part of the rule be neighborhood-preserving.
We shall call the subgraph H of the acyclic graph G contractable if there exists a homomorphism cp of G onto an acyclic graph G' which maps H onto a single point, and is one-to- >ne on the rest of G; any such cp will be called a contraction of H.
Theorem 5.3 H is contractable if and on ly if it is convex.
Proof: Let cp be a contraction of H onto the vertex y'. Since G' is acyclic, the subgraph of y' is convex; hence by Proposition 5.2, so is its preimage H.
Conversely, let H be convex, let cp be a homomorphism of G which takes H onto a single vertex y' and is one-to one on the rest of G, and suppose that G' were not acyclic. If there were a cycle in G' not passing through y', then since cp is one-to-one outside. H, this cycle would be the image of a cycle in G, contradicting the fact that G is acyclic. On the other hand, let cp(p 0 ) , ··· ,cp(p) be a cycle in G' with cp(pj) = y'; tf~en cp(p·-1) and cp (Pj+l) are different from y~, so that Pj-l and p . 1 are not in H. B ul: there is an edge J+ from Pj-l to a vertex rj of H and from a vertex sj of H to Pj+l· so that the path s 1 ,pj+l·····Pn = Po·Pl·····Pj-l'rj contraaicts the convexity of H.//
We recall that a subgraph of a string is convex if and only if it is connected. Thus we are still dealing here with a generalization of the situation which is usually considered in string grammars - namely, that the point a can be rewritten only as a .connected (="continuous") sub string; "discontinuous constituent" grammars are usually not allowed.
By Theorem 5.3, if we want to "parse" an acyclic graph to determine whether it could have been generated by our grammar, we need only examine its convex subgraphs.
Proposition 5.4 Let G be an acylic graph, and let H be a convex subgraph of G which has at least two points; then there exist points p,q in H such that the subgraph on [p,ql is convex in G.
Proof: This is clear if H has just two points; we proceed by induction. Let r be a max imal point of H; then the subgraph on PH - [r} is readily convex in G, so that by induction hypothesis we can choose the required p,q from PH- [r} .//
Proposition 5.5 A contraction of H takes convex subgraphs containing H into convex subgraphs.
Proof: This follows immediately from the definition of convexity and the fact that a contraction is one-to-one out side H.//
These two propositions combine to give us
Theorem 5.6 Any contraction is a compos its of contractions each of which contracts a subgraph having exactly two points.
Proof: To contract the convex subgraph H, first choose two points from it such that the subgraph on them is convex (Proposition 5.4), and contract this subgraph; the image of H under this "partial contraction~' is sti1·1 convex (Proposition 5.5), so that we can repeat the process until all of H has been contracted.//
A similar argument can be used to show that any homomorphism of an acyclic graph onto an acyclic graph is a compos ite of such "two-point" contractions. These results suggest that it may be possible to prove, for context-sensitive web grammars, an analog of Kuroda's resultS that any context-sensitive string grammar is equivalent to one whose rewriting rules involve only strings of lengths s: 2.
@inproceedings{ijcai1969p53,
title = {Web Grammars},
author = {Pfaltz, John L. and Rosenfeld, Azriel},
booktitle = {Proceedings of the First International Joint Conference on
Artificial Intelligence, {IJCAI-69}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Donald E. Walker and Lewis M. Norton},
pages = {609--620},
year = {1969},
month = {5},
note = {Linguistic and Contextual Methods in Pattern Recognition},
url = {https://ijcai.org/proceedings/1969/53},
}
TY - CPAPER TI - Web Grammars AU - Pfaltz, John L. AU - Rosenfeld, Azriel T2 - Proceedings of the First International Joint Conference on Artificial Intelligence, IJCAI-69 PB - International Joint Conferences on Artificial Intelligence PY - 1969 SP - 609 EP - 620 UR - https://ijcai.org/proceedings/1969/53 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
Welcome
Future Conferences
AI Journal Division
IJCAI Proceedings
About IJCAI
IJCAI Awards