On the termination problem for counter machines with incrementing errors

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review

1 Citation (Scopus)
191 Downloads (Pure)

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.

Original languageEnglish
Title of host publicationReachability Problems - 13th International Conference, RP 2019, Proceedings
EditorsEmmanuel Filiot, Raphaël Jungers, Igor Potapov
Pages137-148
Number of pages12
DOIs
Publication statusAccepted/In press - 14 Jul 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11674 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • Halting problem
  • Incrementing error
  • Lossy error
  • Termination
  • Unreliable counter machines

Fingerprint

Dive into the research topics of 'On the termination problem for counter machines with incrementing errors'. Together they form a unique fingerprint.

Cite this