About transitive property of mappings associated with a finite state machines from the groups as_P | Applied Discrete Mathematics. Supplement. 2016. № 9.

About transitive property of mappings associated with a finite state machines from the groups as_P

Checking the transitive property of the automaton mappings is discussed. A general criterion for transitivity of automaton mappings on words of length k G N is presented. For automata from groups AS_p, an algorithm for checking transitive property is proposed. The complexity of the algorithm depends on the number of automaton states and does not depend on the input word length. The upper bound of the algorithm complexity is specified.

Download file

Counter downloads: 212

Keywords

конечные автоматны, автоматные отображения группы ASp, транзитивность, finite state machines, automata mappings, AS_p groups, transitivity

Authors

Name	Organization	E-mail
Karandashov M. V.	Saratov National Research University	norg113@gmail.com

Всего: 1

References

Тяпаев Л. Б. Транзитивные семейства автоматных отображений jj Дискретные модели в теории управляющих систем: IX Междунар. конф., Москва и Подмосковье, 20-22 мая 2015. Труды j отв. ред. В.Б.Алексеев, Д. С. Романов, Б.Р.Данилов. М.: МАКС Пресс, 2015. С. 244-247.

Гилл А. Введение в теорию конечных автоматов. М.: Наука, 1966. 272 с.

Карандашов М. В. Исследование биективных автоматных отображений на кольце вычетов по модулю 2k jj Компьютерные науки и информационные технологии: Материалы Междунар. науч. конф. Саратов: Издат. центр «Наука», 2014. С. 148-152.

Яблонский С. В. Введение в дискретную математику: учеб. пособие для вузов. 2-е изд., перераб. и доп. М.: Наука, 1986. 384 с.

Калужнин Л. А., Сущанский В. И. Преобразования и перестановки: пер. с укр. 2-е изд., перераб. и доп. М.: Наука, 1985. 160 с.

Алешин С. В. Конечные автоматы и проблема Бернсайда о периодических группах // Матем. заметки. 1972. Т. 11. №3. С. 319-328.