On covering problems in hierarchical poset spaces

Marcos Vinicius Pereira Spreafico; Otávio José Neto Tinoco Neves dos Santos; Roberto Assis Machado

doi:10.3934/amc.2023001

Article Contents

2024, Volume 18, Issue 5: 1471-1479. Doi: 10.3934/amc.2023001

This issue Previous Article Efficient keyword search on encrypted dynamic cloud data Next Article Clay and Product-Matrix MSR Codes with Locality

On covering problems in hierarchical poset spaces

1.
Institute of Mathematics, Federal University of Mato Grosso do Sul, Campo Grande - MS - Brazil
2.
State University of Mato Grosso do Sul, Dourados - MS - Brazil
3.
School of Mathematical and Statistical Sciences, Clemson University, Clemson - South Carolina - U.S.A

^*Corresponding author: Otávio dos Santos
^*Corresponding author: Otávio dos Santos

Received: August 2022

Revised: December 2022

Early access: January 2023

Published: October 2024

The first and second authors are supported by FUNDECT/CNPq grant 054/2015.

Abstract / Introduction Full Text(HTML) Figure(0) / Table(1) Related Papers Cited by

Abstract

Given a ground set $ \mathcal{U} $ and a collection $ \mathcal{C} $ of subsets of $ \mathcal{U} $, we investigate the covering number, which is the cardinality of the smallest sub-collection $ \mathcal{S} $ whose union covers the universe $ \mathcal{U} $. This paper embraces three covering-related problems in hierarchical poset spaces: the classic, the short covering and normal codes. In the first two problems, the classical and the short-covering ones, the covering numbers are studied for collections of $ R $-balls and $ R $-strips, respectively. We prove that determining the covering number in hierarchical spaces depends only on their correspondents in the Hamming space. It allows us to express the covering number in hierarchical spaces. Later on, we characterize all $ \mathcal{H} $-normal codes in binary hierarchical spaces, that are a distinctive family of $ R $-coverings.

Keywords:

Mathematics Subject Classification: Primary: 94B25, 94B65; Secondary: 06A06.

Citation:

Full Text(HTML)

Table 1. The Hasse diagrams of hierarchical posets over $ [3] = \{1, 2, 3\} $

Level Decomposition	Hasse Diagram
$ H_1 =\{1, 2\} $ and $ H_2 =\{3\} $
$ H_1 =\{1\} $ and $ H_2 =\{2, 3\} $
$ H_1 =\{1\} $, $ H_2 =\{2\} $ and $ H_3 =\{3\} $
$ H_1 = \{1, 2, 3\} $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	R. A. Brualdi, J. S. Graves and K. M. Lawrence, Codes with a poset metric, Discrete Math., 147 (1995), 57-72. doi: 10.1016/0012-365X(94)00228-B.
[2]	A. G. Castoldi and E. L. Monte Carmelo, The covering problem in Rosenbloom-Tsfasman spaces, Electron. J. Combin., 22 (2015), Paper 3.30, 18 pp. doi: 10.37236/4974.
[3]	A. G. Castoldi, E. L. Monte Carmelo, L. Moura, D. Panario and B. Stevens, Bounds on covering codes in RT-spaces using ordered covering arrays, in Algebraic Informatics, Springer, 2019,100-111. doi: 10.1007/978-3-030-21363-3_9.
[4]	A. G. Castoldi, E. L. do Monte Carmelo and R. da Silva, Partial sums of binomials, intersecting numbers, and the excess bound in Rosenbloom–Tsfasman space, Comput. Appl. Math., 38 (2019), Paper No. 55, 15 pp. doi: 10.1007/s40314-019-0828-2.
[5]	G. Cohen, I. Honkala, S. Litsyn and A. Lobstein, Covering Codes, Elsevier, Netherlands, 1997.
[6]	G. Cohen, A. Lobstein and N. Sloane, Further results on the covering radius of codes, IEEE Trans. Inform. Theory, 32 (1986), 680-694. doi: 10.1109/TIT.1986.1057227.
[7]	T. Etzion, G. Greenberg and I. S. Honkala, Normal and abnormal codes, IEEE Trans. Inform. Theory, 39 (1993), 1453-1456. doi: 10.1109/18.243469.
[8]	L. V. Felix and M. Firer, Canonical-systematic form for codes in hierarchical poset metrics, Adv. Math. Commun., 6 (2012), 315-328. doi: 10.3934/amc.2012.6.315.
[9]	M. Firer, M. M. S. Alves, J. A. Pinheiro and L. Panek, Poset Codes: Partial Orders, Metrics and Coding Theory, Springer International Publishing, 2018. doi: 10.1007/978-3-319-93821-9.
[10]	M. Frances and A. Litman, On covering problems of codes, Theory Comput. Syst., 30 (1997), 113-119. doi: 10.1007/BF02679443.
[11]	R. Graham and N. Sloane, On the covering radius of codes, IEEE Trans. Inform. Theory, 31 (1985), 385-401. doi: 10.1109/TIT.1985.1057039.
[12]	H. K. Kim and D. Y. Oh, A classification of posets admitting the MacWilliams identity, IEEE Trans. Inform. Theory, 51 (2005), 1424-1431. doi: 10.1109/TIT.2005.844067.
[13]	R. A. Machado, J. A. Pinheiro and M. Firer, Characterization of metrics induced by hierarchical posets, IEEE Trans. Inform. Theory, 63 (2017), 3630-3640. doi: 10.1109/TIT.2017.2691763.
[14]	I. N. Nakaoka, E. L. Monte Carmelo and O. J. N. T. N. dos Santos, Sharp covering of a module by cyclic submodules, Linear Algebra Appl., 458 (2014), 387-402. doi: 10.1016/j.laa.2014.06.019.
[15]	I. N. Nakaoka and O. J. N. T. N. dos Santos, A covering problem over finite rings, Appl. Math. Lett., 23 (2010), 322-326. doi: 10.1016/j.aml.2009.09.022.
[16]	O. J. N. T. N. dos Santos and E. L. Monte Carmelo, Invariant sets under linear operator and covering codes over modules, Linear Algebra Appl., 444 (2014), 42-52. doi: 10.1016/j.laa.2013.11.034.
[17]	O. J. N. T. N. dos Santos and I. N. Nakaoka, Cyclic covering of a module over an artinian ring, Internat. J. Algebra Comput., 26 (2016), 763-773. doi: 10.1142/S0218196716500338.
[18]	R. S. Selvaraj and M. Venkatrajam, Normality of binary codes in Rosenbloom-Tsfasman Metric, 2013 International Conference on Advances in Computing, Communications and Informatics (ICACCI), 2013, 1370-1373. doi: 10.1109/ICACCI.2013.6637378.
[19]	B. Yildiz, I. Siap, T. Bilgin and G. Yesilot, The covering problem for finite rings with respect to the RT-metric, Appl. Math. Lett., 23 (2010), 988-992. doi: 10.1016/j.aml.2010.04.023.