Complexity of the problem of ∀-representability for sentences in signatures with unary symbols | Sciact - Система учета научной деятельности ИМ СО РАН

Complexity of the problem of ∀-representability for sentences in signatures with unary symbols Научная публикация

Журнал

Algebra and Logic
ISSN: 0002-5232 , E-ISSN: 1573-8302

Вых. Данные

Год: 2026, Том: 65, Номер: 1, Страницы: 52-63 Страниц : 12 DOI: 10.1007/s10469-026-09854-0

Ключевые слова

∀-sentence, ∃-sentence, computability, m-reducibility, $\Sigma^0_1$-set

Авторы

Kogabaev N.T. ^1,2

Организации

1	Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
2	Novosibirsk State University, Novosibirsk, Russia

Информация о финансировании (1)

Российский научный фонд

23-11-00170

We study the complexity of the existence problem of a ∀-sentence (∃-sentence) equivalent to a given sentence in signatures containing only unary symbols. We prove that if the signature consists of an at most one function symbol and an arbitrary number of predicate symbols, then both these problems are computable. If the signature contains at least two function symbols and arbitrarily many predicate symbols, we establish that each of these problems is an m-complete $\Sigma^0_1$-set.

Kogabaev N.T.
Complexity of the problem of ∀-representability for sentences in signatures with unary symbols
Algebra and Logic. 2026. V.65. N1. P.52-63. DOI: 10.1007/s10469-026-09854-0 WOS Scopus OpenAlex

Поступила в редакцию:	2 июн. 2026 г.
Принята к публикации:	2 сент. 2026 г.
Опубликована online:	15 окт. 2026 г.

≡ Web of science:	WOS:001904541100001
≡ Scopus:	2-s2.0-105053926541
≡ OpenAlex:	W7222250309