Search

• < Previous
• 1
• Next >

---

On the Complexity of Equivalence and Minimisation for Q-weighted Automata

Stefan Kiefer ; Andrzej Murawski ; Joel Ouaknine ; Bjoern Wachter ; James Worrell.

This paper is concerned with the computational complexity of equivalence and minimisation for automata with transition weights in the field Q of rational numbers. We use polynomial identity testing and the Isolation Lemma to obtain complexity bounds, focussing on the class NC of problems within P&nbsp;[&hellip;]

---

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;]

---