Determinization of transducers over finite and infinite words
We study the determinization of transducers over finite and infinite words. The first part of the paper is devoted to finite words. We recall the characterization of subsequential functions due to Choffrut. We describe here a known algorithm to determinize a transducer. In the case of infinite words, we consider transducers with all their states final. We give an effective characterization of sequential functions over infinite words. We describe an algorithm to determinize transducers over infinite words. This part contains the main novel results of the paper. (C) 2002 Elsevier Science B.V. All rights reserved.
determinization transducers infinite words automata