Complexity of the Problem of ∀-Representability for Sentences in Signatures with Unary Symbols

Graphs and Combinatorics · Springer Nature · 2026-03-01 · DOI: 10.1007/s10469-026-09854-0

Abstract

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}_{1}^{0}$$-set.

Read at publisher →

Similar articles