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 tobe insecure, the promise of a new system of PKC relying on different complexityassumptions is still quite exciting. The algorithms there used depend heavily on theresults of invertibility of linear transducers. In this paper we introduce the notion ofpost-initial linear transducer, which is an extension of the notion of linear finitetransducer with memory, and for which the previous fundamental results on invertibilitystill hold. This extension enabled us to give a new method to obtain a left inverse of anyinvertible linear finite transducer with memory. It also plays an essencial role in thenecessary and sufficient condition that we give for left invertibility of linear finitetransducers.
