Decidability in geometric grid classes of permutations

Abstract

We prove that the basis and the generating function of a geometric grid class of permutations Geom$(M)$ are computable from the matrix $M$, as well as some variations on this result. Our main tool is monadic second-order logic on permutations and words.

15 pages; final journal version

References in corpus (1)

• Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions