Context-Free Graph Grammars and Concatenation of Graphs

摘要

An operation of concatenation is defined for graphs. This allows strings to beviewed as expressions denoting graphs, and string languages to be interpreted as graph languages. For a class K of string languages, Int(K) is the class of all graph languages that are interpretations of languages from K. For the classes REG and LIN of regular and linear context-free languages, respectively, Int(REG) = Int(LIN).