Accession Number:

AD0691826

Title:

SEPARABLE GRAPHS, PLANAR GRAPHS AND WEB GRAMMARS

Descriptive Note:

Technical rept.

Corporate Author:

MARYLAND UNIV COLLEGE PARK COMPUTER SCIENCE CENTER

Personal Author(s):

Report Date:

1969-08-01

Pagination or Media Count:

49.0

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.

Subject Categories:

  • Administration and Management
  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE