Pebble, Pushdown, and Parallel-Sequential Picture Acceptors.

摘要

This chapter discusses three specialized acceptor models: Pebble acceptors, which cannot rewrite their input, but can make marks on it, with the restriction that only a bounded number of these marks can exist at any given time; Pushdown acceptors, which cannot rewrite their input, but can store a string of symbols in such a way that only the last symbol in the string can be read (so that to retrieve a given symbol from the string, all the symbols beyond it must first be discarded); and, Parallel/sequential acceptors, which are one-dimensional cellular acceptors that read one row of a rectangular input array at a time, and move up and down to scan the array.