Complexity and expressive power of second‐order extended Horn logic

Mathematical Logic Quarterly 59 (1-2):4-11 (2013)
  Copy   BIBTEX

Abstract

We introduce SO-HORNr which is a revised version of SO-HORN and show that SO-HORNr captures equation image on ordered finite structures. We also introduce second-order extended Horn logic SO-EHORN and a superclass SO-EHORNr of it. We show that both of them capture equation image on ordered finite structures by proving that SO-EHORN and SO-EHORNr have the same expressive power when only consider ordered structures

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Analytics

Added to PP
2013-11-03

Downloads
16 (#774,858)

6 months
4 (#320,252)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations