Prianychnykova O. Algebras of languages representable by labeled graphs

The thesis is dedicated to the problem of developing algebraic tools for analysis of the behavior of generally labeled graphs, directed graphs in which both vertices and transitions are labeled with elements of two arbitrary sets. In recent years, these graphs have found much interest in theoretical computer science, as well as in several applied areas, such as software engineering, object-oriented modeling, description and verification of protocols, robotics. In this work, the theory of generally labelled graphs is developed as a generalization of weighted automata theory. The conditions for the class of all possible behavior of generally labeled graphs with given parameters to be representable by terms of some algebra are defined. Algebra of languages representable by vertex-labeled graphs is introduced. The proposed algebra is equipped with three operations: the union of languages, the merging of languages and the iteration. It can adequately represent many properties of languages defined by vertex-labeled graphs and provides a natural translation from vertex-labeled graphs to regular expressions and vice versa. Several basic constructions, including methods for obtaining of a regular expression in this algebra from vertex-labeled graph and vice versa, determinization and state minimization of vertex-labeled graphs are given. A finitary axiomatization for considered algebra is developed and its completeness is proved. Keywords: labeled graphs, behavior of the graph, languages over the label alphabet, algebra of languages.