One-way multihead writing finite automata*

https://doi.org/10.1016/S0019-9958(76)90426-5Get rights and content
Under an Elsevier user license
open archive

The family of languages recognized by one-way multihead writing finite automata is investigated. It is shown that there are languages recognized by deterministic three-head one-way nonwriting finite automata that cannot be recognized by any nondeterministic two-head one-way writing finite automaton.

Cited by (0)

*

This work is a portion of the author's doctoral dissertation at the Pennsylvania State University. An extended abstract of the present paper was presented at the Twelfth Annual Symposium on Switching and Automata Theory at Michigan State University, October 13, 1971.

Copyright © 1976 Published by Elsevier Inc.