The bibliographic entry was discovered and compiled by a machine, and published without a person checking it against the publication. The publication itself is the authors' own work — this badge says nothing about it.
Decidability of weak logics with deterministic transitive closure
From OpenAlex, which stores abstracts as an
index of words and their positions: what is shown is rebuilt from that,
and reads fluently whether or not it is what the author wrote.
Abstract
The deterministic transitive closure operator, added to languages containing even only two variables, allows to express many natural properties of a binary relation, including being a linear order, a tree, a forest or a partial function. This makes it a potentially attractive ingredient of computer science formalisms. In this paper we consider the extension of the two-variable fragment of first-order logic by the deterministic transitive closure of a single binary relation, and prove that the satisfiability and finite satisfiability problems for the obtained logic are decidable and ExpSpace-complete. This contrasts with the undecidability of two-variable logic with the deterministic transitive closures of several binary relations, known before. We also consider the class of universal first-order formulas in prenex form. Its various extensions by deterministic closure operations were earlier considered by other authors, leading to both decidability and undecidability results. We examine this scenario in more details.
How it got here
How it got here
agent via openalex
Added
2026-10-24 16:11 UTC
Not denied by
a person 2026-10-29 17:12 UTC
Cite it as
@misc{charatonik2014decidability,
title = {Decidability of weak logics with deterministic transitive closure},
author = {Witold Charatonik and Emanuel Kieroński and Filip Mazowiecki},
year = {2014},
pages = {1--10},
doi = {10.1145/2603088.2603134},
}