Ріст графів дії скінченних автоматів
Розглядаються графи д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) для о...
Gespeichert in:
| Veröffentlicht in: | Доповіді НАН України |
|---|---|
| Datum: | 2014 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Видавничий дім "Академперіодика" НАН України
2014
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/87811 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Ріст графів дії скінченних автоматів / Є.В. Бондаренко // Доповiдi Нацiональної академiї наук України. — 2014. — № 6. — С. 37-41. — Бібліогр.: 6 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862678932598292480 |
|---|---|
| author | Бондаренко, Є.В. |
| author_facet | Бондаренко, Є.В. |
| citation_txt | Ріст графів дії скінченних автоматів / Є.В. Бондаренко // Доповiдi Нацiональної академiї наук України. — 2014. — № 6. — С. 37-41. — Бібліогр.: 6 назв. — укр. |
| collection | DSpace DC |
| container_title | Доповіді НАН України |
| 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.
|
| first_indexed | 2025-12-07T15:40:48Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-87811 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | Ukrainian |
| last_indexed | 2025-12-07T15:40:48Z |
| publishDate | 2014 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| 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 |
| spellingShingle | Ріст графів дії скінченних автоматів Бондаренко, Є.В. Інформатика та кібернетика |
| title | Ріст графів дії скінченних автоматів |
| title_alt | Рост графов действия конечных автоматов Growth of action graphs of finite automata |
| title_full | Ріст графів дії скінченних автоматів |
| title_fullStr | Ріст графів дії скінченних автоматів |
| title_full_unstemmed | Ріст графів дії скінченних автоматів |
| title_short | Ріст графів дії скінченних автоматів |
| title_sort | ріст графів дії скінченних автоматів |
| topic | Інформатика та кібернетика |
| topic_facet | Інформатика та кібернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/87811 |
| work_keys_str_mv | AT bondarenkoêv rístgrafívdíískínčennihavtomatív AT bondarenkoêv rostgrafovdeistviâkonečnyhavtomatov AT bondarenkoêv growthofactiongraphsoffiniteautomata |