Skip to main content
SpringerLink
Log in

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

  • Conference proceedings
  • © 1984

Overview

Editors:
  1. E. Börger
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. G. Hasenjaeger
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. D. Rödding
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 171)

Included in the following conference series:

Conference proceedings info: LaM 1983.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
Softcover Book USD 49.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (29 papers)

  1. Front Matter

    Download chapter PDF

  2. P-mitotic sets

    • Klaus Ambos-Spies
    Pages 1-23

  3. Equivalence relations, invariants, and normal forms, II

    • Andreas Blass, Yuri Gurevich
    Pages 24-42

  4. Recurrence relations for the number of labeled structures on a finite set

    • Chr. Blatter, E. Specker
    Pages 43-61

  5. Recursively enumerable extensions of R1 by finite functions

    • W. Menzel, V. Sperschneider
    Pages 62-76

  6. On the complement of one complexity class in another

    • Diana Schmidt
    Pages 77-87

  7. The length-problem

    • V. Sperschneider
    Pages 88-102

  8. On r.e. inseparability of CPO index sets

    • Dieter Spreen
    Pages 103-117

  9. Arithmetical degrees of index sets for complexity classes

    • Kenneth W. Regan
    Pages 118-130

  10. Rudimentary relations and Turing machines with linear alternation

    • Hugo Volger
    Pages 131-136

  11. A critical-pair/completion algorithm for finitely generated ideals in rings

    • B. Buchberger
    Pages 137-161

  12. Extensible algorithms

    • Hans-Georg Carstens, Peter Päppinghaus
    Pages 162-182

  13. Some reordering properties for inequality proof trees

    • Michael M. Richter
    Pages 183-197

  14. Modular decomposition of automata

    • Anne Brüggemann, Lutz Priese, Dieter Rödding, Rüdiger Schätz
    Pages 198-236

  15. Modular machines, undecidability and incompleteness

    • Daniel E. Cohen
    Pages 237-247

  16. Universal Turing machines (UTM) and Jones-Matiyasevich-masking

    • G. Hasenjaeger
    Pages 248-253

  17. Complexity of loop-problems in normed networks

    • H. Kleine Büning
    Pages 254-269

  18. On the solvability of the extended ∀∃ ∧ ∃∀⋆ — Ackermann class with identity

    • Stål Aanderaa
    Pages 270-284

  19. Reductions for the satisfiability with a simple interpretation of the predicate variable

    • Michael Deutsch
    Pages 285-311

  20. The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems)

    • Martin Fürer
    Pages 312-319
Back to top

Other volumes

  1. Logic and Machines: Decision Problems and Complexity

Keywords

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation