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

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