arXiv Analytics

Sign in

arXiv:2308.04201 [math.CO]AbstractReferencesReviewsResources

Decidability in geometric grid classes of permutations

Samuel Braunfeld

Published 2023-08-08Version 1

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.

Comments: 14 pages
Categories: math.CO, math.LO
Related articles: Most relevant | Search more
arXiv:1110.4780 [math.CO] (Published 2011-10-21, updated 2012-07-17)
A proof for the decidability of HD0L ultimate periodicity
arXiv:2010.01634 [math.CO] (Published 2020-10-04)
On decidability of hyperbolicity
arXiv:1506.06688 [math.CO] (Published 2015-06-22)
On the growth of permutation classes

Links

Toolbox