FINITE LANGUAGES FOR THE REPRESENTATION OF FINITE GRAPHS

We introduce a new way of specifying graphs: through languages, i.e., sets of strings. The strings of a given (finite, prefix-free) language represent the vertices of the graph; whether or not there is an edge between the vertices represented by two strings is determined by the p air of symbols al the first position in these strings where they diffe r. With this new, ''positional'' or lexicographic, method, classical a nd well-understood ways of specifying languages can now be used to spe cify graphs, in a compact way; thus, (small) finite automata can be us ed to specify (large) graphs. Since (prefix-free) languages can be vie wed as trees, our method generalizes the hierarchical specification of particular types of graphs such as cographs and VSP graphs. Our main results demonstrate an intrinsic relationship between the fundamental operations of language concatenation and graph substitution. (C) 1996 Academic Press, Inc.