pipette
ENEnglish

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

Klas Marstr\"om, Eero R\"aty

Preprint

En palabras de los autores

In this paper we show that for each small permutation class there exists a regular language such that the monadic second-order TOTO logic on is isomorphic to classical monadic second-order logic on . 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.

Resultado principalLimitación que admiten los autores

Apareció: viernes, 16 de octubre. arXiv. Preprint, todavía sin revisión por pares.