On free inverse monoid languages

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

Autores

Pedro V. Silva (Autor) FCUP

Revista

Título: RAIRO - Theoretical Informatics and Applications

Vol. 30 Nº 4

Páginas: 349-378

ISSN: 0988-3754

Editora: EDP Sciences

Indexação

ISI Web of Knowledge - 16 Citações

Scopus - 18 Citações

Outras Informações

ID Authenticus: P-001-FKG

DOI: 10.1051/ita/1996300403491

Abstract (EN): This is a study on the class of FIM(X)-languages and its important subfamily consisting of inverse automata languages (i-languages). Bath algebraic and combinatorial approaches are used to obtain several results concerning closure operators on (X boolean OR X(-1))*-languages, including a classification of FIM(X)-languages by i-languages. In particular, it is proved that the i-closure of a recognizable (X boolean OR X(-1))*-language is at most deterministic context-free. Infinite trees are an essential tool in this process, and they are also helpful in producing counterexamples for other closure problems. Applications to X*-languages are also produced, involving particular classes of codes.

Idioma: Inglês

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

Nº de páginas: 30