Search

• < Previous
• 1
• Next >

---

The Complexity of Datalog on Linear Orders

Martin Grohe ; Goetz Schwandtner.

We study the program complexity of datalog on both finite and infinite linear orders. Our main result states that on all linear orders with at least two elements, the nonemptiness problem for datalog is EXPTIME-complete. While containment of the nonemptiness problem in EXPTIME is known for finite&nbsp;[&hellip;]

---

Randomisation and Derandomisation in Descriptive Complexity Theory

Kord Eickmeyer ; Martin Grohe.

We study probabilistic complexity classes and questions of derandomisation from a logical point of view. For each logic L we introduce a new logic BPL, bounded error probabilistic L, which is defined from L in a similar way as the complexity class BPP, bounded error probabilistic polynomial time, is&nbsp;[&hellip;]

---

Definable decompositions for graphs of bounded linear cliquewidth

Mikołaj Bojańczyk ; Martin Grohe ; Michał Pilipczuk.

We prove that for every positive integer k, there exists an MSO_1-transduction that given a graph of linear cliquewidth at most k outputs, nondeterministically, some cliquewidth decomposition of the graph of width bounded by a function of k. A direct corollary of this result is the equivalence of&nbsp;[&hellip;]

---