Лінгвістичне зображення графів з поміченими вершинами
DOI:
https://doi.org/10.15407/dopovidi2019.11.017Ключові слова:
визначальна пара, графи з поміченими вершинами, зображення графівАнотація
В роботі введено лінгвістичне зображення Д-графів, у яких в околі кожної вершини всі вершини мають різні мітки, визначальною парою множин слів, перша з яких описує цикли графа, а друга — усі його висячі вершини. Запропоновано процедуру, яка за заданою парою множин або будує відповідний їй Д-граф, або показує, що за цією парою неможливо побудувати Д-граф. Знайдено процедуру побудови мінімальної (канонічної) визначальної пари для графа та процедуру перетворення довільної визначальної пари графа до канонічної. Одержані результати є розповсюдженням відповідних задач теорії автоматів на графи з поміченими вершинами та дозволяють використовувати нові методи та алгоритми для розв’язання задач аналізу графів з поміченими вершинами.
Завантаження
Посилання
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
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
Dudek, G. & Jenkin, M. (2010). Computational Principles of Mobile Robotics, 2nd ed. Cambridge: Cambridge Univ. Press. doi: https://doi.org/10.1017/CBO9780511780929
Baier, C. & Katoen, J.-P. (2008). Principle of Model Checking. Cambridge: MIT Press.
Kapitonova, Yu. V. & Letichevsky, A. A. (1988). Mathematical theory of computer systems design. Moscow: Nauka (in Russian).
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
Grunskii, I., Mikhaylova, I. & Sapunov, S. (2012). Domination on the vertices of labeled graphs. Algebra and Discrete Mathematics, 15, No. 2, pp. 174-184.
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
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
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
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
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2024 Доповіді Національної академії наук України
Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial 4.0 International License.
