Laboratoire d'informatique de l'École polytechnique

Comète Seminar - Talk by Radu Madare and Camilo Rocha

Speaker: Radu Mardare
Location: Salle Grace Hopper (LIX - Alan Turing building, École Polytechnique)
Date: Thu, 26 Oct 2017, 14:00-16:15

The next Comète seminar will take place next Thursday 26th of October at 14h in Salle Grace Hopper (LIX - Alan Turing building, École Polytechnique). Radu Mardare, Associate Professor at the Department of Computer Science, Aalborg University, Denmark, will talk about Quantitative Algebraic Reasoning.

Abstract: The talk is centered on the concept of Quantitative Algebra, a structure that we developed in order to provide canonical metric-based semantics for quantitative (probabilistic, stochastic, timed, weighted, priced, hybrid) systems. Quantitative algebras are universal algebras on metric spaces and are devised with an equational theory developed on top of indexed equations. An indexed equation is an equation of type s=_e t, where the index e is a positive number describing an upper bound of the distance between the terms s and t. This simple idea provides an entirely new way of thinking to algebras and Lawvere theories, and eventually induces a monad on the category of metric spaces. It also opens the discussion on the possibility of having a quantitative theory of effects for quantitative programming languages. This is a joint work with Gordon Plotkin and Prakash Panangaden that was presented to LICS 2016 and LICS 2017.

A second talk has been scheduled. Camilo Rocha, Associate Professor in the Department of Electronics and Computer Science at the Pontificia Universidad Javeriana, in Cali (Colombia), will talk about Guarded Terms for Rewriting Modulo SMT.

Abstract: Rewriting modulo SMT is a novel symbolic technique to model and analyze infinite-state systems that interact with a nondeterministic environment. It seamlessly combines rewriting modulo equational theories, SMT solving, and model checking. One of the main challenges of this technique is to cope with the symbolic state-space explosion problem. In this talk, guarded terms are presented as an approach to deal with this problem for rewriting modulo SMT. Guarded terms can encode many symbolic states into one by using SMT constraints as part of the term structure. This approach enables the reduction of the symbolic state space by limiting branching due to concurrent computation, and the complexity and size of constraints by distributing them in the term structure.