Complexity of the problem of ∀-representability for sentences in signatures with unary symbols Full article
| Journal |
Algebra and Logic
ISSN: 0002-5232 , E-ISSN: 1573-8302 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2026, Volume: 65, Number: 1, Pages: 52-63 Pages count : 12 DOI: 10.1007/s10469-026-09854-0 | ||||
| Tags | ∀-sentence, ∃-sentence, computability, m-reducibility, $\Sigma^0_1$-set | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (1)
| 1 | Russian Science Foundation | 23-11-00170 |
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 $\Sigma^0_1$-set.
Cite:
Kogabaev N.T.
Complexity of the problem of ∀-representability for sentences in signatures with unary symbols
Algebra and Logic. 2026. V.65. N1. P.52-63. DOI: 10.1007/s10469-026-09854-0 WOS Scopus OpenAlex
Complexity of the problem of ∀-representability for sentences in signatures with unary symbols
Algebra and Logic. 2026. V.65. N1. P.52-63. DOI: 10.1007/s10469-026-09854-0 WOS Scopus OpenAlex
Dates:
| Submitted: | Jun 2, 2026 |
| Accepted: | Sep 2, 2026 |
| Published online: | Oct 15, 2026 |
Identifiers:
| ≡ Web of science: | WOS:001904541100001 |
| ≡ Scopus: | 2-s2.0-105053926541 |
| ≡ OpenAlex: | W7222250309 |