Content deleted Content added
→SO(LFP): new section |
m Maintain {{WPBS}} and vital articles: 2 WikiProject templates. Create {{WPBS}}. Keep majority rating "C" in {{WPBS}}. Remove 2 same ratings as {{WPBS}} in {{WikiProject Mathematics}}, {{WikiProject Computer science}}. Remove 1 deprecated parameter: field. Tag: |
||
| (4 intermediate revisions by 3 users not shown) | |||
Line 1:
{{WikiProject banner shell|class=C|
{{merged from|FO (complexity)|date=February 2022}}▼
{{WikiProject Mathematics|priority=Mid}}
{{merged from|SO (complexity)|date=February 2022}}▼
{{WikiProject Computer science|importance=low}}
{{merged from|HO (complexity)|date=February 2022}}▼
}}
== Modal logic ==
Line 28:
Analogously to first-order least-fixed point logic, second-order logic can be augmented by a least-fixed point operator that takes second-order variables as arguments. SO(LFP) is to SO what [[FO (complexity)#Least Fixed Point is P|FO(LFP)]] is to [[FO (complexity)|FO]]. The LFP operator can now also take second-order variable as argument. SO(LFP) is equal to [[EXPTIME]].
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)
: 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)
::Thank you very much for your suggestion, and your kind words! Any improvements to the lead (or elsewhere) would be highly appreciated {{ndash}} I just tried to rearrange, smooth out and verify what was there already, and I am sure one can do better at several places.
::In fact, I will hopefully be attending an algorithmic and finite model theory workshop in March, so I could also use this puzzle for some breaktime discussion :). [[User:Felix QW|Felix QW]] ([[User talk:Felix QW|talk]]) 22:53, 15 February 2022 (UTC)
| |||