Author, as appears in the article.: Nagy, Benedek

Keywords: language

Abstract: Both deterministic and non-deterministic nite state machines (automata) recognize regular languages exactly. Now we extend these machines using two heads to characterize even-linear and linear languages. The heads move in opposite directions in these automata. For even-linear languages, deterministic automata have the same eciency as non-deterministic ones, but for the general case (linear languages) only the non-deterministic version is sucient. We compare our automata to other two-head automata as well.

Journal publication year: 2012

Publication Type: info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/article