One of the more significant achievements of twentieth century mathematics, especially from
the viewpoints of logic and computer science, was the work of Church, Gödel and Turing in …

Despite several decades of research, the problem of formal verification of infinite-state
systems has resisted effective automation. We describe a system---Ivy---for interactively …

For many fixed-parameter problems that are trivially soluable in polynomial time, such as (k-)
DOMINATING SET, essentially no better algorithm is presently known than the one which …

We identify the computational complexity of the satisfiability problem for FO2, the fragment of
first-order logic consisting of all relational first-order sentences with at most two distinct …

This account of propositional logic concentrates on the algorithmic translation of important
methods, especially of decision procedures for (subclasses of) propositional logic. Important …

Distributed protocols such as Paxos play an important role in many computer systems.
Therefore, a bug in a distributed protocol may have tremendous effects. Accordingly, a lot of …

Tiling problems provide for a very simple and transparent mechanism for encoding machine
computations. This gives rise to rather simple master reductions showing various versions of …

The size of an accepting computation tree of an alternating Turing machine (ATM) is
introduced as a complexity measure. Tree-size on ATM's is shown to closely correspond to …

Dependencies are certain sentences of first-order logic that are of special interest for
database theory and practice. There has been quite a bit of research in the last decade in …

Today's distributed systems are increasingly complex, leading to subtle bugs that are difficult
to detect with standard testing methods. Formal verification can provably rule out such bugs …