Betweenness of partial orders

04/21/2020
by   Bruno Courcelle, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset