3 papers
cs.LO2026
Uniform Interpolation in Distributed Knowledge Modal Logics
Kexu Wang, Liangda Fang
Uniform interpolation is the property that, for any formula and set of atoms, there exists the strongest consequence omitting those atoms. It plays a central role in knowledge repr…
cs.LO2022
Capturing the polynomial hierarchy by second-order revised Krom logic
Kexu Wang, Shiguang Feng, Xishun Zhao
We study the expressive power and complexity of second-order revised Krom logic (SO-KROM). On ordered finite structures, we show that its existential fragment -KROM$^r…
cs.LO2019
A Logic that Captures P on Ordered Structures
Kexu Wang, Xishun Zhao
We extend the inflationary fixed-point logic, IFP, with a new kind of second-order quantifiers which have (poly-)logarithmic bounds. We prove that on ordered structures the new log…