The fluted fragment with transitive relations
From MaRDI portal
Publication:2238133
DOI10.1016/j.apal.2021.103042zbMath1490.03010arXiv2006.11169MaRDI 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
03B70: Logic in computer science
03B10: Classical first-order logic
03B25: Decidability of theories and sets of sentences
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q19: Descriptive complexity and finite models
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