2020/04/21 by Bruno Courcelle, Courcelle, Bruno
Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2004.09777
openalex publication_date 2020/04/21 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
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 be-tweenness of a partial order.