WEB GRAMMARS.
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. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1969
- Accession Number
- AD0683684
Entities
People
- Azriel Rosenfeld
- John L. Pfaltz
Organizations
- University of Maryland