Now showing items 1-10 of 15
A colouring protocol for the generalized Russian cards problem [Article]
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 ...
Local induction and provably total computable functions [Article]
Let I¦− 2 denote the fragment of Peano Arithmetic obtained by restricting the induction scheme to parameter free ¦2 formulas. Answering a question of R. Kaye, L. Beklemishev showed that the provably total computable ...
Existentially Closed Models and Conservation Results in Bounded Arithmetic [Article]
(Oxford Academic, 2009)
We develop model-theoretic techniques to obtain conservation results for first order Bounded Arithmetic theories, based on a hierarchical version of the well-known notion of an existentially closed model. We focus on the ...
Envelopes, indicators and conservativeness [Article]
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 ...
On the quantifier complexity of Δ n+1 (T)– induction [Article]
In this paper we continue the study of the theories IΔ n+1 (T), initiated in . We focus on the quantifier complexity of these fragments and theirs (non)finite axiomatization. A characterization is obtained for the class ...
A geometric protocol for cryptography with cards [Article]
In the generalized Russian cards problem, the three players Alice, Bob and Cath draw a, b and c cards, respectively, from a deck of a + b + c cards. Players only know their own cards and what the deck of cards is. Alice ...
A Note on Complexity Measures for Probabilistic P Systems [Article]
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. ...
Dynamic consequence and public announcement [Article]
(Cambridge University Press, 2013)
A Prolog Simulator for Deterministic P Systems with Active Membranes [Article]
In this paper we propose a new way to represent P systems with active membranes based on Logic Programming techniques. This representation allows us to express the set of rules and the configuration of the P system in ...
A secure additive protocol for card players [Article]
(University of Queensland, 2012)
Consider three players Alice, Bob and Cath who hold a, b and c cards, respectively, from a deck of d=a+b+c cards. The cards are all different and players only know their own cards. Suppose Alice and Bob wish to communicate ...