Logic and Machines 1983: Münster, Germany

Egon Börger, Gisbert Hasenjaeger, Dieter Rödding (Eds.): 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/Westfahlen. Lecture Notes in Computer Science 171 Springer 1984, ISBN 3-540-13331-3

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

Last update Tue Feb 14 04:06:56 2012 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page