Some Properties of String Transducers.
Abstract
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 m(L(n)) of L(n) space bounded transducers if, whenever M completes a computation on an input of length n, then M makes use of no more than L(n) squares of working tape. It is shown that the class m(log(n)) is closed under finite composition. (Modified author abstract)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1973
- Accession Number
- AD0770836
Entities
People
- Russell J. Abbott
Organizations
- University of Southern California