Сапунов С. В. Аналіз графів з позначеними вершинами

Дисертацію присвячено створенню експериментів з графами з позначеними вершинами шляхом аналізу та розрізнення пов'язаних з вершинами графа мов у алфавіті позначок для розпізнавання графів та їх вершин. Розроблено дескриптивні і алгоритмічні методи аналізу мов, асоційованих з вершинами графів та самими графами. Знайдено окремий вид графів, названих детермінованими, для яких визначена досяжна лінійна верхня оцінка довжини слова, яке розрізняє вершини. Вперше введено поняття експерименту з позначеним графом, що ґрунтується на перевірці мобільним агентом, який пересувається графом, наявності/відсутності у мові графу заданих множин слів. Запропоновано методи побудови діагностичного і контрольного експериментів з графами, розроблено алгоритми проведення таких експериментів. Введено поняття визначальної пари множин слів; знайдено критерії, за яких ця пара є контрольним експериментом, та за яких довільна пара скінченних множин є визначальною парою деякого позначеного графа.