Diem-Grade Logischer Entscheidungsprobleme

DOI10.1007/BF02276798zbMath0362.02025MaRDI QIDQ4135479

Egon Börger, K. Heidler

Publication date: 1976

Published in: Archiv für Mathematische Logik und Grundlagenforschung (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/137912

Mathematics Subject Classification ID

03D05: Automata and formal grammars in connection with logical questions

03B25: Decidability of theories and sets of sentences

03D30: Other degrees and reducibilities in computability and recursion theory

03Dxx: Computability and recursion theory

Related Items

The reachability problem for Petri nets and decision problems for Skolem arithmetic, Das Entscheidungsproblem der Klasse von Formeln, die höchstens zwei Primformeln enthalten

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Combinatorial systems. I: Cylindrical problems
• Turing-machines and the Entscheidungsproblem
• Many-one degrees associated with problems of tag
• Degrees of unsolvability associated with Markov algorithms
• Beitrag zur Reduktion des Entscheidungsproblems auf Klassen von Hornformeln mit kurzen Alternationen
• Linear orderings under one-one reducibility
• On a Problem of J.H.C. Whitehead and a Problem of Alonzo Church.
• The undecidability of the Turing machine immortality problem
• The many-one equivalence of some general combinatorial decision problems
• Strong Computability and Variants of the Uniform Halting Problem
• Classes of Recursive Functions and Their Index Sets
• Decision problems for tag systems
• The Representation of Many-One Degrees by Decision Problems of Turing Machines
• The Representation of Many-One Degrees by the Word Problem for Thue Systems
• Combinatorial systems with axiom