Algorithmic properties of first-order modal logics of the natural number line in restricted languages

M. Rybakov; Shkatov D.

Публикации

?

Algorithmic properties of first-order modal logics of the natural number line in restricted languages

P. 523–539.

Рыбаков М. Н., Shkatov D.

Язык: английский

Полный текст

Ключевые слова: Undecidability First-order modal logic recursive enumerability Satisfiability problem predicate modal logic restricted languages validity problem

В книге

Advances in Modal Logic

Vol. 13. , College Publications, 2020.

Complexity of finite-variable fragments of propositional temporal and modal logics of computation

Рыбаков М. Н., Shkatov D., Theoretical Computer Science 2022 Vol. 925 P. 45–60

Добавлено: 12 мая 2022 г.

Algorithmic properties of first-order modal logics of linear Kripke frames in restricted languages

Рыбаков М. Н., Shkatov D., Journal of Logic and Computation 2021 Vol. 31 No. 5 P. 1266–1288

Изучается алгоритмическая выразительность предикатных логик шкалы Крипке, задаваемой множеством натуральных чисел с отношениями порядка. ...

Добавлено: 23 января 2022 г.

О верификации моделей и проверке выполнимости формул одного параметрического расширения темпоральной логики линейного времени

Гнатенко А. Р., Захаров В. А., Моделирование и анализ информационных систем 2021 Т. 28 № 4 С. 356–371

К последовательным реагирующим системам относятся компьютерные программы и вычислительные устройства, которые обрабатывают потоки входных данных или сигналов управления и генерируют на выходе последовательности команд или результатов вычислений. Для проектирования таких систем полезно иметь формальные языки спецификаций, способные выражать отношения между входными и выходными потоками данных. В предшествующих работах нами было предложено семейство таких языков спецификаций, ...

Добавлено: 17 января 2022 г.

Undecidability of the logic of partial quasiary predicates

Рыбаков М. Н., Shkatov D., Logic Journal of the IGPL 2022 Vol. 30 No. 3 P. 519–533

Добавлено: 29 мая 2021 г.

The multiplicative-additive Lambek calculus with subexponential and bracket modalities

Канович М. И., Кузнецов С. Л., Щедров А., Journal of Logic, Language and Information 2021 Vol. 30 No. 1 P. 31–88

Добавлено: 25 ноября 2020 г.

Complexity of finite-variable fragments of products with K

Рыбаков М. Н., Shkatov D., Journal of Logic and Computation 2021 Vol. 31 No. 2 P. 426–443

Добавлено: 24 сентября 2020 г.

Algorithmic properties of first-order modal logics of finite Kripke frames in restricted languages

Рыбаков М. Н., Shkatov D., Journal of Logic and Computation 2020 Vol. 30 No. 7 P. 1305–1329

Добавлено: 27 августа 2020 г.

Computational properties of the logic of partial quasiary predicates

Shkatov D., Рыбаков М. Н., , in: Conference of the South African Institute of Computer Scientists and Information Technologists 2020 (SAICSIT '20).: ACM, 2020. P. 58–65.

Доказаны аналоги теоремы Чёрча и теоремы Трахтенброта для логики квазиарных предикатов. ...

Добавлено: 20 июля 2020 г.

Solving difference equations in sequences: Universality and Undecidability

Погудин Г. А., Scanlon T., Wibmer M., / Series "Working papers by Cornell University". 2019.

Добавлено: 1 ноября 2019 г.

Recursive enumerability and elementary frame definability in predicate modal logic

Рыбаков М. Н., Shkatov D., Journal of Logic and Computation 2020 Vol. 30 No. 2 P. 549–560

Добавлено: 25 октября 2019 г.

Undecidability of a newly proposed calculus for CatLog3

Канович М. И., Кузнецов С. Л., Щедров А., , in: Formal Grammar 2019, 24th International ConferenceVol. 11668.: Berlin: Springer, 2019. P. 67–83.

Добавлено: 15 октября 2019 г.

Complexity and expressivity of Branching- and Alternating-time temporal logics with finitely many variables

Рыбаков М. Н., Shkatov D., , in: Theoretical Aspects of Computing – ICTAC 2018Vol. 11187.: Springer, 2018. P. 396–414.

Добавлено: 8 октября 2019 г.

Trakhtenbrot theorem for classical languages with three individual variables

Рыбаков М. Н., Shkatov D., , in: Proceedings of the South African Institute of Computer Scientists and Information Technologists 2019.: NY: ACM, 2019. Ch. 19 P. 1–7.

Добавлено: 6 октября 2019 г.

On complexity of propositional linear-time temporal logic with finitely many variables

Рыбаков М. Н., Shkatov D., , in: Proceedings of the Annual Conference of the South African Institute of Computer Scientists and Information Technologists.: NY: ACM, 2018. P. 313–316.

Добавлено: 6 октября 2019 г.