Известия Саратовского университета. Новая серия.
ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


автоматные отображения

Геометрическая форма автоматных отображений, рекуррентное и Z -рекуррентное определение последовательностей

Для автоматных отображений изложены метод построения геометрических образов, метод оценки сложности автоматных отображений по их геометрическим образам, метод Z-рекуррентного определения последовательностей. Изложен метод оценки сложности любых конечных последовательностей по числовым показателям рекуррентных и Z-рекуррентных определений последовательности. Числовые показатели рекуррентных и Z-рекуррентных определений последовательностей систематизированы в спектр рекуррентных определений, имеющий 5 уровней числовых показателей.

Алгоритм проверки транзитивности отображений, ассоциированных с конечными автоматами из групп ASp

В статье затрагивается вопрос определения свойства транзитивности автоматных отображений, определяемых конечными детерминированными автоматами. Приведен критерий транзитивности автоматных отображений на словах конечной длины в терминах конечных детерминированных автоматов и деревьев детерминированных функций. Показано, что для конечных автоматов из групп ASp можно построить алгоритм проверки транзитивности. Для доказательства данного факта использованы свойства абелевых групп перестановок.