Metraipolis › archive › dc_45dfc48a0699
Logical isomorphism and logical limit laws for small permutation classes and regular languages — arXiv:2610.22218
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.22218
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T10:34:06.164Z
- SHA-256 of the archived text
1a6e5fcfe81bb0b35f2a350afc23fae42208742f8d25cf36b5cee97a98409b65- Stable URL of this page
https://metraipolis.com/documento/dc_45dfc48a0699
How to cite
Logical isomorphism and logical limit laws for small permutation classes and regular languages — arXiv:2610.22218 — arXiv (en), https://arxiv.org/abs/2610.22218 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_45dfc48a0699 (Metraipolis archive dc_45dfc48a0699, sha256 1a6e5fcfe81bb0b35f2a350afc23fae42208742f8d25cf36b5cee97a98409b65)
BibTeX
@misc{dc45dfc48a0699,
title = {Logical isomorphism and logical limit laws for small permutation classes and regular languages — arXiv:2610.22218},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.22218},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_45dfc48a0699; sha256 1a6e5fcfe81bb0b35f2a350afc23fae42208742f8d25cf36b5cee97a98409b65},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.22218. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 second-order logic. In the latter case, the law is modular. Our proofs introduce a way of using the automaton description of regular languages to prove properties of generating functions which may be of independent interest. Potential applications include first-order limit laws for random words in some regular languages.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.22218 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T08:50:47.607Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).