RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 2020, том 32, выпуск 2, страницы 44–60 (Mi dm1588)

Об условиях $A$-полноты линейных автоматов над двоично-рациональными числами

Д. В. Ронжин

МГУ им. М.В. Ломоносова

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

Ключевые слова: конечные автоматы,линейные автоматы, двоично-рациональные числа, $A$-полнота, предполный класс.

УДК: 519.716.3

Статья поступила: 07.08.2019

DOI: 10.4213/dm1588


 Англоязычная версия: Discrete Mathematics and Applications, 2021, 31:3, 179–192

Реферативные базы данных:


© МИАН, 2024