Search

• < Previous
• 1
• Next >

---

Model-Checking Problems as a Basis for Parameterized Intractability

Joerg Flum ; Martin Grohe.

Most parameterized complexity classes are defined in terms of a parameterized version of the Boolean satisfiability problem (the so-called weighted satisfiability problem). For example, Downey and Fellow's W-hierarchy is of this form. But there are also classes, for example, the A-hierarchy, that&nbsp;[&hellip;]

---

The succinctness of first-order logic on linear orders

Martin Grohe ; Nicole Schweikardt.

Succinctness is a natural measure for comparing the strength of different logics. Intuitively, a logic L_1 is more succinct than another logic L_2 if all properties that can be expressed in L_2 can be expressed in L_1 by formulas of (approximately) the same size, but some properties can be expressed&nbsp;[&hellip;]

---