Buscar
Mostrando ítems 11-17 de 17
Artículo
A Note on Σ₁-Maximal Models
(Association for Symbolic Logic, 2007)
Let T be a recursive theory in the language of first order Arithmetic. We prove that if T extends: (a) the scheme of parameter free Δ₁-minimization (plus exp), or (b) the scheme of parameter free Π₁-induction, then there ...
Artículo
Envelopes, indicators and conservativeness
(Wiley, 2006)
A well known theorem proved (independently) by J. Paris and H. Friedman states that BΣn +1 (the fragment of Arithmetic given by the collection scheme restricted to Σn +1‐formulas) is a Πn +2‐conservative extension of IΣn ...
Artículo
Predicativity through Transfinite Reflection
(The Association for Symbolic Logic, 2017)
Let T be a second-order arithmetical theory, Λ a well-order, λ < Λ and X ⊆ ℕ. We use as a formalization of “φ is provable from T and an oracle for the set X, using ω-rules of nesting depth at most λ”. For a set of ...
Artículo
A Note on Complexity Measures for Probabilistic P Systems
(J.UCS.org, 2004)
In this paper we present a first approach to the definition of different entropy measures for probabilistic P systems in order to obtain some quantitative parameters showing how complex the evolution of a P system is. ...
Artículo
A colouring protocol for the generalized Russian cards problem
(Elsevier, 2013)
In the generalized Russian cards problem, Alice, Bob and Cath draw a, b and c cards, respectively, from a deck of size a + b + c. Alice and Bob must then communicate their entire hand to each other, without Cath learning ...
Artículo
Existentially Closed Models in the Framework of Arithmetic
(The Association for Symbolic Logic, 2016)
We prove that the standard cut is definable in each existentially closed model of IΔ0 + exp by a (parameter free) П1–formula. This definition is optimal with respect to quantifier complexity and allows us to improve some ...
Artículo
A note on parameter free Π1-induction and restricted exponentiation
(Wiley, 2011)
We characterize the sets of all Π2 and all $\mathcal {B}(\Sigma _{1})$equation image (= Boolean combinations of Σ1) theorems of IΠ−1 in terms of restricted exponentiation, and use these characterizations to prove that both ...