[ The Types Forum (announcements only),
http://lists.seas.upenn.edu/mailman/listinfo/types-announce ]Dear colleagues,The recently started web Seminar on Semantic and Formal Approaches to Complexity (SCOT) can be of interest to some members of the Types community. The next talk will be given by Georg Moser:
* Tuesday May 18th 2021, 3pm-4pm (CEST). *Georg Moser *(University of Innsbruck). *Title*: Automated Analysis of Splaying et al.
( the virtual room will open at 2:40 for coffee/chat)Abstract: Being able to argue about the performance of self-adjusting data structures such as splay trees has been a main objective, when Sleator and Tarjan introduced the notion of *amortised* complexity. Analysing these data structures requires sophisticated potential functions, which typically contain logarithmic expressions. Possibly for these reasons, and despite the recent progress in automated resource analysis, they have so far eluded automation. In this talk, I will report on the first fully-automated amortised complexity analysis of self-adjusting data structures and the underlying theory. Following earlier work, the analysis is based on potential function templates with unknown coefficients.
This is joint work with Lorenz Leutgeb, David Obwaller and Florian Zuleger.* *Connexion informations:* To get the connexion link please subscribe to the mailing list; for that send an email with subject "subscribe scot_webinar" and empty body to [email protected]
**About the seminar:*The SCOT Seminar is devoted to the problem of reasoning on the complexity of programs in formal and compositional ways. Many approaches have been exploited for that, taking advantage from logic, category theory, denotational semantics, type systems, interpretations, etc. This seminar aims at providing a forum of discussion for all issues related to these questions, from foundational aspects on semantics of complexity to automated time or space complexity analysis. The seminar is held virtually and on a monthly basis.
Best regards For the seminar: Isabel Oitavem, Patrick Baillot, Ugo Dal Lago ------------------------ Seminar web page: http://www.cs.unibo.it/~dallago/SCOSEM/ The list's homepage: https://groupes.renater.fr/sympa/info/scot_webinarGeneral information about mailing lists: https://groupes.renater.fr/sympa/help/introduction To unsubscribe from this list: send an email with subject "unsubscribe scot_webinar" and empty body to [email protected] If you wish to subscribe: same procedure with subject "subscribe scot_webinar"
