Logical isomorphism and logical limit laws for small permutation classes and regular languages
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.22218
curl -X POST /api/v1/records/arxiv/2610.22218/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.22218/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'