Showing cs.LOShow all
2 papers · 1 filter
cs.LO2021
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…
cs.LO2017
Kripke Completeness of Strictly Positive Modal Logics over Meet-semilattices with Operators
Stanislav Kikot, Agi Kurucz, Yoshihito Tanaka +2
Our concern is the completeness problem for spi-logics, that is, sets of implications between strictly positive formulas built from propositional variables, conjunction and modal d…