Extended finite automata over groups

Mitrana, Victor and 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.


Title: Extended finite automata over groups
  • Mitrana, Victor
  • Stiebe, Ralf
Item Type: Article
Event Location: Madrid
Título de Revista/Publicación: Discrete applied mathematics
Date: 15 March 2001
ISSN: 0166-218X
Volume: 108
Freetext Keywords: Finite automata over groups ; closure properties ; accepting capacity ; interchange lemma ; free groups
Faculty: E.T.S.I. de Sistemas Informáticos (UPM)
Department: Sistemas Informáticos
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (816kB) | Preview


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.

More information

Item ID: 41656
DC Identifier: https://oa.upm.es/41656/
OAI Identifier: oai:oa.upm.es:41656
DOI: 10.1016/S0166-218X(00)00200-6
Official URL: http://www.sciencedirect.com/science/article/pii/S0166218X00002006
Deposited by: Memoria Investigacion
Deposited on: 13 Jul 2017 18:07
Last Modified: 13 Jul 2017 18:07
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM