Zobrazeno 1 - 10
of 16
pro vyhledávání: '"Mikhail N. Rybakov"'
Autor:
Dmitry Shkatov, Mikhail N. Rybakov
Publikováno v:
Logic Journal of the IGPL. 30:519-533
We obtain an effective embedding of the classical predicate logic into the logic of partial quasiary predicates. The embedding has the property that an image of a non-theorem of the classical logic is refutable in a model of the logic of partial quas
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d19a8e68f81417fa058672ffb1265486
https://doi.org/10.1093/jigpal/jzab018
https://doi.org/10.1093/jigpal/jzab018
Autor:
Mikhail N. Rybakov, Dmitry Shkatov
Publikováno v:
Journal of Logic and Computation. 31:1266-1288
We study the algorithmic properties of first-order monomodal logics of frames $\langle {\textrm{I}\!\textrm{N}}, \leqslant \rangle $, $\langle {\textrm{I}\!\textrm{N}}, < \rangle $, $\langle \mathbb {Q}, \leqslant \rangle $, $\langle \mathbb {Q}, < \
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3fc67aa0662588b0af2878b873bf4756
https://doi.org/10.1093/logcom/exab030
https://doi.org/10.1093/logcom/exab030
Autor:
Mikhail N. Rybakov, Dmitry Shkatov
Publikováno v:
Journal of Logic and Computation. 31:494-522
We consider the effect of restricting the number of individual variables, as well as the number and arity of predicate letters, in languages of first-order predicate superintuitionistic logics of finite Kripke frames on the logics’ algorithmic prop
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b2e079228d8cc939bfa627cd14683771
https://doi.org/10.1093/logcom/exaa091
https://doi.org/10.1093/logcom/exaa091
Autor:
Dmitry Shkatov, Mikhail N. Rybakov
Publikováno v:
Journal of Logic and Computation. 31:426-443
We show that products and expanding relativized products of propositional modal logics where one component is the minimal monomodal logic K are polynomial-time reducible to their single-variable fragments. Therefore, the known lower-bound complexity
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::8ef76dced8cc209e9b3444cead42ec01
https://doi.org/10.1093/logcom/exaa060
https://doi.org/10.1093/logcom/exaa060
Autor:
Dmitry Shkatov, Mikhail N. Rybakov
Publikováno v:
SAICSIT
We show that the logic of partial quasiary predicates is undecidable over arbitrary structures and not recursively enumerable over finite structures. The results are obtained by reduction from the classical predicate logic.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::63da7615de66ed4f1620927612009b19
https://doi.org/10.1145/3410886.3410889
https://doi.org/10.1145/3410886.3410889
Autor:
L A Chagrova, Mikhail N. Rybakov
Publikováno v:
Международный журнал "Программные продукты и системы". 33:591-597
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f885fec2e954eeccdcd886360983e308
https://doi.org/10.15827/0236-235x.123.591-597
https://doi.org/10.15827/0236-235x.123.591-597
Autor:
Mikhail N. Rybakov
Publikováno v:
Herald of Tver State University. Series: Applied Mathematics. :81-94
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::dd44890761188e0e0bcac69cc7465783
https://doi.org/10.26456/vtpmk511
https://doi.org/10.26456/vtpmk511
Autor:
Dmitry Shkatov, Mikhail N. Rybakov
Publikováno v:
SAICSIT
We present a simple proof of Thrakhtenbrot's theorem for the classical predicate logic in the language with only three individual variables. Both forms of Thrakhtenbrot's theorem are established: we prove that the classical predicate logic QCL over f
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::276b50f2b0265eaf4cd5a0441435af67
https://doi.org/10.1145/3351108.3351128
https://doi.org/10.1145/3351108.3351128
Autor:
Dmitry Shkatov, Mikhail N. Rybakov
We investigate the relationship between recursive enumerability and elementary frame definability in first-order predicate modal logic. On one hand, it is well known that every first-order predicate modal logic complete with respect to an elementary
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c6b697b01b4ae9bc2e9f05c2c1974003
Autor:
Mikhail N. Rybakov, Dmitry Shkatov
We investigate the complexity of satisfiability for finite-variable fragments of propositional dynamic logics. We consider three formalisms belonging to three representative complexity classes, broadly understood,---regular PDL, which is EXPTIME-comp
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e0892065350b5896c81ae1ff90173333