The Fluted Fragment with Transitivity

DOI10.4230/LIPICS.MFCS.2019.18MaRDI QIDQ5092377zbMATH OpenOpenAlexFDO

Authors Ian Pratt-Hartmann, Lidia Tendera

Publication date 21 July 2022

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

zbMATH Keywords

complexitydecidabilityfirst-order logicsatisfiabilitytransitivity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• The fluted fragment with transitive relations
• The fluted fragment revisited
• On the satisfiability problem for fragments of two-variable logic with one transitive relation
• On the Finite Satisfiability Problem for the Guarded Fragment with Transitivity
• The guarded fragment with transitive guards

Cites work

• Complexity and nicety of fluted logic
• Complexity hierarchies beyond elementary
• Finite satisfiability for two‐variable, first‐order logic with one transitive relation is decidable
• Finite satisfiability of unary negation fragment with transitivity
• Fluted formulas and the limits of decidability
• scientific article; zbMATH DE number 1936671 (Why is no real title available?)
• scientific article; zbMATH DE number 965572 (Why is no real title available?)
• Modal languages and bounded fragments of predicate logic
• On the Decision Problem for Two-Variable First-Order Logic
• On the satisfiability problem for fragments of two-variable logic with one transitive relation
• Predicate-functors and the limits of decidability in logic
• Quine's fluted fragment is non-elementary
• Small substructures and decidability issues for first-order logic with two variables
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• The fluted fragment revisited
• Two-variable first-order logic with equivalence closure

Cited in

(4)

• The fluted fragment with transitive relations
• Transitivity and equivalence in decidable fragments of first-order logic: a survey
• Finite satisfiability of unary negation fragment with transitivity
• On homogeneous models of fluted languages

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5092377)