Store languages of Turing machines and counter machines

Read full text Summarise with VIRAT
Authors: Noah Friesen, Óscar H. Ibarra, Jozef Štefan Jirásek, Ian McQuillan
Cited by: 0
References: 34

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

The store language of an automaton is the set of store configurations (state and store contents, but not the input) that can appear as an intermediate step in an accepting computation. A one-way nondeterministic finite-visit Turing machine ( fvNTM ) is a Turing machine with a one-way read-only input tape, and a single worktape, where there is some number k such that in every accepting computation, each worktape cell is visited at most k times. We show that the store language of every fvNTM is a regular language. Furthermore, we show that the store language of every fvNTM augmented by reversal-bounded counters can be accepted by a machine with only reversal-bounded counters and no worktape. Several applications are given to problems in the areas of verification and fault tolerance, and to the study of right quotients. We also continue the investigation of the store languages of one-way and two-way machine models where we present some conditions under which their store languages are recursive or non-recursive.

Fields of Study & Subjects

semigroups and automata theory Computability Logic AI Algorithms Algorithms and Data Compression

Publication details

Journal / source
Theoretical Computer Science
Volume
1074
Pages
115931–115931
Publication date
31 March 2026
Language
EN