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

---

Trace Refinement in Labelled Markov Decision Processes

Nathanaël Fijalkow ; Stefan Kiefer ; Mahsa Shirmohammadi.

Given two labelled Markov decision processes (MDPs), the trace-refinement problem asks whether for all strategies of the first MDP there exists a strategy of the second MDP such that the induced labelled Markov chains are trace-equivalent. We show that this problem is decidable in polynomial time if&nbsp;[&hellip;]

---

Minimisation of Multiplicity Tree Automata

Stefan Kiefer ; Ines Marusic ; James Worrell.

We consider the problem of minimising the number of states in a multiplicity tree automaton over the field of rational numbers. We give a minimisation algorithm that runs in polynomial time assuming unit-cost arithmetic. We also show that a polynomial bound in the standard Turing model would require&nbsp;[&hellip;]

---

Game Characterization of Probabilistic Bisimilarity, and Applications to Pushdown Automata

Vojtěch Forejt ; Petr Jančar ; Stefan Kiefer ; James Worrell.

We study the bisimilarity problem for probabilistic pushdown automata (pPDA) and subclasses thereof. Our definition of pPDA allows both probabilistic and non-deterministic branching, generalising the classical notion of pushdown automata (without epsilon-transitions). We first show a general&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;]

---