Раціональність функцій росту ініціальних автоматів Мілі

Раціональність функцій росту ініціальних автоматів Мілі

Функція росту gA(n) ініціального автомата Мілі A обчислює кількість станів у композиції автоматів A^n = Ao…o A (n разів) після мінімізації, які досягаються з ініціального стану. Досліджено, коли генератриса функції росту є раціональною для таких класів ініціальних автоматів: стискуючих з нільпотен...

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2019
Автори: Бондаренко, Є.В., Скочко, В.М.
Формат: Стаття
Мова:Ukrainian
Опубліковано: Видавничий дім "Академперіодика" НАН України 2019
Назва видання:Доповіді НАН України
Теми:
Математика
Онлайн доступ:http://dspace.nbuv.gov.ua/handle/123456789/158072
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Раціональність функцій росту ініціальних автоматів Мілі / Є.В. Бондаренко, В.М. Скочко // Доповіді Національної академії наук України. — 2019. — № 3. — С. 3-8. — Бібліогр.: 13 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-158072
record_format dspace
spelling irk-123456789-1580722019-07-11T01:24:51Z Раціональність функцій росту ініціальних автоматів Мілі Бондаренко, Є.В. Скочко, В.М. Математика Функція росту gA(n) ініціального автомата Мілі A обчислює кількість станів у композиції автоматів A^n = Ao…o A (n разів) після мінімізації, які досягаються з ініціального стану. Досліджено, коли генератриса функції росту є раціональною для таких класів ініціальних автоматів: стискуючих з нільпотентною автоматною групою, біреверсивних, поліноміальних. Функция роста gA(n) инициального автомата Мили A подcчитывает количество состояний в композиции автоматов A^n = Ao…o A (n раз) после минимизации, достижимых с инициального состояния. Исследовано, когда генератриса функции роста является рациональной для следующих классов автоматов: стягивающих с нильпотентной автоматной группой, биреверсивных, полиномиальных. The growth function γA(n) of an initial Mealy automaton A counts the number of states in a composition of automata A^n = Ao…o A (n times) after the minimization that are reachable from the initial state. We study the question when the generating function of the growth function is rational for the following automata classes: contracting with a nilpotent automaton group, bireversible, and polynomial ones. 2019 Article Раціональність функцій росту ініціальних автоматів Мілі / Є.В. Бондаренко, В.М. Скочко // Доповіді Національної академії наук України. — 2019. — № 3. — С. 3-8. — Бібліогр.: 13 назв. — укр. 1025-6415 DOI: doi.org/10.15407/dopovidi2019.03.003 http://dspace.nbuv.gov.ua/handle/123456789/158072 519.713.2 uk Доповіді НАН України Видавничий дім "Академперіодика" НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Ukrainian
topic Математика
Математика
spellingShingle Математика
Математика
Бондаренко, Є.В.
Скочко, В.М.
Раціональність функцій росту ініціальних автоматів Мілі
Доповіді НАН України
description Функція росту gA(n) ініціального автомата Мілі A обчислює кількість станів у композиції автоматів A^n = Ao…o A (n разів) після мінімізації, які досягаються з ініціального стану. Досліджено, коли генератриса функції росту є раціональною для таких класів ініціальних автоматів: стискуючих з нільпотентною автоматною групою, біреверсивних, поліноміальних.
format Article
author Бондаренко, Є.В.
Скочко, В.М.
author_facet Бондаренко, Є.В.
Скочко, В.М.
author_sort Бондаренко, Є.В.
title Раціональність функцій росту ініціальних автоматів Мілі
title_short Раціональність функцій росту ініціальних автоматів Мілі
title_full Раціональність функцій росту ініціальних автоматів Мілі
title_fullStr Раціональність функцій росту ініціальних автоматів Мілі
title_full_unstemmed Раціональність функцій росту ініціальних автоматів Мілі
title_sort раціональність функцій росту ініціальних автоматів мілі
publisher Видавничий дім "Академперіодика" НАН України
publishDate 2019
topic_facet Математика
url http://dspace.nbuv.gov.ua/handle/123456789/158072
citation_txt Раціональність функцій росту ініціальних автоматів Мілі / Є.В. Бондаренко, В.М. Скочко // Доповіді Національної академії наук України. — 2019. — № 3. — С. 3-8. — Бібліогр.: 13 назв. — укр.
series Доповіді НАН України
work_keys_str_mv AT bondarenkoêv racíonalʹnístʹfunkcíjrostuínícíalʹnihavtomatívmílí
AT skočkovm racíonalʹnístʹfunkcíjrostuínícíalʹnihavtomatívmílí
first_indexed 2025-07-14T10:31:11Z
last_indexed 2025-07-14T10:31:11Z
_version_ 1837617981153083392
fulltext 3ISSN 1025­6415. Допов. Нац. акад. наук Укр. 2019. № 3 МАТЕМАТИКА © Є.В. Бондаренко, В.М. Скочко, 2019 doi: https://doi.org/10.15407/dopovidi2019.03.003 УДК 519.713.2 Є.В. Бондаренко, В.М. Скочко Київський національний університет ім. Тараса Шевченка E­mail: ievgbond@gmail.com, vovaskochko@gmail.com Раціональність функцій росту ініціальних автоматів Мілі Представлено академіком НАН України М.О. Перестюком Функція росту ( )A nγ ініціального автомата Мілі A обчислює кількість станів у композиції автоматів �nA A A= o…o (n разів) після мінімізації, які досягаються з ініціального стану. Досліджено, коли генератри са функції росту є раціональною для таких класів ініціальних автоматів: стискуючих з нільпо­ тентною автоматною групою, біреверсивних, поліноміальних. Ключові слова: автомат Мілі, функція росту, автоматна група, поліноміальний автомат. ОПОВІДІ НАЦІОНАЛЬНОЇ АКАДЕМІЇ НАУК УКРАЇНИ МАТЕМАТИКА Функція росту γ ( )A n автомата Мілі �A обчислює кількість станів у композиції автома тів �nA A A= o…o (n разів) після мінімізації. Активне дослідження росту автоматів Мілі поча­ лося після того, як у 1983 р. Р.І. Григорчук [1] побудував перший приклад групи, яка має проміжний ріст між поліноміальним та експоненційним, що дало відповідь на питання Дж. Мілнора. Ця група, яка зараз називається групою Григорчука, є прикладом автоматної групи, тобто породжується автоматом Мілі. Функція росту автоматної (напів)групи екві­ валентна функції росту відповідного автомата Мілі, що дає алгебраїчну мотивацію для до­ слідження ітерацій автоматів. За останні двадцять років було знайдено багато автоматів Мілі з різноманітним типом росту: nα для ірраціонального α , ne , log 2log n mn для натураль­ них чисел 2m� тощо (див. [2—4]). Проте загалом проблема обчислення асимптотики функцій росту автоматів Мілі є широко відкритою. Тільки нещодавно була знайдена асимп­ тотика функції росту автомата, який породжує групу Григорчука (див. [5]). У даній роботі ми розпочинаємо систематичне вивчення функцій росту ініціальних автоматів Мілі. На відміну від неініціального автомата, функція росту ініціального автома­ та �A обчислює кількість тих станів в �nA після мінімізації, які досягаються з ініціального стану. Іншими словами, якщо ініціальний автомат �A задає деяке перетворення �f на про­ сторі слів, то функція росту ( )A nγ обчислює мінімальну кількість станів в автоматі, який реалізує n­кратну ітерацію функції ( )nf f f= o…o (n разів). Ми дослідили, коли генерат­ риса функції росту є раціональною функцією для стискуючих автоматів з нільпотентною 4 ISSN 1025­6415. Dopov. Nac. akad. nauk Ukr. 2019. № 3 Є.В. Бондаренко, В.М. Скочко автоматною групою, біреверсивних автоматів, поліноміальних автоматів, та знайшли ефек­ тивний метод для обчислення функції росту обмежених ініціальних автоматів. Попередні відомості. Нагадаємо необхідні відомості із теорії автоматів та автоматних груп (більше деталей можна знайти в [6] або [7]). Автоматом Мілі (далі просто автоматом) називається набір ( , , , )A Q X= π λ , де X — скінченна множина, вхідний/вихідний алфавіт; Q — скінченна множина станів автомата; : �Q X Qπ × → — функція переходів; :Q X Xλ × → — функція виходів. Автомат �A із зафік­ сованим початковим станом q Q∈ називається ініціальним і позначається �qA . Автомат можна ототожнювати з орієнтованим поміченим графом з множиною вершин Q та ребром ( ,� )q q x→ π з міткою |� ( ,� )x q xλ для всіх q Q∈ та x X∈ . Добутком (композицією) автоматів 1 1 1( , , , )A Q X= π λ та 2 2 2( , , , )B Q X= π λ над од ним алфавітом X називається автомат A Bo з множиною станів 1 2 ,Q Q× в якому функції пе­ реходів та виходів визначаються за правилом 1 2 1 1 2 2 2 2(( ,� ), � ) ( ( , � ( , � )),� ( , � )),q q x q q x q xπ = π λ π 1 2 1 1 2 2(( ,� ), � ) ( , � ( , � ))q q x q q xλ = λ λ . Неформально добуток автоматів A Bo відповідає за послідовну роботу автоматів, коли вихід автомата B підключено до входу автомата �A . Добутком ініціальних автоматів 1qA та 2qB називається ініціальний автомат 1 2( ,� )( ) q qA Bo . Позначимо через X∗ множину всіх скінченних слів над алфавітом X . Також позна­ чатимемо через kX множину слів довжини ,�k k ∈¥ . Кожен ініціальний автомат �qA ви­ значає перетворення на просторі X∗ , яке задається рекурсивно за правилом 1 2 1 2 )( ) � (q n p nA x x x y A x x=… … , де 1 1( , )y q x= λ і 1( , )p q x= π . Це правило можна інтерпретувати так: якщо автомат �A знаходиться у стані q та на вхід приймає слово 1 2 nx x x… над X , то він читає першу літеру 1x та стирає її, виводить літеру 1( , )q xλ на вихідній стрічці, переходить у стан 1( , )q xπ і так далі, поки не опрацює всі лі­ тери вхідного слова. Таким чином, після роботи автомата на вихідній стрічці буде написане слово 1 2( )q nA x x x… ; кінцевий ініціальний автомат (після опрацювання вхідного слова) бу­ демо позначати 1 2 | nq x x xA … з активним станом 1 2 | nx x xq … . Автомат називається мінімальним або редукованим, якщо різні стани автомата ви зна­ чають різні перетворення на просторі слів. Для кожного автомата �A існує єдиний мінімаль­ ний автомат ( )m A , стани якого задають ту саму множину перетворень, що і стани �A. Ана­ логічно, для ініціального автомата �qA існує єдиний мінімальний ініціальний автомат ( )qm A , який визначає те саме перетворення на просторі слів. Мінімізувати автомат можна за допомогою алгоритма Хопкрофта. Функцією росту (ініціального) автомата �A називається функція :Aγ →¥ ¥ , де ( )A nγ дорівнює кількості станів в автоматі ( )nm A . Оскільки добуток автоматів відповідає компо­ зиції відображень, то, як вже зазначалося на початку роботи, якщо �A є ініціальним і задає перетворення �f на просторі слів, то ( )A nγ дорівнює мінімальній кількості станів, необхід­ них для реалізації автоматом ітерації функції ( )nf f f= o…o (n разів). Будемо казати, що функція росту γ(n) є раціональною (алгебраїчною), якщо її генератриса 0 ( ) � ( ) n n x n xΓ = γ∑ � 5ISSN 1025­6415. Допов. Нац. акад. наук Укр. 2019. № 3 Раціональність функцій росту ініціальних автоматів Мілі є раціональною (відповідно, алгебраїчною) функцією. Зауважимо, що функція росту є ра­ ціональною для ініціальних автоматів �A , які мають скінченний порядок, тобто якщо існує таке n∈¥ , що nA визначає тотожне перетворення. Автомат �A називається оборотним, якщо всі стани автомата визначають оборотні пере­ творення (тобто можна сконструювати мінімальний обернений автомат 1�A − таким чином, що композиція �A та 1�A − тривіальна). Група, породжена відповідними перетвореннями від­ носно композиції, називається автоматною групою AG . Кожна група AG є підгрупою гру­ пи автоморфізмів Aut( )XT дерева XT , множиною вершин якого є X∗ , а ребрами є ( , )v vx для v X∗∈ та x X∈ . Автоморфізми дерева, які відповідають автоматам, можна описати таким чином. Для автоморфізму ∈Aut( )Xg T та вершини v X∗∈ визначимо його секцію ∈Aut( )v Xg T за правилом =( )vg u w , якщо =( ) ( )g vu g v w . Автоморфізм g задається дея­ ким ініціальним автоматом тоді і лише тоді, коли множина його секцій є скінченною. В цьо­ му випадку функція росту відповідного автомата дорівнює функції γ ( )g n , яка обчислює кількість секцій автоморфізму ng . Асимптотична поведінка функції γ ( )g n для Ag G∈ по­ в’язана зі складністю проблеми порядку в групі AG (див. [8]). Кажуть, що автомат �A діє транзитивно на рівнях, якщо група AG діє транзитивно на kX для всіх k ∈¥ . Результати. Окремо розглянемо функції росту для таких класів ініціальних автоматів: стискуючих, біреверсивних, поліноміальних та обмежених. Оборотний автомат �A називається стискуючим, якщо існує така скінченна множина AN G⊂ , що для кожного Ag G∈ виконується vg N∈ для всіх достатньо довгих слів v X∗∈ . У цьому випадку автоматна група AG теж називається стискуючою. Стисливість автомат­ них груп відповідає розширюючим властивостям в асоційованих динамічних системах. Важливими прикладами стискуючих груп є групи ітерованих монодромій посткритично скінченних раціональних функцій (див. [7]). Теорема 1. Нехай �A — стискуючий автомат і група AG нільпотентна. Тоді для Ag G∈ функція росту γ ( )g n є раціональною (еквівалентно, алгебраїчною) тоді і лише тоді, коли g має скінченний порядок. Теорема не виконується для розв’язних груп. Ми розглянули автомати з робіт [6, рис. 6] та [9], які породжують розв’язні групи 2¢ ¢ та 3¢ ¢ , і показали, що ці автомати, ініціа­ лізовані в довільному стані, мають раціональну функцію росту. Означення автомата є симетричним відносно множини станів та алфавіту. Це спосте­ реження дає змогу з кожним автоматом ( , , , )A Q X= π λ асоціювати дуальний автомат ( , , , )A Q X∂ = π λ ∂ = π λ′ ′( , , , )A X Q , в якому множини Q та X міняються ролями. Автомат �A називається біревер­ сивним, якщо �A , A∂ та 1A−∂( ) є оборотними. Біреверсивні автомати введені у роботі [10] у зв’язку з комменшураторами вільних груп. Встановлено, що біреверсивні автомати мають тісний зв’язок з ґратками у добутку двох дерев та квадратними комплексами (див. [11]). Теорема 2. Нехай A — біреверсивний автомат і дуальний автомат A∂ діє транзитивно на рівнях. Тоді для кожного стану s A∈ ініціальний автомат �sA має раціональну функцію росту. Розглянемо клас поліноміальних автоматів, які визначив С. Сідкі в роботі [12]. Нехай �A — ініціальний автомат над алфавітом X . Визначимо функцію ( )A kθ як кількість таких слів kv X∈ , що |vA визначає нетотожне перетворення. Оборотний автомат �A називається поліноміальним, якщо ( ) ( )A k P kθ � для деякого по лі нома ( )P k ; в цьому випадку степе­ нем автомата називається найменший степінь серед многочленів, які обмежують ( )A kθ . 6 ISSN 1025­6415. Dopov. Nac. akad. nauk Ukr. 2019. № 3 Є.В. Бондаренко, В.М. Скочко Теорема 3. Нехай �A — ініціальний поліноміальний автомат степеня d . Якщо �A має не скінченний порядок, то існують такі константи , 0C D > , що ( 1) (4 1)log (lo )( ) g d d AC n n D n + +γ� � для всіх 2n� . Зокрема, функція росту ініціального поліноміального автомата є раціональною (еквівалент­ но, алгебраїчною) тоді і лише тоді, коли він має скінченний порядок. Окремо виділяють клас обмежених автоматів — це поліноміальні автомати нульового степеня; тобто оборотний автомат �A є обмеженим, якщо функція ( )A kθ є обмеженою. Класичні приклади автоматних груп, такі як група Григорчука, група Гупти—Сідкі, група Базиліка, а також групи ітерованих монодромій посткритично скінченних многочленів, по­ роджуються обмеженими автоматами. За теоремою 3 для кожного ініціального обмеженого автомата �A нескінченного по­ рядку існують такі константи , 0C D > , що log (log( ) )AC n n D nγ� � для всіх 2n� . Ми винайшли метод для знаходження нижньої та верхньої границь min ( l ) im inf log A n n C n→∞ γ = та max ( l ) im sup log A n n C n→∞ γ = і показали, що min maxC C< для кожного обмеженого автомата нескінченного порядку. Таким чином, функція росту ( )A nγ коливається між двома логарифмічними функціями min logC n та max logC n . Доведено, що числа Cmin та Cmax можна подати у вигляді min log N d та max log N d для деяких натуральних чисел minN , maxN та d , які можна обчислити алгоритмічно за автома­ том �A . Ці результати спираються на циклічну структуру обмежених автоматів та отрима­ ну нами точну формулу для функції росту циклічних автоматів. Обмежений мінімальний автомат допускає таку характеризацію циклічної структури: різні орієнтовані цикли, крім петель у тривіальному стані, не мають спільних станів та не з’єднані орієнтованим шляхом. Стан автомата q A∈ називається фінітарним, якщо існує таке k ∈¥ , що |q vA визначає тотожне перетворення для всіх kv X∈ . Для кожного стану q обмеженого автомата �A існує така константа k ∈¥ , що для кожного kv X∈ стан |vq є фі­ нітарним або знаходиться на циклі. Це дає змогу звести вивчення функції росту обмеже­ ного автомата до циклічних автоматів (активний стан знаходиться на циклі). Нехай �A — обмежений ініціальний автомат і будемо припускати, що існує таке нату­ ральне число 2k� та літера x X∈ , що ( )kA x x= і |( )k k xA x A= . Зокрема, ця умова гаран­ тує, що �A має нескінченний порядок. Тоді функцію росту ( )A nγ можна обчислити таким чином. Спочатку обчислимо кількість фінітарних станів у ( )nm A , яку позначаємо ( )f A nγ . Для цього ми довели, що існують такі натуральні числа , 2d D� та скінченні множини ф інітарних автоматів iF , iF + для 0, , 1i D= −… , що множину фінітарних станів у ( )nm A можна знайти так: + = = + = ∪∪ ∪/ �mod� / �mod� 0 1 Fin ( ) i i k m A n d D n d D i i k n F F , 7ISSN 1025­6415. Допов. Нац. акад. наук Укр. 2019. № 3 Раціональність функцій росту ініціальних автоматів Мілі де log log n m d = і k — це перша ненульова позиція у зображенні n у системі числення за ос­ новою d . Тоді ( )f A nγ дорівнює кількості елементів у Fin ( )A n . Для знаходження кількості нефінітарних станів ми довели, що існують натуральні чис­ ла , 2d D� та iC для 20, , 1i d= −… і ( , )i jC , ( , )i jC + для 0, , 1i d= −… , 0, , 1j D= −… такі, що функцію росту ( )A nγ можна обчислити у такий спосіб: подамо n у системі числення за основою d , 1 0( )m dn r r r= … , тоді 1( , / �mod� ) ( , / �mod� ) 1 1 ( ) ( ) �i i m mi i k k f A dr rA r n d D r n d D i i n n C C C − + + = = γ = γ + + +∑ ∑ , де k — перша позиція з 0kr ≠ . Це дає ефективний метод для обчислення функції росту об­ межених автоматів. Зауважимо, що залишається відкритою проблема, чи існує алгоритм для знаходження порядку ініціального поліноміального автомата. Для обмежених автоматів такий алгоритм знайдено в роботі [8]. Нерозв’язність проблеми порядку в класі всіх оборотних автоматів нещодавно доведена в роботі [13]. ЦИТОВАНА ЛІТЕРАТУРА 1. Grigorchuk R.I. On the Milnor problem of group growth. Dokl. AN SSSR. 1983. 271, № 1. P. 30–33. 2. Bartholdi L., Reznykov I.I. A Mealy machine with polynomial growth of irrational degree. Int. J. Algebra Comput. 2008. 18, № 1. P. 59—82. doi: https://doi.org/10.1142/S0218196708004287 3. Bartholdi L., Reznykov I.I., Sushchansky V.I. The smallest Mealy automaton of intermediate growth. J. Algebra. 2006. 295, № 2. P. 387—414. doi: https://doi.org/10.1016/j.jalgebra.2004.08.040 4. Reznykov I.I., Sushchansky V.I. On the 3­state Mealy automata over an m­symbol alphabet of growth order log /2log ][ n mn . J. Algebra. 2006. 304, № 2. P. 712–754. doi: https://doi.org/10.1016/j.jalgebra.2006.03.039 5. Erschler A., Zheng T. Growth of periodic Grigorchuk groups. arXiv:1802.09077v1 [math. GR] 25 Feb 2018. 6. Григорчук Р.И., Некрашевич В.В., Сущанский В.И. Автоматы, динамические системы и группы. Тр. Мат. ин­та им. В.А. Стеклова. 2000. 231. С. 134—214. 7. Nekrashevych V. Self­similar groups. Providence, RI: AMS, 2005. 231 p. (Mathematical Surveys and Monographs; Vol. 117). doi: https://doi.org/10.1090/surv/117 8. Bondarenko I.V., Bondarenko N.V., Sidki S.N., Zapata F.R. On the conjugacy problem for finite­state automorphisms of regular rooted trees. With an appendix by Raphaël M. Jungers. Groups Geom. Dyn. 2013. 7, Iss. 2. P. 323—355. doi: https://doi.org/10.4171/GGD/184 9. Bondarenko I., D’Angeli D., Rodaro E. The lamplighter group 3¢ ¢ generated by a bireversible automaton. Commun. Algebra. 2016. 44, № 12. P. 5257—5268. doi: https://doi.org/10.1080/00927872.2016.1172602 10. Macedońska O., Nekrashevych V., Sushchansky V. Commensurators of groups and reversible automata. Dopov. Nac. acad. nauk Ukr. 2000. № 12. P. 36–39. 11. Glasner Y., Mozes S. Automata and square complexes. Geometriae Dedicata. 2005. 111, Iss. 1. P. 43—64. doi: https://doi.org/10.1007/s10711­004­1815­2 12. Sidki S. Automorphisms of one­rooted trees: growth, circuit structure, and acyclicity. J. Math. Sci. 2000. 100, № 1. P. 1925—1943. doi: https://doi.org/10.1007/BF02677504 13. Gillibert P. An automaton group with undecidable order and Engel problems. J. Algebra. 2018. 497. P. 363— 392. doi: https://doi.org/10.1016/j.jalgebra.2017.11.049 Надійшло до редакції 25.12.2018 8 ISSN 1025­6415. Dopov. Nac. akad. nauk Ukr. 2019. № 3 Є.В. Бондаренко, В.М. Скочко REFERENCES 1. Grigorchuk, R. I. (1983). On the Milnor problem of group growth. Dokl. AN SSSR, 271, No.1, pp. 30­33. 2. Bartholdi, L. & Reznykov, I. I. (2008). A Mealy machine with polynomial growth of irrational degree. Int. J. Algebra Comput., 18, No.1, pp. 59­82. doi: https://doi.org/10.1142/S0218196708004287 3. Bartholdi, L., Reznykov, I. I. & Sushchansky, V. I. (2006). The smallest Mealy automaton of intermediate growth. J. Algebra, 295, No. 2, pp. 387­414. doi: https://doi.org/10.1016/j.jalgebra.2004.08.040 4. Reznykov, I. I. & Sushchansky, V. I. (2006). On the 3­state Mealy automata over an m­symbol alphabet of growth order [nlog n/2log m]. J. Algebra, 304, No. 2, pp. 712­754. doi: https://doi.org/10.1016/j.jalgebra. 2006.03.039 5. Erschler, A. & Zheng, T. (2018). Growth of periodic Grigorchuk groups. arXiv:1802.09077v1 [math. GR] 25 Feb 2018. 6. Grigorchuk, R. I., Nekrashevych, V. V. & Sushchansky, V. I. (2000). Automata, dynamic systems and groups. Tr. mat. inst. im. V. A. Steklova, 231, pp. 134­214 (in Russian). 7. Nekrashevych, V. (2005). Self­similar groups. Mathematical Surveys and Monographs, Vol. 117. Providence, RI: AMS. doi: https://doi.org/10.1090/surv/117 8. Bondarenko, I. V., Bondarenko, N. V., Sidki, S. N. & Zapata, F. R. (2013). On the conjugacy problem for finite­ state automorphisms of regular rooted trees. With an appendix by Raphaël M. Jungers. Groups Geom. Dyn., 7, Iss. 2, pp. 323­355. doi: https://doi.org/10.4171/GGD/184 9. Bondarenko, I., D’Angeli, D. & Rodaro, E. (2016). The lamplighter group 3¢ ¢ generated by a bireversible automaton. Commun. Algebra, 44, No. 12, pp. 5257­5268. doi: https://doi.org/10.1080/00927872.2016.1172602 10. Macedońska, O., Nekrashevych, V. & Sushchansky, V. (2000). Commensurators of groups and reversible automata. Dopov. Nac. acad. nauk Ukr., No. 12, pp. 36­39. 11. Glasner, Y. & Mozes, S. (2005). Automata and square complexes. Geometriae Dedicata, 111, Iss. 1, pp. 43­64. doi: https://doi.org/10.1007/s10711­004­1815­2 12. Sidki, S. (2000). Automorphisms of one­rooted trees: growth, circuit structure, and acyclicity. J. Math. Sci., 100, No. 1, pp. 1925­1943. doi: https://doi.org/10.1007/BF02677504 13. Gillibert, P. (2018). An automaton group with undecidable order and Engel problems. J. Algebra, 497, pp. 363­392. doi: https://doi.org/10.1016/j.jalgebra.2017.11.049 Received 25.12.2018 Е.В. Бондаренко, В. М. Скочко Киевский национальный университет им. Тараса Шевченка E­mail: ievgbond@gmail.com, vovaskochko@gmail.com РАЦИОНАЛЬНОСТЬ ФУНКЦИЙ РОСТА ИНИЦИАЛЬНЫХ АВТОМАТОВ МИЛИ Функция роста ( )A nγ инициального автомата Мили A подcчитывает количество состояний в композиции автоматов �nA A A= o…o (n раз) после минимизации, достижимых с инициального состояния. Исследова­ но, когда генератриса функции роста является рациональной для следующих классов автоматов: стяги­ вающих с нильпотентной автоматной группой, биреверсивных, полиномиальных. Ключевые слова: автомат Мили, функция роста, автоматная группа, полиномиальный автомат. I.V. Bondarenko, V.M. Skochko Taras Shevchenko National University of Kiev E­mail: ievgbond@gmail.com, vovaskochko@gmail.com RATIONALITY OF THE GROWTH FUNCTIONS OF INITIAL MEALY AUTOMATA The growth function ( )A nγ of an initial Mealy automaton A counts the number of states in a composition of automata �nA A A= o…o (n times) after the minimization that are reachable from the initial state. We study the question when the generating function of the growth function is rational for the following automata classes: contracting with a nilpotent automaton group, bireversible, and polynomial ones. Keywords: Mealy automaton, growth function, automaton group, polynomial automaton.

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