8 papers
A Cost-Aware Probability Monad for Liquid Haskell
Matthias Hetzenberger, Georg Moser, Florian Zuleger
Probabilistic algorithms and data structures are widely used to obtain favourable expected performance guarantees. While their mathematical analysis is often well understood, mecha…
Regular Grammars as Effective Representations of Recognizable Sets of Series-Parallel Graphs
Marius Bozga, Radu Iosif, Florian Zuleger
Series-parallel (SP) graphs are binary edge-labeled graphs with a designated source and target vertex, built using serial and parallel composition. A set of graphs is recognizable…
Automated Amortised Analysis of Skew Heaps and Leftist Heaps (Extended Version)
Armin Walch, Georg Moser, Berry Schoenmakers +1
We study the fully automated amortised analysis of purely functional data structures like skew heaps, as well as weight- and rank-biased leftist heaps. For that we generalise earli…
Characterizations of Monadic Second Order Definable Context-Free Sets of Graphs
Radu Iosif, Florian Zuleger
We give a characterization of the sets of graphs that are both definable in Counting Monadic Second Order Logic (CMSO) and context-free, i.e., least solutions of Hyperedge-Replacem…
To Zip Through the Cost Analysis of Probabilistic Programs
Matthias Hetzenberger, Georg Moser, Florian Zuleger
Probabilistic programming and the formal analysis of probabilistic algorithms are active areas of research, driven by the widespread use of randomness to improve performance. While…
Parameterized Model-checking of Discrete-Timed Networks and Symmetric-Broadcast Systems
Benjamin Aminof, Sasha Rubin, Francesco Spegni +1
We study the complexity of the model-checking problem for parameterized discrete-timed systems with arbitrarily many anonymous and identical processes, with and without a distingui…