Single-valued a-transducers

摘要

A single-valued a-transducer is an a-transducer for which the transduction relation is a partial function on strings. Our concern is with questions of decidability and with the structure of input strings (and the associated output strings) that are accepted via more than one path. The main results are: Single-valuedness is decidable. Equivalence of single-valued a-transducers is decidable. For an a-transducer multipath-input strings which pass through loops must pass through loops whose inputs satisfy commutativity conditions and when the a-transducer is single-valued the outputs of the loops must satisfy similar conditions.