Helmut Veith

In this paper, we present stronger results in the theory of succinct

problem representation by boolean circuits, and establish a close

relationship between succinct problems and leaf languages. As

a major tool, we use quantifierfree projection reductions

from descriptive complexity theory.

In particular, we show that the succinct upgrading ... more >>>

C. Lautemann, Pierre McKenzie, T. Schwentick, H. Vollmer

Building upon the known generalized-quantifier-based first-order

characterization of LOGCFL, we lay the groundwork for a deeper

investigation. Specifically, we examine subclasses of LOGCFL arising

from varying the arity and nesting of groupoidal quantifiers. Our

work extends the elaborate theory relating monoidal quantifiers to

NC^1 and its subclasses. In the ...
more >>>

Till Tantau

Deciding whether a vertex in a graph is reachable from another

vertex has been studied intensively in complexity theory and is

well understood. For common types of graphs like directed graphs,

undirected graphs, dags or trees it takes a (possibly

nondeterministic) logspace machine to decide the reachability

problem, and ...
more >>>

Argimiro Arratia, Carlos E. Ortiz

We formulate a formal syntax of approximate formulas for the logic with counting

quantifiers, $\mathcal{SOLP}$, studied by us in \cite{aaco06}, where we showed the

following facts:

$(i)$ In the presence of a built--in (linear) order, $\mathcal{SOLP}$ can

describe {\bf NP}--complete problems and fragments of it capture classes like

{\bf P} ...
more >>>

Prabhu Manyem

In Descriptive Complexity, there is a vast amount of literature on

decision problems, and their classes such as \textbf{P, NP, L and NL}. ~

However, research on the descriptive complexity of optimisation problems

has been limited. In a previous paper [Man], we characterised

the optimisation versions of \textbf{P} via expressions ...
more >>>

Walid Gomaa

Model theory is a branch of mathematical logic that investigates the

logical properties of mathematical structures. It has been quite

successfully applied to computational complexity resulting in an

area of research called descriptive complexity theory. Descriptive

complexity is essentially a syntactical characterization of

complexity classes using logical formalisms. However, there ...
more >>>

Kord Eickmeyer, Martin Grohe

We study probabilistic complexity classes and questions of derandomisation from a logical point of view. For each logic $\mathcal{L}$ we introduce a new logic $\mathsf{BP}\mathcal{L}$, bounded error probabilistic $\mathcal{L}$, which is defined from $\mathcal{L}$ in a similar way as the

complexity class $\mathsf{BPP}$, bounded error probabilistic polynomial time, is defined ...
more >>>

Christoph Behle, Andreas Krebs, Stephanie Reifferscheid

Based on different concepts to obtain a finer notion of language recognition via finite monoids we develop an algebraic structure called typed monoid.

This leads to an algebraic description of regular and non regular languages.

We obtain for each language a unique minimal recognizing typed monoid, the typed syntactic monoid.

more >>>

Christoph Behle, Andreas Krebs

We consider first order logic over words and show FO+MOD[<] is contained in MAJ[<] with three variables.

It is known that for the classes FO[<], FO+MOD[<], FO+GROUP[<] three variables suffice. In the case of MOD[<] even two variables are sufficient.

As a consequence we know that if TC^ 0 neq ... more >>>

Yijia Chen, Joerg Flum

Ehrenfeucht-Fraisse games and their generalizations have been quite successful in finite model theory and yield various inexpressibility results. However, for key problems such as P $\ne$ NP or NP $\ne$ coNP no progress has been achieved using the games. We show that for these problems it is already hard to ... more >>>

Christoph Berkholz, Jakob NordstrÃ¶m

We prove near-optimal trade-offs for quantifier depth versus number of variables in first-order logic by exhibiting pairs of n-element structures that can be distinguished by a k-variable first-order sentence but where every such sentence requires quantifier depth at least n^?(k/log k). Our trade-offs also apply to first-order counting logic, and ... more >>>