
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