Header

UZH-Logo

Maintenance Infos

Two first-order logics of permutations


Albert, Michael; Bouvel, Mathilde; Féray, Valentin (2020). Two first-order logics of permutations. Journal of Combinatorial Theory, Series A, 171:105158.

Abstract

We consider two orthogonal points of view on finite permuta-tions, seen as pairs of linear orders (corresponding to the usual one line representation of permutations as words) or seen as bijections (corresponding to the algebraic point of view). For each of them, we define a corresponding first-order logical the-ory, that we call TOTO (Theory Of Two Orders) and TOOB (Theory Of One Bijection) respectively. We consider various expressibility questions in these theories.
Our main results go in three different directions. First, we prove that, for all k ≥ 1, the set of k-stack sortable permuta-tions in the sense of We s t is expressible in TOTO, and that a logical sentence describing this set can be obtained automati-cally. Previously, descriptions of this set were only known for k ≤ 3. Next, we characterize permutation classes inside which it is possible to express in TOTO that some given points form a cycle. Lastly, we show that sets of permutations that can be described both in TOOB and TOTO are in some sense trivial. This gives a mathematical evidence that permutations-as-bijections and permutations-as-words are somewhat different objects.

Abstract

We consider two orthogonal points of view on finite permuta-tions, seen as pairs of linear orders (corresponding to the usual one line representation of permutations as words) or seen as bijections (corresponding to the algebraic point of view). For each of them, we define a corresponding first-order logical the-ory, that we call TOTO (Theory Of Two Orders) and TOOB (Theory Of One Bijection) respectively. We consider various expressibility questions in these theories.
Our main results go in three different directions. First, we prove that, for all k ≥ 1, the set of k-stack sortable permuta-tions in the sense of We s t is expressible in TOTO, and that a logical sentence describing this set can be obtained automati-cally. Previously, descriptions of this set were only known for k ≤ 3. Next, we characterize permutation classes inside which it is possible to express in TOTO that some given points form a cycle. Lastly, we show that sets of permutations that can be described both in TOOB and TOTO are in some sense trivial. This gives a mathematical evidence that permutations-as-bijections and permutations-as-words are somewhat different objects.

Statistics

Citations

Dimensions.ai Metrics
3 citations in Web of Science®
3 citations in Scopus®
Google Scholar™

Altmetrics

Downloads

1 download since deposited on 12 Oct 2020
1 download since 12 months
Detailed statistics

Additional indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:07 Faculty of Science > Institute of Mathematics
Dewey Decimal Classification:340 Law
610 Medicine & health
510 Mathematics
Scopus Subject Areas:Physical Sciences > Theoretical Computer Science
Physical Sciences > Discrete Mathematics and Combinatorics
Physical Sciences > Computational Theory and Mathematics
Uncontrolled Keywords:Theoretical Computer Science, Computational Theory and Mathematics, Discrete Mathematics and Combinatorics
Language:English
Date:1 April 2020
Deposited On:12 Oct 2020 13:23
Last Modified:30 Jan 2021 12:03
Publisher:Elsevier
ISSN:0097-3165
OA Status:Closed
Free access at:Publisher DOI. An embargo period may apply.
Publisher DOI:https://doi.org/10.1016/j.jcta.2019.105158

Download

Closed Access: Download allowed only for UZH members

Content: Published Version
Language: English
Filetype: PDF - Registered users only
Size: 827kB
View at publisher