Betweenness of partial orders
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 54 (2020), article no. 7

We construct a monadic second-order sentence that characterizes the ternary relations that are the betweenness relations of finite or infinite partial orders. We prove that no first-order sentence can do that. We characterize the partial orders that can be reconstructed from their betweenness relations. We propose a polynomial time algorithm that tests if a finite relation is the betweenness of a partial order.

Reçu le :
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ita/2020007
Classification : 06A06, 03B10, 03C13, 03C15
Keywords: Betweenness, partial order, axiomatization, monadic second-order logic, comparability graph 
@article{ITA_2020__54_1_A7_0,
     author = {Courcelle, Bruno},
     title = {Betweenness of partial orders},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     year = {2020},
     publisher = {EDP Sciences},
     volume = {54},
     doi = {10.1051/ita/2020007},
     mrnumber = {4188243},
     zbl = {1484.03050},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ita/2020007/}
}
TY  - JOUR
AU  - Courcelle, Bruno
TI  - Betweenness of partial orders
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2020
VL  - 54
PB  - EDP Sciences
UR  - https://www.numdam.org/articles/10.1051/ita/2020007/
DO  - 10.1051/ita/2020007
LA  - en
ID  - ITA_2020__54_1_A7_0
ER  - 
%0 Journal Article
%A Courcelle, Bruno
%T Betweenness of partial orders
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2020
%V 54
%I EDP Sciences
%U https://www.numdam.org/articles/10.1051/ita/2020007/
%R 10.1051/ita/2020007
%G en
%F ITA_2020__54_1_A7_0
Courcelle, Bruno. Betweenness of partial orders. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 54 (2020), article no. 7. doi: 10.1051/ita/2020007

[1] M. Changat, P. Narasimha-Shenoi and G. Seethakuttyamma, Betweenness in graphs: A short survey on shortest and induced path betweenness. AKCE Int. J. Graphs Combinat. 16 (2019) 96–109. | MR | Zbl | DOI

[2] V. Chvatal, Antimatroids, betweenness, convexity, in Research Trends in Combinatorial Optimization, Spriner (2008) 57–64. | MR | Zbl

[3] B. Courcelle, The monadic second-order logic of graphs XV: On a conjecture by D. Seese. J. Appl. Log. 4 (2006) 79–114. | MR | Zbl | DOI

[4] B. Courcelle, Several notions of rank-width for countable graphs, J. Combin. Theory B 123 (2017) 186–214. | MR | Zbl | DOI

[5] B. Courcelle, Algebraic and logical descriptions of generalized trees, Logical Methods in Computer Science 13 (2017) 7. | MR | Zbl

[6] B. Courcelle, Axiomatization of betweenness in order-theoretic trees, February (2019). , to appear in Logical Methods in Computer Science (2020). | HAL | MR

[7] B. Courcelle, Betweenness in order-theoretic trees, in Fields of Logic and Computation III, Lecture Notes in Computer Science 12180 (2020) 79–94. | MR | Zbl | DOI

[8] B. Courcelle and J. Engelfriet, Graph structure and monadic second-order logic, a language theoretic approach. Cambridge University Press (2012). | MR | Zbl | DOI

[9] D. Duffus, V. Rödl, N. Sauer and R. Woodrow, Coloring ordered sets to avoid monochromatic maximal chains. Canad. J. Math. 44 (1991) 91–103. | MR | Zbl | DOI

[10] J. Lihova, Strict-order betweenness. Acta Univ. M. Belii Ser. Math. 8 (2000) 27–33. | MR | Zbl

[11] W. Thomas. Classifying regular events in symbolic logic. J. Comput. Syst. Sci. 25 (1982) 360–376. | MR | Zbl | DOI

Cité par Sources :