Logic and Machines 1983: Münster, Germany

@proceedings{DBLP:conf/lam/1983,
  editor    = {Egon B{\"o}rger and
               Gisbert Hasenjaeger and
               Dieter R{\"o}dding},
  title     = {Logic and Machines: Decision Problems and Complexity, Proceedings
               of the Symposium "Rekursive Kombinatorik" held from May 23-28,
               1983 at the Institut f{\"u}r Mathematische Logik und Grundlagenforschung
               der Universit{\"a}t M{\"u}nster/Westfahlen},
  booktitle = {Logic and Machines},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {171},
  year      = {1984},
  isbn      = {3-540-13331-3},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Complexity

• Klaus Ambos-Spies: P-mitotic sets. 1-23
• Andreas Blass, Yuri Gurevich: Equivalence relations, invariants, and normal forms. 24-42
• Chr. Blatter, Ernst Specker: Recurrence relations for the number of labeled structures on a finite set. 43-61
• Wolfgang Menzel, Volker Sperschneider: Recursively enumerable extensions of R₁ by finite functions. 62-76
• Diana Schmidt: On the complement of one complexity class in another. 77-87
• Volker Sperschneider: The length-problem. 88-102
• Dieter Spreen: On r.e. inseparability of CPO index sets. 103-117
• Kenneth W. Regan: Arithmetical degrees of index sets for complexity classes. 118-130
• Hugo Volger: Rudimentary relations and Turing machines with linear alternation. 131-136

Algorithms

• Bruno Buchberger: A critical-pair/completion algorithm for finitely generated ideals in rings. 137-161
• Hans Georg Carstens, Peter Päppinghaus: Extensible algorithms. 162-182
• Michael M. Richter: Some reordering properties for inequality proof trees. 183-197

Automata and Machines

• Anne Brüggemann-Klein, Lutz Priese, Dieter Rödding, Rüdiger Schätz: Modular decomposition of automata. 198-236
• Daniel E. Cohen: Modular machines, undecidability and incompleteness. 237-247
• Gisbert Hasenjaeger: Universal Turing machines (UTM) and Jones-Matijasevich-masking. 248-253
• Hans Kleine Büning: Complexity of loop-problems in normed networks. 254-269

Decision Problems

• Stål Aanderaa: On the solvability of the extended (exist-forall)and(exists-forall*)-Ackermann class with identity. 270-284
• Michael Deutsch: Reductions for the satisfiability with a simple interpretation of the predicate variable. 285-311
• Martin Fürer: The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems). 312-319
• Jerzy Tiuryn: Implicit definability of finite binary trees by sets of equations. 320-332

Spektralproblem

• Egon Börger: Spektralproblem and completeness of logical decision problems. 333-356
• Elias Dahlhaus: Reduction to NP-complete problems by interpretations. 357-365
• Etienne Grandjean: Universal quantifiers and time complexity of random access machines. 366-379
• Bruno Scarpellini: Second order spectra. 380-389

Complexity of Boolean Functions

• Ulrich Hedtstück: On the argument complexity of multiply transitive Boolean functions. 390-396
• Mark R. Kramer, Jan van Leeuwen: The VLSI complexity of Boolean functions. 397-407
• Walter Oberschelp: Fast parallel algorithms for finding all prime implicants for discrete functions. 408-420
• Pavel Pudlák: Bounds for Hodes-Specker theorem. 421-445
• Ingo Wegener: Proving lower bounds of the monotone complexity of Boolean functions. 446-456