Content deleted Content added
Icandostuff (talk | contribs) Adding local short description: "Form of second‐order logic", overriding Wikidata description "form of second‐order logic in which one can quantify over sets but not over predicates" |
m Fix invalid character(s) in short description |
||
Line 1:
{{Short description|Form of
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.<ref>{{cite book|first1=Bruno|last1=Courcelle|author1-link=Bruno Courcelle|first2=Joost|last2=Engelfriet| title=Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach| publisher=Cambridge University Press|date=2012-01-01|isbn=978-0521898331|url=http://dl.acm.org/citation.cfm?id=2414243|access-date=2016-09-15}}</ref> It is particularly important in the [[logic of graphs]], because of [[Courcelle's theorem]], which provides algorithms for evaluating monadic second-order formulas over graphs of bounded [[treewidth]]. It is also of fundamental importance in [[automata theory]], where the [[Büchi–Elgot–Trakhtenbrot theorem]] gives a logical characterization of the [[regular language]]s.
| |||