Observatorio de I+D+i UPM

Memorias de investigación
Conferences:
Extended Finite Automata Over Groups
Year:2014
Research Areas
  • Information technology and adata processing
Information
Abstract
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.
International
Si
1310-0513
Entity
Entity Nationality
ESPAÑA
Place
Madrid
Participants
  • Autor: Victor Mitrana (UPM)
Research Group, Departaments and Institutes related
  • Creador: Departamento: Sistemas Informáticos
S2i 2020 Observatorio de investigación @ UPM con la colaboración del Consejo Social UPM
Cofinanciación del MINECO en el marco del Programa INNCIDE 2011 (OTR-2011-0236)
Cofinanciación del MINECO en el marco del Programa INNPACTO (IPT-020000-2010-22)