77 citations · 281 across the 23 of their papers we have counts for
4 papers · 1 filter
A note on the expressive power of linear orders
Thomas Schwentick, Nicole Schweikardt
This article shows that there exist two particular linear orders such that first-order logic with these two linear orders has the same expressive power as first-order logic with th…
Feasible Automata for Two-Variable Logic with Successor on Data Words
Ahmet Kara, Thomas Schwentick, Tony Tan
We introduce an automata model for data words, that is words that carry at each position a symbol from a finite alphabet and a value from an unbounded data domain. The model is (se…
Two-Variable Logic with Two Order Relations
Thomas Schwentick, Thomas Zeume
It is shown that the finite satisfiability problem for two-variable logic over structures with one total preorder relation, its induced successor relation, one linear order relatio…
Rewriting Ontological Queries into Small Nonrecursive Datalog Programs
Georg Gottlob, Thomas Schwentick
We consider the setting of ontological database access, where an Abox is given in form of a relational database D and where a Boolean conjunctive query q has to be evaluated agains…