Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
Complexity of the Problem of ∀-Representation for Sentences. / Когабаев, Нурлан Талгатович.
в: Algebra and Logic, Том 62, № 4, 09.2023, стр. 372-375.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - Complexity of the Problem of ∀-Representation for Sentences
AU - Когабаев, Нурлан Талгатович
N1 - Supported by the Russian Science Foundation, project No. 23-11-00170; https://rscf.ru/project/23-11-00170 .
PY - 2023/9
Y1 - 2023/9
N2 - The algorithmic problem of Horn representability for sentences was dealt with in [1, 2] where sharp complexity bounds for this problem were obtained for all possible signatures. The study of the given problem was initially justified by peculiarities of stable functioning of certain applied logic systems. As a natural mathematical modification of the problem we may consider representability of sentences in some other special form. At the International Conference “Mal’tsev readings 2022,” S. S. Goncharov asked me the question on estimation of the complexity of the problem of ∀-representability for sentences. The present paper is devoted to the answer to this question.
AB - The algorithmic problem of Horn representability for sentences was dealt with in [1, 2] where sharp complexity bounds for this problem were obtained for all possible signatures. The study of the given problem was initially justified by peculiarities of stable functioning of certain applied logic systems. As a natural mathematical modification of the problem we may consider representability of sentences in some other special form. At the International Conference “Mal’tsev readings 2022,” S. S. Goncharov asked me the question on estimation of the complexity of the problem of ∀-representability for sentences. The present paper is devoted to the answer to this question.
KW - PA-degree
KW - autostability relative to strong constructivizations
KW - computable categoricity
KW - computable model
KW - decidable categoricity
KW - decidable categoricity spectrum
KW - decidable model
KW - degree of decidable categoricity
UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85200033494&origin=inward&txGid=949af25442215bd1012b9ac7a393af4b
UR - https://www.mendeley.com/catalogue/ca70a847-24e1-3147-b9f9-677591b642c5/
U2 - 10.1007/s10469-024-09751-4
DO - 10.1007/s10469-024-09751-4
M3 - Article
VL - 62
SP - 372
EP - 375
JO - Algebra and Logic
JF - Algebra and Logic
SN - 0002-5232
IS - 4
ER -
ID: 60410762