Complexity of the problem of ∀-representation for sentences ArticleGenre_short.SHORT_COMMUNICATION
| Journal |
Algebra and Logic
ISSN: 0002-5232 , E-ISSN: 1573-8302 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2023, Volume: 62, Number: 4, Pages: 372-375 Pages count : 4 DOI: 10.1007/s10469-024-09751-4 | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (1)
| 1 | Russian Science Foundation | 23-11-00170 |
Abstract:
We calculate the complexity of the existence problem of a ∀-sentence (exists-sentence) which is equivalent to a given sentence. We prove that for a signature consisting only of unary predicate symbols both of these problems are computable. If a signature contains at least two unary function 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 ∀-representation for sentences
Algebra and Logic. 2023. V.62. N4. P.372-375. DOI: 10.1007/s10469-024-09751-4 WOS Scopus РИНЦ OpenAlex
Complexity of the problem of ∀-representation for sentences
Algebra and Logic. 2023. V.62. N4. P.372-375. DOI: 10.1007/s10469-024-09751-4 WOS Scopus РИНЦ OpenAlex
Original:
Когабаев Н.Т.
О сложности проблемы ∀-представимости предложений
Алгебра и логика. 2023. Т.62. №4. С.552-557. DOI: 10.33048/alglog.2023.62.406 РИНЦ MathNet
О сложности проблемы ∀-представимости предложений
Алгебра и логика. 2023. Т.62. №4. С.552-557. DOI: 10.33048/alglog.2023.62.406 РИНЦ MathNet
Dates:
| Submitted: | Mar 22, 2024 |
| Published print: | Apr 27, 2024 |
| Accepted: | Jul 19, 2024 |
| Published online: | Jul 27, 2024 |
Identifiers:
| Web of science: | WOS:001279118700001 |
| Scopus: | 2-s2.0-85200033494 |
| Elibrary: | 73442216 |
| OpenAlex: | W4401052916 |
Citing:
Пока нет цитирований