Часть 3. Математические модели

О сложности реализации элементарного базиса в классе одноместных линейных автоматов, сохраняющих нулевую последовательность

И. Ю. Ильин

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

Аннотация: Сейчас нам известны некоторые факты о полноте конечных множеств линейно-автоматных функций, найдены все предполные классы по операциям суперпозиции и композиции, выведены критерии полноты в терминах предполных классов. В данной работе доказаны оценки количества операций для выразимости задержки и нейтрального элемента в случая одноместных линейных автоматов, сохраняющих нулевую последовательность.

Ключевые слова: линейные автоматы, оценки сложности.