Гончаров С. С., Свириденко Д. И.
Рекурсивные термы в семантическом программировании

Для построения обогащения языка с ограниченными кванторами расширяется понятие терма конструкцией построения условных и рекурсивных по спискам термов. Показано, что полученное расширение языка формул с ограниченными кванторами над структурами с наследственно конечными списками является консервативным обогащением, а новые термы $\Delta$-определимы в основном языке.

S. S. Goncharov, D. I. Sviridenko
Recursive Terms in Semantic Programming

For constructing an enrichment of a language with restricted quantifiers, we extend the notion of term by the construction of the terms conditional and recursive with respect to lists. We show that the so-obtained extension of the language of formulas with restricted quantifiers over structures with hereditary finite lists is a conservative enrichment and the new terms are $\Delta$-definable in the basic language.

DOI 10.17377/smzh.2018.59.605
Ключевые слова: формулы, термы, ограниченные кванторы, $\Delta_0$-формулы, $\Delta$-формулы, $\Sigma$-формулы, семантическое программирование, вычислимость, вычислимость над абстрактными структурами, условные термы, рекурсивные термы, модели, наследственно конечные списки, наследственно конечные множества.

Свободный доступ к полным текстам предоставляется после 1 июля года, следующего за годом публикации