Creating and sharing knowledge for telecommunications

A HIstory of Until

on 10-02-2010

... Luca Viganò (U Verona, Italy).

February 10, 2010, Wednesday, 15h30m.

Abstract: Until is a notoriously difficult temporal operator as it is both existential and universal at the same time: A∪B holds at the current time instant w iff either B holds at w or there exists a time instant w’ in the future at which B holds and such that A holds in all the time instants between the current one and w’. This "ambivalent"t; nature poses a significant challenge when attempting to give deduction rules for until. In this paper, in contrast, we make explicit this duality of until by introducing a new temporal operator that allows us to formalize the “history” of until, i.e., the “internal” universal quantification over the time instants between the current one and w′. This approach provides the basis for formalizing deduction systems for temporal logics endowed with the until operator. For concreteness, we give here a labeled natural deduction system for a linear-time logic endowed with the new history operator and show that, via a proper translation, such a system is also sound and complete with respect to the linear temporal logic LTL with until. Reporting on joint work with Andrea Masini and Marco Volpe.

More Information..

Seminar Zero-Error Capacity of a Quantum Channel

on 05-02-2010

... Francisco Marcos de Assis (U Federal de Campina Grande).

February 5, 2010, Friday, 15h.
Location: Room P4.35, Post-Graduation Building, IST.


Quantum channels have a number of capacities that depends fundamentally on the kind of information to be carried, the employed resources and the communication protocol. In this work, we generalize the definition of zero-error capacity of a classical channel to the zero-error capacity of a quantum channel. We propose a new kind of capacity for transmitting classical information through a quantum channel.
The quantum zero-error capacity is defined by the maximum amount of classical information per channel use that can be sent over a noisy quantum channel, with the restriction that the probability of error must be equal to zero. The communication protocol used in the definition assumes codewords are built as tensor products of input quantum states, whereas entangled measurements can be performed between several channel outputs. Hence, our communication protocol is similar to the Holevo-Schumacher-Westmoreland protocol. Additionally we introduce some connection between concepts related to quantum channel capacity with concepts found in graph theory.

More Information..