Verifying monadic second order graph properties with tree automata

Parameterized Complexity

Michael R. Fellows · Electronic Notes in Theoretical Computer Science · 2002 · 2.9K citations · Full text

Mathematical Programming, Engineering, Parameterized Complexity +13

Tree automata techniques and applications

Hubert Comon, Max Dauchet · 1997 · 1.2K citations · Full text

Generalized finite automata theory with an application to a decision problem of second-order logic

J. W. Thatcher, Jesse B. Wright · Theory of Computing Systems · 1968 · 734 citations

Fuzzy Logic, Engineering, Logical Automaton +10

The complexity of first-order and monadic second-order logic revisited

Markus Frick, Martin Grohe · Annals of Pure and Applied Logic · 2004 · 207 citations

Monadic Second-order Logic, Engineering, Abstract Complexity +6

On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic

Bruno Courcelle, Johann A. Makowsky, Udi Rotics · Discrete Applied Mathematics · 2001 · 204 citations

Fixed Parameter Complexity, Monadic Second-order Logic, Graph Theory +11