Interval-valued rank in finite ordered sets

DOI10.1007/S11083-016-9411-2MaRDI QIDQ1686200zbMATH OpenOpenAlexFDO

Authors Cliff Joslyn, Alex Pogel, Emilie Purvine

Publication date 21 December 2017

Published in Order (Search for Journal in Brave)

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

zbMATH Keywords

graded ordered set interval-valued rank ordered rank set ordered set

Mathematics Subject Classification ID

Partial orders, general (06A06) Knowledge representation (68T30)

Abstract: We consider the concept of rank as a measure of the vertical levels and positions of elements of partially ordered sets (posets). We are motivated by the need for algorithmic measures on large, real-world hierarchically-structured data objects like the semantic hierarchies of ontological databases. These rarely satisfy the strong property of gradedness, which is required for traditional rank functions to exist. Representing such semantic hierarchies as finite, bounded posets, we recognize the duality of ordered structures to motivate rank functions which respect verticality both from the bottom and from the top. Our rank functions are thus interval-valued, and always exist, even for non-graded posets, providing order homomorphisms to an interval order on the interval-valued ranks. The concept of rank width arises naturally, allowing us to identify the poset region with point-valued width as its longest graded portion (which we call the "spindle"). A standard interval rank function is naturally motivated both in terms of its extremality and on pragmatic grounds. Its properties are examined, including the relationship to traditional grading and rank functions, and methods to assess comparisons of standard interval-valued ranks.

Review text

The authors consider the rank as a measure of the vertical levels and positions of elements of an ordered set. Representing semantic hierarchies as finite, bounded ordered sets, they recognize the duality of ordered structures to motivate rank functions with respect to verticality both from bottom and from the top. Their rank functions are interval-valuated even for non-graded ordered sets. The concept of rank width arises naturaly, allowing to identify the ordered set region with point-valued width as longest graded portion. The properties of standard interval rank function are examined, including the relationship to traditional grading and rank functions.

Recommendations

Cites work

Cited in

(4)

Describes a project that uses

Uses Software

This page was built for publication: Interval-valued rank in finite ordered sets

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