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
Herausgegeben:Börger, E.; Hasenjaeger, G.; Rödding, D.
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
Herausgegeben:Börger, E.; Hasenjaeger, G.; Rödding, D.
- Broschiertes Buch
Andere Kunden interessierten sich auch für
- Fundamentals of Computation Theory39,99 €
- Thomas ThieraufThe Computational Complexity of Equivalence and Isomorphism Problems39,99 €
- Andrzej SzepietowskiTuring Machines with Sublogarithmic Space39,99 €
- Borut RobicThe Foundations of Computability Theory66,99 €
- Jörg Flum / Mario Rodriguez-Artalejo (eds.)Computer Science Logic39,99 €
- Fundamentals of Computation Theory37,99 €
- Klaus WeihrauchComputability38,99 €
-
-
-
Produktdetails
- Lecture Notes in Computer Science 171
- Verlag: Springer / Springer Berlin Heidelberg / Springer, Berlin
- Artikelnr. des Verlages: 978-3-540-13331-5
- Softcover reprint of the original 1st ed. 1984
- Seitenzahl: 472
- Erscheinungstermin: 1. Mai 1984
- Englisch
- Abmessung: 235mm x 155mm x 26mm
- Gewicht: 653g
- ISBN-13: 9783540133315
- ISBN-10: 3540133313
- Artikelnr.: 23110954
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.
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.