Logic and Machines: Decision Problems and Complexity
Springer Berlin (Verlag)
978-3-540-13331-5 (ISBN)
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.
| Erscheint lt. Verlag | 1.5.1984 |
|---|---|
| Reihe/Serie | Lecture Notes in Computer Science |
| Zusatzinfo | VI, 460 p. |
| Verlagsort | Berlin |
| Sprache | englisch |
| Maße | 155 x 235 mm |
| Gewicht | 653 g |
| Themenwelt | Informatik ► Software Entwicklung ► User Interfaces (HCI) |
| Mathematik / Informatik ► Informatik ► Theorie / Studium | |
| Mathematik / Informatik ► Mathematik ► Logik / Mengenlehre | |
| Schlagworte | arithmetic • Automatentheorie • boolean satisfiability problem • Complexity • Entscheidung (Math.) • Equivalence • Komplexität (Math.) • Logic • Mathematical Logic • NP • Proof • turing degree • Turing Machine |
| ISBN-10 | 3-540-13331-3 / 3540133313 |
| ISBN-13 | 978-3-540-13331-5 / 9783540133315 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
