ON THE INVERTIBILITY OF FINITE LINEAR TRANSDUCERS

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

Autores

Ivone Amorim (Autor) Outra; Antonio Machiavelo (Autor) FCUP; Rogerio Reis (Autor) FCUP

Revista

Título: RAIRO - Theoretical Informatics and Applications

Vol. 48

Páginas: 107-125

ISSN: 0988-3754

Editora: EDP Sciences

Indexação

ISI Web of Knowledge - 3 Citações

Scopus - 3 Citações

Classificação Científica

FOS: Ciências exactas e naturais > Ciências da computação e da informação

Outras Informações

ID Authenticus: P-009-8JN

DOI: 10.1051/ita/2014004

Abstract (EN): Linear finite transducers underlie a series of schemes for Public Key Cryptography (PKC) proposed in the 90s of the last century. The uninspiring and arid language then used, condemned these works to oblivion. Although some of these schemes were afterwards shown to be insecure, the promise of a new system of PKC relying on different complexity assumptions is still quite exciting. The algorithms there used depend heavily on the results of invertibility of linear transducers. In this paper we introduce the notion of post-initial linear transducer, which is an extension of the notion of linear finite transducer with memory, and for which the previous fundamental results on invertibility still hold. This extension enabled us to give a new method to obtain a left inverse of any invertible linear finite transducer with memory. It also plays an essencial role in the necessary and sufficient condition that we give for left invertibility of linear finite transducers.

Idioma: Inglês

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

Nº de páginas: 19