The many-one equivalence of some general combinatorial decision problems

DOI10.1090/S0002-9904-1971-12742-8MaRDI QIDQ5619078zbMATH OpenOpenAlexFDO

Authors Charles E. Hughes, W. E. Singletary, Ross A. Overbeek

Publication date 1971

Published in Bulletin of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1090/s0002-9904-1971-12742-8

Mathematics Subject Classification ID

Thue and Post systems, etc. (03D03) Turing machines and related notions (03D10)

Cites work

• A Remark on Post Normal Systems
• A variant of a recursively unsolvable problem
• Degrees of Unsolvability in Formal Grammars
• Formal Reductions of the General Combinatorial Decision Problem
• scientific article; zbMATH DE number 3131080 (Why is no real title available?)
• scientific article; zbMATH DE number 3285233 (Why is no real title available?)
• Machine Configuration and Word Problems of Given Degree of Unsolvability
• Monogenic Post Normal Systems of Arbitrary Degree
• On deterministic normal systems
• Recursive unsolvability of a problem of Thue
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• The equivalence of some general combinatorial decision problems
• The post correspondence problem
• Word problems and recursively enumerable degrees at unsolvability. A first paper on Thue systems

Cited in

(5)

• Many-one degrees associated with semi-Thue systems
• Many-one degrees associated with problems of tag
• Degrees of unsolvability associated with Markov algorithms
• Combinatorial systems defined over one- and two-letter alphabets
• Diem-Grade Logischer Entscheidungsprobleme

This page was built for publication: The many-one equivalence of some general combinatorial decision problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5619078)