Add note about FO variables

1 files changed, 4 insertions, 0 deletions

diff --git a/mgr.tex b/mgr.tex
index cfb5bd2..c08e0e6 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -76,6 +76,10 @@
     $\vec{X}$? In other words, does $T \models \varphi(\vec{W})$?
 }
 
+Though we speak about MSO formulae with second-order variables only, first-order
+variables are also supported simply by restricting to queries in which sets
+assigned to single-order variables are singletons.
+
 \queryproblem[%
     a deterministic bottom-up tree automaton $A$ over ranked alphabet $\Sigma$.
 ]{%