Search

• < Previous
• 1
• Next >

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

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