Monadic second-order logic

In mathematical logic, monadic second order logic (MSO) is the fragment of second-order logic where the second-order quantification is limited to quantification over sets.[1] 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.

Existential monadic second-order logic (EMSO) is the fragment of MSO in which all quantifiers over sets must be existential quantifiers, outside of any other part of the formula. The first-order quantifiers are not restricted. By analogy to Fagin's theorem, according to which existential (non-monadic) second-order logic captures precisely the descriptive complexity of the complexity class NP, the class of problems that may be expressed in existential monadic second-order logic has been called monadic NP. The restriction to monadic logic makes it possible to prove separations in this logic that remain unproven for non-monadic second-order logic; for instance, testing the connectivity of graphs belongs to monadic co-NP (the complement of monadic NP) but not to monadic NP itself.[2][3]

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.
  2. ↑ Fagin, Ronald (1975), "Monadic generalized spectra", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 21: 89–96, MR 0371623.
  3. ↑ Fagin, R.; Stockmeyer, L.; Vardi, M. Y. (1993), "On monadic NP vs. monadic co-NP", Proceedings of the Eighth Annual Structure in Complexity Theory Conference, Institute of Electrical and Electronics Engineers, doi:10.1109/sct.1993.336544.


This article is issued from Wikipedia - version of the 9/27/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.