From an algorithmic perspective, \(\mathrm {MSO}\)  logic is particularly useful as the
language for describing tractable problems in algorithmic metatheorems
(e.g., for the aforementioned graphs of bounded clique-width
[1]} or tree-width [2]}).
In this respect, we consider the \({L}\) -model checking problem in which the
input is a graph \(G\) , the parameter is a formula \(\phi \)  of the considered logic \({L}\)  (such as \(\mathrm {MSO}_1\) ), and the question is whether \(G\models \phi \) .

С алгоритмической точки зрения логика \(\mathrm {MSO}\) особенно полезна как язык для описания решаемых задач алгоритмических метатеорем (например, для упомянутых выше графов с ограниченной шириной клики [1] или шириной дерева [2]). В этом отношении мы рассматриваем проблему проверки модели \({L}\), в которой входом является граф \(G\), параметром является формула \(\phi\) рассматриваемой логики \({L}\) (например, \(\mathrm {MSO}_1\)), и вопрос состоит в том, выполняется ли \(G \models \phi\).