SYSTEM DEVELOPMENT CORP SANTA MONICA CA
Pagination or Media Count:
In previous papers the notion of a family of one-way nondeterministic devices was abstracted and studied extensively. A natural extension of a device with a particular type of storage tape is a multitape storage device, each tape of the same kind. In most familiar cases--counter, pushdown, stack--adding a second storage tape increases the power of the device to that of a Turing acceptor. By suitable restrictions on multitape devices, families can be obtained so that the associated languages do not include all recursively enumerable sets. The purpose of the paper is to abstract the notion of an abstract family of multitape acceptors abbreviated multitape AFA, each storage tape not necessarily of the same kind, and examine the family of associated languages.
- Computer Programming and Software
- Computer Hardware