Accession Number : AD0770836

Title :   Some Properties of String Transducers.

Descriptive Note : Technical rept.,

Corporate Author : UNIVERSITY OF SOUTHERN CALIFORNIA LOS ANGELES DEPT OF ELECTRICAL ENGINEERING

Personal Author(s) : Abbott,Russell J.

Report Date : SEP 1973

Pagination or Media Count : 84

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)

Descriptors :   *Computer programming, *Automata, *Programming languages, Mathematical logic, Computations, Transducers, Theorems, Theses

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE