Most logics we have seen so far are not well suited for expressing many tractable graph properties, such as graph connectivity, reachability, and so on. The limited expressiveness of FO and counting logics is due to the fact that they lack mechanisms for expressing fixed point computations. Other logics we have seen, such as MSO, ∃SO, and ∀SO, can express intractable graph properties.
Weitere Kapitel dieses Buchs durch Wischen aufrufen
- Fixed Point Logics and Complexity Classes
Prof. Leonid Libkin
- Springer Berlin Heidelberg
ec4u, Neuer Inhalt/© ITandMEDIA