On the termination and structural termination problems for counter machines with incrementing errors

DOI10.1016/j.jcss.2021.03.007zbMath1480.68008OpenAlexW3153709765MaRDI QIDQ2037198

Christopher Hampson

Publication date: 30 June 2021

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2021.03.007

zbMATH Keywords

terminationhalting problemincrementing errorlossy errorstructural terminationunreliable counter machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Classical models of computation (Turing machines, etc.) (68Q04)

Cites Work

• Unnamed Item
• Computability and complexity theory.
• Undecidable problems in unreliable computations.
• Using forward reachability analysis for verification of lossy channel systems
• Unreliable channels are easier to verify than perfect channels
• Verifying programs with unreliable channels
• On termination and invariance for faulty channel machines
• On the termination problem for counter machines with incrementing errors
• Complexity Hierarchies beyond Elementary
• LTL with the freeze quantifier and register automata
• Undecidable Propositional Bimodal Logics and One-Variable First-Order Linear Temporal Logics with Counting
• Lossy Counter Machines Decidability Cheat Sheet
• Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets
• The complexity of decision procedures in relevance logic II
• On the decidability and complexity of Metric Temporal Logic over finite words
• Counter machines and counter languages
• Foundations of Software Science and Computation Structures

This page was built for publication: On the termination and structural termination problems for counter machines with incrementing errors