Розроблено алгоритми функціонування кінцевих автоматів з псевдовипадковими переходами з одного стану в інший, які є завадостійкими до віртуальних послідовностей і здійснюють одновимірний пошук точки екстремуму унімодальної функції. Такі кінцеві автомати є генераторами шифру заміни (підстановки) для символів вхідного алфавіту. Підстановки, що формуються таким автоматом, дозволили для одного й того ж самого символу генерувати множину підстановок різної довжини (генеруються префіксні коди). Вибір підстановок для того ж самого символу вхідного алфавіту здійснюється псевдовипадковим чином. Різноманіття алгоритмів функціонування кінцевих автоматів з псевдовипадковими переходами, які є завадостійкими до віртуальних послідовностей, і використання запропонованих кодів значно ускладнює процес розкриття шифротексту.

  Скачати повний текст

Досліджено групу всіх скінченно станових автоморфізмів регулярного кореневого дерева. Встановлено умови скінченності самоподібних підгруп цієї групи й умови спряженості елементів у цій групі. Виділено клас автоматів без циклів з виходом і доведено, що група автомата без циклів з виходом скінченна. Встановлено критерій абелевості групи автомата та доведено, що абелева група автомата буде скінченною тоді і лише тоді, коли автомат не містить циклів з виходом. Для автомата без циклів з виходом з n станами за певних додаткових умов доведено точність дії його групи на n-му рівні кореневого дерева. У випадку бінарного алфавіту знайдено точну оцінку порядку групи автомата як функцію від n. З точністю до ізоморфізму знайдено повний список груп автоматів без циклів з виходом з 2, 3, 4 та 5 станами. Доведено критерій спряженості елементів скінченного порядку та критерій спряженості з додавальною машиною над бінарним алфавітом в групі всіх скінченно станових автоморфізмів.

  Скачати повний текст

Досліджено функції росту автоматів Мілі з двома станами над двохелементним алфавітом та породжених ними напівгруп автоматних перетворень. Обчислено функції росту автоматів Мілі, описано в термінах твірних та визначальних співвідношень напівгрупи автоматних перетворень, породжених зазначеними автоматами, наведено їх функції росту та висвітлено основні властивості. Знайдено найменший можливий автомат Мілі проміжного росту, охарактеризовано автомати лінійного росту, які породжують напівгрупи квадратичного росту, а також всі необоротні автомати з двома станами над двохелементним алфавітом, що породжують напівгрупи експоненційного росту з нетривіальними визначальними співвідношеннями та вільну напівгрупу другого рангу. Розроблено програмний комплекс для дослідження функцій росту автоматів та породжених ними напівгруп автоматних перетворень.

  Скачати повний текст