### ?

## Tiling problems and complexity of logics

P. 68-70.

Rybakov M., Serova D.

We apply domino problems to give short proofs for some known theorems for the classical predicate logic and some modal logics.

Publication based on the results of:

Sergey Dudakov, Karlov B., Theory of Computing Systems 2021 Vol. 65 No. 3 P. 462-478

This paper is dedicated to studying decidability properties of theories of regular languages with classical operations: union, concatenation, and the Kleene star. The theory with union only is a theory of some Boolean algebra, so it is decidable. We prove that the theory of regular languages with the Kleene star only is decidable. If we ...

Added: November 12, 2023

Skopenkov M., Малиновская О. А., Дориченко С. А., Квант 2015 № 2 С. 6-11

In the present popular science paper we determine when a square can be dissected into rectangles similar to a given rectangle. The approach to the question is based on a physical interpretation using electrical networks. Only secondary school background is assumed in the paper. ...

Added: October 16, 2015

Predicate counterparts of modal logics of provability: High undecidability and Kripke incompleteness

Rybakov M., Logic Journal of the IGPL 2024

In this paper, the predicate counterparts, defined both axiomatically and semantically by means of Kripke frames, of the modal propositional logics GL, Grz, wGrz and their extensions are considered. It is proved that the set of semantical consequences on Kripke frames of every logic between QwGrz and QGL.3 or between QwGrz and QGrz.3 is Pi-1-1-hard even in languages with ...

Added: July 7, 2023

Zakharov V., Новикова Т. А., Труды Института системного программирования РАН 2014 Т. 26 № 2 С. 245-268

It is generally accepted that to unify a pair of substitutions θ_1 and θ_2 means to find out a pair of substitutions η' and η'' such that the compositions θ_1 η' and θ_2 η'' are the same. Actually, unification is the problem of solving linear equations of the form θ_1 X=θ_2 Y in the semigroup ...

Added: September 30, 2015

The symmetric Post Correspondence Problem, and errata for the freeness problem for matrix semigroups

Birget J., Talambutsa A., International Journal of Algebra and Computation 2022 Vol. 32 No. 6 P. 1261-1274

In this paper, we define the symmetric Post Correspondence Problem (PCP) and prove that it is undecidable. As an application, we show that the original proof of undecidability of the freeness problem for 3×3 integer matrix semigroups works for the symmetric PCP, but not for the PCP in general. ...

Added: December 9, 2022

Lakshmanan K., Mahendran A., Kamala K. et al., Nano Communication Networks 2011 Vol. 2 P. 106-118

Gene insertion and deletion are the operations that occur commonly in DNA processing
and RNA editing. Based on these operations, a computing model has been formulated
in formal language theory known as insertion–deletion systems. In this paper we study
about ambiguity issues of these systems. First, we define six levels of ambiguity for
insertion–deletion systems that are based on ...

Added: November 24, 2021

Rybakov M., Серова Д. А., / Cornell University. Series arXiv "math". 2023.

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. ...

Added: July 7, 2023

Zakharov V., Новикова Т. А., , in : Proceedings of the 28th International Workshop on Unification, UNIF 2014. Technical report no. 14-06 in RISC Report Series. : Linz : Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz, 2014. P. 55-61.

It is generally accepted that to unify a pair of substitutions 1 and 2 means to find out
a pair of substitutions 0 and 00 such that the compositions 10 and 200 are the same.
Actually, unification is the problem of solving linear equations of the form 1X = 2Y in
the semigroup of substitutions. But some other ...

Added: October 13, 2015

Kuppusamy L., Mahendran A., Krithivasan K., International Journal of Foundations of Computer Science 2011 Vol. 22 No. 7 P. 1747-1758

Gene insertion and deletion are the operations that occur commonly in DNA processing and RNA editing. Based on these evolutionary transformations, a computing model has been formulated in formal language theory known as insertion-deletion systems. In this paper, we study about the ambiguity issues of insertion systems. First, we define six levels of ambiguity for insertion systems ...

Added: November 24, 2021