Revistes Publicacions URV: Triangle - llenguatge, literatura, computació> 2012

A Class of 2-Head Finite Automata for Linear Languages

  • Datos identificativos

    Identificador: RP:4410
    Handle: https://hdl.handle.net/20.500.11797/RP4410
    Autores:
    Nagy, Benedek
    Resumen:
    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.

  • Otros:

    Autor según el artículo: Nagy, Benedek
    Palabras clave: language
    Resumen: 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.
    Año de publicación de la revista: 2012
    Tipo de publicación: info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/article