On maximal almost balanced non-overlapping codes and non-overlapping codes with restricted run-lengths

Stanovnik, Lidija (author), Moškon, Miha (author), Mraz, Miha (author)

This paper concerns non-overlapping codes, block codes motivated by synchronisation and DNA-based storage applications. Most existing constructions of these codes do not account for the restrictions posed by the physical properties of communication channels. If undesired sequences are not avoided, the system using the encoding may start behaving incorrectly. Hence, we aim to characterise all non-overlapping codes satisfying two additional constraints. For the first constraint, where approximately half of the letters in each word are positive, we derive necessary and sufficient conditions for the code’s non-expandability and improve known bounds on its maximum size. We also determine exact values for the maximum sizes of polarity-balanced non-overlapping codes having small block and alphabet sizes. For the other constraint, where long sequences of consecutive equal symbols lead to undesired behaviour, we derive bounds and constructions of constrained non-overlapping codes. Moreover, we provide constructions of non-overlapping codes that satisfy both constraints and analyse the sizes of the obtained codes.

• Language: English
• Keywords: balanced code, almost balanced code, Dyck words, non-overlapping code, run-length limit, restricted words
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FRI - Faculty of Computer and Information Science
• Publication status: Published
• Publication version: Version of Record
• Year: 2025
• Number of pages: 19 str.
• Numbering: Vol. 44, iss. 1, art. 109
• PID: 20.500.12556/RUL-167036
• UDC: 004
• ISSN on article: 2238-3603
• DOI: 10.1007/s40314-024-03055-0
• COBISS.SI-ID: 225011203
• Publication date in RUL: 05.02.2025

Record is a part of a journal

• Title: Computational & Applied Mathematics
• Shortened title: Comput. Appl. Math.
• Publisher: Springer, Sociedade Brasileira de Matemática Aplicada e Computacional.
• ISSN: 2238-3603
• COBISS.SI-ID: 73925379

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Secondary language

• Language: Slovenian
• Keywords: uravnotežen kod, skoraj uravnotežen kod, Dyckove besede, kod brez prekritij, omejitev dolžine členkov, besede z omejitvami