Ріст графів дії скінченних автоматів

Ріст графів дії скінченних автоматів

Розглядаються графи дiї Γn(A) i Γ∞(A) для обмежених i полiномiальних автоматiв A, якi моделюють дiю автоматiв на словах довжиною n i нескiнченних словах вiдповiдно. Встановлено метод знаходження орбiтального коефiцiєнта стиску обмежених автоматiв, росту дiаметрiв графiв Γn(A) для обмежених автомат...

Повний опис

Збережено в:
Бібліографічні деталі
Опубліковано в: :Доповіді НАН України
Дата:2014
Автор: Бондаренко, Є.В.
Формат: Стаття
Мова:Ukrainian
Опубліковано: Видавничий дім "Академперіодика" НАН України 2014
Теми:
Інформатика та кібернетика
Онлайн доступ:https://nasplib.isofts.kiev.ua/handle/123456789/87811
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Ріст графів дії скінченних автоматів / Є.В. Бондаренко // Доповiдi Нацiональної академiї наук України. — 2014. — № 6. — С. 37-41. — Бібліогр.: 6 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-87811
record_format dspace
spelling Бондаренко, Є.В.
2015-10-26T17:35:55Z
2015-10-26T17:35:55Z
2014
Ріст графів дії скінченних автоматів / Є.В. Бондаренко // Доповiдi Нацiональної академiї наук України. — 2014. — № 6. — С. 37-41. — Бібліогр.: 6 назв. — укр.
1025-6415
https://nasplib.isofts.kiev.ua/handle/123456789/87811
519.176
Розглядаються графи дiї Γn(A) i Γ∞(A) для обмежених i полiномiальних автоматiв A, якi моделюють дiю автоматiв на словах довжиною n i нескiнченних словах вiдповiдно. Встановлено метод знаходження орбiтального коефiцiєнта стиску обмежених автоматiв, росту дiаметрiв графiв Γn(A) для обмежених автоматiв, наведено оцiнки на степiнь полiномiального росту графiв Γ∞(A). Доведено, що графи Γ∞(A) для недетермiнованих полiномiальних автоматiв мають субекспоненцiйний рiст.
Рассматриваются графы действия Γn(A) и Γ∞(A) для ограниченных и полиномиальных автоматов A, которые моделируют действие автоматов на словах длиной n и бесконечных словах соответственно. Установлен метод нахождения орбитального коэффициента стягивания ограниченных автоматов, роста диаметров графов Γn(A) для ограниченных автоматов, приведены оценки на степень полиномиального роста графов Γ∞(A). Доказано, что графы Γ∞(A) для недетерминированных полиномиальных автоматов имеют субэкспоненциальный рост.
We consider the action graphs Γn(A) and Γ∞(A) for bounded and polynomial automata A, which model the action of automata on words of length n and infinite words, respectively. A method for finding the orbital contracting coefficient and the growth of the diameters of graphs Γn(A) for a bounded automaton is established. We give estimates on the growth degrees of the graphs Γ∞(A) for bounded automata. It is proved that the graphs Γ∞(A) for non-deterministic polynomial automata have subexponential growth.
uk
Видавничий дім "Академперіодика" НАН України
Доповіді НАН України
Інформатика та кібернетика
Ріст графів дії скінченних автоматів
Рост графов действия конечных автоматов
Growth of action graphs of finite automata
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Ріст графів дії скінченних автоматів
spellingShingle Ріст графів дії скінченних автоматів
Бондаренко, Є.В.
Інформатика та кібернетика
title_short Ріст графів дії скінченних автоматів
title_full Ріст графів дії скінченних автоматів
title_fullStr Ріст графів дії скінченних автоматів
title_full_unstemmed Ріст графів дії скінченних автоматів
title_sort ріст графів дії скінченних автоматів
author Бондаренко, Є.В.
author_facet Бондаренко, Є.В.
topic Інформатика та кібернетика
topic_facet Інформатика та кібернетика
publishDate 2014
language Ukrainian
container_title Доповіді НАН України
publisher Видавничий дім "Академперіодика" НАН України
format Article
title_alt Рост графов действия конечных автоматов
Growth of action graphs of finite automata
description Розглядаються графи дiї Γn(A) i Γ∞(A) для обмежених i полiномiальних автоматiв A, якi моделюють дiю автоматiв на словах довжиною n i нескiнченних словах вiдповiдно. Встановлено метод знаходження орбiтального коефiцiєнта стиску обмежених автоматiв, росту дiаметрiв графiв Γn(A) для обмежених автоматiв, наведено оцiнки на степiнь полiномiального росту графiв Γ∞(A). Доведено, що графи Γ∞(A) для недетермiнованих полiномiальних автоматiв мають субекспоненцiйний рiст. Рассматриваются графы действия Γn(A) и Γ∞(A) для ограниченных и полиномиальных автоматов A, которые моделируют действие автоматов на словах длиной n и бесконечных словах соответственно. Установлен метод нахождения орбитального коэффициента стягивания ограниченных автоматов, роста диаметров графов Γn(A) для ограниченных автоматов, приведены оценки на степень полиномиального роста графов Γ∞(A). Доказано, что графы Γ∞(A) для недетерминированных полиномиальных автоматов имеют субэкспоненциальный рост. We consider the action graphs Γn(A) and Γ∞(A) for bounded and polynomial automata A, which model the action of automata on words of length n and infinite words, respectively. A method for finding the orbital contracting coefficient and the growth of the diameters of graphs Γn(A) for a bounded automaton is established. We give estimates on the growth degrees of the graphs Γ∞(A) for bounded automata. It is proved that the graphs Γ∞(A) for non-deterministic polynomial automata have subexponential growth.
issn 1025-6415
url https://nasplib.isofts.kiev.ua/handle/123456789/87811
citation_txt Ріст графів дії скінченних автоматів / Є.В. Бондаренко // Доповiдi Нацiональної академiї наук України. — 2014. — № 6. — С. 37-41. — Бібліогр.: 6 назв. — укр.
work_keys_str_mv AT bondarenkoêv rístgrafívdíískínčennihavtomatív
AT bondarenkoêv rostgrafovdeistviâkonečnyhavtomatov
AT bondarenkoêv growthofactiongraphsoffiniteautomata
first_indexed 2025-12-07T15:40:48Z
last_indexed 2025-12-07T15:40:48Z
_version_ 1850864617487597568

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