A new family of automata, one-way multihead marker automata, is introduced. Intuitively these devices consist of one or more read heads travelling in a single direction on a bounded tape and a finite fixed pool of markers which may be deposited on the tape, sensed, and later removed. The major results obtained are:
(i) A one-way n-head k-marker automaton with distinguished markers (each marker is recognizably distinct) may be simulated by a one-way n-head
(k+1)-marker automaton with uniform markers (one marker cannot be told from another);
(ii) Minor restrictions in pebble use and head movement do not significantly affect the recognition power of these devices, consequently it is possible to obtain normal forms for devices with either distinguished or uniform markers;
(iii) If p(x) is a polynomial with positive integer coefficients of degree k>0 then the language {0P(n) |n Ɵ {0,1,2,...}} is recognized by a deterministic
s.one-way k-head (k-1)-marker automaton;
(iv) There exists a class of one-letter languages, characterized by finite linear difference equations, which are recognized by a deterministic one-way n-head 2-marker automaton. Members of this class include the fibonacci numbers and all languages {0(kn) |n Ɵ {0,1,2,...}}, k a fixed natural number. This class is of particular interest since it contains languages not generable by any polynomial, proving that a complete characterization of the one-letter languages recognized by one-way multihead marker automata can not rest upon the polynomial languages alone. / Science, Faculty of / Computer Science, Department of / Graduate
| Identifer | oai:union.ndltd.org:UBC/oai:circle.library.ubc.ca:2429/21005 |
| Date | January 1978 |
| Creators | Gorlick, Michael Martin |
| Source Sets | University of British Columbia |
| Language | English |
| Detected Language | English |
| Type | Text, Thesis/Dissertation |
| Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
Page generated in 0.0022 seconds