119
Conjecture about Regularity ofPrefix Square Roots of Regular Languages

Kayoko Shikishima‐Tsuji
Center for Liberal Arts Education and Research

Tenri University

Zsolt Fazekas, Robert Mercas, Daniel Reidenbach gave the conjecture in [2] which

gives necessary and sufficient condition for the primitive prefix square root of aregular language L to be regular. The author gives a counterexample of theirconjecture and gives a new conjecture.
1. Preliminary

An alphabet V is a finite and nonempty set of symbols, called letters. Every finite

sequence of letters of V is called a word over V . Words over V together with theoperation of concatenation with the empty word \varepsilon form a free monoid V^{*} We denoteV^{+}=V^{*}-\{\varepsilon\}.
Let w=a_{1}a_{2}\cdots a_{n} where a_{1} , a_{2} ,, a_{n}\in V . The length of a word w is n and denoted by|w| and the length of the empty word \varepsilon is 0.
For a positive integerp,

V^{\leq p}=\{w\in V^{*}||w|\leq p\},V^{p}=\{w\in V^{*}||w|=p\}.
For a wordofw

isw=xyz

for x,y,z\in V^{*}, a prefix of w is x , a factor of w is y and a suffixz.

For a word w\in V^{+}, the following operations are defined in [1]:\bullet

prefix square reduction: \square 1(w)= { uv|w=uuv , for u\in V^{+},v\in V^{*} }120\bulletsuffix square reduction: |\square (w)= { uv|w=vuu , for u\in V^{+},v\in V^{*} }0prefix‐suffix square reduction: \square 1\square (w)=\square 1(w)\cup 1\square (w)For simplicity, we restrict the argument to prefix square reduction.

We define the bounded version for a fixed positive integer p :p ‐prefix square reduction:\bulletp\square 1(w)= { uv|w=uuv , for u\in V^{\leq}P , v\in V^{*} }For a language L , we have language:\square I(L)=\bigcup_{w\in L}\square |(w)The following languages are defined:\square |^{0}(w)=\{w\},\square 1^{k+1}(w)=\square |(\square |^{k+1}(w)) for any k\geq 0\square 1^{*}(w)=\bigcup_{k\geq 0}\square |^{k}(w)For a word w , the primitive prefix square root of w is the set \{u1u\in\square 1^{*}(w) and\square 1(u)=u\} and it is denoted by \sqrt[\square ]{w}| . The primitive bounded prefix square root ofw

isthe set { u|u\in_{p}\square 1^{*}(w) and p\square |(u)=u } and it is denoted by p\sqrt[\square ]{w}^{1} . For a language L , wedefine2.

\sqrt[\square ]{L}|=\bigcup_{w\in L}\sqrt[\square ]{w}| and p \sqrt[\square ]{L}^{1}=\bigcup_{w\in L}^{p}\sqrt[\square ]{w}^{1}.

Conjectures

Zsolt Fazekas, Robert Mercas, Daniel Reidenbach gave the following conjecture in[2].

Conjecture (in [2]). Let L be a regular language. The primitive prefix square root ofLis regular if and only if there exists some positive integer p such that \sqrt[\square 1]{L}=^{l^{7} \sqrt[\square ]{L}^{1}.

But, I give here the following counterexample and new conjecture.

Example. Let L=aab^{+}aab^{+}c wherea,b,c\in V . The language L is regular. On theother hand, the primitive prefix square root of L is \sqrt[\square ]{L}1=ab^{+}aab^{+}c\cup ab^{+}c and thislanguage is regular.

121
121
But, there is no positive integer p such that \psi^{\square }\overline{L}=^{p}\sqrt[\square ]{L}^{1}.
Now, we define a new term to describe our new conjecture: For a word w , if xx is a

non‐trivial prefix of w and X is prefix square free, then we say that xx is the minimal
prefix square of w.

Conjecture. Let L be a regular language. The primitive prefix square root of L isregular if and only if there exists positive integer N such that, for every word
W\in DI^{*}(L) , the length of the minimal prefix square of w is smaller than N.
References[1] P. Bottoni, A. Labella and V. Mitrana, Theor. Comput. Sci., 682, (2017), pp 49‐56.
[2] Szilárd Zsolt Fazekas, Robert Mercas, Daniel Reidenbach, On the Prefix‐Suffix

Duplication Reduction, International Journal of Foundations of Computer Science (inprint).

Center for Liberal Arts Education and Research

Tenri UniversityNara632‐8510

JAPANE‐mail address: tsuji@tenri‐u.ac.jp