FO^2 with one transitive relation is decidable.
Wieslaw SzwastLidia TenderaPublished in: STACS (2013)
Keyphrases
- transitive closure
- binary relations
- first order logic
- expressive power
- guarded fragment
- datalog queries
- query language
- query evaluation
- constraint databases
- directed acyclic graph
- unions of conjunctive queries
- preference relations
- fixpoint
- spatial databases
- query containment
- database
- integrity constraints
- special case