Jump to content

Monadic second-order logic

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by David Eppstein (talk | contribs) at 03:53, 17 September 2016 (why). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In mathematical logic, monadic second order logic[1] (MSO) is the fragment of second-order logic where the second-order quantification is limited to quantification over sets. It is particularly important in the logic of graphs, because of Courcelle's theorem, which provides algorithms for evaluating monadic second-order formulas over certain types of graphs.

References

  1. ^ Courcelle, Bruno; Engelfriet, Joost (2012-01-01). Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach. Cambridge University Press. ISBN 978-0521898331. Retrieved 2016-09-15.
Stub icon

This logic-related article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Monadic_second-order_logic&oldid=739806865"