Web grammars and several graphs

摘要

This paper is concerned with the class of web grammars introduced by Pfaltz Rosenfeld and Montanari. In this paper, we show that context-sensitive web grammar cannot erase arcs, and monotone context-sensitive web grammar can erase arcs but cannot erase any vertices and they satisfy the condition |α|≤|β| in the rules α⇒β. Then some hierarchical results hold, when grammars are normal and nonnormal. Normal grammars have rules that each vertex to be rewritten has exactly one image in the right member of the rule; nonnormal ones have rules that some vertices have two more images. Also, it is shown that there exists a complete grammar which generates some types of Eulerian graphs, line graphs and 3-connected graphs.