A topological approach to transductions

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

Autores

Jean-Eric Pin (Autor) Outra; Pedro V. Silva (Autor) FCUP

Revista

Título: Theoretical Computer Science

Vol. 340

Páginas: 443-456

ISSN: 0304-3975

Editora: Elsevier

Indexação

ISI Web of Knowledge - 9 Citações

ISI Web of Science

Scopus - 13 Citações

Classificação Científica

FOS: Ciências exactas e naturais

Outras Informações

ID Authenticus: P-000-2T2

DOI: 10.1016/j.tcs.2005.03.029

Abstract (EN): This paper is a contribution to the mathematical foundations of the theory of automata. We give a topological characterization of the transductions tau from a monoid M into a monoid N, such that if R is a recognizable subset of N, tau(-1) (R) is a recognizable subset of M. We impose two conditions on the monoids, which are fullfilled in all cases of practical interest: the monoids must be residually finite and, for every positive integer n, must have only finitely many congruences of index n. Our solution proceeds in two steps. First we show that such a monoid, equipped with the so-called Hall distance, is a metric space whose completion is compact. Next we prove that tau can be lifted to a map tau from M into the set of compact subsets of the completion of N. This latter set, equipped with the Hausdorff metric, is again a compact monoid. Finally, our main result states that tau(-1) preserves recognizable sets if and only if is continuous.

Idioma: Inglês

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

Nº de páginas: 14