The many-one equivalence of some general combinatorial decision problems

DOI10.1090/S0002-9904-1971-12742-8zbMath0216.00903OpenAlexW2092354571MaRDI QIDQ5619078

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

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

Related Items

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, Many-one degrees associated with semi-Thue systems

Cites Work

• Unnamed Item
• Unnamed Item
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Word problems and recursively enumerable degrees at unsolvability. A first paper on Thue systems
• Recursive Unsolvability of a problem of Thue
• Machine Configuration and Word Problems of Given Degree of Unsolvability
• Monogenic Post Normal Systems of Arbitrary Degree
• The post correspondence problem
• The equivalence of some general combinatorial decision problems
• Degrees of Unsolvability in Formal Grammars
• A Remark on Post Normal Systems
• On deterministic normal systems
• Formal Reductions of the General Combinatorial Decision Problem
• A variant of a recursively unsolvable problem