SEPARABLE GRAPHS, PLANAR GRAPHS AND WEB GRAMMARS

Abstract

The paper is concerned with the class of 'web grammars', introduced by Pfaltz and Rosenfeld, whose languages are sets of labelled graphs.9 A slightly modified definition of web grammars is given, in which the rewriting rules can have an applicability condition, and it is proved that in general, this extension does not increase the generative power of the grammar. This extension is useful, however, for otherwise it is not possible to incorporate negative contextual conditions into the rules, since the context of given vertex can be unbounded. A number of web grammars are presented which define interesting classes of graphs, including unseparable graphs, unseparable planar graphs and planar graphs. All the grammars in this paper use 'normal embeddings' in which the connections between the web that is written and the host web are conserved, so that any rewriting rule affects the web only locally.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1969
Accession Number
AD0691826

Entities

People

  • G. Ugo Montanari

Organizations

  • University of Maryland

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Abstracts
  • Boundaries
  • Classification
  • Computer Science
  • Embedding
  • Grammars
  • Graph Theory
  • Image Processing
  • Language
  • Maryland
  • Security
  • Sequences
  • Terminals
  • Trees (Data Structures)
  • Universities
  • Vocabulary
  • Words (Language)

Fields of Study

  • Computer science

Readers

  • Computational Linguistics
  • Graph Algorithms and Convex Optimization.