Free group languages: Rational versus recognizable

• Tipo: Artigo em Revista Científica Internacional
• Data: 2004

Autores

Pedro V. Silva (Autor) FCUP

Revista

Título: RAIRO - Theoretical Informatics and Applications

Vol. 38

Páginas: 49-67

ISSN: 0988-3754

Editora: EDP Sciences

Indexação

ISI Web of Knowledge - 5 Citações

Scopus - 7 Citações

Outras Informações

ID Authenticus: P-000-DK8

DOI: 10.1051/ita:2004003

Abstract (EN): We provide alternative proofs and algorithms for results proved by Senizergues on rational and recognizable free group languages. We consider two different approaches to the basic problem of deciding recognizability for rational free group languages following two fully independent paths: the symmetrification method (using techniques inspired by the study of inverse automata and inverse monoids) and the right stabilizer method (a general approach generalizable to other classes of groups). Several different algorithmic characterizations of recognizability are obtained, as well as other decidability results.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 19