Once-Marking and Always-Marking 1-Limited Automata

Single-tape nondeterministic Turing machines that are allowed to replace the symbol in each tape cell only when it is scanned for the first time are also known as [Formula: see text]-limited automata. These devices characterize, exactly as finite automata, the class of regular languages. However, they can be extremely more succinct. Indeed, in the worst case, the size gap from [Formula: see text]-limited automata to one-way deterministic finite automata is double exponential. Here we introduce two restricted versions of [Formula: see text]-limited automata, once-marking[Formula: see text]-limited automata and always-marking[Formula: see text]-limited automata, and study their descriptional complexity. We prove that once-marking [Formula: see text]-limited automata still exhibit a double exponential size gap to one-way deterministic finite automata. However, their deterministic restriction is polynomially related in size to two-way deterministic finite automata, in contrast to deterministic [Formula: see text]-limited automata, whose equivalent two-way deterministic finite automata in the worst case are exponentially larger. For always-marking [Formula: see text]-limited automata, we prove that the size gap to one-way deterministic finite automata is only a single exponential. The gap remains exponential even in the case the given machine is deterministic. We obtain other size relationships between different variants of these machines and finite automata and we present some problems that deserve investigation.