Linguistic representation of vertex-labeled graphs

Sapunov, SV
1Senchenko, AS
1Taras Shevchenko National University of Kyiv
Dopov. Nac. akad. nauk Ukr. 2019, 11:17-24
https://doi.org/10.15407/dopovidi2019.11.017
Section: Information Science and Cybernetics
Language: Russian
Abstract: 

The representation of deterministic graphs (D-graphs) by sets of words over the vertex labels alphabet is studied. A vertex-labeled graph is said to be a D-graph, if all vertices in the neighborhood of every its vertex have different labels. Vertex-labeled graphs are widely used in the modeling of various computational processes in programming, robotics, model checking, etc. In such models, graphs play the role of an information environment of single or several mobile agents. Walks of agents on a graph determine the sequence of vertices labels or words in the alphabet of labels. For D-graphs in case where the graph as a whole and the initial vertex (i.e. the vertex, from which the agent started walking) are known, there exists the one-to-one correspondence between the sequence of vertices visited by the agent and the trajectory of its walks on the graph. In the case where the D-graph is not known as a whole, the agent walks on it can be arranged in such way that an observer obtains information about the structure of the graph sufficient to solve the problems of graph recognizing, finding the op timal path between vertices, comparison between current graph and etalon graph, etc. In this paper, the linguistic representation of D-graphs by the defining pair of sets of words (the first describes cycles of the graph and the second — all its vertices of degree 1) is introduced. This representation is an analog of the system of defining re lations for everywhere defined automata. A procedure that either constructs a D-graph using a given pair of sets or shows that it is impossible to construct a D-graph from this pair is proposed. A procedure for constructing a minimal (canonical) defining pair for a graph and a procedure for converting an arbitrary defining pair of a graph to the canonical one are found. The obtained results are the extension of corresponding problems of the automata theory to vertex-labeled graphs. This representation allows us to use new methods and algorithms to solve the problems of analyzing vertex-labeled graphs.

Keywords: defining pair, graph representation, vertex-labeled graphs
References: 

1. Letichevsky, A. (2005). Algebra of behavior transformation and its application. In Kudryavtsev V.B., Rosenberg I.G., Goldstein M. (Ed.) Structural Theory of Automata, Semigroups, and Universal Algebra. NATO Science Series II: Mathematics, Physics and Chemistry, Vol. 207, pp. 241-272, Dordrecht: Springer. doi: https://doi.org/10.1007/1-4020-3817-8_10
2. Droste, M., Kuich, W. & Vogler, H. (2009). Handbook of Weighted Automata. Berlin, Heidelberg: Springer. doi: https://doi.org/10.1007/978-3-642-01492-5
3. Dudek, G. & Jenkin, M. (2010). Computational Principles of Mobile Robotics, 2nd ed. Cambridge: Cambridge Univ. Press. doi: https://doi.org/10.1017/CBO9780511780929
4. Baier, C. & Katoen, J.-P. (2008). Principle of Model Checking. Cambridge: MIT Press.
5. Kapitonova, Yu. V. & Letichevsky, A. A. (1988). Mathematical theory of computer systems design. Moscow: Nauka (in Russian).
6. Kilibarda, G., Kudryavtsev, V. B. & Ushchumlich, Sh. (2003). Collectives of automata in labyrints. Discrete Math. and Appl., 13, Iss. 5, pp. 429-466. doi: https://doi.org/10.1515/156939203322694736
7. Grunskii, I., Mikhaylova, I. & Sapunov, S. (2012). Domination on the vertices of labeled graphs. Algebra and Discrete Mathematics, 15, No. 2, pp. 174-184.
8. Stepkin, A. V. (2015). Using a Collective of Agents for Exploration of Undirected Graphs. Cybernetics and System Analysis, 51, Iss. 2, pp. 223-233. doi: https://doi.org/10.1007/s10559-015-9715-z
9. Sapunov, S. V. (2015). Reconstruction of a Labeled Graph by a Graph-walking Mobile Agent. Izvestiya of Saratov University. New Series. Series: Mathematics. Mechanics. Informatics, 15, Iss. 2, pp. 228-238 (in Russian). doi: https://doi.org/10.18500/1816-9791-2015-15-2-228-238
10. Grunskii, I.,S. & Senchenko, A.,S. (2004). Properties of systems of defining relations for automata. Discrete Math. and Appl., 14, Iss. 6, pp. 593-601. doi: https://doi.org/10.1515/1569392043272458
11. Albers, S. & Henzinger, M. R. (2000). Exploring Unknown Environments. SIAM Journal on Computing, 29, No. 4, pp. 1164-1188. doi: https://doi.org/10.1137/S009753979732428X