Journal article icon

Journal article

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

Abstract:

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
Publication status:
Published

Actions


Access Document


Publisher copy:
10.2168/LMCS-9(1:08)2013

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
Journal:
LOGICAL METHODS IN COMPUTER SCIENCE
Volume:
9
Issue:
1
Publication date:
2013-01-01
DOI:
EISSN:
1860-5974
ISSN:
1860-5974
Source identifiers:
394319
Language:
English
Keywords:
Pubs id:
pubs:394319
UUID:
uuid:cbf02afe-32bd-407c-a829-e5b0515ce98a
Local pid:
pubs:394319
Deposit date:
2013-11-17

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP