一句话：将正则文法从词推广到无序无秩树与树宽至多 2 的图，并刻画其可识别/CMSO 可定义集合及复杂度。
论文将词上的正则文法推广到图形结构，为无序无秩树和树宽至多 2 的图定义正则文法。其“正则”性体现在这些文法恰好刻画相应图类中的可识别集合，即 CMSO 可定义集合。证明通过有效构造一个识别器代数，其大小对文法为双指数；由此得到上下文无关语言包含于正则语言问题的 2EXPTIME 上界，而该问题已知 EXPTIME-hard。作者进一步用句法限制刻画树宽至多 2 的图上的 MSO 可定义集合（不含基数约束的 CMSO 公式），并证明 MSO 可定义性与具有非周期并行复合半群的代数可识别性一致。
Regular word grammars are restricted context-free grammars that define all the recognizable languages of words. This paper generalizes regular grammars from words to certain classes of graphs, by defining regular grammars for unordered unranked trees and graphs of tree-width 2 at most. The qualifier "regular" is justified because these grammars define precisely the recognizable (equivalently, CMSO-definable) sets of the respective graph classes. The proof of equivalence between regular and recognizable sets of graphs relies on the effective construction of a recognizer algebra of size doubly-exponential in the size of the grammar. This sets a 2EXPTIME upper bound on the (EXPTIME-hard) problem of inclusion of a context-free language in a regular language, for graphs of tree-width 2 at most. A further syntactic restriction of regular grammars suffices to capture precisely the MSO-definable sets of graphs of tree-width 2 at most, i.e., the sets defined by CMSO formulæ without cardinality constraints. Moreover, we show that MSO-definability coincides with recognizability by algebras having an aperiodic parallel composition semigroup, for each class of graphs defined by a bound on the tree-width.