@inbook{87ceb73d325c4580949f484f38f45676,
title = "On the termination problem for counter machines with incrementing errors",
abstract = "In contrast to their reliable and lossy-error counterparts whose termination problems are either undecidable or non-primitive recursive, the termination problem for counter machines with incrementing errors is shown to be PSpace-hard but remains solvable in ExpSpace. This is a notable decrease in complexity over that of insertion-error channel systems (with emptiness testing) whose termination problem is known to be non-elementary. Furthermore, by fixing the number of available counters, we obtain a tight NLogSpace-complete bound for the termination problem.",
keywords = "Halting problem, Incrementing error, Lossy error, Termination, Unreliable counter machines",
author = "Hampson, {Christopher Samuel}",
year = "2019",
month = jul,
day = "14",
doi = "10.1007/978-3-030-30806-3_11",
language = "English",
isbn = "9783030308056",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "137--148",
editor = "Emmanuel Filiot and Rapha{\"e}l Jungers and Igor Potapov",
booktitle = "Reachability Problems - 13th International Conference, RP 2019, Proceedings",
}