The Fluted Fragment with Transitivity

DOI10.4230/LIPIcs.MFCS.2019.18OpenAlexW2971340596MaRDI QIDQ5092377

Lidia Tendera, Ian Pratt-Hartmann

Publication date: 21 July 2022

Full work available at URL: https://arxiv.org/abs/1906.09131

zbMATH Keywords

complexityfirst-order logicdecidabilitytransitivitysatisfiability

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

The fluted fragment with transitive relations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Predicate-functors and the limits of decidability in logic
• Modal languages and bounded fragments of predicate logic
• Complexity and nicety of fluted logic
• Complexity Hierarchies beyond Elementary
• Small substructures and decidability issues for first-order logic with two variables
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• On the Decision Problem for Two-Variable First-Order Logic
• Fluted formulas and the limits of decidability
• Finite satisfiability for two‐variable, first‐order logic with one transitive relation is decidable
• THE FLUTED FRAGMENT REVISITED
• On the satisfiability problem for fragments of two-variable logic with one transitive relation
• Quine's Fluted Fragment is Non-Elementary
• Two-Variable First-Order Logic with Equivalence Closure

This page was built for publication: The Fluted Fragment with Transitivity