Proceedings

Web Grammars

Download BibTeX Cite

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.

  1. W. F. Miller and A. C. Shaw, Linguistic methods in picture processing -a sur vey, Proc. Fall Joint Computer Conf., December 1968 , 279-290.
  2. 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 .
  3. R. A. Kirsch, Computer interpreta- tion of English text and picture patterns, I.E.E.E. Trans. EC -1 3 , August 1964, 363-376.
  4. 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).
  5. 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.

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