Ріст графів дії скінченних автоматів
Розглядаються графи д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 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Видавничий дім "Академперіодика" НАН України
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| Резюме: | Розглядаються графи д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 |