Восстановление вектора начального состояния нелинейных автоматов над конечным кольцом

Abstract

Для автоматів Мілі та Мура над скінченним комутативно-асоціативним кільцем з одиницею, функція переходів яких визначена за допомогою нелінійних рівнянь другого степеня, а функція виходу є відповідно афінним та лінійним відображенням множини станів, розв’язано задачу відновлення вектора початкового стану. Розглянуто випадок, коли ця задача тривіальна. Виявлено, що у інших випадках ця задача є важкою. Встановлено, що властивість «бути оборотним автоматом» взагалі не впливає на складність розв’язання задачі відновлення вектора початкового стану для досліджуваних автоматів.

For Mealy and Moore automata presented via quadric equations over any finite associative-commutative ring with the unit it is resolved the problem of reconstruction of initial state vector. Situation when this problem is a trivial one is considered. It is shown that in any other situation investigated problem is difficult. It is also established that for investigated automata the quality «to be reversible one» has no influence onto hardness of resolving reconstruction problem of initial state vector.