{"id":"arxiv/2610.22218","url":"https://arxiv.org/abs/2610.22218","tags":["math.CO"],"score":0,"title":"Logical isomorphism and logical limit laws for small permutation classes and regular languages","domain":"math.CO","source":"arxiv","authors":["Klas Markström","Eero Räty"],"reviews":0,"subject":"math.CO","summary":"In this paper we show that for each small permutation class $\\mathcal{F}$ there exists a regular language $L_\\mathcal{F}$ such that the monadic second-order TOTO logic on $\\mathcal{F}$ is isomorphic to classical monadic second-order logic on $L_\\mathcal{F}$. Thanks to the fact that regular languages are closed under monadic second-order restrictions this shows that many subsets of $\\mathcal{F}$ have a well-behaved structure. In particular, this allows us to show that random permutations from any small permutation class satisfies convergence laws for both first-order logic and monadic…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-15","reactions":{}}