Computation Theory and Logic

Klaus Ambos-Spies (auth.), Egon Börger (eds.)3540181709, 9783540181705

This volume contains 37 invited research papers collected in memory of Dieter Rödding, who is known for his work on the classification of recursive functions, on reduction classes, on the spectrum problem and on the complexity of cardinality quantifiers in predicate logic and in arithmetical hierarchy. He was one of the first to pursue the interaction of logic and computer science. The volume reflects the wide spectrum of Dieter Rödding’s scientific interests.

---

Table of contents :
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