# A New Approach to Regular & Indeterminate Strings

Felipe A. Louza<EMAIL_ADDRESS>Faculty of Electrical Engineering, Federal
University of Uberlândia, Brazil  Neerja Mhaskar<EMAIL_ADDRESS>Department of Computing and Software, McMaster University, Canada  W. F. Smyth
<EMAIL_ADDRESS>Department of Informatics, King’s College London, UK  School
of Engineering & Information Technology, Murdoch University, Australia

###### Abstract

In this paper we propose a new, more appropriate definition of regular and
indeterminate strings. A regular string is one that is “isomorphic” to a
string whose entries all consist of a single letter, but which nevertheless
may itself include entries containing multiple letters. A string that is not
regular is said to be indeterminate. We begin by proposing a new model for the
representation of strings, regular or indeterminate, then go on to describe a
linear time algorithm to determine whether or not a string
$\mbox{\boldmath$x$}=\mbox{\boldmath$x$}[1..n]$ is regular and, if so, to
replace it by a lexicographically least (lex-least) string $y$ whose entries
are all single letters. Furthermore, we connect the regularity of a string to
the transitive closure problem on a graph, which in our special case can be
efficiently solved. We then introduce the idea of a feasible palindrome array
MP of a string, and prove that every feasible MP corresponds to some (regular
or indeterminate) string. We describe an algorithm that constructs a string
$x$ corresponding to given feasible MP, while ensuring that whenever possible
$x$ is regular and if so, then lex-least. A final section outlines new
research directions suggested by this changed perspective on regular and
indeterminate strings.

###### keywords:

indeterminate string , degenerate string , generalized string , transitive
closure , palindrome , maximal palindrome array , Manacher’s condition ,
reverse engineering , algorithm , stringology

##  1 Introduction

Under various names and guises, the idea of a string as something other than a
sequence of single letters has been discussed for almost half a century. In
1974 Fischer & Paterson [1] studied pattern-matching on strings $x$ whose
entries could be don’t-care letters; that is, letters matching any single
letter in the alphabet $\Sigma$ on which the string is defined, hence matching
every position in $x$. (Thus the don’t care letter $*$ would match every
letter in a given alphabet $\Sigma=\\{a,b,c\\}$.) In 1987 Abrahamson [2]
extended this model by considering pattern-matching on generalized strings
whose entries could be non-empty subsets of $\Sigma$. (Thus entries $\\{b\\}$,
$\\{a,b\\}$, $\\{b,c\\}$ would match each other due to the shared $b$.)

Both of these models have been intensively studied in this century, with
interest fueled by applications, especially to computational biology, where as
a byproduct of the DNA sequencing process and in other contexts, indeterminate
letters such as $\\{a,t\\}$, $\\{c,g\\}$ or $\\{a,c,g,t\\}$ may arise. The
properties of strings with don’t care letters, also called holes, have been
intensively studied by Blanchet-Sadri, culminating in a 2008 book [3] on
strings with holes, also called partial words, that summarized the
contributions of her many previous research articles. In 2009 a periodicity
lemma for partial words was formulated in [4].

Meanwhile Iliopoulos and various collaborators (see, for example, [5, 6, 7])
studied pattern-matching and other problems, especially related to
bioinformatics applications, on generalized strings (now renamed degenerate
strings, or even elastic degenerate strings). Another sequence of papers [8,
9, 10, 11, 12] studied other pattern-matching algorithms on generalized
strings (renamed indeterminate strings, with indeterminate letters such as
$\\{a,b\\}$ or $\\{b,c\\}$ in some positions). In addition, other aspects of
indeterminate strings have been studied, such as their border arrays [13],
cover arrays [14], prefix arrays [15, 16] and suffix arrays [17, 13]. The
computation of an indeterminate string from its prefix graph was recently
considered in [18].

The traditional approach to defining an indeterminate string only relies on
the scope of its letters irrespective of the matching relationship between
them. Therefore, a string $\mbox{\boldmath$x$}=a\\{a,c\\}b\\{a,d\\}bb$ can be
seen as an indeterminate string, when in essence it can be reduced to an
“isomorphic” string $\mbox{\boldmath$x^{\prime}$}=aababb$ that is regular (see
Section 2 for definitions). It is evident that algorithms designed for
indeterminate strings are slower and at times require more space for
processing. Therefore, it is important to identify strings that are “truly”
indeterminate. In this paper we redefine an indeterminate string in a context
that we believe captures the idea in a more appropriate way — at once more
general and more precise.

The outline of the paper is as follows: in Section 2 we present the necessary
definitions, including in particular a model for the representation of strings
that efficiently incorporates both regular and indeterminate. In Section 3, we
apply this model to describe a linear time algorithm that determines whether
or not a given string is regular and, if so, returns an isomorphic
lexicographically least (lex-least) regular string, whose entries are all
single letters. We go on to present an interesting connection between strings
defined using our approach and the transitive closure of a relation, showing
that for some special cases of a relation, its transitive closure can be
computed in quadratic time. In Section 4 we introduce a “Reverse Engineering”
problem [19, 20, 21, 22] for both regular and indeterminate strings (in our
new formulation). We first show that every feasible palindrome array MP does
indeed correspond to some string, regular or indeterminate. Then, following
[23], we describe an algorithm that, given a feasible palindrome array MP,
computes a lex-least regular string corresponding to MP, whenever that is
possible; and, if not, returns a corresponding indeterminate string. Section 5
discusses open problems and questions arising from this new approach.

##  2 Regular & Indeterminate Strings

A letter $\ell$ is a finite list of $s$ distinct characters
$c_{1},c_{2},\ldots,c_{s}$, each drawn from a set $\Sigma$ of size
$\sigma=|\Sigma|$ called the alphabet. In the case that $\Sigma$ is ordered,
$\ell$ is said to be in normal form if its characters occur in the ascending
order determined by $\Sigma$. The integer $s=s(\ell)$ is called the scope of
$\ell$. If $s=1$, $\ell$ is said to be regular, otherwise indeterminate. Two
letters $\ell_{1},\ell_{2}$ are said to match, written
$\ell_{1}\approx\ell_{2}$, if and only if $\ell_{1}\cap\ell_{2}\neq\emptyset$.
In the case that matching $\ell_{1}$ and $\ell_{2}$ are both regular, we may
write $\ell_{1}=\ell_{2}$.

For $n\geq 1$, a string $\mbox{\boldmath$x$}=\mbox{\boldmath$x$}[1..n]$ is a
sequence
$\mbox{\boldmath$x$}[1],\mbox{\boldmath$x$}[2],\ldots,\mbox{\boldmath$x$}[n]$
of letters, where $n=|\mbox{\boldmath$x$}|$ is the length of $x$, and every
$i\in\\{1,\ldots,n\\}$ is a position in $x$. If every letter in $x$ is in
normal form, then $x$ itself is said to be in normal form. A tuple
$T=(i,j_{1},j_{2})$ of distinct positions $i,j_{1},j_{2}$ in $x$ such that

$\mbox{\boldmath$x$}[j_{1}]\approx\mbox{\boldmath$x$}[i]\approx\mbox{\boldmath$x$}[j_{2}]$

is said to be a triple. A triple $T$ is transitive if
$\mbox{\boldmath$x$}[j_{1}]\approx\mbox{\boldmath$x$}[j_{2}]$, otherwise
intransitive. If every triple $T$ in $x$ is transitive, then we say that $x$
is regular; otherwise, $x$ is indeterminate. The scope of $x$ is given by

$S(\mbox{\boldmath$x$})=\max_{i\in\\{1,\dots,n\\}}s(\mbox{\boldmath$x$}[i]).$

Two strings $x$ and $y$ of equal length $n$ are said to be isomorphic if and
only if for every $i,j\in$ $\\{1,\dots,n\\}$,

$\mbox{\boldmath$x$}[i]\approx\mbox{\boldmath$x$}[j]\Longleftrightarrow\mbox{\boldmath$y$}[i]\approx\mbox{\boldmath$y$}[j].$
(1)

Note that isomorphic strings may superficially have quite different
representations; for example,
$\mbox{\boldmath$y$}=\\{a,b\\}\\{b,c\\}\\{a,c\\}$ is isomorphic to
$\mbox{\boldmath$x$}=aaa$. Thus we see that the definition given here of
regularity of a string $x$ is more general, including many more strings, than
the usual definition (scope $=1$) given in the literature. However:

###### Lemma 1

Every regular string is isomorphic to a string of scope 1.

Proof. In [16, 18] and elsewhere it is observed that a regular string
$\mbox{\boldmath$x$}[1..n]$ is equivalent to a graph $\mathcal{G}$ on vertices
$\\{1,\dots,n\\}$ which is a collection of cliques with the property that
vertices $i$ and $j\neq i$ are in the same clique if and only if
$\mbox{\boldmath$x$}[i]\approx\mbox{\boldmath$x$}[j]$. Now if, for every
clique $\mathcal{C}$ of $\mathcal{G}$, we choose a unique regular letter
$\ell_{\mathcal{C}}$ and, corresponding to every position $i$ in
$\mathcal{C}$, make the assignment
$\mbox{\boldmath$x$}[i]\leftarrow\ell_{\mathcal{C}}$, we thus construct a
string on regular letters equivalent to $\mathcal{G}$; that is, a string of
scope 1.

We remark that constructing the graph $\mathcal{G}$ described in Lemma 1, then
checking whether or not it is a collection of cliques, is a trivial and
obvious approach to determining the regularity of $x$. In this paper we
propose more efficient and interesting algorithms.

The following result is an easy corollary of Lemma 1:

###### Corollary 1

Given a regular string $\mbox{\boldmath$x$}[1..n]$, then, corresponding to
every triple $(i,j_{1},j_{2})$, we can assign a regular letter to
$\mbox{\boldmath$y$}[i],\mbox{\boldmath$y$}[j_{1}],\mbox{\boldmath$y$}[j_{2}]$
in such a way that the resulting string $\mbox{\boldmath$y$}[1..n]$ is
isomorphic to $\mbox{\boldmath$x$}[1..n]$.

For example, $\mbox{\boldmath$y$}=ccdcdd$ is isomorphic to
$\mbox{\boldmath$x$}=a\\{a,c\\}b\\{a,d\\}bb$.

###  2.1 A Model for the Representation of Indeterminate Strings

The preceding result suggests a need for an algorithm to determine whether or
not an apparently indeterminate string is nevertheless actually regular, even
though, like the string $\mbox{\boldmath$x$}=a\\{a,c\\}b\\{a,d\\}bb$ mentioned
in the Introduction, it contains indeterminate letters. We describe such an
algorithm in the next section, but first we must deal with the following
issue: in order to design algorithms on indeterminate strings $x$, we need to
have some practical representation of such strings — in particular, of
indeterminate letters. This requires us to deal in some realistic way with the
fact that, on an alphabet of size $\sigma$, there are $2^{\sigma}\\!-\\!1$
possible nonempty distinct letters. For $\sigma=2$, we have only
$a,b,\\{a,b\\}$, but for $\sigma=26$, dealing efficiently with $2^{26}-1$
distinct letter sets is beyond current processing capabilities. Fortunately,
in practice, such cases do not arise: there may be “many” letter sets but, for
large $\sigma$, not $2^{\sigma}\\!-\\!1$ of them.

Thus we need a model of computation that deals efficiently with indeterminate
letters even when their number is large — though not “too large”. For given
$\sigma$, we shall accordingly assume an integer alphabet with letters
$\ell\in\\{1,2,\ldots,\sigma\\}$ and we shall interpret letter $\ell=0$ as
denoting a hole or don’t-care. Otherwise, $\ell>\sigma$ represents an
indeterminate letter, that also determines the position
$\sigma^{\prime}=\ell\\!-\\!\sigma$ in an array $I[1..\sigma^{*}]$, where
$\sigma^{*}$ is the maximum number of indeterminate letters (in addition to
the don’t care) allowed to occur in $x$. Each entry $I[\sigma^{\prime}]$ is a
pair $(s(\ell),loc)$ that gives the scope $s(\ell)$ of the indeterminate
letter $\ell$ and the starting location $loc$ in an array $L$, consisting of
integers in the range $\\{1\dots\sigma\\}$, of the subarray specifying the
$s(\ell)$ regular letters that constitute $\mbox{\boldmath$x$}[i]$:

$(\ell_{1},\ell_{2},\ldots,\ell_{s(\ell)}).$

Here the $\ell_{j},1\leq j\leq s(\ell)$, are distinct elements of $\Sigma$ in
normal form, thus satisfying $\ell_{1}<\ell_{2}<\cdots<\ell_{s(\ell)}$. For
instance, consider
$\mbox{\boldmath$x$}=aac\\{a,c\\}gta\\{g,t\\}\\{a,c\\}\\{g,t\\}$ over
$\Sigma=\\{a,c,g,t\\}$. To represent it using the above encoding, we map
$a\rightarrow 1,c\rightarrow 2,g\rightarrow 3,t\rightarrow 4$. Since we have
two indeterminate letters in $x$, $\sigma^{*}=2$, $0\leq\ell\leq 6$, and
$\\{a,c\\}\rightarrow 5$ and $\\{g,t\\}\rightarrow 6$. Further,
$I=[(2,1),(2,3)]$, $L=[1,2,3,4]$, and the encoding of $x$ is $1125341656$.

To fix the ideas, we suppose here that $\ell$, hence every entry in array $L$,
is constrained to one byte (8 bits) of storage. Thus, for example, to handle
English text, we should suppose that $\sigma=77$ (26 lower case letters, 26
upper case, 10 numerical digits, 14 punctuation symbols, and space), leaving
available values $\ell\in 78..255$: $\sigma^{*}=178$ distinct indeterminate
letters. (Doubling storage for $\ell$ to two bytes permits 65,458
indeterminate English letters to be defined.)

Another example: for DNA strings on $\Sigma=\\{a,c,g,t\\}$, $\sigma=4$, we
could define $a\rightarrow 1,c\rightarrow 2,g\rightarrow 3,t\rightarrow 4$,
use zero for the don’t care and 5–14 for the other 10 possible combinations of
letters:

$ac,ag,at,cg,ct,gt,acg,act,agt,cgt.$

Then for DNA a half byte (4 bits) for $\ell$ would be sufficient to identify
all the indeterminate letters, and the associated array $L$ would require at
most 24 half bytes to represent them.

Other models to represent indeterminate strings have been proposed. For
example, in [24] all the non-empty letters (both regular and indeterminate)
over the DNA alphabet $\Sigma_{DNA}=\\{A,C,G,T\\}$ are mapped to the IUPAC
symbols $\Sigma_{IUPAC}=\\{A,C,G,T,R,Y,S,W,K,M,B,D,H,V,N\\}$, to construct an
isomorphic regular string of scope $1$ over $\Sigma_{IUPAC}$. Further, in [25]
each symbol in the DNA alphabet is represented as a 4-bit integer power of $2$
($2^{i}$, with $i\in\\{0,1,2,3\\}$). A non-empty indeterminate letter over
$\Sigma_{DNA}$ is represented as $\Sigma_{\\{s\in\mathcal{P}(\Sigma)\\}}s$.
Then instead of using the natural order on integers it uses a Gray code [26]
(also known as the reflected binary code) to order indeterminate letters over
$\Sigma_{DNA}$. Note that with the Gray code two successive values differ only
by one bit, such as 1100 and 1101, which enables minimizing the number of
separate intervals associated with each of the four symbols of $\Sigma_{DNA}$.
The models described here are of interest primarily for representing
indeterminate strings over the DNA alphabet. However, the same approach is
applicable to any alphabet.

##  3 Determining the regularity of $x$

In this section we discuss a function REGULAR (Figure 1) that determines
whether or not a given string $x$ is regular. REGULAR deals with strings $x$
of scope $S(\mbox{\boldmath$x$})>1$, since otherwise, for
$S(\mbox{\boldmath$x$})=1$, the regularity of $x$ is immediate. As a
byproduct, in the case that $x$ is regular, REGULAR computes the lex-least
string $y$ of scope 1 on an integer alphabet that is isomorphic to $x$.

Before getting into the details of REGULAR, we need to consider the overall
strategy. An issue that arises is this: in order to determine whether or not
$\mbox{\boldmath$x$}[1..n]$ is regular, it is necessary to look at all triples
to determine whether or not one of them is intransitive, a process that it
seems must require $n\choose 2$ letter comparisons, thus
$\mathcal{O}(S(\mbox{\boldmath$x$})n^{2})$ time. However, it suffices to apply
REGULAR to a reduced string
$\mbox{\boldmath$x_{R}$}=\mbox{\boldmath$x_{R}$}[1..m]$ consisting of exactly
one occurrence of each of the $m$ distinct letters (both regular and
indeterminate) in $x$. Thus, in view of our constraint on $\ell$, $m\leq 256$.
Clearly $x_{R}$ is regular if and only if $x$ is regular. Consequently triple-
testing time reduces to $\mathcal{O}(m^{2})$, where of course $m<<n$. (Indeed,
even for the extreme two-byte case mentioned above, with $m=65,536$, $m^{2}$
is only 4 billion or so, thus still $\mathcal{O}(n)$ in many cases.)

function $REGULAR(\mbox{\boldmath$x$},n;\mbox{\boldmath$y$},\sigma^{\prime})$
: Boolean
construct $x_{R}$ $\triangleright$ contains each distinct letter of $x$
exactly once
$m\leftarrow|\mbox{\boldmath$x_{R}$}|$
$ret\leftarrow
regular_{min}(\mbox{\boldmath$x_{R}$},m,\mbox{\boldmath$y_{R}$},\sigma^{\prime})$
if $ret$ then
construct $y$ from $y_{R}$
$REGULAR\leftarrow ret$; return

Figure 1: This Boolean function determines whether ($REGULAR=\tt{true}$) or
not ($REGULAR=\tt{false}$) a string $\mbox{\boldmath$x$}[1..n]$ of scope
$S(\mbox{\boldmath$x$})>1$ on alphabet $\Sigma$ is regular. In the former
case, on exit the string $y$ is the lex-least regular string of scope 1 on an
integer alphabet $\Sigma^{\prime}=\\{1,2,\ldots,\sigma^{\prime}\\}$ that is
isomorphic to $x$.

The first step of REGULAR therefore computes $x_{R}$, a process performed in
$\Theta(n)$ time by a single scan of $x$, using a Boolean array
$found[1..256]$ to indicate whether ($found[j]=\tt{true}$) or not
($found[j]=\tt{false}$) the letter $j=\mbox{\boldmath$x$}[i]$ has occurred
previously in $\mbox{\boldmath$x$}[1..i-1]$. Note that in this process, the
letters are placed in $x_{R}$ in the order of their first occurrence in $x$.
Thus:

###### Claim 1

In cases of practical interest — that is, when $n$ greatly exceeds $m$ — the
replacement of $\mbox{\boldmath$x$}=\mbox{\boldmath$x$}[1..n]$ by the reduced
string $\mbox{\boldmath$x_{R}$}=\mbox{\boldmath$x_{R}$}[1..m]$, where $m$ is
the number of distinct letters in $x$, permits the regularity of $x$ to be
determined in $\mathcal{O}(n)$ time.

Indeed, in many cases that arise in practice, the status of $x$ follows from
conditions that are more easily evaluated. For instance, $x$ is indeterminate
if

  * 1.

it contains all regular letters in $\Sigma$ and at least one indeterminate
letter; or

  * 2.

it contains a don’t-care and at least two regular letters; or

  * 3.

it contains an indeterminate letter $\ell$ as well as any two characters of
$\ell$.

Having constructed $x_{R}$, REGULAR executes the Boolean function
$regular_{min}$ (Figure 2), which returns $\tt{true}$ if and only if $x_{R}$
is regular. In that case, $regular_{min}$ also outputs a string $y_{R}$ of
scope 1 on an integer alphabet $\Sigma^{\prime}$ that is isomorphic to
$x_{R}$. As explained below, it is then straightforward to compute a lex-least
string $y$ of scope 1 isomorphic to $x$.

function
$regular_{min}(\mbox{\boldmath$x_{R}$};m,\mbox{\boldmath$y_{R}$},\sigma^{\prime})$
: Boolean
$\mbox{\boldmath$y_{R}$}[1..m]\leftarrow 0^{m};\ \sigma^{\prime}\leftarrow 0$
for $i=1$ to $m$ do
if $\mbox{\boldmath$y_{R}$}[i]=0$ then
$\sigma^{\prime}\leftarrow\sigma^{\prime}\\!+\\!1;\
\mbox{\boldmath$y_{R}$}[i]\leftarrow\sigma^{\prime}$
for $j\leftarrow i\\!+\\!1$ to $m$ do
if $\mbox{\boldmath$x_{R}$}[j]\approx\mbox{\boldmath$x_{R}$}[i]$ then
if $\mbox{\boldmath$y_{R}$}[j]=0$ then
$\mbox{\boldmath$y_{R}$}[j]\leftarrow\sigma^{\prime}$
else $regular_{min}\leftarrow\tt{false};\ {\bf return\ }$
else
for $j\leftarrow i\\!+\\!1$ to $m$ do
if $\mbox{\boldmath$y_{R}$}[j]=\mbox{\boldmath$y_{R}$}[i]$ then
if $\mbox{\boldmath$x_{R}$}[j]\not\approx\mbox{\boldmath$x_{R}$}[i]$ then
$regular_{min}\leftarrow\tt{false}$; return
else if $\mbox{\boldmath$x_{R}$}[j]\approx\mbox{\boldmath$x_{R}$}[i]$ then
$regular_{min}\leftarrow\tt{false}$; return
$regular_{min}\leftarrow\tt{true}$; return

Figure 2: Determine whether ($regular_{min}=\tt{true}$) or not
($regular_{min}=\tt{false}$) a reduced string $\mbox{\boldmath$x_{R}$}[1..m]$
of scope $S(\mbox{\boldmath$x_{R}$})>1$ on alphabet $\Sigma$ is regular. If
$\tt{true}$, on exit the string $y_{R}$ is the lex-least regular string of
scope 1 on the integer alphabet
$\Sigma^{\prime}=\\{1,2,\ldots,\sigma^{\prime}\\}$ that is isomorphic to
$x_{R}$.

In the function $regular_{min}$, we first initialize each letter in
$\mbox{\boldmath$y_{R}$}[1..m]$ to $0$. Then we scan $x_{R}$ from left to
right, using $y_{R}$ to record previous matches. During this scan the
following condition holds as long as $x_{R}$ is regular:

$\mbox{\boldmath$x_{R}$}[i]\approx\mbox{\boldmath$x_{R}$}[j]\Leftrightarrow\mbox{\boldmath$y_{R}$}[i]=\mbox{\boldmath$y_{R}$}[j]\wedge\mbox{\boldmath$y_{R}$}[i]\neq
0.$ (2)

If at position $i\in\\{1,\dots,m\\}$, we find $\mbox{\boldmath$y_{R}$}[i]=0$ —
that is, it was not part of a previous match — we form the new character
$\sigma^{\prime}\leftarrow\sigma^{\prime}\\!+\\!1$. We then scan right in the
strings $\mbox{\boldmath$x_{R}$}[i+1..m]$ and
$\mbox{\boldmath$y_{R}$}[i+1..m]$ to see if condition (2) continues to hold.
If it does not, we mark $x_{R}$ as indeterminate and exit; otherwise, whenever
$\mbox{\boldmath$x_{R}$}[j]\approx\mbox{\boldmath$x_{R}$}[i]$ and
$\mbox{\boldmath$y_{R}$}[j]=0$, we assign
$\mbox{\boldmath$y_{R}$}[j]\leftarrow\sigma^{\prime}$.

In $regular_{min}$ the inner loops execute $\binom{m}{2}$ times, and checking
if two letters match takes $\mathcal{O}(\sigma)$ time for $x$ in normal form,
$\mathcal{O}(\sigma\log\sigma)$ otherwise. Therefore:

###### Lemma 2

Algorithm $regular_{min}$ runs in $\mathcal{O}(m^{2}\sigma)$ time, where
$m=|\mbox{\boldmath$x_{R}$}|$ and $1\leq m\leq 2^{\sigma}$, when $x_{R}$ is in
normal form; otherwise, $\mathcal{O}(m^{2}\sigma\log\sigma)$ time, where
$\mathcal{O}(\sigma\log\sigma)$ is the maximum time needed to sort the
characters in two letters.

###### Lemma 3

When $\mbox{\boldmath$x$}[1..n]$ is regular, the (lex-least) corresponding $y$
can be computed from $y_{R}$ in $\Theta(n)$ time.

Proof. As noted above, the letters in $\mbox{\boldmath$x_{R}$}[1..m]$ occur in
order of their first appearance in $x$. Moreover, the letters in $y_{R}$ are
assigned in increasing order $1,2,\ldots,\sigma^{\prime}$ of occurrence of the
positions of new letters in $x_{R}$. Thus, to compute $y$, we first form
$P_{\mbox{\boldmath$x_{R}$}}[1..n]$, in which $P_{\mbox{\boldmath$x_{R}$}}[j]$
is the position at which the letter $\mbox{\boldmath$x$}[j]$ occurs in
$x_{R}$. Therefore, the elements of $P_{\mbox{\boldmath$x_{R}$}}$ are integers
in the range $\\{1\dots m\\}$. Clearly, $P_{\mbox{\boldmath$x_{R}$}}[1..n]$
can be computed in $\Theta(n)$ time. Then for every $i\in\\{1\dots n\\}$, we
compute

$\mbox{\boldmath$y$}[i]\leftarrow\mbox{\boldmath$y_{R}$}\big{[}P_{\mbox{\boldmath$x_{R}$}}[i]\big{]},$

yielding a lex-least string of scope 1 isomorphic to $x$.

###### Lemma 4

Algorithm REGULAR runs in $\Theta(n)$ time for a string
$\mbox{\boldmath$x$}[1..n]$ from a constant alphabet.

Proof. The running time of REGULAR is equal to the total time required for (1)
construction of $x_{R}$ from $x$; (2) execution of $regular_{min}$; (3)
construction of $y$ from $y_{R}$.

As we have seen (Claim 1), (1) requires $\Theta(n)$ time, while Lemma 2 tells
us that (2) requires $\mathcal{O}(m^{2}\sigma\log\sigma)$ time. However, since
$m$ and $\sigma$ are constants, (2) requires constant time. Further, as
explained in Lemma 3, $y$ can be computed from $y_{R}$ in $\Theta(n)$ time.
Therefore, we conclude that the running time of REGULAR is $\Theta(n)$.

At a cost of adding $\Theta(m^{2})$ bits of additional storage, together with
$\mathcal{O}(m^{2}\sigma)$ preprocessing time, the regularity of the reduced
string $x_{R}$ can actually be determined in $\mathcal{O}(m^{2})$ time in all
cases, as we now explain. Essentially, we replace $x_{R}$ by a symmetric
adjacency matrix
$M^{\approx}_{\mbox{\boldmath$x_{R}$}}=M^{\approx}_{\mbox{\boldmath$x_{R}$}}[1..m,1..m]$
based on the matches in $x_{R}$: for $1\leq i,j\leq m$,

$\displaystyle
M^{\approx}_{\mbox{\boldmath$x_{R}$}}[i,j]=\begin{cases}1&\mbox{ if
}\mbox{\boldmath$x_{R}$}[i]\approx\mbox{\boldmath$x_{R}$}[j];\\\ 0&\mbox{
otherwise}.\end{cases}$ (3)

Since each match may require $\mathcal{O}(\sigma)$ time, this construction can
be performed in $\mathcal{O}(m^{2}\sigma)$ time in the worst case.

Then, simply replacing references to $x_{R}$ in function regular_min by
references to $M^{\approx}_{\mbox{\boldmath$x_{R}$}}$, we obtain the
$\mathcal{O}(m^{2})$ function regular_min_matrix (Figure 3).

function
$regular_{min\\_matrix}(M^{\approx}_{\mbox{\boldmath$x_{R}$}},m;\mbox{\boldmath$y_{R}$},\sigma^{\prime})$
$\mbox{\boldmath$y_{R}$}[1..m]\leftarrow 0^{m};\ \sigma^{\prime}\leftarrow 0$
for $i=1$ to $m$ do
if $\mbox{\boldmath$y_{R}$}[i]=0$ then
$\sigma^{\prime}\leftarrow\sigma^{\prime}\\!+\\!1;\
\mbox{\boldmath$y_{R}$}[i]\leftarrow\sigma^{\prime}$
for $j\leftarrow i\\!+\\!1$ to $m$ do
if $M^{\approx}_{\mbox{\boldmath$x_{R}$}}[i,j]=1$ then
if $\mbox{\boldmath$y_{R}$}[j]=0$ then
$\mbox{\boldmath$y_{R}$}[j]\leftarrow\sigma^{\prime}$
else $regular_{min\\_matrix}\leftarrow\tt{false};\ {\bf return\ }$
else
for $j\leftarrow i\\!+\\!1$ to $m$ do
if $\mbox{\boldmath$y_{R}$}[j]=\mbox{\boldmath$y_{R}$}[i]$ then
if $M^{\approx}_{\mbox{\boldmath$x_{R}$}}[i,j]=0$ then
$regular_{min\\_matrix}\leftarrow\tt{false}$; return
else if $M^{\approx}_{\mbox{\boldmath$x_{R}$}}[i,j]=1$ then
$regular_{min\\_matrix}\leftarrow\tt{false}$; return
$regular_{min\\_matrix}\leftarrow\tt{true}$; return

Figure 3: Determine in $\mathcal{O}(m^{2})$ time whether
($regular_{min\\_matrix}=\tt{true}$) or not
($regular_{min\\_matrix}=\tt{false}$) an $m\times m$ bit matrix
$M^{\approx}_{\mbox{\boldmath$x_{R}$}}$ is regular. In the former case, the
algorithm computes, corresponding to $M^{\approx}_{\mbox{\boldmath$x_{R}$}}$,
a lex-least regular string $y_{R}$ of scope 1 on the integer alphabet
$\Sigma^{\prime}=\\{1,2,\ldots,\sigma^{\prime}\\}$.

Effectively, $M^{\approx}_{\mbox{\boldmath$x_{R}$}}$ defines an undirected
graph $G^{\approx}_{\mbox{\boldmath$x_{R}$}}=(V,E)$ on $m$ vertices, where
there exists an edge $(i,j)\in E$ if and only if
$M^{\approx}_{\mbox{\boldmath$x_{R}$}}[i,j]=1$. The match relation $\approx$
is necessarily both reflexive ($M^{\approx}_{\mbox{\boldmath$w$}}[i,i]=1$) and
symmetric
($M^{\approx}_{\mbox{\boldmath$w$}}[i,j]=M^{\approx}_{\mbox{\boldmath$w$}}[j,i])$
for any string $w$. If in addition our string
$\mbox{\boldmath$w$}=\mbox{\boldmath$x_{R}$}$ is regular, it follows
immediately from our definition that the match relation is transitive:

$M^{\approx}_{\mbox{\boldmath$x_{R}$}}[i,j_{1}]=M^{\approx}_{\mbox{\boldmath$x_{R}$}}[i,j_{2}]\Longleftrightarrow
M^{\approx}_{\mbox{\boldmath$x_{R}$}}[j_{1},j_{2}]=M^{\approx}_{\mbox{\boldmath$x_{R}$}}[i,j_{1}].$

Thus for a regular string $x_{R}$, algorithms $regular_{min}$ and
$regular_{min\\_matrix}$ effectively compute the transitive closure of the
match relation $\approx$ on $x_{R}$ (equivalently, of the adjacent vertices in
$G^{\approx}_{\mbox{\boldmath$x_{R}$}}$); that is, they identify the maximum
sets of positions that match in $x_{R}$ (the cliques in
$G^{\approx}_{\mbox{\boldmath$x_{R}$}}$).

In the literature the Floyd-Warshall algorithms [27, 28] are the standard for
computing the transitive closure on a graph $G=(V,E)$, with $|V|=m$. These
algorithms execute in time $\mathcal{O}(m^{3})$, and it is a long-standing
open problem whether a faster algorithm exists. They are very general, not
assuming the reflexive and symmetric conditions that hold in our case.
Nevertheless, we have:

###### Lemma 5

For a relation on $m$ objects that is reflexive and symmetric, the transitive
closure can be computed in $\mathcal{O}(m^{2})$ time.

##  4 Strings from the Maximal Palindrome Array

Given $\mbox{\boldmath$x$}=\mbox{\boldmath$x$}[1..n]$, a substring
$\mbox{\boldmath$u$}=\mbox{\boldmath$x$}[i..j]$, $1\leq i\leq j\leq n$, of
length $\ell=j\\!-\\!i\\!+\\!1$ is said to be a palindrome if
$\mbox{\boldmath$x$}[i\\!+\\!h]\approx\mbox{\boldmath$x$}[j\\!-\\!h]$ for
every $h\in 0..\lfloor\ell/2\rfloor$; a maximal palindrome if one of the
following holds: $i=1$, $j=n$, or
$\mbox{\boldmath$x$}[i\\!-\\!1]\not\approx\mbox{\boldmath$x$}[j\\!+\\!1]$. The
centre of a palindrome $u$ is at position $i\\!+\\!\frac{\ell\\!-\\!1}{2}$,
which is not an integer for odd $\ell$. Thus to facilitate discussion of the
palindromic structure of $x$, we form the string

$\mbox{\boldmath$x^{*}$}[1..m]=\\#x_{1}\\#x_{2}\\#\cdots\\#x_{n}\\#,$

where $\\#\not\in\Sigma$ and $m=2n\\!+\\!1$. Now every palindromic substring
of $x$ of length $\ell\geq 1$ maps into a palindromic substring of $x^{*}$ of
odd length $d=2\ell\\!+\\!1$, and every palindrome in $x^{*}$ has an integral
centre position. We call $d$ the diameter and $r=\lfloor d/2\rfloor$ the
radius of the palindrome in $x^{*}$.

We can now define the maximal palindrome array
$\mbox{MP}=\mbox{MP}_{\mbox{\boldmath$x^{*}$}}$ of $x^{*}$: for every
$i\in\\{1,\dots,m\\}$, if $\mbox{\boldmath$x^{*}$}[i]=\\#$ and
$\mbox{\boldmath$x^{*}$}[i\\!-\\!1]\not\approx\mbox{\boldmath$x^{*}$}[i\\!+\\!1]$,
then $\mbox{MP}[i]=0$ (radius zero); otherwise, $\mbox{MP}[i]\geq 1$ is the
radius of the maximal palindrome centred at position $i$. We assume that
$\mbox{\boldmath$x^{*}$}[0]=\mbox{\boldmath$x^{*}$}[m+1]=\emptyset$. For
example, $\mbox{MP}_{\mbox{\boldmath$x^{*}$}}$ derived from
$\mbox{\boldmath$x$}=aabac$ is as follows:

$\begin{array}[]{rcccccccccc}\scriptstyle 1&\scriptstyle 2&\scriptstyle
3&\scriptstyle 4&\scriptstyle 5&\scriptstyle 6&\scriptstyle 7&\scriptstyle
8&\scriptstyle 9&\scriptstyle 10&\scriptstyle 11\\\
\mbox{\boldmath$x^{*}$}=\\#&a&\\#&a&\\#&b&\\#&a&\\#&c&\\#\\\
\mbox{MP}_{\mbox{\boldmath$x^{*}$}}=0&1&2&1&0&3&0&1&0&1&0\end{array}$ (4)

The most general form of the palindrome array is given by

$\mbox{MP}=0i_{2}i_{3}\cdots i_{m-1}0,$ (5)

where for every $j\in\\{2,\dots,m-1\\}$:

  * (a)

$i_{j}\in(1\\!-\\!j\bmod 2)..\min(j\\!-\\!1,m\\!-\\!j)$;

  * (b)

$i_{j}$ is odd if and only if $j$ is even.

Any array satisfying (5) is said to be feasible.

###### Lemma 6

There exists a string corresponding to every feasible palindrome array.

Proof. Suppose that a feasible palindrome array
$\mbox{MP}=\mbox{MP}_{\mbox{\boldmath$x^{*}$}}[1..m]$ is given for some odd
positive integer $m$. We show how to construct a corresponding $x^{*}$. First,
for every odd $c\in\\{1,\dots,m\\}$, we may of course assign
$\mbox{\boldmath$x^{*}$}[c]\leftarrow\\#$. Suppose that the even positions $c$
in $x^{*}$ are initially empty. For every $c\in\\{3,\dots,m\\!-\\!2\\}$ such
that $\mbox{MP}[i]=r\geq 2$, add a unique character to each pair of positions
$c\\!-\\!k,c\\!+\\!k$ in $x^{*}$, where

  * $\bullet$

($c$ even, $r$ odd) $k=2,4,\ldots,r\\!-\\!1$;

  * $\bullet$

($c$ odd, $r$ even) $k=1,3,\ldots,r\\!-\\!1$.

Finally, assign a unique character to each position that remains empty. The
resulting (perhaps indeterminate) string will have MP as its palindrome array.

Applying the construction of Lemma 6 to
$\mbox{MP}_{\mbox{\boldmath$x^{*}$}}=01210301010$ given in (4) yields a string
such as:

$\begin{array}[]{rcccccccccc}\scriptstyle 1&\scriptstyle 2&\scriptstyle
3&\scriptstyle 4&\scriptstyle 5&\scriptstyle 6&\scriptstyle 7&\scriptstyle
8&\scriptstyle 9&\scriptstyle 10&\scriptstyle 11\\\
\mbox{\boldmath$x^{*}$}=\\#&a&\\#&\\{a,b\\}&\\#&c&\\#&b&\\#&d&\\#\\\
\mbox{MP}_{\mbox{\boldmath$x^{*}$}}=0&1&2&1&0&3&0&1&0&1&0\end{array}$ (6)

Note that, since the triple $(4,2,8)$ is intransitive
($\mbox{\boldmath$x$}[2]\not\approx\mbox{\boldmath$x$}[8]$), $x^{*}$ is
indeterminate. However, as we have seen in (4), the regular string
$\\#a\\#a\\#b\\#a\\#c\\#$ has the same palindrome array: a palindrome array
can correspond to both a regular and an indeterminate string!

To each position $c\in\\{1,\dots,m\\}$ of a feasible MP array we associate a
pair of integers $(i,j)$ such that $i=c-\mbox{MP}[c]-1$ and
$j=c+\mbox{MP}[c]+1$; then, provided $0<i,j<m+1$, we must have
$\mbox{\boldmath$x^{*}$}[i]\not\approx\mbox{\boldmath$x^{*}$}[j]$. We call
this pair $(i,j)$ the forbidden pair with respect to $c$, and the characters
at $\mbox{\boldmath$x^{*}$}[i],\mbox{\boldmath$x^{*}$}[j]$ forbidden
characters with respect to $c$. For processing purposes, it will be convenient
to assume that
$\mbox{\boldmath$x^{*}$}[0]=\mbox{\boldmath$x^{*}$}[m+1]=\emptyset$. We denote
by FP the set of all forbidden pairs with respect to each centre
$c\in\\{1,\dots,m\\}$. See (7) for an example.

Consider the feasible MP array given in (7). This array does not correspond to
any regular string because the triple $(6,2,4)$ is intransitive
($\mbox{\boldmath$x^{*}$}[2]\not\approx\mbox{\boldmath$x^{*}$}[4]$), since the
pair $(2,4)$ is a forbidden pair with respect to the centre $3$. Indeed, any
triple of $x^{*}$ which includes a forbidden pair is intransitive, resulting
in an indeterminate string. However, if a given MP array does correspond to a
regular string, we will say that it is regular.

$\begin{array}[]{rcccccc}c\qquad 1&2&3&4&5&6&7\\\ MP\qquad 0&1&0&3&2&1&0\\\
\mbox{\boldmath$x^{*}$}\qquad\\#&1&\\#&\\{2,3\\}&\\#&\\{1,3\\}&\\#\\\
\mbox{FP}\qquad(0,2)&(0,4)&(2,4)&(0,8)&(2,8)&(4,8)&(6,8)\end{array}$ (7)

In order to characterize MP arrays, it is useful to introduce Manacher’s
condition [29], restated in [23], and further restated here.

In $\mbox{MP}=\mbox{MP}_{\mbox{\boldmath$x^{*}$}}$, we consider each centre
$c$ of a palindrome of radius $r=\mbox{MP}[c]$, where for $c$ even, $r\geq 3$,
and for $c$ odd, $r\geq 2$. Then we must have
$\mbox{\boldmath$x^{*}$}[c\\!-\\!k]\approx\mbox{\boldmath$x^{*}$}[c\\!+\\!k]$,
where $1\leq k\leq r$. We then have

###### Definition 1

[Manacher’s condition] Let $r_{\ell}=\mbox{MP}[c\\!-\\!k]$ and
$r_{r}=\mbox{MP}[c\\!+\\!k]$, for each $1\leq k\leq r$, where
$r=\mbox{MP}[c]$. Every position $c$ in a regular palindrome array
$\mbox{MP}=\mbox{MP}_{\mbox{\boldmath$x^{*}$}}$ satisfies the following:

  * (a)

if $r_{\ell}\neq r\\!-\\!k$ then $r_{r}=\min(r_{\ell},r\\!-\\!k)$ else
$r_{r}\geq r_{\ell}$;

  * (b)

if $r_{r}\neq r\\!-\\!k$ then $r_{\ell}=\min(r_{r},r\\!-\\!k)$ else
$r_{\ell}\geq r_{r}$.

For completeness, we outline here Manacher’s algorithm to construct an MP
array for a given string $x^{*}$ of scope $1$. The algorithm scans $x^{*}$
from left to right and evaluates centres to compute $\mbox{MP}[c]$. While
evaluating a centre $c$ and each value of the range $k$, it checks whether
$r_{\ell}=r-k$; if so, it stops evaluating centre $c$ and moves to evaluating
centre $c\\!+\\!k$; otherwise it assigns
$r_{r}\leftarrow\min(r_{\ell},r\\!-\\!k)$ and continues evaluating the same
centre $c$ and the next range value $k+1$.

In [29] it is shown that, for every palindrome in string $x^{*}$ such that
$S(\mbox{\boldmath$x^{*}$})=1$, Manacher’s condition must hold. Thus, by Lemma
1, Manacher’s condition holds for every regular string; that is, for every
string whose triples are all transitive.

On the other hand, note that in example (7), for $c=4$ we have

$r=\mbox{MP}[4]=3,\ k=1,\ r_{\ell}=\mbox{MP}[3]=0,\ r_{r}=\mbox{MP}[5]=2,$

so that, by Definition 1(a), since $r_{\ell}\neq r\\!-\\!k$, therefore
$r_{r}=\min(0,2)=0$ should hold, which is false. Thus for this indeterminate
string, Manacher’s condition does not hold.

The above suggests extending the construction of Lemma 6 so as to yield,
whenever possible, a regular string corresponding to a given palindrome array.
See Figure 4.

The procedure $construct$ takes a feasible MP array as input and returns a
lex-least regular string $x^{*}$ if MP is regular; otherwise it returns an
indeterminate string. This procedure is based on the Manacher’s algorithm
presented in [29]. To ensure that the resulting string, if regular, is a lex-
least string, it maintains for each centre $c$ a set $\mbox{FS}[c]$ containing
the indices of the forbidden characters.

function $construct(\mbox{MP},m;\ \mbox{\boldmath$x^{*}$},\sigma,regular)$
$\triangleright$ $\mbox{MP}[1..m]$ is assumed to be feasible, and
$m=|\mbox{\boldmath$x^{*}$}|$.
$\triangleright$ $\mbox{FS}[1..m]$ gives the index position of all forbidden
characters w.r.t each centre of the MP array.
$\triangleright$ $empty[1..m]$ is a Boolean array initially set to true, where
$\triangleright$ $empty[c]=true$ whenever $update\mbox{FS}$ has not been
called for centre $c$.
$regular\leftarrow\tt{true};\ \sigma\leftarrow 0;\
\mbox{\boldmath$x^{*}$}[1]\leftarrow\\#;\ \mbox{FS}[1]\leftarrow\emptyset$
for $c\leftarrow 2$ to $m\\!-\\!1$ step 2 do  $\triangleright$ Initialize
$x^{*}$ and FS array.
$\mbox{\boldmath$x^{*}$}[c]\leftarrow 0;\ \mbox{FS}[c]\leftarrow\emptyset$
$\mbox{\boldmath$x^{*}$}[c+1]\leftarrow\\#;\
\mbox{FS}[c+1]\leftarrow\emptyset$
$empty[1..2]=false;\ empty[3..m]=true$
$\sigma\leftarrow\sigma\\!+\\!1;\ \mbox{\boldmath$x^{*}$}[2]\leftarrow\sigma$
for $c\leftarrow 3$ to $m\\!-\\!1$
$r\leftarrow\mbox{MP}[c]$
if $regular$ and $empty[c]$ then
$empty[c]\leftarrow false;\ update\mbox{FS}(c,r,m,\mbox{FS})$
if $r>1$ then
$nextc\leftarrow c\\!+\\!r\\!+\\!1$
for $k\leftarrow r$ downto $1$ do

$r_{\ell}=\mbox{MP}[c\\!-\\!k];\ r_{r}=\mbox{MP}[c\\!+\\!k]$
$\triangleright$ $MC$ is a function that tests Manacher’s condition
$\triangleright$ for centre $c$, radius $r$ and range $k$.
if $regular$ and $MC(c,r,k)$ then
if $empty[c\\!+\\!k]$ then
$empty[c\\!+\\!k]\leftarrow false;\
update\mbox{FS}(c\\!+\\!k,r_{r},m,\mbox{FS})$
if $\mbox{\boldmath$x^{*}$}[c\\!+\\!k]=0$ then
$\mbox{\boldmath$x^{*}$}[c\\!+\\!k]\leftarrow\mbox{\boldmath$x^{*}$}[c\\!-\\!k]$
if $r_{\ell}=r-k$ and $r_{r}>r_{\ell}$ then $nextc\leftarrow c+k$
else
$regular\leftarrow false$

if $c\\!+\\!k\mod 2=0$ and
$\mbox{\boldmath$x^{*}$}[c\\!-\\!k]\not\approx\mbox{\boldmath$x^{*}$}[c\\!+\\!k]$
then
$\sigma\leftarrow\sigma\\!+\\!1;\
\mbox{\boldmath$x^{*}$}[c\\!-\\!k]\stackrel{{\scriptstyle+}}{{\leftarrow}}\sigma;\
\mbox{\boldmath$x^{*}$}[c\\!+\\!k]\stackrel{{\scriptstyle+}}{{\leftarrow}}\sigma$
$k\leftarrow k\\!-\\!1$
if $\mbox{\boldmath$x^{*}$}[c]=0$ then  $\triangleright$ Fill empty position
at centre.
if $regular$ then
$\mbox{\boldmath$x^{*}$}[c]\leftarrow$ Lex-least character not in
$\mbox{FS}[c]$
else $\sigma\leftarrow\sigma\\!+\\!1;\
\mbox{\boldmath$x^{*}$}[c]\stackrel{{\scriptstyle+}}{{\leftarrow}}\sigma$
if $regular$ then $c\leftarrow nextc$
else $c\leftarrow c\\!+\\!1$
return $x^{*}$

Figure 4: Given a feasible palindrome array MP, $construct$ if possible
produces a corresponding lex-least regular string $x^{*}$ of scope 1 on an
integer alphabet $\Sigma=\\{1,2,.\ldots\\}$. If such a string is not possible,
then on exit $regular=\tt{false}$ and $x^{*}$ is an indeterminate string on
$\Sigma$ corresponding to MP.

procedure $update\mbox{FS}(c,r,m,\mbox{FS})$
if $c\\!-\\!r\\!-\\!1\neq 0$ and $c\\!+\\!r\\!+\\!1\neq m\\!+\\!1$ then
$\mbox{FS}[c\\!+\\!r\\!+\\!1]\stackrel{{\scriptstyle+}}{{\leftarrow}}c-r-1$

Figure 5: Given centre $c$ and its radius $r$, $update\mbox{FS}$ updates the
FS array at the left position in the forbidden pair with respect to $c$.

In procedure $construct$ the output string is first initialized with $0$ at
even positions and $\\#$ at odd positions. Then $\mbox{\boldmath$x^{*}$}[2]$
is set to $1$, as we are interested in the lex-least regular $x^{*}$, if it
exists. Next we examine a centre $3\leq c\leq m\\!-\\!1$ and update the
$\mbox{FS}[c]$ set based on its forbidden pair. If the string
$\mbox{\boldmath$x^{*}$}[1..c\\!-\\!1]$ constructed so far is regular and the
centre $c$ and range $k$ satisfy Manacher’s condition, we continue to
construct the regular string by copying the previously filled letter
$\mbox{\boldmath$x^{*}$}[c\\!-\\!k]$ to its corresponding matching position
$c\\!+\\!k$. Whenever there is a choice of filling an empty position — that
is, when $\mbox{\boldmath$x^{*}$}[c]=0$ — the lex-least character which is not
in the forbidden set of characters $\mbox{FS}[c]$ is chosen. Note that we use
the same strategy as presented in Manacher’s algorithm [29] to avoid
evaluating every centre if MP is regular. However, unlike Manacher’s
algorithm, instead of evaluating a new centre when $r_{\ell}=r-k$ and
$r_{r}>r_{\ell}$, we record the next centre to be evaluated, and finish
evaluating the current centre. After which we move to the recorded centre and
check if Manacher’s condition is satisfied.

Furthermore, to avoid invoking the $update\mbox{FS}$ procedure repeatedly on a
centre $c$, we use a Boolean array $empty$ of length $m$, such that
$empty[c]=true$ if and only if the centre $c$ has not been used to update the
FS array; otherwise, we set $empty[c]\leftarrow false$. If a given centre $c$
and range $k$ do not satisfy Manacher’s condition, $regular$ is set to $false$
and every subsequent letter match including the current one is achieved by
adding a new character to the letters at positions $c\\!-\\!k$ and
$c\\!+\\!k$, if they are even. Furthermore, for the remainder of the MP array
all centres are examined.

###### Lemma 7

Let $x^{*}$ be the string produced by procedure $construct$. Then
$S(\mbox{\boldmath$x^{*}$})=1\Leftrightarrow\mbox{\boldmath$x^{*}$}$ is
regular.

Proof. ($\Rightarrow$) Since $S(\mbox{\boldmath$x^{*}$})=1$, the regularity of
$x^{*}$ is immediate, as for all positions $1\leq i,j\leq m$,
$\mbox{\boldmath$x^{*}$}[i]\approx\mbox{\boldmath$x^{*}$}[j]\Leftrightarrow\mbox{\boldmath$x^{*}$}[i]=\mbox{\boldmath$x^{*}$}[j]$.
Then any triple in $x^{*}$ is transitive by the associative property of
equality. Therefore $x^{*}$ is regular.

($\Leftarrow$) $x^{*}$ is regular only if Manacher’s condition holds for every
centre $c$, radius $r$ and range $k$. In such a case $construct$ either copies
existing letters of scope one or fills an empty position with a new character
to produce $x^{*}$. Therefore $S(\mbox{\boldmath$x^{*}$})=1$.

###### Theorem 1

Let $x^{*}$ be the string produced by the procedure $construct$ on an input
MP. Then $x^{*}$ is regular $\Leftrightarrow$ MP is regular.

Proof. ($\Rightarrow$) $x^{*}$ is regular only if Manacher’s condition holds
for every centre $c\in\\{1,\ldots,m\\}$, and for every corresponding radius
$r$ and range $k$. Since Manacher’s condition holds, it follows from the
result in [29] that MP is regular.

($\Leftarrow$) From [29], MP is regular only if Manacher’s condition holds.
Since the condition holds, during the execution of $construct$ an empty
position is filled either by copying previously occurring letters of scope one
or by a new character. Thus the resulting string is of scope $1$, so that from
Lemma 7, $x^{*}$ is regular.

Using the two examples given below in (8) and (9), we illustrate the execution
of procedure $construct$.

In (8) the positions corresponding to all odd centres are filled with $\\#$
and positions corresponding to all even centres are filled with $0$.
Furthermore, $\mbox{FS}[1..m]\leftarrow\emptyset$, $empty[1..2]\leftarrow
false$ and $empty[3..m]\leftarrow true$. Then for centre $c=2$,
$\mbox{\boldmath$x^{*}$}[2]\leftarrow 1$, and for centre $c=3$,
$FS[4]\leftarrow\\{2\\}$ and $empty[3]\leftarrow false$. At centre $c=4$,
$empty[4]\leftarrow false$, and since $r=3$ we check if Manacher’s condition
holds for $k=3,2,1$. As we do this, we also check whether $empty[c+k]$ is
$true$; if so, we set it to $false$ and compute the FS set w.r.t to these
centres, thereby setting $\mbox{FS}[6]$ and $\mbox{FS}[8]$ to
$\\{4\\},\\{4,6\\}$ respectively. Since Mancher’s condition holds, the setting
at position $\mbox{\boldmath$x^{*}$}[2]$ is copied into
$\mbox{\boldmath$x^{*}$}[6]$; next, since position
$\mbox{\boldmath$x^{*}$}[4]=0$, it is filled with the next lex-least character
which is not equal to a character at any index position in the forbidden set
$\mbox{FS}[4]=\\{2\\}$ — that is, $2$.

Similarly for centre $c=8$, $empty[8..15]\leftarrow false$,
$\mbox{FS}[10]\leftarrow\\{8\\},\mbox{FS}[12]\leftarrow\\{8,10\\}$. Since
Manacher’s condition holds for all $k=7,6,\ldots,1$,
$\mbox{\boldmath$x^{*}$}[2]$, $\mbox{\boldmath$x^{*}$}[4]$ and
$\mbox{\boldmath$x^{*}$}[6]$ are copied into
$\mbox{\boldmath$x^{*}$}[14],\mbox{\boldmath$x^{*}$}[12]$ and
$\mbox{\boldmath$x^{*}$}[10]$, respectively. Finally, since
$\mbox{\boldmath$x^{*}$}[8]=0$, the position is filled with the next lex-least
character $3$ which is not equal to a character at any index position in the
forbidden set $\mbox{FS}[8]=\\{4,6\\}$. The resulting string $x^{*}$ is
regular and lex-least.

$\begin{array}[]{rcccccccccccccccc}\scriptstyle 1&\scriptstyle 2&\scriptstyle
3&\scriptstyle 4&\scriptstyle 5&\scriptstyle 6&\scriptstyle 7&\scriptstyle
8&\scriptstyle 9&\scriptstyle 10&\scriptstyle 11&\scriptstyle 12&\scriptstyle
13&\scriptstyle 14&\scriptstyle 15\\\ MP=0&1&0&3&0&1&0&7&0&1&0&3&0&1&0\\\
\mbox{\boldmath$x^{*}$}=\\#&1&\\#&2&\\#&1&\\#&3&\\#&1&\\#&2&\\#&1&\\#\\\
FS=\emptyset&\emptyset&\emptyset&\\{2\\}&\emptyset&\\{4\\}&\emptyset&\\{4,6\\}&\emptyset&\\{8\\}&\emptyset&\\{8,10\\}&\emptyset&\\{12\\}&\emptyset\\\
\end{array}$ (8)

Observe that the MP array in (9) only differs from the MP array in (8) at
position $12$. However, the MP array in (9) does not correspond to any regular
string, since, as we shall see, it fails Manacher’s condition for $c=8,\ r=7$,
and $k=4$. In (9) $construct$ produces the same string as in (8) up until
$c=7$. Then at centre $c=8$, $\mbox{\boldmath$x^{*}$}[2]$ is first copied into
$\mbox{\boldmath$x^{*}$}[14]$. However, since for $k=4$ the MP array fails
Manacher’s condition, a new lex-least character $3$ is added to the letters at
positions $4$ and $12$. Then at positions $6$ and $10$, a new character $4$ is
added to both $\mbox{\boldmath$x^{*}$}[6]$ and $\mbox{\boldmath$x^{*}$}[10]$.
Finally, since $\mbox{\boldmath$x^{*}$}[8]=0$, it is filled with another new
character $5$.

$\begin{array}[]{rcccccccccccccccc}\scriptstyle 1&\scriptstyle 2&\scriptstyle
3&\scriptstyle 4&\scriptstyle 5&\scriptstyle 6&\scriptstyle 7&\scriptstyle
8&\scriptstyle 9&\scriptstyle 10&\scriptstyle 11&\scriptstyle 12&\scriptstyle
13&\scriptstyle 14&\scriptstyle 15\\\ MP=0&1&0&3&0&1&0&7&0&1&0&1&0&1&0\\\
\mbox{\boldmath$x^{*}$}=\\#&1&\\#&\\{2,3\\}&\\#&\\{1,4\\}&\\#&5&\\#&4&\\#&3&\\#&1&\\#\\\
\end{array}$ (9)

We now discuss the running time complexity of $construct$. This is dependent
on the input MP array. If MP is regular, then $construct$ yields a lex-least
regular string in $\mathcal{O}(n)$ time; otherwise it yields an indeterminate
string in $\mathcal{O}(n^{2})$ time. We remark that to avoid having $\sigma$
in the running time, we use the strategy discussed in [23] to fill the lex-
least character not in the list of forbidden characters at centre $c$. Here we
briefly outline the strategy: The paper [23] uses a bit vector $F$ of length
$n$ where the element $F[h]$ corresponds to the $h$-th lex-least least
character. Initially all elements of $F$ are set to $0$. If a character
$\mbox{\boldmath$x$}[j]$ is forbidden w.r.t the character
$\mbox{\boldmath$x$}[i]$, and if $\mbox{\boldmath$x$}[j]$ is the $h$-th lex-
least character, then $F[h]$ is set to $1$. After finding all forbidden
characters for $\mbox{\boldmath$x$}[i]$ and setting the $F$ vector
appropriately, the lex-least character for $\mbox{\boldmath$x$}[i]$ is set
equal to the $k$-th lex-least character, where $k$ is the first (or smallest)
index such that $F[k]=0$.

If MP is regular, then similar to Manacher’s algorithm, not every centre is
evaluated to yield a regular string. Suppose $c$, $1\leq c\leq m$, is the
least centre for which the Manacher’s test is performed and is satisfied.
Then, two cases arise. First, there exists a $k$ (in $construct$ we consider
the minimum $k$), $1\leq k\leq r$, where the following subcondition of
Manacher’s condition (Definition 1) is satisfied: $r_{\ell}=r\\!-\\!k$ and
$r_{r}>r_{\ell}$. Second, when the subcondition is not satisfied, all the
palindromes that arise at centres $c^{\prime}\leq c\\!+\\!r$ are contained in
the palindrome at $c$ and also satisfy Manacher’s condition. Therefore, to
avoid duplication the next centre to be evaluated is $c\\!+\\!r\\!+\\!1$.

In the former case, however, the palindrome at centre $c+k$ extends beyond the
right edge of the palindrome centred at $c$. Therefore, $c\\!+\\!k$ is the
next centre to be evaluated. However, since $c$ satisfies Manacher’s, a
shorter palindrome of length $r\\!-\\!k$ at centre $c\\!+\\!k$ also occurs at
centre $c\\!-\\!k$. Therefore, we only need to check the positions occurring
after the first $r\\!-\\!k$ positions on both sides of $c\\!+\\!k$. In both
these cases a position in the MP array is visited at most twice. Therefore,
the running time of $construct$ to yield a regular string is $\mathcal{O}(n)$.

If MP is not regular, after the first centre that fails Manacher’s test, every
centre is evaluated, and as a result $construct$ yields an indeterminate
string in $\mathcal{O}(n^{2})$ time. However, note that the running time for
an MP array that is not regular largely depends on the centre that fails the
Manacher’s test. If the centre lies close to the end of the array, then the
indeterminate string is constructed in $\mathcal{O}(n)$ time; otherwise it
takes $\mathcal{O}(n^{2})$ time. Thus we have:

###### Theorem 2

Given a regular MP array of length $m=2n\\!+\\!1$, procedure $construct$
yields a lex-least regular string in $\mathcal{O}(n)$ time.

###### Theorem 3

Given a MP array of length $m=2n\\!+\\!1$ that is not regular, procedure
$construct$ yields an indeterminate string in $\mathcal{O}(n^{2})$ time.

We remark that our algorithm $construct$ is similar to the approach presented
in [23, Algorithm 2] to construct a regular string if MP is regular. The key
differences between $construct$ and their approach is that their algorithm
sometimes verifies an MP array which is not regular to be regular, and
therefore outputs an incorrect lex-least regular string $w$. To correct this,
they execute Manacher’s algorithm [23, Algorithm 1] on $w$ to compute its
palindrome array $\mbox{MP}_{\mbox{\boldmath$x$}}$. Then they output $w$ if
and only if $\mbox{MP}_{\mbox{\boldmath$x$}}=\mbox{MP}$. We on the other hand
use a direct approach — our algorithm outputs a regular string if and only if
the input MP array is regular. Furthermore, if MP is not regular, their
algorithm simply exits, while $construct$ on the other hand yields an
indeterminate string.

Consider the example shown in Figure 6. For the given MP array, $construct$
produces the string $x^{*}$. Observe that not all the centres $4-11$ satisfy
Manacher’s condition. Furthermore, if a centre $c$ and a range $k$ fail
Manacher’s condition, it is not necessarily the case that the centre $c+k$
also fails it. For example, for centre $c=8$, and range $k=3$, Manacher’s
condition fails; however, the centre $c+k=11$ satisfies it.

$\begin{array}[]{rcccccccccccccccc}\scriptstyle 1&\scriptstyle 2&\scriptstyle
3&\scriptstyle 4&\scriptstyle 5&\scriptstyle 6&\scriptstyle 7&\scriptstyle
8&\scriptstyle 9&\scriptstyle 10&\scriptstyle 11&\scriptstyle 12&\scriptstyle
13\\\ MP=0&1&0&3&2&3&6&3&4&1&2&1&0\\\
\mbox{\boldmath$x^{*}$}=\\#&\\{1,5\\}&\\#&\\{2,3,4,6\\}&\\#&\\{1,3,7,8,9\\}&\\#&\\{4,7,10\\}&\\#&\\{6,8,10,11\\}&\\#&\\{5,9,11\\}&\\#\\\
\mbox{FS}=\emptyset&\emptyset&\emptyset&\\{2\\}&\emptyset&\emptyset&\emptyset&\\{2\\}&\emptyset&\\{2\\}&\emptyset&\\{4,8\\}&\emptyset\end{array}$
Figure 6: Given an MP array that is not regular, procedure $construct$
produces the indeterminate string $x^{*}$.

As can be observed in the example shown in Figure 6, the number of centres
that fail Manacher’s condition is of order $n$, where $n$ is the length of the
string. Therefore, we are forced to evaluate $\mathcal{O}(n)$ centres in this
example. Hence we state the following:

###### Conjecture 1

To construct an indeterminate string over an MP array of length $m=2n\\!+\\!1$
that is not regular requires at least $\Omega(n^{2})$ time.

##  5 Conclusion and Open Problems

In this paper we have characterized regular strings as those whose triples are
all transitive; the strings for which this is not true are called
indeterminate. A new approach based on the transitivity of matching among the
regular letters of a string enables us to precisely define strings and
eliminate false positive cases seen in the traditional definition of
indeterminate strings. Based on this new definition, we present a linear time
algorithm REGULAR that checks the regularity of the given string $x$ by
checking the regularity of its corresponding reduced string $x_{R}$, and as a
byproduct yields a lex-least regular string that is isomorphic to $x$ whenever
$x$ is regular.

To check the regularity of $x_{R}$, we present two algorithms $regular_{min}$
and $regular_{min\\_matrix}$, which illustrate an interesting connection
between the matching relation defined on the letters of $x$ and the
computation of the relation’s transitive closure. Many algorithms exist to
compute the transitive closure of a relation in $\mathcal{O}(n^{3})$ time.
However, it is a long standing open problem whether this complexity can be
reduced. We show that for important special cases, the transitive closure can
be computed in $\mathcal{O}(n^{2})$ time using the $regular_{min\\_matrix}$
function.

Furthermore, we consider the reverse engineering problem of constructing a
string (regular or indeterminate) from the given palindrome array. We present
the algorithm $construct$ to output a lex-least regular string, if it exists,
in $\mathcal{O}(n)$ time; otherwise the algorithm returns an indeterminate
string in $\mathcal{O}(n^{2})$ time. An immediate question arises whether an
algorithm faster than $construct$ exists to output an indeterminate string. It
would also be interesting to develop an algorithm that yields an indeterminate
string over a minimum alphabet, corresponding to an MP array that is not
regular. Furthermore, although the running time complexity of REGULAR is
$\mathcal{O}(n)$, the constant hidden in it could in extreme cases be rather
large – is it possible to reduce the size of this constant?

More generally, a new definition of regularity in strings may affect the
relationship between strings and the data structures mentioned in the
Introduction that facilitate their use: border array, cover array, prefix
array, and suffix array. A string containing indeterminate letters may now
actually be regular, provided all its triples are transitive: can these
important arrays be computed accordingly in linear time?

Conversely, what effect does this new definition have on the “reverse
engineering” problem related to these arrays? We have presented in Section 4
an algorithm that reverse engineers the palindrome array to a regular string,
whenever possible. There exist algorithms to reverse engineer the other array
noted above — can they be modified/extended to yield equivalent results? Can
the time requirements of these algorithms be reduced to near-linear, except in
pathological cases?

## Acknowledgments

We thank the reviewers for carefully reading the manuscript and providing
insightful comments which led to substantial improvements in the manuscript.

#### Funding:

Louza was supported by Grant $\\#$2017/09105-0 from the São Paulo Research
Foundation (FAPESP). Mhaskar and Smyth were supported by Grant 36797 from the
Natural Sciences & Engineering Research Council of Canada (NSERC).

## References

  * [1] M. Fischer, M. Paterson, String matching and other products, in: R. Karp (Ed.), Complexity of Computation,, American Mathematical Society, 1974, pp. 113–125.
  * [2] K. Abrahamson, Generalized string matching, SIAM Journal of Computing 16 (6) (1987) 1039–1051.
  * [3] F. Blanchet-Sadri, Algorithmic Combinatorics on Partial Words, Chapman & Hall CRC, 2008.
  * [4] W. F. Smyth, S. Wang, A new approach to the periodicity lemma on strings with holes, Theoret. Comput. Sci. 410 (43) (2009) 4295 – 4302.
  * [5] C. S. Iliopoulos, L. Mouchard, M. S. Rahman, A new approach to pattern matching in degenerate DNA/RNA sequences and distributed pattern matching, Math. in Computer Science (2008) 557–569.
  * [6] C. Iliopoulos, M. S. Rahman, M. Voráček, L. Vagner, Finite automata based algorithms on subsequences and supersequences of degenerare strings, J. Discrete Algorithms 6 (2) (2010) 117–130.
  * [7] C. Iliopoulos, R. Kundu, S. P. Pissis, Efficient pattern-matching in elastic-degenerate strings, Proc. Language & Automata Theory & Applications (LATA 2017), LNCS 10168 (2017) 131–142.
  * [8] J. Holub, W. F. Smyth, Algorithms on indeterminate strings, Proc. 14th Australasian Workshop on Combinatorial Algs. (AWOCA) (2003) 36–45.
  * [9] J. Holub, W. F. Smyth, S. Wang, Fast pattern–matching on indeterminate strings, Proc. 16th Australasian Workshop on Combinatorial Algorithms (2005) 415–428.
  * [10] J. Holub, W. F. Smyth, S. Wang, Hybrid pattern-matching algorithms on indeterminate strings, in: J. W. Daykin, M. Mohamed, K. Steinhofel (Eds.), London Algorithmics and Stringology, King’s College Texts in Algorithmics, 2006, pp. 115–133.
  * [11] J. Holub, W. F. Smyth, S. Wang, Fast pattern–matching on indeterminate strings, J. Discrete Algorithms 6 (1) (2008) 37–50.
  * [12] W. F. Smyth, S. Wang, An adaptive hybrid pattern-matching algorithm on indeterminate strings, Internat. J. Foundations of Computer Science 20 (6) (2009) 985–1004.
  * [13] S. Nazeen, S. M. Rahman, R. Reaz, Indeterminate string inference algorithms, J. Discrete Algorithms 10 (2012) 23–34.
  * [14] M. F. Bari, M. S. Rahman, R. Shahriyar, Finding all covers of an indeterminate string in $o(n)$ time on average, in: J. Holub, J. Žďárek (Eds.), Proceedings of the Prague Stringology Conference 2009, 2009, pp. 263–271.
  * [15] A. Alatabbi, M. S. Rahman, W. F. Smyth, Inferring an indeterminate string from a prefix graph, J. Discrete Algorithms 32 (2015) 6–13.
  * [16] M. Christodoulakis, P. J. Ryan, W. F. Smyth, S. Wang, Indeterminate strings, prefix arrays and undirected graphs, Theoretical Comput. Sci. 600 (4) (2015) 34–48.
  * [17] H. Bannai, S. Inenaga, A. Shinohara, M. Takeda, Inferring strings from graphs and arrays., in: B. Rovan, P. Vojt’s (Eds.), Symp. on Mathematical Foundations of Computer Science, Vol. 2747 of Lecture Notes in Computer Science, Springer, 2003, pp. 208–217.
  * [18] J. Helling, P. J. Ryan, W. F. Smyth, M. Soltys, Constructing an indeterminate string from its associated graph, Theoret. Comput. Sci. 710 (2018) 88–96.
  * [19] F. Franek, W. Lu, P. J. Ryan, W. F. Smyth, Y. Sun, L. Yang, Verifying a border array in linear time (preliminary version), Proc. 10th Australasian Workshop on Combinatorial Algs. (AWOCA) School of Computing, Curtin University of Technology (1999) 26–33.
  * [20] F. Franek, S. Gao, W. Lu, P. J. Ryan, W. F. Smyth, Y. Sun, L. Yang, Verifying a border array in linear time, J. Combinatorial Maths. and Combinatorial Comput. 42 (2002) 223–236.
  * [21] J. Clément, M. Crochemore, G. Rindone, Reverse engineering prefix tables, in: Proc. 26th Symp. on Theoretical Aspects of Computer Science, 2009, pp. 289–300.
  * [22] J. W. Daykin, F. Franek, J. Holub, A. S. M. S. Islam, W. F. Smyth, Reconstructing a string from its Lyndon arrays, Theoret. Comput. Sci. 710 (2018) 44–51.
  * [23] T. I, S. Inenaga, H. Bannai, M. Takeda, Counting and verifying maximal palindromes, Proc. 17th Symposium on String Proocessing & Information Retrieval (SPIRE), LNCS 6393 (2010) 135–146.
  * [24] P. Procházka, J. Holub, On-line searching in IUPAC nucleotide sequences, in: E. D. Maria, A. L. N. Fred, H. Gamboa (Eds.), Proceedings of the 12th International Joint Conference on Biomedical Engineering Systems and Technologies (BIOSTEC 2019) - Volume 3: BIOINFORMATICS, Prague, Czech Republic, February 22-24, 2019, SciTePress, 2019, pp. 66–77.
  * [25] L. Huang, V. Popic, S. Batzoglou, Short read alignment with populations of genomes, Bioinformatics 29 (13) (2013) i361–i370.
  * [26] F. Gray, Pulse code communication.
  * [27] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 2nd Edition, MIT Press, Cambridge, MA, 2001.
  * [28] R. W. Floyd, Algorithm 97: Shortest path, Communications of the ACM 5 (6) (1962) 345.
  * [29] G. Manacher, A new linear-time on-line algorithm for finding the smallest initial palindrome of a string, J. Assoc. Comput. Mach. 22 (1975) 346–351.