Decidability in geometric grid classes of permutations

Autoři: Samuel Walker Braunfeld
Rok vydání: 2025
Typ publikace: Článek v odborném periodiku
Periodikum: Proceedings of the American Mathematical Society
Bibliografická citace: 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 záznam: Zobrazit online záznam

Abstrakt

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.