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):

Report Date:

1973-09-01

Pagination or Media Count:

84.0

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 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

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE