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

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

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.

• Jezik: Angleški jezik
• Ključne besede: balanced code, almost balanced code, Dyck words, non-overlapping code, run-length limit, restricted words
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2025
• Št. strani: 19 str.
• Številčenje: Vol. 44, iss. 1, art. 109
• PID: 20.500.12556/RUL-167036
• UDK: 004
• ISSN pri članku: 2238-3603
• DOI: 10.1007/s40314-024-03055-0
• COBISS.SI-ID: 225011203
• Datum objave v RUL: 05.02.2025

Gradivo je del revije

• Naslov: Computational & Applied Mathematics
• Skrajšan naslov: Comput. Appl. Math.
• Založnik: Springer, Sociedade Brasileira de Matemática Aplicada e Computacional.
• ISSN: 2238-3603
• COBISS.SI-ID: 73925379

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: uravnotežen kod, skoraj uravnotežen kod, Dyckove besede, kod brez prekritij, omejitev dolžine členkov, besede z omejitvami