Аннотация:
В работе показано, что если рассмотреть алгебру из некоторых уноидов в виде «кустов», соединённых в бесконечную линию, и построить алгебру её конечных подмножеств, то полученная система имеет теорию, допускающую эффективную элиминацию кванторов независимо от исходной. Таким образом, показано, что теория алгебры конечных подмножеств может быть существенно проще алгоритмически, чем теория исходной, а операция объединения для алгебр подмножеств является существенной для алгоритмических свойств.
\RBibitem{Dud19}
\by С.~М.~Дудаков
\paper Об алгоритмических свойствах алгебры конечных подмножеств некоторых уноидов
\jour Вестник ТвГУ. Серия: Прикладная математика
\yr 2019
\issue 4
\pages 108--116
\mathnet{http://mi.mathnet.ru/vtpmk550}
\crossref{https://doi.org/10.26456/vtpmk550}
\elib{https://elibrary.ru/item.asp?id=41803978}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vtpmk550
https://www.mathnet.ru/rus/vtpmk/y2019/i4/p108
Эта публикация цитируется в следующих 8 статьяx:
С. М. Дудаков, “Проблемы алгоритмической разрешимости и аксиоматизации алгебры конечных подмножеств для бинарных операций”, Изв. РАН. Сер. матем., 89:2 (2025), 3–24
B. N. Karlov, “On Undecidability of Subset Theories of Some Unars”, Dokl. Math., 2024
B. N. Karlov, “On undecidability of subset theories of some unars”, Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ, 516 (2024), 15
С. М. Дудаков, “О моноиде с разрешимой теорией конечных подмножеств”, Вестник ТвГУ. Серия: Прикладная математика, 2024, № 2, 27–38
С. М. Дудаков, “О теории моноида конечных подмножеств для одной абелевой группы кручения”, Вестник ТвГУ. Серия: Прикладная математика, 2021, № 2, 39–55
Б. Н. Карлов, “Об элементарной эквивалентности некоторых уноидов и уноидов их подмножеств”, Вестник ТвГУ. Серия: Прикладная математика, 2021, № 3, 18–32
S M Dudakov, “On Undecidability of Subset Theory for Some Monoids”, J. Phys.: Conf. Ser., 1902:1 (2021), 012060
С. М. Дудаков, “Об определимости в алгебре конечных языков с конкатенацией множества односимвольных языков”, Вестник ТвГУ. Серия: Прикладная математика, 2020, № 4, 5–13
Цитирование в формате AMSBIB
Обратная связь: