Some Properties of String Transducers.
UNIVERSITY OF SOUTHERN CALIFORNIA LOS ANGELES DEPT OF ELECTRICAL ENGINEERING
Pagination or Media Count:
The paper compares the computational power of various classes of transducers. A transducer is an automaton which transforms an input string into an output string, where both the input and output strings consist of symbols from some finite alphabet of symbols. A transducer performs its computations on a working tape of discrete squares. Each square may contain one symbol from a finite working alphabet. A transducer M is said to be a member of the class mLn of Ln space bounded transducers if, whenever M completes a computation on an input of length n, then M makes use of no more than Ln squares of working tape. It is shown that the class mlogn is closed under finite composition. Modified author abstract
- Computer Programming and Software