Monotonic use of space and computational complexity over abstract structures

Abstract: "We use relational pointer machines as a framework for generalized computational complexity. Non-reuse of memory space, dubbed monotonic computing, is proposed as a fundamental concept that threads together various abstract generalizations of PTime. Depending on the use of space, relational machines generalize DLogSpace, PTime, NPTime and PSpace, [w]e show that alternating first order machines are equivalent, over all finite structures, to monotonic machines with positive queries, generalizing the Chandra-Kozen-Stockmeyer Theorem ASpace(f) = DTime(2[superscript f]), and showing that the letter does not depend on any counting mechanism.We show that of two generalizations of PTime, deterministic monotonic machnies and nondeterministic monotonic positive machines, the former can stimulate the latter on all structures, and the latter can stimulate the former on enumerated structures. Finally, first order inductive definitions are shown to be equivalent to monotonic pointer machines with random selection."