Name
Abstract | ||
|---|---|---|
In the context of probabilistic automata, time-efficient algorithms for simulation have been proposed lately. The space complexity thereof is quadratic in the size of the transition relation, thus space requirements often become the practical bottleneck. In this paper, we propose a space-efficient algorithm for computing simulation based on partition refinement. Experimental evidence is given showing that not only the space efficiency is improved drastically: The experiments often require orders of magnitude less time. In practice, they are even faster than the (asymptotically) optimal algorithm by Crafa and Ranzato (2012). |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.ic.2016.04.002 | Information and Computation |
Keywords | Field | DocType |
Probabilistic automata,Simulation,Partition refinement,Decision algorithm | Quantum finite automata,Orders of magnitude (numbers),Bottleneck,Computer science,Quadratic equation,Algorithm,Probabilistic analysis of algorithms,Partition refinement,Simulation algorithm,Probabilistic automaton | Journal |
Volume | Issue | ISSN |
249 | C | 0890-5401 |
Citations | PageRank | References |
3 | 0.39 | 29 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lijun Zhang | 1 | 245 | 37.10 |
| David N. Jansen | 2 | 309 | 24.09 |