Investigations on the Construction and Number of Linear Extensions of the Marginal Order on the Class of Subintervals of Any Finite Chain

• Grant number: 23/03449-0
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: May 01, 2023
• End date: April 30, 2024
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Peter Sussner
• Grantee: Felipe Scherer Vicentin
• Host Institution: Instituto de Matemática, Estatística e Computação Científica (IMECC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Company: Universidade Estadual de Campinas (UNICAMP). Faculdade de Engenharia Elétrica e de Computação (FEEC)
• Associated research grant: 20/09838-0 - BI0S - Brazilian Institute of Data Science, AP.PCPE

Abstract

In several areas, there is a need to process data that may only adopt a finite number of values. Examples include:* Grayscale digital images can be represented by matrices whose values are integers between 0 (black) and 255 (white);* Evaluations typically take values in a set of the form {0, 1, ..., n}, where n = 5 or n = 10.To express uncertainties regarding these values,one may resort to so called epistemic intervals.Without loss of generality, one may assume that the set of values is of the form L_n = {0, ..., n}. The class of non-empty subintervals of L_n is equipped with two natural partial orders, namely the inclusion order and the product order, also called the marginal order. However, a partial order is insufficient for applications in automatic final decision making, image edge detection and segmentation. To this end, the given partial order, namely the marginal order of I*_n = {[x, y] | x, y em L_n e x <= y}, denoted <=_n in this work, must be extended to a total order, called a linear extension of <=_n. The goal of this "iniciação científica" undergraduate project is to determine the number of all linear extensions of <=_n and to design an algorithm for generating them.