Satisfiability of the smallest binary program

DOI10.1016/0020-0190(93)90210-ZMaRDI QIDQ2366070zbMATH OpenFDO

Authors Philipp Hanschke, Jörg Würtz

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

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

Recommendations

• Smallest horn clause programs
• scientific article; zbMATH DE number 512814
• scientific article; zbMATH DE number 1555187

Cites work

• scientific article; zbMATH DE number 3872640 (Why is no real title available?)
• scientific article; zbMATH DE number 3978424 (Why is no real title available?)
• scientific article; zbMATH DE number 1256672 (Why is no real title available?)
• scientific article; zbMATH DE number 1348461 (Why is no real title available?)
• scientific article; zbMATH DE number 512814 (Why is no real title available?)
• scientific article; zbMATH DE number 3366917 (Why is no real title available?)
• A variant of a recursively unsolvable problem
• Controlling recursive inference
• Flow diagrams, turing machines and languages with only two formation rules
• Implication of clauses is undecidable
• Krom formulas with one dyadic predicate letter
• Weighted graphs: A tool for studying the halting problem and time complexity in term rewriting systems and logic programming

Cited in

(8)

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

This page was built for publication: Satisfiability of the smallest binary program

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