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.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Finite Automaton Computations
ReversalBounded Counter Machines
1 1 42
2 other sections not shown
1-way NSM languages 1-way simple 2-tape DFA accepting computation alphabet arguments atomic formulae augmented Baker and Book binary encoding branching test BSP accepts class of 1-way class of languages closed under complementation CM's configuration constant context-free languages Corollary counter machines counterexamples decision problems decrement definable deterministic DTIME effectively constructible empty finite automata finite control finite memory finite reversal finite reversal-bounded counters forcible execution function Greibach guess head reversals Herbrand interpretation hierarchy homomorphism ignored POPs induction input head input tape languages accepted Lemma linear log n reversal-bounded logn multihead multitape NCM's nondeterministic NSM's positive integer predicate Presburger arithmetic program schemes proof proper subclass pushdown automata pushdown store recognizable recursive recursive sets regular sets result reversal bounds reversal complexity reversal hierarchy reversal-bounded 1-way scan segment sequence simulation space-bounded TCS values Theorem time-bounded Turing machine unary unary languages underlying language valid computation variables verify