The fluted fragment with transitive relations

DOI10.1016/j.apal.2021.103042zbMath1490.03010arXiv2006.11169OpenAlexW3197582276MaRDI QIDQ2238133

Lidia Tendera, Ian Pratt-Hartmann

Publication date: 29 October 2021

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

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

zbMATH Keywords

decidabilitytransitivitysatisfiabilityfluted logic

Mathematics Subject Classification ID

Logic in computer science (03B70) Classical first-order logic (03B10) Decidability of theories and sets of sentences (03B25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Descriptive complexity and finite models (68Q19)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Predicate-functors and the limits of decidability in logic
• On the complexity of the two-variable guarded fragment with transitive guards
• Complexity and nicety of fluted logic
• The guarded fragment with transitive guards
• 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
• Finite Satisfiability of the Two-Variable Guarded Fragment with Transitive Guards and Related Variants
• Fluted formulas and the limits of decidability
• The Fluted Fragment with Transitivity
• 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
• Computer Science Logic
• Two-Variable First-Order Logic with Equivalence Closure

This page was built for publication: The fluted fragment with transitive relations