Ordered Fragments of First-Order Logic

Using a recently introduced algebraic framework for classifying fragments of first-order logic, we study the complexity of the satisfiability problem for several ordered fragments of first-order logic, which are obtained from the ordered logic and the fluted logic by modifying some of their syntactical restrictions.

Logic, Reasoning, and Knowledge Computability, Logic, AI Algorithms Logic, programming, and type systems

View graph Source

Paper

Similar papers

On the Limits of Decision:the Adjacent Fragment of First-Order LogicBednarczyk, Bartosz, Kojelis, Daumantas; id_orcid 0000-0002-1632-9498, Pratt-Hartmann, Ian; id_orcid 0000-0003-0062-043X2023 · Research Explorer (The University of Manchester) In Library

FlutingIan Pratt‐Hartmann2023 In Library

Algebraic classifications for fragments of first-order logic and beyondReijo Jaakkola, Antti Kuusisto2020 · arXiv (Cornell University) In Library

Generalized Bundled Fragments for First-Order Modal LogicMo Liu, Anantha Padmanabha, R. Ramanujam et al.2022 · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) In Library

On two-variable first-order logic with a partial orderDariusz Marzec, Lidia Tendera2025 · Journal of Logic and Computation In Library

Complexity Assessments for Decidable Fragments of Set Theory. I: A Taxonomy for the Boolean Case*Domenico Cantone, Andrea De Domenico, Pietro Maugeri et al.2021 · Fundamenta Informaticae In Library

Order-Invariance in the Two-Variable Fragment of First-Order LogicJulien Grange2022 · arXiv (Cornell University) In Library

Second-Order Quantifier Elimination and Uniform Interpolation for Bath Path Logic and the Ordered FragmentRenate A. Schmidt, Hongkai Yin2026 · arXiv (Cornell University) In Library

Separation and Definability in Fragments of Two-Variable First-Order Logic with CountingLouwe B. Kuijer, Tony Tan, Frank Wolter et al.2025 · arXiv (Cornell University) In Library

Modal FragmentsNick Bezhanishvili, Balder ten Cate, Arunavo Ganguly et al.2026 · Open MIND In Library

Source of record

OpenAlex

44B

Welcome.

This panel sticks with you. Pick anything below and it opens right beside it, so you can dig through 60,000-plus records without ever losing your spot here.

Travel 44B

LibraryPapers, policy, standards, statute LabsEvery organization building AI ModelsIntelligence, price, and speed BenchmarksThe evaluation catalog IncidentsAI failures and harms SearchOne field across everything DashboardThe state of AI accountability in NY 44B RegistryThe Art. 44-B compliance portal