О сложности проблемы ∀-представимости предложений Full article
| Journal |
Алгебра и логика
ISSN: 0373-9252 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2023, Volume: 62, Number: 4, Pages: 552-557 Pages count : 6 DOI: 10.33048/alglog.2023.62.406 | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (1)
| 1 | Russian Science Foundation | 23-11-00170 |
Abstract:
Изучается сложность проблемы существования ∀-предложения (exists-предложения), эквивалентного данному предложению. Доказывается, что для сигнатуры, состоящей только из одноместных предикатных символов, обе данные проблемы вычислимы. Если же сигнатура содержит хотя бы два одноместных функциональных символа, установлено, что каждая из указанных проблем является m-полным Sigma^0_1-множеством.
Cite:
Когабаев Н.Т.
О сложности проблемы ∀-представимости предложений
Алгебра и логика. 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
Translated:
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
Dates:
| Submitted: | Mar 22, 2024 |
| Published print: | Apr 27, 2024 |
| Accepted: | Jul 19, 2024 |
| Published online: | Jul 27, 2024 |
Citing:
Пока нет цитирований