Search

• < Previous
• 1
• Next >

---

L-Recursion and a new Logic for Logarithmic Space

Martin Grohe ; Berit Grußien ; André Hernich ; Bastian Laubner.

We extend first-order logic with counting by a new operator that allows it to formalise a limited form of recursion which can be evaluated in logarithmic space. The resulting logic LREC has a data complexity in LOGSPACE, and it defines LOGSPACE-complete problems like deterministic reachability and&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;]

---