Ріст графів дії скінченних автоматів
Розглядаються графи д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
|
| Назва видання: | Доповіді НАН України |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/87811 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Цитувати: | Ріст графів дії скінченних автоматів / Є.В. Бондаренко // Доповiдi Нацiональної академiї наук України. — 2014. — № 6. — С. 37-41. — Бібліогр.: 6 назв. — укр. |
Репозиторії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-87811 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-878112015-10-27T03:02:00Z Ріст графів дії скінченних автоматів Бондаренко, Є.В. Інформатика та кібернетика Розглядаються графи д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. 2014 Article Ріст графів дії скінченних автоматів / Є.В. Бондаренко // Доповiдi Нацiональної академiї наук України. — 2014. — № 6. — С. 37-41. — Бібліогр.: 6 назв. — укр. 1025-6415 http://dspace.nbuv.gov.ua/handle/123456789/87811 519.176 uk Доповіді НАН України Видавничий дім "Академперіодика" НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Інформатика та кібернетика Інформатика та кібернетика |
| spellingShingle |
Інформатика та кібернетика Інформатика та кібернетика Бондаренко, Є.В. Ріст графів дії скінченних автоматів Доповіді НАН України |
| 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ст. |
| format |
Article |
| author |
Бондаренко, Є.В. |
| author_facet |
Бондаренко, Є.В. |
| author_sort |
Бондаренко, Є.В. |
| title |
Ріст графів дії скінченних автоматів |
| title_short |
Ріст графів дії скінченних автоматів |
| title_full |
Ріст графів дії скінченних автоматів |
| title_fullStr |
Ріст графів дії скінченних автоматів |
| title_full_unstemmed |
Ріст графів дії скінченних автоматів |
| title_sort |
ріст графів дії скінченних автоматів |
| publisher |
Видавничий дім "Академперіодика" НАН України |
| publishDate |
2014 |
| topic_facet |
Інформатика та кібернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/87811 |
| citation_txt |
Ріст графів дії скінченних автоматів / Є.В. Бондаренко // Доповiдi Нацiональної академiї наук України. — 2014. — № 6. — С. 37-41. — Бібліогр.: 6 назв. — укр. |
| series |
Доповіді НАН України |
| work_keys_str_mv |
AT bondarenkoêv rístgrafívdíískínčennihavtomatív |
| first_indexed |
2023-10-18T19:36:23Z |
| last_indexed |
2023-10-18T19:36:23Z |
| _version_ |
1796147417550159872 |