О сложности проблемы эквивалентности хорновским формулам. II Full article
| Journal |
Алгебра и логика
ISSN: 0373-9252 |
||
|---|---|---|---|
| Output data | Year: 2022, Volume: 61, Number: 4, Pages: 469-482 Pages count : 14 DOI: 10.33048/alglog.2022.61.406 | ||
| Tags | хорновская формула, m-сводимость, Σ01-множество | ||
| Authors |
|
||
| Affiliations |
|
Funding (2)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0011 |
| 2 | Russian Foundation for Basic Research | 20-01-00300 |
Abstract:
Изучается сложность проблемы существования хорновского предложения, эквивалентного данному предложению. Доказывается, что для сигнатуры, состоящей из одного одноместного функционального символа и любого конечного числа одноместных предикатных символов, данная проблема вычислима. Если же сигнатура содержит хотя бы два одноместных функциональных символа, устанавливается, что указанная проблема является m-полным Σ01-множеством.
Cite:
Когабаев Н.Т.
О сложности проблемы эквивалентности хорновским формулам. II
Алгебра и логика. 2022. Т.61. №4. С.469-482. DOI: 10.33048/alglog.2022.61.406 РИНЦ
О сложности проблемы эквивалентности хорновским формулам. II
Алгебра и логика. 2022. Т.61. №4. С.469-482. DOI: 10.33048/alglog.2022.61.406 РИНЦ
Translated:
Kogabaev N.T.
Complexity of the problem of being equivalent to Horn formulas. II
Algebra and Logic. 2022. V.61. N4. P.318-327. DOI: 10.1007/s10469-023-09700-7 WOS Scopus РИНЦ OpenAlex
Complexity of the problem of being equivalent to Horn formulas. II
Algebra and Logic. 2022. V.61. N4. P.318-327. DOI: 10.1007/s10469-023-09700-7 WOS Scopus РИНЦ OpenAlex
Dates:
| Submitted: | Feb 16, 2022 |
| Accepted: | Mar 29, 2023 |
| Published print: | Apr 6, 2023 |
| Published online: | Apr 6, 2023 |
Identifiers:
| Elibrary: | 50464757 |
Citing:
| DB | Citing |
|---|---|
| Elibrary | 1 |