Complexity of the Problem of ∀-Representation for Sentences

Standard

Complexity of the Problem of ∀-Representation for Sentences. / Когабаев, Нурлан Талгатович.

In: Algebra and Logic, Vol. 62, No. 4, 09.2024, p. 372-375.

Research output: Contribution to journal › Article › peer-review

BibTeX

@article{d693983f77ed4d83805661feb4199416,

title = "Complexity of the Problem of ∀-Representation for Sentences",

abstract = "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{\textquoteright}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.",

keywords = "PA-degree, autostability relative to strong constructivizations, computable categoricity, computable model, decidable categoricity, decidable categoricity spectrum, decidable model, degree of decidable categoricity",

author = "Когабаев, {Нурлан Талгатович}",

note = "Supported by the Russian Science Foundation, project No. 23-11-00170; https://rscf.ru/project/23-11-00170 .",

year = "2024",

month = sep,

doi = "10.1007/s10469-024-09751-4",

language = "English",

volume = "62",

pages = "372--375",

journal = "Algebra and Logic",

issn = "0002-5232",

publisher = "Springer US",

number = "4",

}

RIS

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 - 2024/9

Y1 - 2024/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

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