Satisfiability of the smallest binary program

DOI10.1016/0020-0190(93)90210-ZzbMath0771.68035MaRDI QIDQ2366070

Jörg Würtz, Philipp Hanschke

Publication date: 29 June 1993

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

theory of computationsmallest binary program

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Logic programming (68N17)

Related Items

More problems in rewriting, Unification of infinite sets of terms schematized by primal grammars, Monadic logic programs and functional complexity, On the complexity of single-rule datalog queries., Detecting non-provable goals, Primal grammars and unification modulo a binary clause, Thue trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Weighted graphs: A tool for studying the halting problem and time complexity in term rewriting systems and logic programming
• Controlling recursive inference
• Implication of clauses is undecidable
• Krom formulas with one dyadic predicate letter
• Flow diagrams, turing machines and languages with only two formation rules
• A variant of a recursively unsolvable problem