The decision problem of modal product logics with a diagonal, and faulty counter machines (Q295920)

This paper explores the effects of supplementing the product of two modal logics with a diagonal (identity) relation. In particular, the validity problem for the supplemented product (called ``\(\delta\)-product'') may be harder to compute than that of the ordinary product. For example, the validity problems for \({\mathbf K}\times{\mathbf K}\) and \({\mathbf K4}\times{\mathbf K}\) are decidable, while the problems for the \(\delta\)-versions are not. On the other hand, the \(\delta\)-product of \({\mathbf S5}\) with itself is not only decidable, but of the same computational complexity as \({\mathbf S5}\times{\mathbf S5}\). The main technical tool used is that of counter machines that are subject to certain errors.