论文标题
二维打字机自动机
Two-Dimensional Typewriter Automata
论文作者
论文摘要
打字机自动机是二维自动机的特殊变体，该变体接收二维单词作为输入，并且只能将其输入头移动到三个方向：向下，向左和向右移动其输入单词。此外，只能通过特殊的“重置”移动来向下和向左移动，该移动模拟打字机的马车返回的动作。 在本文中，我们启动了打字机自动机模型的研究，并将其与类似模型（包括三维二维自动机，Boustrophedon Automata和返回自动机）相关联。我们研究打字机自动机模型的识别能力，建立模型识别的语言类别的闭合属性，并考虑用于行串联串联的特定操作的操作状态复杂性界限。我们还提供了与模型有关的各种潜在的未来研究方向。
A typewriter automaton is a special variant of a two-dimensional automaton that receives two-dimensional words as input and is only capable of moving its input head through its input word in three directions: downward, leftward, and rightward. In addition, downward and leftward moves may only be made via a special "reset" move that simulates the action of a typewriter's carriage return. In this paper, we initiate the study of the typewriter automaton model and relate it to similar models, including three-way two-dimensional automata, boustrophedon automata, and returning automata. We study the recognition powers of the typewriter automaton model, establish closure properties of the class of languages recognized by the model, and consider operational state complexity bounds for the specific operation of row concatenation. We also provide a variety of potential future research directions pertaining to the model.
