A Class of 2-Head Finite Automata for Linear Languages

Authors

  • Benedek Nagy

DOI:

https://doi.org/10.17345/triangle8.89-99

Keywords:

language, literature, computation

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.

Downloads

Download data is not yet available.

Downloads

Published

2018-06-29

How to Cite

Nagy, B. (2018). A Class of 2-Head Finite Automata for Linear Languages. Triangle, (8), 89–99. https://doi.org/10.17345/triangle8.89-99

Issue

No. 8 (2012)

Section

Articles

License

This journal provides immediate open access to its contents based on the principle that the making research available to the public free of charge promotes the global exchange of knowledge. The journal Triangle is published under a Creative Commons licence.

This journal allows the authors to hold the copyright without restrictions. This journal allows the authors to retain the publishing rights without restrictions.

All articles published in our journals are open access and freely available online, immediately upon publication. There are no submission charges and no processing charges for Publicacions URV Journals.