Skip to content
DraconiticResearch
Search Sources API
197,578 studies31 sourcesUpdated 3 min ago
PreprintCC BY 4.0arXiv

Logical isomorphism and logical limit laws for small permutation classes and regular languages

  • Klas Markström
  • Eero Räty
Open at sourcePDFDOICite

Abstract

In this paper we show that for each small permutation class ℱ there exists a regular language LF such that the monadic second-order TOTO logic on ℱ is isomorphic to classical monadic second-order logic on LF. Thanks to the fact that regular languages are closed under monadic second-order restrictions this shows that many subsets of ℱ 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.

Related

  1. Isomorphism classes and geometric classification of three-dimensional Jordan algebras and the length function
    Isabel Hernandez, Maria Eugenia Martin, Rodrigo Lucas Rodrigues +1
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  2. New classes of trace-form permutation polynomials and their compositional inverses
    Kirpa Garg
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  3. Finiteness theorems for Cayley permutation classes
    Giulio Cerbai, Anders Claesson
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. On first-order limiting probabilities for small permutation classes
    Victor Falgas-Ravry, Klas Markström, Eero Räty +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Permutation classes need not have proper growth rates
    Jay Pantone, Vincent Vatter
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{markstrom2026logical,
  title = {{Logical isomorphism and logical limit laws for small permutation classes and regular languages}},
  author = {Klas Markström and Eero Räty},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.22218},
  eprint = {2610.22218},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.22218},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Logical isomorphism and logical limit laws for small permutation classes and regular languages
AU  - Klas Markström
AU  - Eero Räty
PY  - 2026
DA  - 2026/10/19
PB  - arXiv
DO  - 10.48550/arxiv.2610.22218
UR  - https://arxiv.org/abs/2610.22218
AB  - In this paper we show that for each small permutation class ℱ there exists a regular language L_F such that the monadic second-order TOTO logic on ℱ is isomorphic to classical monadic second-order logic on L_F. Thanks to the fact that regular languages are closed under monadic second-order restrictions this shows that many subsets of ℱ 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.
ER  -