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

Displaying 21 – 40 of 84

Showing per page

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

Hierarchies of function classes defined by the first-value operator

Armin Hemmerling (2008)

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

The first-value operator assigns to any sequence of partial functions of the same type a new such function. Its domain is the union of the domains of the sequence functions, and its value at any point is just the value of the first function in the sequence which is defined at that point. In this paper, the first-value operator is applied to establish hierarchies of classes of functions under various settings. For effective sequences of computable discrete functions, we obtain a hierarchy connected...

Hierarchies of function classes defined by the first-value operator

Armin Hemmerling (2007)

RAIRO - Theoretical Informatics and Applications

The first-value operator assigns to any sequence of partial functions of the same type a new such function. Its domain is the union of the domains of the sequence functions, and its value at any point is just the value of the first function in the sequence which is defined at that point. In this paper, the first-value operator is applied to establish hierarchies of classes of functions under various settings. For effective sequences of computable discrete functions, we obtain a hierarchy connected...

Highly Undecidable Problems For Infinite Computations

Olivier Finkel (2009)

RAIRO - Theoretical Informatics and Applications

We show that many classical decision problems about 1-counter ω-languages, context free ω-languages, or infinitary rational relations, are Π½ -complete, hence located at the second level of the analytical hierarchy, and “highly undecidable”. In particular, the universality problem, the inclusion problem, the equivalence problem, the determinizability problem, the complementability problem, and the unambiguity problem are all Π½ -complete for context-free ω-languages or for infinitary rational...

Hilbert algebras as implicative partial semilattices

Jānis Cīrulis (2007)

Open Mathematics

The infimum of elements a and b of a Hilbert algebra are said to be the compatible meet of a and b, if the elements a and b are compatible in a certain strict sense. The subject of the paper will be Hilbert algebras equipped with the compatible meet operation, which normally is partial. A partial lower semilattice is shown to be a reduct of such an expanded Hilbert algebra i ?both algebras have the same ?lters.An expanded Hilbert algebra is actually an implicative partial semilattice (i.e., a relative...

Historic forcing for Depth

Andrzej Rosłanowski, Saharon Shelah (2001)

Colloquium Mathematicae

We show that, consistently, for some regular cardinals θ <λ, there exists a Boolean algebra 𝔹 such that |𝔹| = λ⁺ and for every subalgebra 𝔹'⊆ 𝔹 of size λ⁺ we have Depth(𝔹') = θ.

HOD-supercompactness, Indestructibility, and Level by Level Equivalence

Arthur W. Apter, Shoshana Friedman (2014)

Bulletin of the Polish Academy of Sciences. Mathematics

In an attempt to extend the property of being supercompact but not HOD-supercompact to a proper class of indestructibly supercompact cardinals, a theorem is discovered about a proper class of indestructibly supercompact cardinals which reveals a surprising incompatibility. However, it is still possible to force to get a model in which the property of being supercompact but not HOD-supercompact holds for the least supercompact cardinal κ₀, κ₀ is indestructibly supercompact, the strongly compact and...

Holland’s theorem for pseudo-effect algebras

Anatolij Dvurečenskij (2006)

Czechoslovak Mathematical Journal

We give two variations of the Holland representation theorem for ℓ -groups and of its generalization of Glass for directed interpolation po-groups as groups of automorphisms of a linearly ordered set or of an antilattice, respectively. We show that every pseudo-effect algebra with some kind of the Riesz decomposition property as well as any pseudo M V -algebra can be represented as a pseudo-effect algebra or as a pseudo M V -algebra of automorphisms of some antilattice or of some linearly ordered set.

Holonomie et cycle évanouissant

Guy Wallet (1981)

Annales de l'institut Fourier

On démontre que l’holonomie est non triviale au voisinage d’un cycle évanouissant au moyen d’un critère d’Imanishi et on donne une démonstration non standard de ce dernier.

Currently displaying 21 – 40 of 84