$Q$-ary non-overlapping codes: a generating function approach Article Swipe

MAKE IMPACT

Geyang Wang , Qi Wang · YOU? · · 2021 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2108.06934

Non-overlapping codes are a set of codewords in $\bigcup_{n \ge 2} \mathbb{Z}_q^n$, where $\mathbb{Z}_q = \{0,1,\dots,q-1\}$, such that, the prefix of each codeword is not a suffix of any codeword in the set, including itself; and for variable-length codes, a codeword does not contain any other codeword as a subword. In this paper, we investigate a generic method to generalize binary codes to $q$-ary for $q > 2$, and analyze this generalization on the two constructions given by Levenshtein (also by Gilbert; Chee, Kiah, Purkayastha, and Wang) and Bilotta, respectively. The generalization on the former construction gives large non-expandable fixed-length non-overlapping codes whose size can be explicitly determined; the generalization on the later construction is the first attempt to generate $q$-ary variable-length non-overlapping codes. More importantly, this generic method allows us to utilize the generating function approach to analyze the cardinality of the underlying $q$-ary non-overlapping codes. The generating function approach not only enables us to derive new results, e.g., recurrence relations on their cardinalities, new combinatorial interpretations for the constructions, and the limit superior of their cardinalities for some special cases, but also greatly simplifies the arguments for these results. Furthermore, we give an exact formula for the number of fixed-length words that do not contain the codewords in a variable-length non-overlapping code as subwords. This thereby solves an open problem by Bilotta and induces a recursive upper bound on the maximum size of variable-length non-overlapping codes.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2108.06934

PDF

https://arxiv.org/pdf/2108.06934

OA Status

green

Related Works

10

OpenAlex ID

https://openalex.org/W4298159118

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W4298159118

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2108.06934

Digital Object Identifier

Title

$Q$-ary non-overlapping codes: a generating function approach

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2021

Year of publication

Publication date

2021-08-16

Full publication date if available

Authors

Geyang Wang, Qi Wang

List of authors in order

Landing page

https://arxiv.org/abs/2108.06934

Publisher landing page

PDF URL

https://arxiv.org/pdf/2108.06934

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2108.06934

Direct OA link when available

Concepts

Mathematics, Cardinality (data modeling), Combinatorics, Generalization, Code word, Discrete mathematics, Function (biology), Generating function, Variable (mathematics), Algorithm, Computer science, Decoding methods, Biology, Evolutionary biology, Data mining, Mathematical analysis

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload