RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Тверского государственного университета. Серия: Прикладная математика // Архив

Вестник ТвГУ. Серия: Прикладная математика, 2019, выпуск 4, страницы 108–116 (Mi vtpmk550)

Эта публикация цитируется в 5 статьях

Теоретические основы информатики

Об алгоритмических свойствах алгебры конечных подмножеств некоторых уноидов

С. М. Дудаков

Тверской государственный университет, г. Тверь

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

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

УДК: 512.573, 519.17

Поступила в редакцию: 03.12.2019
Исправленный вариант: 20.12.2019

DOI: 10.26456/vtpmk550



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


© МИАН, 2024