All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 52 Next

Displaying 1021 – 1040 of 5970

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

Comparison game on Borel ideals

Michael Hrušák, David Meza-Alcántara (2011)

Commentationes Mathematicae Universitatis Carolinae

We propose and study a “classification” of Borel ideals based on a natural infinite game involving a pair of ideals. The game induces a pre-order ⊑ and the corresponding equivalence relation. The pre-order is well founded and “almost linear”. We concentrate on F σ and F σ δ ideals. In particular, we show that all F σ -ideals are ⊑ -equivalent and form the least equivalence class. There is also a least class of non- F σ Borel ideals, and there are at least two distinct classes of F σ δ non- F σ ideals.

Compatibility and central elements in pseudo-effect algebras

Paolo Vitolo (2010)

Kybernetika

An equivalent definition of compatibility in pseudo-effect algebras is given, and its relationships with central elements are investigated. Furthermore, pseudo-MV-algebras are characterized among pseudo-effect algebras by means of compatibility.

Compatible Idempotent Terms in Universal Algebra

Ivan Chajda, Antonio Ledda, Francesco Paoli (2014)

Acta Universitatis Palackianae Olomucensis. Facultas Rerum Naturalium. Mathematica

In universal algebra, we oftentimes encounter varieties that are not especially well-behaved from any point of view, but are such that all their members have a “well-behaved core”, i.e. subalgebras or quotients with satisfactory properties. Of special interest is the case in which this “core” is a retract determined by an idempotent endomorphism that is uniformly term definable (through a unary term t ( x ) ) in every member of the given variety. Here, we try to give a unified account of this phenomenon....

Complete pairs of coanalytic sets

Jean Saint Raymond (2007)

Fundamenta Mathematicae

Let X be a Polish space, and let C₀ and C₁ be disjoint coanalytic subsets of X. The pair (C₀,C₁) is said to be complete if for every pair (D₀,D₁) of disjoint coanalytic subsets of ω ω there exists a continuous function f : ω ω → X such that f - 1 ( C ₀ ) = D ₀ and f - 1 ( C ₁ ) = D ₁ . We give several explicit examples of complete pairs of coanalytic sets.

Complete sequences of coanalytic sets

Riccardo Camerlo (2014)

Fundamenta Mathematicae

The notion of a complete sequence of pairwise disjoint coanalytic sets is investigated. Several examples are given and such sequences are characterised under analytic determinacy. The ideas are based on earlier results of Saint Raymond, and generalise them.

Currently displaying 1021 – 1040 of 5970