On the definition of a family of automata

Abstract

In this note we discuss the definition of a family (~ of automata derived from the family a0 of the finite one-way one-tape automata (Rabin and Scott, 1959). In loose terms, the automata from (~ are among the machines characterized by the following restrictions: (a) Their output consists in the acceptance (or reieetion ) of input words belonging to the set F of all words in the letters of a finite alphabet X. (b) The automaton operates sequentially on the sueessive letters of the input word without the possibility of coming back on the previously read letters and, thus, all the information to be used in the further computations has to be stored in the internal memory. (c) The unbounded part of the memory, V~¢, is the finite dimensional vector space of the vectors with N integral coordinates; this part of the memory plays only a passive role and all the control of the automaton is performed by the finite part. (d) 0n ly elementary arithmetic operations are used and the amount of computation allowed for each input letter is bounded in terms of the total number of additions and subtractions. (e) The rule by which it is decided to accept or reject a given input word is submitted to the same type of requirements and it involves only the storage of a finite amount of information. Thus the family (~ is a very elementary modification of G0 and it is not