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
| Other Authors: | , , |
|---|---|
| Format: | eBook |
| Language: | English |
| Published: |
Berlin, Heidelberg
Springer Berlin Heidelberg
1984, 1984
|
| Edition: | 1st ed. 1984 |
| Series: | Lecture Notes in Computer Science
|
| Subjects: | |
| Online Access: | |
| Collection: | Springer Book Archives -2004 - Collection details see MPG.ReNa |
Table of Contents:
- P-mitotic sets
- Equivalence relations, invariants, and normal forms, II
- Recurrence relations for the number of labeled structures on a finite set
- Recursively enumerable extensions of R1 by finite functions
- On the complement of one complexity class in another
- The length-problem
- On r.e. inseparability of CPO index sets
- Arithmetical degrees of index sets for complexity classes
- Rudimentary relations and Turing machines with linear alternation
- A critical-pair/completion algorithm for finitely generated ideals in rings
- Extensible algorithms
- Some reordering properties for inequality proof trees
- Modular decomposition of automata
- Modular machines, undecidability and incompleteness
- Universal Turing machines (UTM) and Jones-Matiyasevich-masking
- Complexity of loop-problems in normed networks
- On the solvability of the extended ?? ? ??? — Ackermann class with identity
- Reductions for the satisfiability with a simple interpretation of the predicate variable
- The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems)
- Implicit definability of finite binary trees by sets of equations
- Spektralproblem and completeness of logical decision problems
- Reduction to NP-complete problems by interpretations
- Universal quantifiers and time complexity of random access machines
- Second order spectra
- On the argument complexity of multiply transitive Boolean functions
- The VLSI complexity of Boolean functions
- Fast parallel algorithms for finding all prime implicants for discrete functions
- Bounds for Hodes - Specker theorem
- Proving lower bounds on the monotone complexity of Boolean functions