Title :
Finite-Turn Repetitive Checking Automata and Sequential/ Parallel Matrix Languages
Author :
Wang, Patrick Shen-pei
Author_Institution :
GTE Research Laboratories
fDate :
5/1/1981 12:00:00 AM
Abstract :
A class of machines capable of recognizing two-dimensional sequential/parallel matrix languages is introduced. It is called "finite-turn repetitive checking automata" (FTRCA). This checking automaton is provided with three READ-WRITE heads, one READ only head, and a control register in its memory to keep track of the internal transition states and the stack symbols. The value of the register ranges from 0 to a finite positive integer k and can repetitively appear as many times as necessary. A one-to-one correspondence is established between the class of FIRCA and (R:R)ML–the smallest class of the sequential/parallel matrix languages. Several closure properties are also investigated.
Keywords :
Automata; instantaneous description; matrix languages; row(column) Kleene´s closure; row(column) catenation; Application software; Automata; Automatic control; Concurrent computing; Hardware; Magnetic heads; Parallel processing; Power generation; Read-write memory; Registers; Automata; instantaneous description; matrix languages; row(column) Kleene´s closure; row(column) catenation;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.1981.1675797