Cover Image

On Polynomial-Time Decidability of k-Negations Fragments of First-Order Theories

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Haase, Christoph, Mansutti, Alessio, Pouly, Amaury
Format:	Preprint
Published:	2024
Subjects:	Logic in Computer Science
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Craig Interpolation for Decidable First-Order Fragments
by: Cate, Balder ten, et al.
Published: (2023)

Decidability Results for Fragments of First-Order Logic via a Symbolic Model Property
by: Elad, Neta, et al.
Published: (2026)

A Decidable Bundled Fragment of First-Order Modal Logic Without Finite Model Property
by: Joshi, Varad, et al.
Published: (2025)

Adding Circumscription to Decidable Fragments of First-Order Logic: A Complexity Rollercoaster
by: Lutz, Carsten, et al.
Published: (2024)

Decidability in First-Order Modal Logic with Non-Rigid Constants and Definite Descriptions
by: Artale, Alessandro, et al.
Published: (2025)

Decidability of Querying First-Order Theories via Countermodels of Finite Width
by: Feller, Thomas, et al.
Published: (2023)

On the Existential Theory of the Reals Enriched with Integer Powers of a Computable Number
by: Gallego-Hernández, Jorge, et al.
Published: (2025)

The Alternation Hierarchy of First-Order Logic on Words is Decidable
by: Barloy, Corentin, et al.
Published: (2025)

Deciding the Existence of Interpolants and Definitions in First-Order Modal Logic
by: Kurucz, Agi, et al.
Published: (2023)

How (and when) can you fit examples to logic-based hypothesis classes over infinite structures?
by: Benedikt, Michael, et al.
Published: (2026)

Positivity of Nearly Linearly Recurrent Sequences
by: Pouly, Amaury, et al.
Published: (2025)

Deciding Equations in the Time Warp Algebra
by: van Gool, Sam, et al.
Published: (2023)

Completeness Theorems for k-SUM and Geometric Friends: Deciding Fragments of Integer Linear Arithmetic
by: Gokaj, Geri, et al.
Published: (2025)

The Finite Satisfiability Problem for Two-Variable, First-Order Logic with one Transitive Relation is Decidable
by: Pratt-Hartmann, Ian
Published: (2017)

Optimization Modulo Integer Linear-Exponential Programs
by: Hitarth, S, et al.
Published: (2025)

On the Decidability of Monadic Theories of Arithmetic Predicates
by: Berthé, Valérie, et al.
Published: (2024)

The complexity of Presburger arithmetic with power or powers
by: Benedikt, Michael, et al.
Published: (2023)

One-Parametric Presburger Arithmetic has Quantifier Elimination
by: Mansutti, Alessio, et al.
Published: (2025)

Interpolation with Automated First-Order Reasoning
by: Wernhard, Christoph
Published: (2025)

Decidability of Quantum Modal Logic
by: Tokuo, Kenji
Published: (2026)

Decidability for Sturmian words
by: Hieronymi, Philipp, et al.
Published: (2021)

Integer Linear-Exponential Programming in NP by Quantifier Elimination
by: Chistikov, Dmitry, et al.
Published: (2024)

MCSAT Modulo Transcendental Arithmetics
by: Gallego-Hernández, Jorge, et al.
Published: (2026)

Dynamic Probability Logic: Decidability & Computability
by: Chopoghloo, Somayeh, et al.
Published: (2024)

Decidability of Quasi-Dense Modal Logics
by: Ostropolski-Nalewaja, Piotr, et al.
Published: (2024)

Generalized Decidability via Brouwer Trees
by: de Jong, Tom, et al.
Published: (2026)

Deciding Predicate Logical Theories of Real-Valued Functions
by: Ratschan, Stefan
Published: (2023)

Universal quantification makes automatic structures hard to decide
by: Haase, Christoph, et al.
Published: (2023)

Decidable Reasoning About Time in Finite-Domain Situation Calculus Theories
by: Hofmann, Till, et al.
Published: (2024)

Unravelling Cyclic First-Order Arithmetic
by: Leigh, Graham E., et al.
Published: (2025)

The Complexity of Fragments of Second-Order HyperLTL
by: Regaud, Gaëtan, et al.
Published: (2025)

Complexity of Weighted First-Order Model Counting in the Two-Variable Fragment with Counting Quantifiers: A Bound to Beat
by: Tóth, Jan, et al.
Published: (2024)

Modal Fragments
by: Bezhanishvili, Nick, et al.
Published: (2026)

Negated String Containment is Decidable (Technical Report)
by: Havlena, Vojtěch, et al.
Published: (2025)

Succinctness of Cosafety Fragments of LTL via Combinatorial Proof Systems (extended version)
by: Geatti, Luca, et al.
Published: (2024)

Deciding the Value of Two-Clock Almost Non-Zeno Weighted Timed Games
by: Vialard, Isa
Published: (2025)

A Two-Watched Literal Scheme for First-Order Logic
by: Briefs, Yasmine, et al.
Published: (2026)

Measuring Decidability as Related to Busy Beaver Numbers
by: Tandi, Gurpreet, et al.
Published: (2026)

On the Decidability of Presburger Arithmetic Expanded with Powers
by: Karimov, Toghrul, et al.
Published: (2024)

Deciding Termination of Simple Randomized Loops
by: Meyer, Éléanore, et al.
Published: (2025)