Logic and Machines: Decision Problems and Complexity: Proceedings of the Symposium “Rekursive Kombinatorik” held from May 23 – 28, 1983 at the Institut für Mathematische Logik und Grundlagenforschung der Universität Münster/Westfalen

Klaus Ambos-Spies (auth.), E. Börger, G. Hasenjaeger, D. Rödding (eds.)3540133313, 9783540133315

Table of contents :
P-mitotic sets….Pages 1-23
Equivalence relations, invariants, and normal forms, II….Pages 24-42
Recurrence relations for the number of labeled structures on a finite set….Pages 43-61
Recursively enumerable extensions of R 1 by finite functions….Pages 62-76
On the complement of one complexity class in another….Pages 77-87
The length-problem….Pages 88-102
On r.e. inseparability of CPO index sets….Pages 103-117
Arithmetical degrees of index sets for complexity classes….Pages 118-130
Rudimentary relations and Turing machines with linear alternation….Pages 131-136
A critical-pair/completion algorithm for finitely generated ideals in rings….Pages 137-161
Extensible algorithms….Pages 162-182
Some reordering properties for inequality proof trees….Pages 183-197
Modular decomposition of automata….Pages 198-236
Modular machines, undecidability and incompleteness….Pages 237-247
Universal Turing machines (UTM) and Jones-Matiyasevich-masking….Pages 248-253
Complexity of loop-problems in normed networks….Pages 254-269
On the solvability of the extended ∀∃ ∧ ∃∀⋆ — Ackermann class with identity….Pages 270-284
Reductions for the satisfiability with a simple interpretation of the predicate variable….Pages 285-311
The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems)….Pages 312-319
Implicit definability of finite binary trees by sets of equations….Pages 320-332
Spektralproblem and completeness of logical decision problems….Pages 333-356
Reduction to NP-complete problems by interpretations….Pages 357-365
Universal quantifiers and time complexity of random access machines….Pages 366-379
Second order spectra….Pages 380-389
On the argument complexity of multiply transitive Boolean functions….Pages 390-396
The VLSI complexity of Boolean functions….Pages 397-407
Fast parallel algorithms for finding all prime implicants for discrete functions….Pages 408-420
Bounds for Hodes – Specker theorem….Pages 421-445
Proving lower bounds on the monotone complexity of Boolean functions….Pages 446-456