Complexity of the Problem of ∀-Representability for Sentences in Signatures with Unary Symbols

Standard

Complexity of the Problem of ∀-Representability for Sentences in Signatures with Unary Symbols. / Kogabaev, N. T.

In: Algebra and Logic, Vol. 65, No. 1, 15.10.2026, p. 52-63.

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

BibTeX

@article{032869ec1a6b45ba9f072703e52f7643,

title = "Complexity of the Problem of ∀-Representability for Sentences in Signatures with Unary Symbols",

abstract = "We study the complexity of the existence problem of a ∀-sentence (∃-sentence) equivalent to a given sentence in signatures containing only unary symbols. We prove that if the signature consists of an at most one function symbol and an arbitrary number of predicate symbols, then both these problems are computable. If the signature contains at least two function symbols and arbitrarily many predicate symbols, we establish that each of these problems is an m-complete Σ10-set.",

keywords = "computability, m-reducibility, Σ10-set, ∀-sentence, ∃-sentence, ∀-предложение, ∃-предложение, вычислимость, m-сводимость, Σ⁰₁-множество",

author = "Kogabaev, {N. T.}",

note = "Kogabaev, N.T. Complexity of the Problem of ∀-Representability for Sentences in Signatures with Unary Symbols. Algebra Logic 65, 52–63 (2026). https://doi.org/10.1007/s10469-026-09854-0 The work was carried out with the support of the Russian Science Foundation (project No. 23-11-00170, https://rscf.ru/project/23-11-00170).",

year = "2026",

month = oct,

day = "15",

doi = "10.1007/s10469-026-09854-0",

language = "English",

volume = "65",

pages = "52--63",

journal = "Algebra and Logic",

issn = "0002-5232",

publisher = "Springer US",

number = "1",

}

RIS

TY - JOUR

T1 - Complexity of the Problem of ∀-Representability for Sentences in Signatures with Unary Symbols

AU - Kogabaev, N. T.

N1 - Kogabaev, N.T. Complexity of the Problem of ∀-Representability for Sentences in Signatures with Unary Symbols. Algebra Logic 65, 52–63 (2026). https://doi.org/10.1007/s10469-026-09854-0 The work was carried out with the support of the Russian Science Foundation (project No. 23-11-00170, https://rscf.ru/project/23-11-00170).

PY - 2026/10/15

Y1 - 2026/10/15

N2 - We study the complexity of the existence problem of a ∀-sentence (∃-sentence) equivalent to a given sentence in signatures containing only unary symbols. We prove that if the signature consists of an at most one function symbol and an arbitrary number of predicate symbols, then both these problems are computable. If the signature contains at least two function symbols and arbitrarily many predicate symbols, we establish that each of these problems is an m-complete Σ10-set.

AB - We study the complexity of the existence problem of a ∀-sentence (∃-sentence) equivalent to a given sentence in signatures containing only unary symbols. We prove that if the signature consists of an at most one function symbol and an arbitrary number of predicate symbols, then both these problems are computable. If the signature contains at least two function symbols and arbitrarily many predicate symbols, we establish that each of these problems is an m-complete Σ10-set.

KW - computability

KW - m-reducibility

KW - Σ10-set

KW - ∀-sentence

KW - ∃-sentence

KW - ∀-предложение

KW - ∃-предложение

KW - вычислимость

KW - m-сводимость

KW - Σ⁰₁-множество

UR - https://www.mendeley.com/catalogue/ebee89c9-c9be-3478-a58f-61e24256413b/

UR - https://www.scopus.com/pages/publications/105053926541

U2 - 10.1007/s10469-026-09854-0

DO - 10.1007/s10469-026-09854-0

M3 - Article

VL - 65

SP - 52

EP - 63

JO - Algebra and Logic

JF - Algebra and Logic

SN - 0002-5232

IS - 1

ER -

ID: 85123915