Betweenness of partial orders

DOI10.1051/ITA/2020007MaRDI QIDQ5021103zbMATH OpenOpenAlexFDO

Authors Bruno Courcelle

Publication date 12 January 2022

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2004.09777

zbMATH Keywords

axiomatizationbetweennesscomparability graphmonadic second-order logicpartial order

Mathematics Subject Classification ID

Higher-order logic (03B16) Model theory of finite structures (03C13) Model theory of denumerable and separable structures (03C15) Partial orders, general (06A06)

Abstract: 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.

Recommendations

• Betweenness and Comparability Obtained from Binary Relations
• Betweenness relations and cycle-free partial orders
• Strict betweennesses induced by posets as well as by graphs
• Betweenness in order-theoretic trees
• Axiomatization of betweenness in order-theoretic trees

Cites work

• Algebraic and logical descriptions of generalized trees
• Antimatroids, betweenness, convexity
• Axiomatization of betweenness in order-theoretic trees
• Betweenness in graphs: a short survey on shortest and induced path betweenness
• Betweenness in order-theoretic trees
• Classifying regular events in symbolic logic
• Coloring Ordered Sets to Avoid Monochromatic Maximal Chains
• Graph structure and monadic second-order logic. A language-theoretic approach
• Several notions of rank-width for countable graphs
• Strict order-betweennesses
• The monadic second-order logic of graphs. XV: On a conjecture by D. Seese

Cited in

(11)

• Compatibility between interval structures and partial orderings
• scientific article; zbMATH DE number 3557823 (Why is no real title available?)
• Betweenness relations and cycle-free partial orders
• Induced betweenness in order-theoretic trees
• Betweenness in order-theoretic trees
• Axiomatization of betweenness in order-theoretic trees
• On limits of betweenness relations
• Strict betweennesses induced by posets as well as by graphs
• Hybrid logic of strict betweenness
• On strict fuzzy betweenness relations
• Directed transit functions

This page was built for publication: Betweenness of partial orders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5021103)