Creating and sharing knowledge for telecommunications

Talk - Verification of Markov chains and its relation to the Skolem Problem

on 31-10-2014

... The talk of Manuel Biscaia had to be postponed to this Friday, October 31. To Manuel and to the participants my apologies for the inconvenience.
Verification of Markov chains and its relation to the Skolem Problem

Manuel Biscaia, SQIG - Instituto de Telecomunicações

October 31, 2014, Friday, 16h15m.

Abstract: When studying probabilistic dynamical systems, temporal logic has typically been used to reason about path properties. Recently, there has been some interest in reasoning about the dynamical evolution of state probabilities of these systems. In this paper we show that verifying linear temporal properties concerning the state evolution induced by a Markov chain is equivalent to the decidability of the Skolem problem -- a long standing open problem in Number Theory. However, from a practical point of view, usually it is enough to check properties up to some acceptable error bound. We show that an approximate version of Skolem problem is decidable, and that it can be applied to verify, up to an arbitrarily small error, linear temporal properties of the state evolution induced by a Markov chain.
L states that whenever {γ1,…,γk}⊢Lα there is a proof in which each formula occurrence is either a sub-formula of α or of some of γi. In this work we extend Statman's result and show that any propositional (possibly modal) structural logic satisfying a particular statement of the sub-formula principle is PSPACE-complete. As a consequence, EXPTIME-complete propositional logics, such as PDL and the common-knowledge epistemic logic with at least 2 agents satisfy this particular sub-formula principle, if and only if, PSPACE=EXPTIME.

Room: 3.10, Mathematics

Support: SQIG/Instituto de Telecomunicações with support from FCT and FEDER namely by the FCT project PEst-OE/EEI/LA0008/2013. More Information..


on 29-10-2014

... Dia 29 de Outubro de 2014 (quarta-feira), às 14h30m, na Sala B3-01

Post-Selected Measurements and The Arrow of Time in Classical and Quantum Physics

Janne Karimäki

Abstract: In 1932 Erwin Schrödinger pointed out a curious analogy between classical diffusion and the probabilistic formalism of quantum physics.
This analogy is further deepened, when post-selection of measurement data is considered. While classical diffusion (Wiener Process) is an irreversible physical process, with a clearly defined arrow of time, post-selection allows one to reveal a time-symmetric level (Bernstein Process) hidden in it.
Now, application of post-selection is becoming more and more important in both theoretical and experimental research in quantum physics. This is particularly important when studying entangled quantum systems, or performing experiments using the so-called weak measurement technique.
While the implications of the classical–quantum analogy discovered by Schrödinger, and further elaborated e.g. by Zambrini et al., are still somewhat unclear, there is hope that studying this property will shed light on many questions in Foundations of Physics, especially the role of time in physics, and many of the so-called ‘mysteries’ of quantum physics.
Further, a deepened understanding of this connection may also shed more light on the possibilities of practical applications in fields such as Quantum Computing & Quantum Cryptography.

Seminário financiado por Fundos Nacionais através da FCT – Fundação para a Ciência e a Tecnologia no âmbito do projeto PEst-OE/MAT/UI0208/2013

Instituto para a Investigação Interdisciplinar da Universidade de Lisboa
Av. Prof. Gama Pinto, 2
1649-003 Lisboa
Portugal More Information..