Complexity of the problem of being equivalent to Horn formulas. II Full article
| Journal |
Algebra and Logic
ISSN: 0002-5232 , E-ISSN: 1573-8302 |
||
|---|---|---|---|
| Output data | Year: 2022, Volume: 61, Number: 4, Pages: 318-327 Pages count : 10 DOI: 10.1007/s10469-023-09700-7 | ||
| Tags | horn formula, m-reducibility, algebra, mathematical logic and foundations | ||
| Authors |
|
||
| Affiliations |
|
Funding (2)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0011 |
| 2 | Russian Foundation for Basic Research | 20-01-00300 |
Abstract:
We look at the complexity of the existence problem for a Horn sentence equivalent to a given one. It is proved that for a signature consisting of one unary function symbol and any finite number of unary predicate symbols, the problem is computable. For a signature with at least two unary function symbols, it is stated that the problem mentioned is an m-complete ∑01set .
Cite:
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
Original:
Когабаев Н.Т.
О сложности проблемы эквивалентности хорновским формулам. 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 РИНЦ
Dates:
| Submitted: | Feb 16, 2022 |
| Published online: | Sep 30, 2022 |
| Accepted: | Mar 29, 2023 |
| Published print: | Apr 28, 2023 |
Identifiers:
| Web of science: | WOS:000980226100001 |
| Scopus: | 2-s2.0-85153747027 |
| Elibrary: | 59285581 |
| OpenAlex: | W4367314728 |