Sapunov S. The analysis of vertex-labeled graphs

The thesis is dedicated to creating experiments with vertex-labeled graphs for graphs and their vertices identification by the way of analysis and distinction the vertex-dependent languages over the label alphabet. The descriptive and algorithmic analysis methods for languages over the alphabet of labels associated with graphs and their vertices are developed. A particular kind of graphs, the so-called deterministic graphs, with attainable linear upper bound of vertex distinguishing word length is discovered. For the first time the concept of experiments with graphs, where a mobile agent checks if given sets of words are a part of graph's language, is introduced. Construction and realization methods and algorithms for distinguishing and checking experiments are proposed. The concept of defining pair of finite sets of words is proposed. Criteria at which this pair is checking experiment are discovered. Criteria at which an arbitrary pair of finite sets of words is a defining pair of some labeled graph are discovered.