Back to search

University of British Columbia

Computation by one-way multihead marker automata

Abstract

dc:description

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.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
1978

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Gorlick, Michael Martin

Rights

dc:rights
Statement dc: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.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/21005

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Gorlick, Michael Martin. Computation by one-way multihead marker automata. master's thesis, University of British Columbia, 1978. http://hdl.handle.net/2429/21005