О направленном перемещении графоходного автомата без компаса на бесконечной цепи

О направленном перемещении графоходного автомата без компаса на бесконечной цепи

Решена задача организации направленного перемещения графоходного автомата без компаса на бесконечной цепи (т. е. бесконечном связном 2-регулярном графе). Получены необходимые и достаточные условия в виде ограничений на свойства автомата и разметку цепи, при которых автомат сохраняет направление пере...

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2017
Автор: Сапунов, С.В.
Формат: Стаття
Мова:Russian
Опубліковано: Інститут прикладної математики і механіки НАН України 2017
Назва видання:Праці Інституту прикладної математики і механіки НАН України
Онлайн доступ:http://dspace.nbuv.gov.ua/handle/123456789/145116
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:О направленном перемещении графоходного автомата без компаса на бесконечной цепи / С.В. Сапунов // Праці Інституту прикладної математики і механіки НАН України. — Слов’янськ: ІПММ НАН України, 2017. — Т. 31. — С. 124-139. — Бібліогр.: 12 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-145116
record_format dspace
spelling irk-123456789-1451162019-01-16T01:23:12Z О направленном перемещении графоходного автомата без компаса на бесконечной цепи Сапунов, С.В. Решена задача организации направленного перемещения графоходного автомата без компаса на бесконечной цепи (т. е. бесконечном связном 2-регулярном графе). Получены необходимые и достаточные условия в виде ограничений на свойства автомата и разметку цепи, при которых автомат сохраняет направление перемещения на цепи. Предложены два типа вершинной разметки цепи, допускающие направленное перемещение автомата: так называемые детерминированная и слабо детерминированная разметки. Разработаны методы и алгоритмы обхода автоматом конечных и бесконечных помеченных цепей. Для обоих типов разметки разработаны алгоритмы разметки цепей, все вершины которых не помечены или помечены одной и той же меткой. Полученные результаты закладывают основы для изучения навигации автоматов без компаса и их коллективов в стационарных однородных дискретных средах. Розв’язано задачу органiзацiї спрямованого перемiщення графохiдного автомату без компаса на нескiнченному ланцюзi (тобто нескiнченному зв’язному 2-регулярному графi). Отриманi необхiднi та достатнi умови у виглядi обмежень на властивостi автомата i розмiтку ланцюга, за яких автомат зберiгає напрямок перемiщення на ланцюзi. Запропоновано два типи вершинної розмiтки ланцюгу, що допускають спрямоване перемiщення автомата: так званi детермiнована i слабо детермiнована розмiтки. Розроблено методи та алгоритми обходу автоматом скiнченних i нескiнченних помiчених ланцюгiв. Для обох типiв розмiтки розроблено алгоритми розмiтки ланцюгiв, усi вершини яких не позначенi або позначенi однiєю i тiєю ж позначкою. Отриманi результати закладають основи для вивчення навiгацiї автоматiв без компасу та їх колективiв у стацiонарних однорiдних дискретних середовищах. This paper deals with the problem of organizing a directional movement of a graph-walking automaton on infinite path graph (i.e. infinite connected two-regular graph). 2017 Article О направленном перемещении графоходного автомата без компаса на бесконечной цепи / С.В. Сапунов // Праці Інституту прикладної математики і механіки НАН України. — Слов’янськ: ІПММ НАН України, 2017. — Т. 31. — С. 124-139. — Бібліогр.: 12 назв. — рос. 1683-4720 MSC: 68R10, 05C85, 68Q45, 68T40 http://dspace.nbuv.gov.ua/handle/123456789/145116 519.7 ru Праці Інституту прикладної математики і механіки НАН України Інститут прикладної математики і механіки НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
description Решена задача организации направленного перемещения графоходного автомата без компаса на бесконечной цепи (т. е. бесконечном связном 2-регулярном графе). Получены необходимые и достаточные условия в виде ограничений на свойства автомата и разметку цепи, при которых автомат сохраняет направление перемещения на цепи. Предложены два типа вершинной разметки цепи, допускающие направленное перемещение автомата: так называемые детерминированная и слабо детерминированная разметки. Разработаны методы и алгоритмы обхода автоматом конечных и бесконечных помеченных цепей. Для обоих типов разметки разработаны алгоритмы разметки цепей, все вершины которых не помечены или помечены одной и той же меткой. Полученные результаты закладывают основы для изучения навигации автоматов без компаса и их коллективов в стационарных однородных дискретных средах.
format Article
author Сапунов, С.В.
spellingShingle Сапунов, С.В.
О направленном перемещении графоходного автомата без компаса на бесконечной цепи
Праці Інституту прикладної математики і механіки НАН України
author_facet Сапунов, С.В.
author_sort Сапунов, С.В.
title О направленном перемещении графоходного автомата без компаса на бесконечной цепи
title_short О направленном перемещении графоходного автомата без компаса на бесконечной цепи
title_full О направленном перемещении графоходного автомата без компаса на бесконечной цепи
title_fullStr О направленном перемещении графоходного автомата без компаса на бесконечной цепи
title_full_unstemmed О направленном перемещении графоходного автомата без компаса на бесконечной цепи
title_sort о направленном перемещении графоходного автомата без компаса на бесконечной цепи
publisher Інститут прикладної математики і механіки НАН України
publishDate 2017
url http://dspace.nbuv.gov.ua/handle/123456789/145116
citation_txt О направленном перемещении графоходного автомата без компаса на бесконечной цепи / С.В. Сапунов // Праці Інституту прикладної математики і механіки НАН України. — Слов’янськ: ІПММ НАН України, 2017. — Т. 31. — С. 124-139. — Бібліогр.: 12 назв. — рос.
series Праці Інституту прикладної математики і механіки НАН України
work_keys_str_mv AT sapunovsv onapravlennomperemeŝeniigrafohodnogoavtomatabezkompasanabeskonečnojcepi
first_indexed 2023-05-20T17:21:18Z
last_indexed 2023-05-20T17:21:18Z
_version_ 1796153106331860992

Схожі ресурси