ON THE COMPLEXITY OF EQUIVALENCE AND MINIMISATION FOR Q-WEIGHTED AUTOMATA

Journal article

This paper is concerned with the computational complexity of equivalence and minimisation for automata with transition weights in the ring ℚ 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 solvable in polylogarithmic parallel time. For finite ℚ-weighted automata, we give a randomised NC procedure that either outputs that two automata are equivalent or returns a word on which they differ...

Expand abstract

Authors: Kiefer, S; Murawski, A; Ouaknine, J; Wachter, B; Worrell, J

• Publication status: Published
• Journal: LOGICAL METHODS IN COMPUTER SCIENCE
• Volume: 9
• Issue: 1
• Publication date: 2013-01-01
• DOI: 10.2168/LMCS-9(1:08)2013
• EISSN: 1860-5974
• ISSN: 1860-5974
• Language: English
• Keywords: minimisation; polynomial identity testing; weighted automata; equivalence checking