Logic and machines, decision problems and complexity. Proceedings of the Symposium "Rekursive Kombinatorik" held from May 23-28, 1983 at the Inst. für Mathematische Logik u. Grundlagenforschung d. Universität Münster. Westfalen.

Börger, E. / G. Hasenjaeger / D. Rödding (Hrsg.).

ISBN 10: 3540133313 / ISBN 13: 9783540133315

Editore: Berlin / Heidelberg / New York / Tokyo Springer 1984, 1984

Riguardo questo articolo

VI,456 S. Orig.-Karton. Erste Ausgabe.- (= Lecture notes in computer science , 171).- Gutes Exemplar.

Codice articolo 97738

Dati bibliografici

• Titolo: Logic and machines, decision problems and complexity. Proceedings of the Symposium "Rekursive Kombinatorik" held from May 23-28, 1983 at the Inst. für Mathematische Logik u. Grundlagenforschung d. Universität Münster. Westfalen.
• Editore: Berlin / Heidelberg / New York / Tokyo Springer 1984
• Data di pubblicazione: 1984
• Lingua: Inglese
• ISBN 10: 3540133313
• ISBN 13: 9783540133315
• Rilegatura: Brossura
• Edizione: prima edizione
• Cataloghi dei venditori:
  • Naturwissenschaft/Technik

Descrizione articolo

Contenuti

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.