Willkommen, schön sind Sie da!
Logo Ex Libris

Logic and Machines: Decision Problems and Complexity

  • Kartonierter Einband
  • 472 Seiten
(0) Erste Bewertung abgeben
Bewertungen
(0)
(0)
(0)
(0)
(0)
Alle Bewertungen ansehen
InhaltP-mitotic sets.- Equivalence relations, invariants, and normal forms, II.- Recurrence relations for the number of labeled st... Weiterlesen
20%
49.50 CHF 39.60
Sie sparen CHF 9.90
Print on Demand - Auslieferung erfolgt in der Regel innert 4 bis 6 Wochen.
Bestellung & Lieferung in eine Filiale möglich

Beschreibung

Inhalt
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.

Produktinformationen

Titel: Logic and Machines: Decision Problems and Complexity
Untertitel: 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
Editor:
EAN: 9783540133315
ISBN: 3540133313
Format: Kartonierter Einband
Herausgeber: Springer Berlin Heidelberg
Genre: Informatik
Anzahl Seiten: 472
Gewicht: 709g
Größe: H235mm x B155mm x T25mm
Jahr: 1984
Untertitel: Englisch
Auflage: Softcover reprint of the original 1st ed. 1984

Weitere Produkte aus der Reihe "Lecture Notes in Computer Science"