1 citations · 2 across the 9 of their papers we have counts for
16 papers
Necklaces and Lyndon words in colexicographic order
Daniel Gabric, Joe Sawada
We present the first constant-amortized-time algorithms for generating all length- necklaces and Lyndon words over a -letter alphabet in colexicographic order, for arbitrary…
Decoding universal cycles for t-subsets and t-multisets by decoding bounded-weight de Bruijn sequences
Daniel Gabric, Wazed Imam, Lukas Janik Jones +1
A universal cycle for a set S of combinatorial objects is a cyclic sequence of length |S| that contains a representative of each element in S exactly once as a substring. Despite t…
Construction of orientable sequences in -amortized time per bit
Daniel Gabrić, Joe Sawada
An orientable sequence of order is a cyclic binary sequence such that each length- substring appears at most once \emph{in either direction}. Maximal length orientable seque…
Ranking and unranking bordered and unbordered words
Daniel Gabric
A \emph{border} of a word is a word that is both a non-empty proper prefix and suffix of . If has a border, then it is said to be \emph{bordered}; otherwise, it is said…
Smallest and Largest Block Palindrome Factorizations
Daniel Gabric, Jeffrey Shallit
A \emph{palindrome} is a word that reads the same forwards and backwards. A \emph{block palindrome factorization} (or \emph{BP-factorization}) is a factorization of a word into blo…
Asymptotic bounds for the number of closed and privileged words
Daniel Gabric
A word~ has a border if is a non-empty proper prefix and suffix of . A word~ is said to be \emph{closed} if is of length at most or if has a border tha…
Words that almost commute
Daniel Gabric
The \emph{Hamming distance} between two equal-length words , is the number of positions where and differ. The words and are said to be \emp…
Mutual Borders and Overlaps
Daniel Gabric
A word is said to be \emph{bordered} if it contains a non-empty proper prefix that is also a suffix. We can naturally extend this definition to pairs of non-empty words. A pair of…
The Simplest Binary Word with Only Three Squares
Daniel Gabric, Jeffrey Shallit
We re-examine previous constructions of infinite binary words containing few distinct squares with the goal of finding the "simplest", in a certain sense. We exhibit several new co…
An inequality for the number of periods in a word
Daniel Gabric, Narad Rampersad, Jeffrey Shallit
We prove an inequality for the number of periods in a word x in terms of the length of x and its initial critical exponent. Next, we characterize all periods of the length-n prefix…
Investigating the discrepancy property of de Bruijn sequences
Daniel Gabric, Joe Sawada
The discrepancy of a binary string refers to the maximum (absolute) difference between the number of ones and the number of zeroes over all possible substrings of the given binary…
Avoidance of split overlaps
Daniel Gabric, Jeffrey Shallit
We generalize Axel Thue's familiar definition of overlaps in words, and show that there are no infinite words containing split occurrences of these generalized overlaps. Along the…
Borders, Palindrome Prefixes, and Square Prefixes
Daniel Gabric, Jeffrey Shallit
We show that the number of length-n words over a k-letter alphabet having no even palindromic prefix is the same as the number of length-n unbordered words, by constructing an expl…
Circularly squarefree words and unbordered conjugates: a new approach
Trevor Clokie, Daniel Gabric, Jeffrey Shallit
Using a new approach based on automatic sequences, logic, and a decision procedure, we reprove some old theorems about circularly squarefree words and unbordered conjugates in a ne…
Maximal State Complexity and Generalized de Bruijn Words
Daniel Gabric, Štěpán Holub, Jeffrey Shallit
We compute the exact maximum state complexity for the language consisting of words of length , and characterize languages achieving the maximum. We also consider a special c…
Constructing de Bruijn sequences by concatenating smaller universal cycles
Daniel Gabric, Joe Sawada
We present sufficient conditions for when an ordering of universal cycles for disjoint sets can be conca…