Content deleted Content added
m →SO(LFP): precise |
→SO(LFP): re |
||
Line 29:
Indeed, SO(LFP) is depicted as EXPTIME on the illustration on the cover of Immerman (1999). However, I couldn't find any discussion of it inside the book, and Ebbinghaus and Flum (Finite model theory, 2nd Ed. 1999, Theorem 8.5.1) say that SO(PFP), which should certainly be at least as expressive as SO(LFP), reduces to FO(PFP) (which equals PSPACE) on ordered structures. Any insight would be much appreciated! [[User:Felix QW|Felix QW]] ([[User talk:Felix QW|talk]]) 21:40, 15 February 2022 (UTC)
: You might consider emailing Immerman directly -- I emailed him a couple years ago about FO(REGULAR) and he was kind enough to explain the definition directly to me :) By the way, good work on the article so far, it's looking much improved. Lead probably needs a rewrite to be more accessible, I will try to take a pass sometime if I get some free time for it. [[User:Caleb Stanford|Caleb Stanford]] ([[User talk:Caleb Stanford|talk]]) 22:19, 15 February 2022 (UTC)
| |||