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

О свойстве линейной реализуемости отображений

С. Б. Родин

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

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

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