EuDML | Browse

Items

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

Displaying 241 – 260 of 515

On sequent calculi for intuitionistic propositional logic

Vítězslav Švejdar (2006)

Commentationes Mathematicae Universitatis Carolinae

The well-known Dyckoff's 1992 calculus/procedure for intuitionistic propositional logic is considered and analyzed. It is shown that the calculus is Kripke complete and the procedure in fact works in polynomial space. Then a multi-conclusion intuitionistic calculus is introduced, obtained by adding one new rule to known calculi. A simple proof of Kripke completeness and polynomial-space decidability of this calculus is given. An upper bound on the depth of a Kripke counter-model is obtained.

On the axiomatisation of Boolean categories with and without medial.

Strassburger, Lutz (2007)

Theory and Applications of Categories [electronic only]

On the complexity of computable real sequences

Jacobo Torán (1987)

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

On the Goldbach conjecture and the consistency of general recursive arithemetic.

H.A. Pogorzelski (1974)

Journal für die reine und angewandte Mathematik

On the hierarchies of Δ20-real numbers

Xizhong Zheng (2007)

RAIRO - Theoretical Informatics and Applications

A real number x is called Δ20 if its binary expansion corresponds to a Δ20-set of natural numbers. Such reals are just the limits of computable sequences of rational numbers and hence also called computably approximable. Depending on how fast the sequences converge, Δ20-reals have different levels of effectiveness. This leads to various hierarchies of Δ20 reals. In this survey paper we summarize several recent developments related to such kind of hierarchies shown by the author and his collaborators. ...

On the Quantifier of Limiting Realizability

N. A. Shanin (1977)

Zbornik Radova

On the structure of intuitionistic algebras with relational probabilities.

Francesc Esteva (1988)

Stochastica

Trillas ([1]) has defined a relational probability on an intuitionistic algebra and has given its basic properties. The main results of this paper are two. The first one says that a relational probability on a intuitionistic algebra defines a congruence such that the quotient is a Boolean algebra. The second one shows that relational probabilities are, in most cases, extensions of conditional probabilities on Boolean algebras.

On the weak pigeonhole principle

Jan Krajíček (2001)

Fundamenta Mathematicae

We investigate the proof complexity, in (extensions of) resolution and in bounded arithmetic, of the weak pigeonhole principle and of the Ramsey theorem. In particular, we link the proof complexities of these two principles. Further we give lower bounds to the width of resolution proofs and to the size of (extensions of) tree-like resolution proofs of the Ramsey theorem. We establish a connection between provability of WPHP in fragments of bounded arithmetic and cryptographic assumptions (the existence...