Page 1 Next

Displaying 1 – 20 of 27

Showing per page

Comparing the succinctness of monadic query languages over finite trees

Martin Grohe, Nicole Schweikardt (2004)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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

Comparing the succinctness of monadic query languages over finite trees

Martin Grohe, Nicole Schweikardt (2010)

RAIRO - Theoretical Informatics and Applications

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

Finite models and finitely many variables

Anuj Dawar (1999)

Banach Center Publications

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.

Hierarchies and reducibilities on regular languages related to modulo counting

Victor L. Selivanov (2009)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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

Hierarchies and reducibilities on regular languages related to modulo counting

Victor L. Selivanov (2008)

RAIRO - Theoretical Informatics and Applications

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, Modal Logic and Complexities

Eugénie Foustoucos, Irène Guessarian (2007)

RAIRO - Theoretical Informatics and Applications

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

Inf-datalog, modal logic and complexities

Eugénie Foustoucos, Irène Guessarian (2009)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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

Linear identities in graph algebras

Agata Pilitowska (2009)

Commentationes Mathematicae Universitatis Carolinae

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.

Local-global convergence, an analytic and structural approach

Jaroslav Nešetřil, Patrice Ossona de Mendez (2019)

Commentationes Mathematicae Universitatis Carolinae

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.

The directed geodetic structure of a strong digraph

Ladislav Nebeský (2004)

Czechoslovak Mathematical Journal

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 ( D ) = U 0 and T 0 ( u , v , w ) if and only if d D ( u , v ) + d D ( v , w ) = d D ( u , w ) for all u , v , w 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...

The induced paths in a connected graph and a ternary relation determined by them

Ladislav Nebeský (2002)

Mathematica Bohemica

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 X 0 T 0 ( u , x , v ) } { x 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 X 0 : T 0 ( x , u , y ) if and only if u belongs to an induced x - y ...

Varieties with polynomially many models, I

Paweł M. Idziak, Ralph McKenzie (2001)

Fundamenta Mathematicae

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.

Currently displaying 1 – 20 of 27

Page 1 Next