Voir la notice de l'article provenant de la source Numdam
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.
@article{ITA_2014__48_1_107_0,
author = {Amorim, Ivone and Machiavelo, Ant\'onio and Reis, Rog\'erio},
title = {On the invertibility of finite linear transducers},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {107--125},
publisher = {EDP-Sciences},
volume = {48},
number = {1},
year = {2014},
doi = {10.1051/ita/2014004},
mrnumber = {3195791},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2014004/}
}
TY - JOUR AU - Amorim, Ivone AU - Machiavelo, António AU - Reis, Rogério TI - On the invertibility of finite linear transducers JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2014 SP - 107 EP - 125 VL - 48 IS - 1 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita/2014004/ DO - 10.1051/ita/2014004 LA - en ID - ITA_2014__48_1_107_0 ER -
%0 Journal Article %A Amorim, Ivone %A Machiavelo, António %A Reis, Rogério %T On the invertibility of finite linear transducers %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2014 %P 107-125 %V 48 %N 1 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita/2014004/ %R 10.1051/ita/2014004 %G en %F ITA_2014__48_1_107_0
Amorim, Ivone; Machiavelo, António; Reis, Rogério. On the invertibility of finite linear transducers. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) no. 1, pp. 107-125. doi: 10.1051/ita/2014004
Cité par Sources :