Интеллектуальные системы.
Теория и приложения

Аннотация

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

Ключевые слова: теория автоматов, переходные системы, подстановка, кодирование, сложность, булев оператор.