Computation over algebraic structures and a classification of undecidable problems

DOI10.1017/S0960129516000116zbMath1423.03139MaRDI QIDQ4593236

Christine Gaßner

Publication date: 22 November 2017

Published in: Mathematical Structures in Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Cites Work

• Finite model theory and its applications.
• Descriptive set theory
• Complexity theory and the operational structure of algebraic programming systems
• A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
• Computing over the reals with addition and order
• On NP-completeness for linear machines
• On some decision problems in programming
• Computing over the reals with addition and order: Higher complexity classes
• An explicit solution to Post's problem over the reals
• Implicit complexity over an arbitrary structure: Quantifier alternations
• Some definitional suggestions for automata theory
• Strong Turing Degrees for Additive BSS RAM's
• Noncomputable functions in the Blum-Shub-Smale model
• Every $\Delta^0_2$ -Set Is Natural, Up to Turing Equivalence
• The Arithmetical Hierarchy Over the Reals
• Algorithmic Procedures
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Computability of String Functions Over Algebraic Structures Armin Hemmerling
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Abstract First Order Computability. I
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Computation over algebraic structures and a classification of undecidable problems