A Logic that Captures \betaP on Ordered Structures
From MaRDI portal
Publication:6330718
arXiv1912.03841MaRDI QIDQ6330718FDOQ6330718
Authors: Xishun Zhao 
Publication date: 8 December 2019
Abstract: 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 logic captures the limited nondeterminism class . In order to study its expressive power, we also design a new version of Ehrenfeucht-Fra"iss'e game for this logic and show that our capturing result will not hold on the general case, i.e. on all the finite structures.
This page was built for publication: A Logic that Captures $\beta$P on Ordered Structures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6330718)
