Where First-Order and Monadic Second-Order Logic Coincide.

Michael Elberfeld Martin Grohe Till Tantau

Published in: ACM Trans. Comput. Log. (2016)

Keyphrases

monadic second order logic
first order logic
expressive power
higher order
data complexity
regular expressions
tree automata