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

Вестник ТвГУ. Серия: Прикладная математика, 2017, выпуск 4, страницы 25–33 (Mi vtpmk186)

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

О выразительной силе логики одноместного транзитивного замыкания для дискретного порядка

С. М. Дудаков

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

Аннотация: В работе показано, что в теории дискретного линейного порядка с одноместным оператором транзитивного замыкания с помощью формул длины $n$ можно представить сложение, умножение и экспоненту для натуральных чисел вплоть до $H_2(n)$, где $H_2(n)$ — гиперэкспонента.

Ключевые слова: транзитивное замыкание, дискретный порядок, выразительная сила.

УДК: 510.675, 510.531

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

DOI: 10.26456/vtpmk186



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


© МИАН, 2024