Memorias de investigación
Conferencias:
Extended Finite Automata Over Groups
Año:2014
Áreas de investigación
  • Ciencias de la computación y tecnología informática
Datos
Descripción
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.
Internacional
Si
ISSN o ISBN
1310-0513
Entidad relacionada
Nacionalidad Entidad
ESPAÑA
Lugar del congreso
Madrid
Esta actividad pertenece a memorias de investigación
Participantes
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Departamento: Sistemas Informáticos