[Club2] Invitation: Proof of the Amortized Time Complexity of an Efficient Un... @ Wed Oct 16, 2019 14:45 - 15:15 (CEST) (club2 at mailbroy.informatik.tu-muenchen.de)

[julianbrunner at gmail.com]

You have been invited to the following event.

Title: Proof of the Amortized Time Complexity of an Efficient Union-Find  
Data Structure in Isabelle/HOL

Speaker: Adrián Löwenberg
Type: Bachelor's Thesis Presentation

Abstract:

Union-Find is a classical data structure whose complexity analysis is  
famously non-trivial. In this thesis we prove the alpha-bound amortized  
time complexity of an efficient imperative implementation of this data  
structure. We first revise the history of this emblematic result by Tarjan  
and arrive at the modern proof by Alstrup et al..

To reproduce this proof in a formal context within Isabelle/HOL, we first  
gather the mathematical and technical tools required, most prominently a  
more comprehensive theory about the Ackermann function than the one already  
available in the Isabelle/HOL distribution, properties about its inverses,  
as well as the framework implementing Separation Logic with Time Credits  
for Imperative/HOL, which already contained a non optimal implementation of  
this data structure. We then follow closely the work of Charguéraud and  
Pottier, which formalized this proof in a similar framework in Coq.

In the end, we prove the asymptotically optimal bound of the operations in  
an efficient implementation of the Union-Find data structure. The whole  
proof in Isabelle is available online. As with any other program in  
Imperative/HOL, the implementation can be exported to several languages.
When: Wed Oct 16, 2019 14:45 – 15:15 Central European Time - Berlin
Where: MI 00.09.038 (Turing)
Calendar: club2 at mailbroy.informatik.tu-muenchen.de
Who:
     * julianbrunner at gmail.com - creator
     * club2 at mailbroy.informatik.tu-muenchen.de

Event details:  
https://www.google.com/calendar/event?action=VIEW&eid=NTY4azB1dG5oazM5bWt2YmZxdHViM2RiZDIgY2x1YjJAbWFpbGJyb3kuaW5mb3JtYXRpay50dS1tdWVuY2hlbi5kZQ&tok=NTIjc2U2ZWJlM3RvZmY0Y2g1bm11bmlibTVtOThAZ3JvdXAuY2FsZW5kYXIuZ29vZ2xlLmNvbTY0YWRhNTVkMTQ2NTQ4ZDZiNGJhODljOTE1NDFhNTdkYzE3ZDk5ZDQ&ctz=Europe%2FBerlin&hl=en&es=0

Invitation from Google Calendar: https://www.google.com/calendar/

You are receiving this courtesy email at the account  
club2 at mailbroy.informatik.tu-muenchen.de because you are an attendee of  
this event.

To stop receiving future updates for this event, decline this event.  
Alternatively you can sign up for a Google account at  
https://www.google.com/calendar/ and control your notification settings for  
your entire calendar.

Forwarding this invitation could allow any recipient to send a response to  
the organizer and be added to the guest list, or invite others regardless  
of their own invitation status, or to modify your RSVP. Learn more at  
https://support.google.com/calendar/answer/37135#forwarding
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman46.in.tum.de/pipermail/club2/attachments/20191014/e04dc781/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: text/calendar
Size: 2750 bytes
Desc: not available
URL: <https://mailman46.in.tum.de/pipermail/club2/attachments/20191014/e04dc781/attachment-0001.ics>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: invite.ics
Type: application/ics
Size: 2802 bytes
Desc: not available
URL: <https://mailman46.in.tum.de/pipermail/club2/attachments/20191014/e04dc781/attachment-0001.bin>