Tiling problems and complexity of logics (extended version)

2023/06/23 by Rybakov, M., Serova, D.
#FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.2306.13736

Abstract

We apply domino problems to give short proofs for some known theorems for the classical predicate logic and to obtain lower bounds for complexity of modal predicate logics defined by Noetherian orders as Kripke frames.

Related

• Modelling of logical systems by means of their fragments
• The complexity of generalized domino tilings
• Algorithmic complexity of monadic multimodal predicate logics with equality over finite Kripke frames
• Logics with the axiom of convergence: complexity with a small number of variables in the language (extended version)
• Proof Complexity and Feasible Interpolation