Extended finite automata over groups

Mitrana, Victor y Stiebe, Ralf (2001). Extended finite automata over groups. "Discrete applied mathematics", v. 108 (n. 3); pp. 287-300. ISSN 0166-218X. https://doi.org/10.1016/S0166-218X(00)00200-6.

Descripción

Título: Extended finite automata over groups
Autor/es:
  • Mitrana, Victor
  • Stiebe, Ralf
Tipo de Documento: Artículo
Lugar del Evento: Madrid
Título de Revista/Publicación: Discrete applied mathematics
Fecha: 15 Marzo 2001
Volumen: 108
Materias:
Palabras Clave Informales: Finite automata over groups ; closure properties ; accepting capacity ; interchange lemma ; free groups
Escuela: E.T.S.I. de Sistemas Informáticos (UPM)
Departamento: Sistemas Informáticos
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (816kB) | Vista Previa

Resumen

We consider a simple and natural extension of a finite automaton, namely an element of a given group is associated with each configuration. An input string is accepted if and only if the neutral element of the group is associated to a final configuration reached by the automaton. The accepting power is smaller when abelian groups are considered, in comparison with the non-abelian groups. We prove that this is due to the commutativity. Each language accepted by a finite automaton over an abelian group is actually a unordered vector language. We get a new characterization of the context-free languages as soon as the considered group is the binary free group. The result cannot be carried out in the deterministic case. Some remarks about other groups are also presented.

Más información

ID de Registro: 41656
Identificador DC: http://oa.upm.es/41656/
Identificador OAI: oai:oa.upm.es:41656
Identificador DOI: 10.1016/S0166-218X(00)00200-6
URL Oficial: http://www.sciencedirect.com/science/article/pii/S0166218X00002006
Depositado por: Memoria Investigacion
Depositado el: 13 Jul 2017 18:07
Ultima Modificación: 13 Jul 2017 18:07
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM