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 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 sol...
| Egile Nagusiak: | , , , , |
|---|---|
| Formatua: | Journal article |
| Hizkuntza: | English |
| Argitaratua: |
2013
|