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 technique ... more >>>

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 absence ... more >>>

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 the ... more >>>

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 >>>

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 >>>

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 >>>