Search

• < Previous
• 1
• Next >

---

Block structure vs scope extrusion: between innocence and omniscience

Andrzej S. Murawski ; Nikos Tzevelekos.

We study the semantic meaning of block structure using game semantics. To that end, we introduce the notion of block-innocent strategies and characterise call-by-value computation with block-allocated storage through soundness, finite definability and universality results. This puts us in a good&nbsp;[&hellip;]

---

The Big-O Problem

Dmitry Chistikov ; Stefan Kiefer ; Andrzej S. Murawski ; David Purser.

Given two weighted automata, we consider the problem of whether one is big-O of the other, i.e., if the weight of every finite word in the first is not greater than some constant multiple of the weight in the second. We show that the problem is undecidable, even for the instantiation of weighted&nbsp;[&hellip;]

---