Complexity and expressive power of second‐order extended Horn logic

We introduce SO‐HORN r which is a revised version of SO‐HORN and show that SO‐HORN r captures \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‐EHORN r of 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‐EHORN r have the same expressive power when only consider ordered structures.