4 papers
Unique Characterisability and Learnability of Temporal Instance Queries
Marie Fortin, Boris Konev, Vladislav Ryzhikov +3
We aim to determine which temporal instance queries can be uniquely characterised by a (polynomial-size) set of positive and negative temporal data examples. We start by considerin…
Deciding FO-definability of regular languages
Agi Kurucz, Vladislav Ryzhikov, Yury Savateev +1
We prove that, similarly to known PSpace-completeness of recognising FO(<)-definability of the language L(A) of a DFA A, deciding both FO(<,C)- and FO(<,MOD)-definability are PSpac…
Cut Elimination for Weak Modal Grzegorczyk Logic via Non-Well-Founded Proofs
Yury Savateev, Daniyar Shamkanov
We present a sequent calculus for the weak Grzegorczyk logic Go allowing non-well-founded proofs and obtain the cut-elimination theorem for it by constructing a continuous cut-elim…
Non-Well-Founded Proofs for the Grzegorczyk Modal Logic
Yury Savateev, Daniyar Shamkanov
We present a sequent calculus for the Grzegorczyk modal logic Grz allowing cyclic and other non-well-founded proofs and obtain the cut-elimination theorem for it by constructing a…