On Deleting Deterministic Restarting Automata That Have Two Windows

Abstract

We study deterministic restarting automata with two windows, abbreviated as det-2-RR-automata. In each cycle of a computation, a det-2-RR-automaton can perform up to two delete operations, one with each of its two windows.

We study the class of languages accepted by these automata, comparing it to other well-known language classes and exploring closure properties and algorithmic properties.

Keywords

• restarting automaton
• language class
• closure property
• decision problem