?
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:
Speranski S. O., Grefenshtein A., Izvestiya. Mathematics 2026 Vol. 90 No. 4 P. 105–126
The article is concerned with Halpern's first-order logics of probability, which we denote by L_1 and L_2 – the first of these deals with probability distributions on the domain, while the second employs distributions on external sets of possible worlds. The proofs of [Abadi & Halpern 1994] of the complexity lower bound results for L_1 and L_2 ...
Added: August 12, 2026
Speranski S. O., Logic Journal of the IGPL 2025 Vol. 33 No. 3 Article jzae114
We shall be concerned with two natural expansions of the quantifier-free ‘polynomial’ probability logic of [Fagin et al. 1990]. One of these, denoted by QPL-e, is obtained by adding quantifiers over arbitrary events, and the other, denoted by p-QPL-e, uses quantifiers over propositional formulas — or equivalently, over events expressible by such formulas. The earlier proofs ...
Added: December 26, 2025
Rybakov M., / Series math "arxiv.org". 2025. No. 2505.00531.
The paper presents a solution to the long-standing question about the decidability of the two-variable fragment of the superintuitionistic predicate logic QLC defined by the class of linear Kripke frames, which is also the superintuitionistic’ fragment of the modal predicate logic QS4:3, under the Gödel translation. We prove that the fragment is undecidable. The result remains true ...
Added: May 21, 2025
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
Rybakov M., Серова Д. А., / 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
Predicate counterparts of modal logics of provability: High undecidability and Kripke incompleteness
Rybakov M., Logic Journal of the IGPL 2024 Vol. 32 No. 3 P. 465–492
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
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
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
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
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
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