Complexity and expressive power of second‐order extended Horn logic
Shiguang Feng, Xishun Zhao · Mathematical logic quarterly · 2013
Abstract We introduce SO‐HORNrwhich is a revised version of SO‐HORN and show that SO‐HORNrcaptures\documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathsf {P}$\end{document} on ordered finite structures. We also introduce second‐order extended Horn logic SO‐EHORN and a superclass SO‐EHORNrof it. We show that both of them capture\documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathsf {co}\mbox{-}\mathsf {NP}$\end{document} on ordered finite structures by proving that SO‐EHORN and SO‐EHORNrhave the same expressive power when only consider ordered structures.