## Computation Theory and LogicThis 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. |

### What people are saying - Write a review

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

### Contents

I | xi |

II | 14 |

III | 20 |

IV | 37 |

V | 49 |

VI | 59 |

VII | 67 |

VIII | 78 |

XXIII | 224 |

XXIV | 237 |

XXV | 249 |

XXVI | 256 |

XXVII | 265 |

XXVIII | 277 |

XXIX | 294 |

XXX | 306 |

IX | 88 |

X | 101 |

XII | 107 |

XIII | 117 |

XIV | 131 |

XV | 143 |

XVI | 154 |

XVIII | 166 |

XIX | 181 |

XX | 189 |

XXI | 208 |

XXXI | 320 |

XXXII | 334 |

XXXIII | 349 |

XXXIV | 360 |

XXXV | 382 |

XXXVI | 391 |

XXXVII | 403 |

XXXVIII | 415 |

XXXIX | 427 |

XL | 433 |

### Common terms and phrases

algebra algorithm arithmetic expressions ascending chain condition automata automaton binary bounded C*-algebras circuits complete complexity classes computation concept construction decision problems Dedekind defined denote deterministic E+LFP elements equivalent example existential finite first-order first-order logic function f geometric given graph Hence hierarchy Hilbert Horn clause implies induction infinite input integer Isba-evaluation isomorphic Knoten language least fixpoint Lemma length logic Logik machine numbers Math mathematical Mathematik mathematische minimal minimal pair Monte Carlo MV-algebra nondeterministic notation obtain operations opt-form oracle oracle set output pair polynomial time-bounded pr-hard predicate problem proof Proposition prove pupils quantifier query recursive functions recursive set reducible reduction ring register machine relation resp result SASL satisfying behaviour sentence sequence simulation Skolem normal form stage s+1 string structure subset symbols tape Theorem theory Turing machines Turing transducer unary value-schedule variables Zahlen