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

AvE. Börger,G. Hasenjaeger

Häftad, Engelska, 1984

Del i serien Lecture Notes in Computer Science

391 kr

Beställningsvara. Skickas inom 10-15 vardagar. Fri frakt över 249 kr.

Produktinformation

Utgivningsdatum:1984-05-01
Mått:155 x 235 x 26 mm
Vikt:709 g
Format:Häftad
Språk:Engelska
Serie:Lecture Notes in Computer Science
Antal sidor:460
Förlag:Springer-Verlag Berlin and Heidelberg GmbH & Co. KG
ISBN:9783540133315

Utforska kategorier

Systemvetenskap och AI inom Data och IT
Matematikens grunder inom Naturvetenskap och teknik
Matematik inom Naturvetenskap och teknik

Innehållsförteckning

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.

Du kanske också är intresserad av

Introduction to the Basic Concepts and Problems of Modern Logic

G. Hasenjaeger

Häftad, 2011

556 kr

Del 1104

Proceedings of the Logic Colloquium. Held in Aachen, July 18-23, 1983

M. M. Richter, E. Börger, W. Oberschelp, B. Schinzel, W. Thomas

Häftad, 1984

500 kr

Introduction to the Basic Concepts and Problems of Modern Logic

G. Hasenjaeger

E-bok

2012

718 kr

Nyhet

Exit Adventskalender - Julens magi (SE)

Exit

439 kr

Nyhet

Del 11

Medusa

Lars Kepler

Inbunden, 2026

269 kr

Signerad!

SIGNERAD - Ropet från rymden

Joanna André

Inbunden, 2026

179 kr

Ruth Kvarnström-Jones - SIGNERAD - Systrarna på Sophiahemmet, Inbunden

Signerad!

Del 3

SIGNERAD - Systrarna på Sophiahemmet

Ruth Kvarnström-Jones

Inbunden, 2026

249 kr

Nyhet

Jag såg hur vi var stjärnor

Laleh Pourkarim

Inbunden, 2026

269 kr

Signerad!

SIGNERAD - Hälsorevolutionen : nya insikter

Yourlife Books

Inbunden, 2026

259 kr

-12%

När allt faller

Måns Petter Zelmerlöw

Inbunden, 2026

229 kr259 kr

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

AvE. Börger,G. Hasenjaeger

Häftad, Engelska, 1984

Del i serien Lecture Notes in Computer Science

391 kr

Beställningsvara. Skickas inom 10-15 vardagar. Fri frakt över 249 kr.

Produktinformation

Utgivningsdatum:1984-05-01
Mått:155 x 235 x 26 mm
Vikt:709 g
Format:Häftad
Språk:Engelska
Serie:Lecture Notes in Computer Science
Antal sidor:460
Förlag:Springer-Verlag Berlin and Heidelberg GmbH & Co. KG
ISBN:9783540133315

Utforska kategorier

Systemvetenskap och AI inom Data och IT
Matematikens grunder inom Naturvetenskap och teknik
Matematik inom Naturvetenskap och teknik

Innehållsförteckning

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.