scientific article; zbMATH DE number 3876591

MaRDI QIDQ3341896zbMATH OpenFDO

Authors Martin Fürer

Publication date 1984

zbMATH Keywords

computational complexitydecision problem of predicate calculusnondeterministic exponential time completetilingunconstrained limited domino problem

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Combinatorial aspects of tessellation and tiling problems (05B45) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 4061218
• On the computational complexity of the domination game
• The undecidability of the domino problem
• On the computational complexity of upper total domination
• On the Algorithmic Complexity of Total Domination
• A decidability result for the dominating set problem
• On the complexity landscape of the domination chain
• Dominoes and the complexity of subclasses of logical theories
• On the domino-parity inequalities for the STSP

Cited in

(10)

• Dominoes and the complexity of subclasses of logical theories
• On logics with two variables
• First-order logic with two variables and unary temporal logic
• Recurring Dominoes: Making the Highly Undecidable Highly Understandable
• scientific article; zbMATH DE number 4025423 (Why is no real title available?)
• scientific article; zbMATH DE number 4061218 (Why is no real title available?)
• Two-variable logics with some betweenness relations: expressiveness, satisfiability and membership
• Infinite games with finite knowledge gaps
• Explanations for query answers under existential rules
• The decision problems about the periodic solutions of the domino problems

This page was built for publication:

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