Reversal-bounded computations

Front Cover
Dept. of Computer Science, Cornell University, 1980 - Computers - 312 pages
IN computations by abstract computing devices such as the Turing machine, head reversals are required for searching the input or retrieving intermediate results. Hence the number of head reversals is a measure of the complexity of a computation. This thesis is a study of reversal-bounded computation on three models of abstract computing devices.

From inside the book

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Finite Automaton Computations
12
ReversalBounded Counter Machines
32
1 1 42
62

2 other sections not shown

Common terms and phrases

Bibliographic information