| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 11021132 | Information and Computation | 2018 | 31 Pages |
Abstract
We study the decidability and complexity of multi-buffer simulations and obtain the following results: P-completeness for fixed bounded buffers, EXPTIME-completeness in case of a single unbounded buffer and high undecidability (in the analytic hierarchy) with two buffers of which at least one is unbounded. We also consider a variant in which the buffers are kept untouched or flushed and show PSPACE-completeness for the single-buffer case.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Milka Hutagalung, Norbert Hundeshagen, Dietrich Kuske, Martin Lange, Ãtienne Lozes,