We study the succinctness of monadic second-order logic and a variety of monadic fixed point logics on trees. All these languages are known to have the same expressive power on trees, but some can express the same queries much more succinctly than others. For example, we show that, under some complexity theoretic assumption, monadic second-order logic is non-elementarily more succinct than monadic least fixed point logic, which in turn is non-elementarily more succinct than monadic datalog. Succinctness...

We study the succinctness of monadic second-order logic and a variety of monadic fixed point logics on trees. All these languages are known to have the same expressive power on trees, but some can express the same queries much more succinctly than others. For example, we show that, under some complexity theoretic assumption, monadic second-order logic is non-elementarily more succinct than monadic least fixed point logic, which in turn is non-elementarily more succinct than monadic datalog.
Succinctness...

We give a new proof of the fact that finite bipartite graphs cannot be axiomatized by finitely many first-order sentences among finite graphs. (This fact is a consequence of a general theorem proved by L. Ham and M. Jackson, and the counterpart of this fact for all bipartite graphs in the class of all graphs is a well-known consequence of the compactness theorem.) Also, to exemplify that our method is applicable in various fields of mathematics, we prove that neither finite simple groups, nor the...

This paper is a survey of results on finite variable logics in finite model theory. It focusses on the common underlying techniques that unite many such results.

We discuss some known and introduce some new hierarchies and reducibilities on regular languages, with the emphasis on the quantifier-alternation and difference hierarchies of the quasi-aperiodic languages. The non-collapse of these hierarchies and decidability of some levels are established. Complete sets in the levels of the hierarchies under the polylogtime and some quantifier-free reducibilities are found. Some facts about the corresponding degree structures are established. As an application,...

We discuss some known and introduce some new hierarchies and reducibilities on regular languages, with the emphasis on the quantifier-alternation and difference hierarchies of the quasi-aperiodic languages. The non-collapse of these hierarchies and decidability of some levels are established. Complete sets in the levels of the hierarchies under the polylogtime and some quantifier-free reducibilities are found. Some facts about the corresponding degree structures are established. As an application, we...

Inf-Datalog extends the usual least fixpoint semantics of Datalog with greatest fixpoint semantics: we defined inf-Datalog and characterized the expressive power of various fragments of inf-Datalog in [16]. In the present paper, we study the complexity of query evaluation on finite models for (various fragments of) inf-Datalog. We deduce a unified and elementary proof that global model-checking (i.e. computing all nodes satisfying a formula in a given structure) has 1. quadratic data complexity...

Inf-Datalog extends the usual least fixpoint semantics of Datalog with greatest fixpoint semantics: we defined inf-Datalog and characterized the expressive power of various fragments of inf-Datalog in [CITE]. In the present paper, we study the complexity of query evaluation on finite models for (various fragments of) inf-Datalog. We deduce a unified and elementary proof that global model-checking (i.e. computing all nodes satisfying a formula in a given structure) has 1. quadratic data complexity...

We find the basis of all linear identities which are true in the variety of entropic graph algebras. We apply it to describe the lattice of all subvarieties of power entropic graph algebras.

Based on methods of structural convergence we provide a unifying view of local-global convergence, fitting to model theory and analysis. The general approach outlined here provides a possibility to extend the theory of local-global convergence to graphs with unbounded degrees. As an application, we extend previous results on continuous clustering of local convergent sequences and prove the existence of modeling quasi-limits for local-global convergent sequences of nowhere dense graphs.

By a ternary structure we mean an ordered pair $(U_0,T_0)$, where $U_0$ is a finite nonempty set and $T_0$ is a ternary relation on $U_0$. A ternary structure $(U_0,T_0)$ is called here a directed geodetic structure if there exists a strong digraph $D$ with the properties that $V\left(D\right)=U_0$ and $$T_0(u,v,w)\text{if}\text{and}\text{only}\text{if}{d}_D(u,v)+d_D(v,w)=d_D(u,w)$$ for all $u,v,w\in U_0$, where $d_D$ denotes the (directed) distance function in $D$. It is proved in this paper that there exists no sentence $𝐬$ of the language of the first-order logic such that a ternary structure is a directed geodetic structure if and only if it satisfies...

By a ternary structure we mean an ordered pair $(X_0,T_0)$, where $X_0$ is a finite nonempty set and $T_0$ is a ternary relation on $X_0$. By the underlying graph of a ternary structure $(X_0,T_0)$ we mean the (undirected) graph $G$ with the properties that $X_0$ is its vertex set and distinct vertices $u$ and $v$ of $G$ are adjacent if and only if $$\{x\in X_0{T}_0(u,x,v)\}\cup \{x\in X_0{T}_0(v,x,u)\}=\{u,v\}.$$ A ternary structure $(X_0,T_0)$ is said to be the B-structure of a connected graph $G$ if $X_0$ is the vertex set of $G$ and the following statement holds for all $u,x,y\in X_0$: $T_0(x,u,y)$ if and only if $u$ belongs to an induced $x-y$...

A characterization of locally finite congruence modular varieties with the number of at most k-generated models being bounded from above by a polynomial in k is given. These are exactly the varieties polynomially equivalent to the varieties of unitary modules over a finite ring of finite representation type.