RUS  ENG
Full version
JOURNALS // Algebra i logika // Archive

Algebra Logika, 2022 Volume 61, Number 4, Pages 469–482 (Mi al2723)

This article is cited in 1 paper

Complexity of the problem of being equivalent to Horn formulas. II

N. T. Kogabaev

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk

Abstract: We calculate 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 $\Sigma^0_1$-set.

Keywords: Horn formula, $m$-reducibility, $\Sigma^0_1$-set.

UDC: 510.53

Received: 16.02.2022
Revised: 29.03.2023

DOI: 10.33048/alglog.2022.61.406



© Steklov Math. Inst. of RAS, 2025