Source author record

Daniel Gabric

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics math.CO Formal Languages and Automata Theory

Catalog footprint

Research overview

6works

3topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Mutual Borders and Overlaps

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 words $(u,v)$ is said to be \emph{mutually bordered} if there exists a word that is a non-empty proper prefix of $u$ and suffix of $v$ , and there exists a word that is a non-empty proper suffix of $u$ and prefix of $v$ . In other words, $(u,v)$ is mutually bordered if $u$ overlaps $v$ and $v$ overlaps $u$ . We give a recurrence for the number of mutually bordered pairs of words. Furthermore, we show that, asymptotically, there are $c\cdot k^{2n}$ mutually bordered words of length- $n$ over a $k$ -letter alphabet, where $c$ is a constant. Finally, we show that the expected shortest overlap between pairs of words is bounded above by a constant.

preprint2022arXiv

Words that almost commute

The \emph{Hamming distance} $\text{ham}(u,v)$ between two equal-length words $u$ , $v$ is the number of positions where $u$ and $v$ differ. The words $u$ and $v$ are said to be \emph{conjugates} if there exist non-empty words $x,y$ such that $u=xy$ and $v=yx$ . The smallest value $\text{ham}(xy,yx)$ can take on is $0$ , when $x$ and $y$ commute. But, interestingly, the next smallest value $\text{ham}(xy,yx)$ can take on is $2$ and not $1$ . In this paper, we consider conjugates $u=xy$ and $v=yx$ where $\text{ham}(xy,yx)=2$ . More specifically, we provide an efficient formula to count the number $h(n)$ of length- $n$ words $u=xy$ over a $k$ -letter alphabet that have a conjugate $v=yx$ such that $\text{ham}(xy,yx)=2$ . We also provide efficient formulae for other quantities closely related to $h(n)$ . Finally, we show that there is no one easily-expressible good bound on the growth of $h(n)$ .

preprint2020arXiv

An inequality for the number of periods in a word

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 of a characteristic Sturmian word in terms of the lazy Ostrowski representation of n, and use this result to show that our inequality is tight for infinitely many words x. We propose two related measures of periodicity for infinite words. Finally, we also consider special cases where x is overlap-free or squarefree.

preprint2020arXiv

Avoidance of split overlaps

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 way we prove a useful theorem about repeated disjoint occurrences in words -- an interesting natural variation on the classical de Bruijn sequences.

preprint2020arXiv

Borders, Palindrome Prefixes, and Square Prefixes

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 explicit bijection between the two sets. A slightly different but analogous result holds for those words having no odd palindromic prefix. Using known results on borders, we get an asymptotic enumeration for the number of words having no even (resp., odd) palindromic prefix . We obtain an analogous result for words having no nontrivial palindromic prefix. Finally, we obtain similar results for words having no square prefix, thus proving a 2013 conjecture of Chaffin, Linderman, Sloane, and Wilks.

preprint2020arXiv

The Simplest Binary Word with Only Three Squares

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 constructions. Rather than using tedious case-based arguments to prove that the constructions have the desired property, we rely instead on theorem-proving software for their correctness.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Daniel Gabric

Research overview

Is this your work?

6 publications

Mutual Borders and Overlaps

Words that almost commute

An inequality for the number of periods in a word

Avoidance of split overlaps

Borders, Palindrome Prefixes, and Square Prefixes

The Simplest Binary Word with Only Three Squares

See the researcher in context

Building this map preview