Decidability in geometric grid classes of permutations

Authors: Samuel Walker Braunfeld
Publication year: 2025
Publication type: Článek v odborném periodiku
Periodical: Proceedings of the American Mathematical Society
Bibliographic citation: BRAUNFELD, Samuel Walker. Decidability in geometric grid classes of permutations. Proceedings of the American Mathematical Society. 2025, 153(3), 987-1000. ISSN 0002-9939. E-ISSN 1088-6826
Dostupné z: doi:10.1090/proc/17083.
DOI: 10.1090/proc/17083
ID: 604101
Online record: View online record

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.