?
О задаче верификации для одного класса автоматов реального времени
С. 257–260.
Zakharov V., Винарский Е. М.
Language:
Russian
Keywords: разрешимостьmodel checkingверификация моделей программтемпоральная логикаdecidabilityreal time automataконечный автомат реального времениtemporal logic
Publication based on the results of:
In book
М.: Изд-во механико-математического факультета МГУ, 2019.
Rybakov M., Annals of Pure and Applied Logic 2026 Vol. 177 No. 10 Article 103811
The paper presents a solution to the 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 for the ...
Added: July 11, 2026
Shehtman V. B., Gagarin A., , in: Graph Games and Logic Design. Recent Developments and Further Directions. (TREN, volume 66)Vol. 66.: Springer, 2026. Ch. 17 P. 419–450.
The chapter contains an overview of results on products of propositional modal logics and related constructions: semiproducts, Segerberg squares, and others. We focus mainly on axiomatizations, finite model property, and decidability; we also sketch connections with classical and modal predicate logics. In some cases we give ideas of proofs, especially of those using games. ...
Added: June 30, 2026
Springer, 2026.
This book presents established and new research on the close connections between graph games and systems of logic, particularly existing and newly designed modal logics. The volume utilizes two graph games – the sabotage game and the hide-and-seek game – to demonstrate the natural interplay between designing new graph games and exploring new kinds of ...
Added: June 30, 2026
Speranski S. O., Вестник Новосибирского государственного университета. Серия: Математика, механика, информатика 2011 Т. 11 № 4 С. 78–93
В настоящей статье изучаются вычислительные аспекты формального требования максимальной специфичности, накладываемого на правила в языке пропозициональной классической логики, когда над этим языком задана вычислимая рационально-значная вероятностная мера. Доказана неразрешимость ряда общих проблем по обнаружению максимально специфичных правил и вероятностных мер, для которых совокупность всех специфичных правил вычислима; установлена разрешимость множества максимально специфичных правил при неких ...
Added: December 27, 2025
Speranski S. O., Алгебра и логика 2011 Т. 50 № 4 С. 533–546
Язык для рассуждений о вероятности обобщается за счёт добавления в него кванторов по пропозициональным формулам. Далее рассматриваются соответствующие вопросы разрешимости. В частности, представленные результаты демонстрируют неразрешимость проблемы общезначимости для довольно слабого фрагмента нового языка. С другой стороны, устанавливается разрешимость ограниченной проблемы общезначимости для АЕ-предложений. ...
Added: December 27, 2025
Speranski S. O., Journal of Logic and Computation 2013 Vol. 23 No. 5 P. 1035–1055
In the present article, the quantifiers over propositions are first introduced into the language for reasoning about probability, then the complexity issues for validity problems dealing with the corresponding hierarchy of probabilistic sentences are investigated. We prove, among other things, the $\Pi^1_1$-completeness for the general validity and also indicate the least level in the hierarchy ...
Added: December 27, 2025
Speranski S. O., Archive for Mathematical Logic 2013 Vol. 52 No. 5–6 P. 507–516
We carry out a study of definability issues in the standard models of Presburger and Skolem arithmetics (henceforth referred to simply as Presburger and Skolem arithmetics, for short, because we only deal with these models, not the theories, thus there is no risk of confusion) supplied with free unary predicates — which are strongly related to definability in ...
Added: December 27, 2025
Speranski S. O., Izvestiya. Mathematics 2025 Vol. 89 No. 3 P. 609–627
Let QPL-e expand the quantifier-free ‘polynomial’ probability logic of [Fagin et al. 1990] by adding quantifiers over arbitrary events; it can be viewed as a one-sorted elementary language for reasoning about probability spaces. We prove that the $\Sigma_2$-fragment of the QPL-e-theory of finite spaces is hereditarily undecidable. By earlier observations, this implies that $\Pi_2$ is the ...
Added: December 26, 2025
Speranski S. O., Logic Journal of the IGPL 2025 Vol. 33 No. 2 Article jzae042
This paper is concerned with a two-sorted probabilistic language, denoted by QPL, which contains quantifiers over events and over reals, and can be viewed as an elementary language for reasoning about probability spaces. The fragment of QPL containing only quantifiers over reals is a variant of the well-known ‘polynomial’ language from [Fagin et al. 1990, Section 6]. ...
Added: December 26, 2025
Rybakov M., Shkatov D., Studia Logica 2025 Vol. 113 P. 1–48
In the early 1960s, to prove undecidability of monadic fragments of sublogics of the predicate modal logic QS5 that include the classical predicate logic QCl, Saul Kripke showed how a classical atomic formula with a binary predicate letter can be simulated by a monadic modal formula. We consider adaptations of Kripke's simulation, which we call the Kripke trick, to various modal ...
Added: December 2, 2023
Dudakov S., Авхимович Н. В., Вестник Тверского государственного университета. Серия: Прикладная математика 2023 № 1 С. 24–35
В работе рассматриваются алгебраические системы, где в качестве носителя выступают конечные подмножества некоторой безатомной булевой алгебры. Для полученной системы мы вводим новое отношение для конечных подмножеств: считаем, что одно подмножество состоит в отношении с другим подмножеством в том и только том случае, когда все элементы одного подмножества меньше всех элементов другого. Мы демонстрируем, что теория ...
Added: November 12, 2023
Rybakov M., Shkatov D., Journal of Logic and Computation 2025 Vol. 35 No. 2 Article exad078
We show that the monadic modal logic of a single Kripke frame with finitely many possible worlds, but possibly infinite domains, is decidable. This holds true even for monadic multimodal logics with equality, both if equality interpreted as identity and if equality interpreted as congruence. ...
Added: November 3, 2023
Агаджанян И. А., Rybakov M., Шкатов Д. П., / Series arXiv "math". 2023.
The paper investigates algorithmic complexity of monadic multimodal predicate logics with equality over finite Kripke frames or classes of finite Kripke frames. Precise complexity bounds for monadic logics of classes of Kripke frames with finitely many possible worlds are obtained. ...
Added: July 7, 2023
Semenov A., Сопрунов С. Ф., Чебышевский сборник 2021 Т. 22 № 1(77) С. 304–327
The article presents results and open problems related to definability spaces (reducts) and sources of this field since the XIX century. Finiteness conditions and constraints are investigated, including the depth of quantifier alternation and the number of arguments. Results related to the description of lattices of definability spaces for numerical and other natural structures are ...
Added: March 11, 2023
Lomazova I. A., Vladimir A. Bashkin, Jančar P., Fundamenta Informaticae 2022 Vol. 186 No. 1-4 P. 175–194
Petri nets are a popular formalism for modeling and analyzing distributed systems. Tokens in Petri net models can represent the control flow state or resources produced/consumed by transition firings. We define a resource as a part (a submultiset) of Petri net markings and call two resources equivalent when replacing one of them with another in ...
Added: September 4, 2022
Popova E., Логико-философские штудии 2022 Vol. 20 No. 1 P. 1–7
There are two approaches to merging temporal and epistemic models. The first one consists in starting with a temporal model and enriching it with epistemic dimension (as temporal epistemic logic), while the second one is supposed to start with an epistemic model introducing temporal dimension (dynamic epistemic logic, epistemic temporal logic). The proposed evolutionary epistemic ...
Added: August 1, 2022
Gnatenko A., Zakharov V., Automatic Control and Computer Sciences 2021 Vol. 55 No. 7 P. 776–785
Sequential reactive systems include programs and devices that work with two streams of
data and convert input streams of data into output streams. Such information processing systems
include controllers, device drivers, computer interpreters. The results of operation of such computing
systems are infinite sequences of pairs of events of the request-response type, and, therefore, finite
transducers are most often ...
Added: January 17, 2022
Vinarskii E., Zakharov V., Automatic Control and Computer Sciences 2021 Vol. 55 No. 7 P. 751–762
Sequential reactive systems include hardware devices and software programs which operate
in continuous interaction with the external environment, from which they receive streams of input signals
(data, commands) and in response to them form streams of output signals. Systems of this type
include controllers, network switches, program interpreters, system drivers. The behavior of some
reactive systems is determined not ...
Added: January 17, 2022
Gnatenko A., Zakharov V., Моделирование и анализ информационных систем 2021 Т. 28 № 4 С. 356–371
Sequential reactive systems are computer programs or hardware devices which process the flows of input data or control signals and output the streams of instructions or responses. When designing such systems one needs formal specification languages capable of expressing the relationships between the input and output flows. Previously, we introduced a family of such specification ...
Added: January 17, 2022