Проблема породження для оборотних автоматів Мілі

Автор(и)

DOI:

https://doi.org/10.24144/2616-7700.2025.46(1).13-17

Ключові слова:

автомат Мілі, автоматна група, проблема породження, проблема підгрупи, нерозв'язна проблема

Анотація

Оборотний автомат Мілі A над алфавітом входів-виходів X породжує групу G(A) своєю дією на словах над X. Ми доводимо, що наступна проблема алгоритмічно нерозв'язна: за заданими двома оборотними автоматами Мілі, визначити, чи породжують вони одну й ту ж автоматну групу. Крім того, ми будуємо оборотний автомат Мілі A, для якого наступна проблема є нерозв'язною: за заданим оборотним автоматом Мілі B, визначити, чи породжує B групу G(A). Ми також доводимо, що проблема автоматної підгрупи та проблема тривіальності перетину є нерозв'язними.

Біографія автора

Є. Бондаренко, Київський національний університет імені Тараса Шевченка

Професор кафедри алгебри та комп'ютерної математики. Доктор фізико-математичних наук

Посилання

  1. 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. Groups Geom. Dyn., 7(2), 323–355. https://doi.org/10.4171/ggd/184
  2. Bondarenko, I. V., & Wächter, J. P. (2021). On orbits and the finiteness of bounded automaton groups. Internat. J. Algebra Comput., 31(6), 1177–1190. https://doi.org/10.1142/S0218196721400087
  3. Brunner, A. M., & Sidki, S. N. (1998). The generation of GL(n, Z) by finite state automata. Internat. J. Algebra Comput., 8(1), 127–139. https://doi.org/10.1142/s0218196798000077
  4. Gillibert, P. (2018). An automaton group with undecidable order and Engel problems. J. Algebra, 497, 363–392. https://doi.org/10.1016/j.jalgebra.2017.11.049
  5. Miller, C. F. III. (1972). On group theoretic decision problems and their classification. Princeton, NJ: Princeton University Press. https://doi.org/10.1515/9781400881789
  6. Nekrashevych, V. V. (2005). Self-similar groups. Providence, RI: Amer. Math. Soc. https://doi.org/10.1090/surv/117
  7. Šunić, Z., & Ventura, E. (2012). The conjugacy problem in automaton groups is not solvable. J. Algebra, 364, 148–154. https://doi.org/10.1016/j.jalgebra.2012.04.014

##submission.downloads##

Опубліковано

2025-06-03

Як цитувати

Бондаренко, Є. (2025). Проблема породження для оборотних автоматів Мілі. Науковий вісник Ужгородського університету. Серія «Математика і інформатика», 46(1), 13–17. https://doi.org/10.24144/2616-7700.2025.46(1).13-17

Номер

Том 46 № 1 (2025)

Розділ

Математика та статистика

Ліцензія

Авторське право (c) 2025 Є. Бондаренко

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.