The Library
On the complexity of equivalence and minimisation for Q-weighted automata
Tools
Kiefer, Stefan , Murawski, Andrzej S., Ouaknine, Joel , Wachter, Bjoern and Worrell, James (2013) On the complexity of equivalence and minimisation for Q-weighted automata. Logical Methods in Computer Science, Volume 9 (Number 1). Article number 8. doi:10.2168/LMCS-9(1:8)2013 ISSN 1860-5974.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.2168/LMCS-9(1:8)2013
Abstract
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 solvable in polylogarithmic parallel time. For finite Q-weighted automata, we give a randomised NC procedure that either outputs that two automata are equivalent or returns a word on which they differ. We also give an NC procedure for deciding whether a given automaton is minimal, as well as a randomised NC procedure that minimises an automaton. We consider probabilistic automata with rewards, similar to Markov Decision Processes. For these automata we consider two notions of equivalence: expectation equivalence and distribution equivalence. The former requires that two automata have the same expected reward on each input word, while the latter requires that each input word induce the same distribution on rewards in each automaton. For both notions we give algorithms for deciding equivalence by reduction to equivalence of Q-weighted automata. Finally we show that the equivalence problem for Q-weighted visibly pushdown automata is logspace equivalent to the polynomial identity testing problem.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Alternative Title: | |||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | Logical Methods in Computer Science | ||||
Publisher: | International Federation for Computational Logic | ||||
ISSN: | 1860-5974 | ||||
Official Date: | 4 March 2013 | ||||
Dates: |
|
||||
Volume: | Volume 9 | ||||
Number: | Number 1 | ||||
Page Range: | Article number 8 | ||||
DOI: | 10.2168/LMCS-9(1:8)2013 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |