Combinatorial systems defined over one- and two-letter alphabets

DOI10.1007/BF02280809zbMath0336.02035OpenAlexW2013317804MaRDI QIDQ4103085

W. E. Singletary, Charles E. Hughes

Publication date: 1975

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

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

Mathematics Subject Classification ID

Word problems, etc. in computability and recursion theory (03D40) Other degrees and reducibilities in computability and recursion theory (03D30) Turing machines and related notions (03D10) Thue and Post systems, etc. (03D03)

Related Items (1)

Unsolvable algorithmic problems for semigroups, groups and rings

Cites Work

• Unnamed Item
• Word problems and recursively enumerable degrees at unsolvability. A first paper on Thue systems
• The general decision problem for Markov algorithms with axiom
• Many-one degrees associated with problems of tag
• TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
• Degrees of unsolvability associated with Markov algorithms
• Machine Configuration and Word Problems of Given Degree of Unsolvability
• The post correspondence problem
• The equivalence of some general combinatorial decision problems
• Canonical systems which produce periodic sets
• The many-one equivalence of some general combinatorial decision problems
• The Representation of Many-One Degrees by the Word Problem for Thue Systems
• Formal Reductions of the General Combinatorial Decision Problem
• Combinatorial systems with axiom

This page was built for publication: Combinatorial systems defined over one- and two-letter alphabets