A Pumping Lemma for Two-Way Finite Transducers


* [2019 May 24] Olivier Gauwin has brought to my attention the prior work of Brigitte Rozoy, who proved a similar pumping lemma in "Outils et résultats pour les transducteurs boustrophédons", published in RAIRO - Informatique théorique et applications in 1986.


The errors below are present in the conference publication, but have been fixed in the latest version available here.

Section 5 (Application)

* [2014 Aug 12] In the proof of Theorem 2, replace {w,u,z,h,a,o} with {w,u,z,h,a,o}* and replace {a,b} with {a,b}*.