Computation Theory and Logic

Minimal pairs for polynomial time reducibilities....Pages 1-13
Primitive recursive word-functions of one variable....Pages 14-19
Existential fixed-point logic....Pages 20-36
Unsolvable decision problems for PROLOG programs....Pages 37-48
You have not understood a sentence, unless you can prove it....Pages 49-58
On the minimality of K , F , and D or: Why löten is non-trivial....Pages 59-66
A 5-color-extension-theorem....Pages 67-77
Closure relations, Buchberger's algorithm, and polynomials in infinitely many variables....Pages 78-87
The benefit of microworlds in learning computer programming....Pages 88-100
Skolem normal forms concerning the least fixpoint....Pages 101-106
Spectral representation of recursively enumerable and coenumerable predicates....Pages 107-116
Aggregating inductive expertise on partial recursive functions....Pages 117-130
Domino threads and complexity....Pages 131-142
Modelling of cooperative processes....Pages 143-153
A setting for generalized computability....Pages 154-165
First-order spectra with one variable....Pages 166-180
On the early history of register machines....Pages 181-188
Randomness, provability, and the separation of Monte Carlo Time and space....Pages 189-207
Representation independent query and update operations on propositional definite Horn formulas....Pages 208-223
Direct construction of mutually orthogonal latin squares....Pages 224-236
Negative results about the length problem....Pages 237-248
Some results on the complexity of powers....Pages 249-255
The Turing complexity of AF C*-algebras with lattice-ordered K O ....Pages 256-264
Remarks on SASL and the verification of functional programming languages....Pages 265-276
Numerical stability of simple geometric algorithms in the plane....Pages 277-293
Communication with concurrent systems via I/0-procedures....Pages 294-305
A class of exp-time machines which can be simulated by polytape machines....Pages 306-319
αβγ-Automata realizing preferences....Pages 320-333
Ein einfaches Verfahren zur Normalisierung unendlicher Herleitungen....Pages 334-348
Grammars for terms and automata....Pages 349-359
Relative konsistenz....Pages 360-381
Segment translation systems....Pages 382-390
First steps towards a theory of complexity over more general data structures....Pages 391-402
On the power of single-valued nondeterministic polynomial time computations....Pages 403-414
A concatenation game and the dot-depth hierarchy....Pages 415-426
Do there exist languages with an arbitrarily small amount of context-sensitivity?....Pages 427-432
The complexity of symmetric boolean functions....Pages 433-442