The fluted fragment with transitive relations

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

zbMATH Keywords

decidability; transitivity; satisfiability; fluted logic

Mathematics Subject Classification ID

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