Two first-order logics of permutations

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:171

Article

Albert, Michael¹  Bouvel, Mathilde²  Feray, Valentin² 

[1] Univ Otago, Dept Comp Sci, Owheo Bldg,133 Union St East, Dunedin 9016, New Zealand

[2] Univ Zurich, Inst Math, Winterthurerstr 190, CH-8057 Zurich, Switzerland

关键词: Permutations;    Patterns;    First order logic;    Ehrenfeucht-Fraisse games;    Sorting operators;   

DOI  :  10.1016/j.jcta.2019.105158

来源: Elsevier

【 摘 要 】

We consider two orthogonal points of view on finite permutations, 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 theory, 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 permutations in the sense of West is expressible in TOTO, and that a logical sentence describing this set can be obtained automatically. 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. (C) 2019 Elsevier Inc. All rights reserved.

【 授权许可】

Free