Adding a NAND gate

IfP ends with any of

$, #, x²_a, x_ab⁰x_a, a, x_ac⁰x_a, x⁴_a, $⁰, #⁰, x⁷_a, b⁰, x_a¯ax_a, c⁰, x³_a, x⁶_a,

$, #, x²_a, x_ab⁰x_a, a, x_ac⁰x_a, x⁴_a, $⁰, #⁰, x⁷_a, b⁰, x_a¯ax_a, c⁰, x⁶_a, x³_a,

$, #, x²_a, xab⁰xa, a, xac⁰xa, x⁴_a, $⁰, #⁰, x⁷_a, b⁰, xa¯axa, c⁰, x⁹_a

followed by

$⁰⁰, #⁰⁰, x_bbx_b, b⁰, x_bb⁰x_b, ¯b, x_b, $⁰⁰⁰, #⁰⁰⁰, x_ccx_c, c⁰, x_cc⁰x_c, ¯c, x_c,

then¯a must be a complete factor in the prefix ofP encodingτ, soτ must make the output of Ci−1 labelled afalse. Since¯b, c,¯ x_b, x_c, x_bbx_b andx_ccx_c are complete factors butb, c, x_b¯bx_b, xccx¯ c, x^j_b andx^j_c for j > 1 are not, P encodes the assignment to the inputs of Ci that makes them true or false according toτ.

Since these are all the possibilities for howP can end, each diverse palindromic factorization ofS_i encodes some assignment to the inputs ofC_i. This gives us the following lemma:

Lemma 15. If we have a string Si−1 that represents Ci−1 and C_i is obtained from Ci−1 by splitting an output ofCi−1 into two outputs, then in constant time we can append symbols to Si−1 to obtain a stringS_ithat representsC_i.

Since$,$⁰,$⁰⁰,$⁰⁰⁰,#and#⁰do not occur inS_i−1and occur as pairs of consecutive charac-ters inS_i⁰, they must each be complete factors in any palindromic factorization ofS_i⁰. Therefore, any diverse palindromic factorization ofS_i⁰ consists of

1. a diverse palindromic factorization ofS_i−1⁰ , 2. $, #,

3. a diverse palindromic factorization ofx³_c0a⁰₁x_c⁰a₁x_c⁰a₁x_c⁰a⁰₁x⁵_c0, 4. $⁰, #⁰,

5. a diverse palindromic factorization ofx⁷_c0a⁰₂x_c⁰a₂x_c⁰a₂x_c⁰a⁰₂x⁹_c0, 6. $⁰⁰, #⁰⁰,

7. a diverse palindromic factorization ofx¹¹_c0b⁰x_c⁰bx_c⁰¯bx_c⁰b⁰x¹³_c0.

Ifa₁is a complete factor in the factorization ofS_i−1⁰ , then the diverse palindromic factoriza-tion of

x³_c⁰a⁰₁xc⁰a1xc⁰a1xc⁰a⁰₁x⁵_c⁰

must include either

a⁰₁, xc⁰a1xc⁰, a1, xc⁰a⁰₁xc⁰ or a⁰₁, xc⁰a1xc⁰, a1, xc⁰, a⁰₁.

Notice that in the former case, the factorization need not containx_c⁰. Ifa₁ is a complete factor in the factorization ofS_i−1⁰ , then the diverse palindromic factorization of

x³_c0a⁰₁x_c⁰a₁x_c⁰a₁x_c⁰a⁰₁x⁵_c0

must include either

x_c⁰a⁰₁x_c⁰, a₁, x_c⁰a₁x_c⁰, a⁰₁ or a⁰₁, x_c⁰, a₁, x_c⁰a₁x_c⁰, a⁰₁.

Again, in the former case, the factorization need not containxc⁰. Symmetric propositions hold fora₂andb.

We set

S_i⁰⁰ =S_i⁰$^†#^†x¹⁵_c0a⁰₁x_c⁰c⁰x_c⁰b⁰x¹⁷_c0 $^††#^††x¹⁹_c0a⁰₂x_c⁰dx_c⁰b⁰x²¹_c0 ,

where$^†,#^†,$^††,#^††,c⁰ anddare symbols we use only here. Any diverse palindromic factor-ization ofS_i⁰⁰consists of

1. a diverse palindromic factorization ofS_i⁰, 2. $^†, #^†,

3. a diverse palindromic factorization ofx¹⁵_c0a⁰₁x_c⁰c⁰x_c⁰b⁰x¹⁷_c0, 4. $^††, #^††,

5. a diverse palindromic factorization ofx¹⁹_c0a⁰₂x_c⁰dx_c⁰b⁰x²¹_c0.

Sincea₁anda₂label outputs inC_i−1⁰ split from the same output inCi−1, it follows thata₁is a complete factor in a diverse palindromic factorization ofS_i−1⁰ if and only if a₂ is. Therefore, we need consider only four cases:

Case 1: The factorization ofS_i−1⁰ includesa₁,a₂andbas complete factors, so the factorization ofS_i⁰ includes as complete factors eitherx_c⁰a⁰₁x_c⁰, ora⁰₁ andx_c⁰; eitherx_c⁰a⁰₂x_c⁰, ora⁰₂ andx_c⁰; eitherx_c⁰b⁰x_c⁰, orb⁰ andx_c⁰; andb⁰. Trying all the combinations — there are only four, sincex_c⁰ can appear as a complete factor at most once — shows that any diverse palindromic factorization ofS_i⁰⁰includes one of

a⁰₁, x_c⁰c⁰x_c⁰, b⁰, . . . , a⁰₂, x_c⁰, d, x_c⁰b⁰x_c⁰, a⁰₁, x_c⁰c⁰x_c⁰, b⁰, . . . , x_c⁰a⁰₂x_c⁰, d, x_c⁰b⁰x_c⁰,

with the latter only possible ifx_c⁰ appears earlier in the factorization.

Case 2: The factorization ofS_i−1⁰ includesa1,a2andbas complete factors, so the factorization ofS_i⁰includes as complete factors eitherxc⁰a⁰₁xc⁰, ora⁰₁andxc⁰; eitherxc⁰a⁰₂xc⁰, ora⁰₂andxc⁰;b⁰; and eitherx_c⁰b⁰x_c⁰, orb⁰andx_c⁰. Trying all the combinations shows that any diverse palindromic factorization ofS_i⁰⁰includes one of

a⁰₁, x_c⁰, c⁰, x_c⁰b⁰x_c⁰, . . . , a⁰₂, x_c⁰dx_c⁰, b⁰, x_c⁰a⁰₁x_c⁰, c⁰, x_c⁰b⁰x_c⁰, . . . , a⁰₂, x_c⁰dx_c⁰, b⁰,

with the latter only possible ifx_c⁰ appears earlier in the factorization.

Case 3: The factorization ofS_i−1⁰ includesa₁,a₂andbas complete factors, so the factorization of S_i⁰ includes as complete factorsa⁰₁; a⁰₂; either x_c⁰b⁰x_c⁰, or b⁰ and x_c⁰; and b⁰. Trying all the combinations shows that any diverse palindromic factorization ofS_i⁰⁰ includes one of

xc⁰a⁰₁xc⁰, c⁰, xc⁰, b⁰, . . . , xc⁰a⁰₂xc⁰, d, xc⁰b⁰xc⁰, x_c⁰a⁰₁x_c⁰, c⁰, x_c⁰b⁰x_c⁰, . . . , x_c⁰a⁰₂x_c⁰, d, x_c⁰b⁰x_c⁰,

with the latter only possible ifx_c⁰ appears earlier in the factorization.

Case 4: The factorization ofS_i−1⁰ includesa₁,a₂andbas complete factors, so the factorization ofS_i⁰includes as complete factorsa⁰₁;a⁰₂;b⁰; and eitherx_c⁰b⁰x_c⁰, orb⁰andx_c⁰. Trying all the com-binations shows that any diverse palindromic factorization ofS_i⁰⁰ that extends the factorization ofS_i⁰ includes one of

x_c⁰a⁰₁x_c⁰, c⁰, x_c⁰b⁰x_c⁰, . . . , x_c⁰a⁰₂x_c⁰, d, x_c⁰, b⁰, x_c⁰a⁰₁x_c⁰, c⁰, x_c⁰b⁰x_c⁰, . . . , x_c⁰a⁰₂x_c⁰, d, x_c⁰b⁰x_c⁰,

with the latter only possible ifxc⁰ appears earlier in the factorization.

Summing up, any diverse palindromic factorization ofS_i⁰⁰ always includesxc⁰ and includes eitherx_c⁰c⁰x_c⁰ if the factorization ofS_i−1⁰ includesa₁,a₂ andb as complete factors, orc⁰ other-wise.

We set

S_i⁰⁰⁰ =S_i⁰⁰$^†††#^†††x²³_c0c⁰⁰x_c⁰c⁰x_c⁰c⁰x_c⁰c⁰⁰x²⁵_c0 ,

where$^†††and#^†††are symbols we use only here. Any diverse palindromic factorization ofS_i⁰⁰⁰ consists of

1. a diverse palindromic factorization ofS_i⁰⁰, 2. $^†††, #^†††,

3. a diverse palindromic factorization ofx²³_c0c⁰⁰x_c⁰c⁰x_c⁰c⁰x_c⁰c⁰⁰x²⁵_c0.

Since x_c⁰ must appear as a complete factor in the factorization of S_i⁰⁰, if c⁰ is a complete factor in the factorization ofS_i⁰⁰, then the factorization of

x²³_c0c⁰⁰x_c⁰c⁰x_c⁰c⁰x_c⁰c⁰⁰x²⁵_c0

must include

c⁰⁰, x_c⁰c⁰x_c⁰, c⁰, x_c⁰c⁰⁰x_c⁰; otherwise, it must include

x_c⁰c⁰⁰x_c⁰, c⁰, x_c⁰c⁰x_c⁰, c⁰⁰.

That is, the factorization of x²³_c0c⁰⁰x_c⁰c⁰x_c⁰c⁰x_c⁰c⁰⁰x²⁵_c0 includes c⁰⁰, x_c⁰ and x_c⁰c⁰⁰x_c⁰ but notc⁰⁰ or x_c⁰c⁰⁰x_c⁰, if and only if the factorization of S_i⁰⁰ includes c⁰; otherwise, it includes c⁰⁰, x_c⁰ and x_c⁰c⁰⁰x_c⁰ but notc⁰⁰orx_c⁰c⁰⁰x_c⁰.

We set

S_i =S_i⁰⁰⁰$^‡#^‡x_ccx_cc⁰⁰x_cc⁰⁰x_ccx_c,

where $^‡, #^‡, c, c and x_c are symbols that do not appear in S_i⁰⁰⁰. Any diverse palindromic factorization ofS_i consists of

1. a diverse palindromic factorization ofS_i⁰⁰⁰, 2. $^‡, #^‡,

3. a diverse palindromic factorization ofx_ccx_cc⁰⁰x_cc⁰⁰x_ccx_c.

Since exactly one ofc⁰⁰andc⁰⁰must appear as a complete factor in the factorization ofS_i⁰⁰⁰, the factorization of

x_ccx_cc⁰⁰x_cc⁰⁰x_ccx_c must be either

x_c, c, x_cc⁰⁰x_c, c⁰⁰, x_ccx_c or

x_ccx_c, c⁰⁰, x_cc⁰⁰x_c, c, x_c.

Thus if c⁰⁰ is a complete factor in the factorization of S_i⁰⁰⁰, then c, x_c and x_c¯cx_c are complete factors in the factorization ofS_ibut¯c,x_ccx_candx^j_care not forj >1; otherwise,¯c,x_candx_ccx_c are complete factors butc,xccx¯ candx^j_care not forj >1.

AssumeS_i−1 representsC_i−1. Letτ be an assignment to the inputs ofC_i−1 and letP be a diverse palindromic factorization ofS_i−1 encodingτ. By Lemma 15 we can extendP toP⁰ so that it encodes the assignment to the inputs ofC_i−1⁰ that makes them true or false according to τ. There are four cases to consider:

Case 1: τ makes the outputs ofC_i−1 labelleda and b both true. ThenP⁰ concatenated with, e.g.,

$, #, x³_c⁰, a⁰₁, x_c⁰a₁x_c⁰, a₁, x_c⁰a⁰₁x_c⁰, x⁴_c⁰,

$⁰, #⁰, x⁷_c0, a⁰₂, x_c⁰a₂x_c⁰, a₂, x_c⁰a⁰₂x_c⁰, x⁸_c0,

$⁰⁰, #⁰⁰, x¹¹_c0, b⁰, x_c⁰bx_c⁰, ¯b, x_c⁰b⁰x_c⁰, x¹²_c0

is a diverse palindromic factorizationP⁰⁰ofS_i⁰which, concatenated with, e.g.,

$^†, #^†, x¹⁵_c0, a⁰₁, x_c⁰c⁰x_c⁰, b⁰, x¹⁷_c0,

$^††, #^††, x¹⁹_c⁰, a⁰₂, xc⁰, d, xc⁰b⁰xc⁰, x²⁰_c⁰

is a diverse palindromic factorizationP⁰⁰⁰ ofS_i⁰⁰which, concatenated with, e.g.,

$^†††, #^†††, x²²_c0, x_c⁰c⁰⁰x_c⁰, c⁰, x_c⁰c⁰x_c⁰, c⁰⁰, x²⁵_c0

is a diverse palindromic factorizationP^†ofS_i⁰⁰⁰ which, concatenated with

$^‡, #^‡, x_ccx_c, c⁰⁰, x_cc⁰⁰x_c, ¯c, x_c

is a diverse palindromic factorizationP^‡ofS_iin whichc,¯ x_candx_ccx_care complete factors but c,xc¯cxcandx^j_care not forj >1.

Case 2: τ makes the output of C_i−1 labelled a true but the output labelled b false. Then P⁰ concatenated with, e.g.,

$, #, x³_c⁰, a⁰₁, x_c⁰a₁x_c⁰, a₁, x_c⁰a⁰₁x_c⁰, x⁴_c⁰,

$⁰, #⁰, x⁷_c0, a⁰₂, x_c⁰a₂x_c⁰, a₂, x_c⁰a⁰₂x_c⁰, x⁸_c0,

$⁰⁰, #⁰⁰, x¹⁰_c0, x_c⁰b⁰x_c⁰, b, x_c⁰¯bx_c⁰, b⁰, x¹³_c0

is a diverse palindromic factorizationP⁰⁰ofS_i⁰which, concatenated with, e.g.,

$^†, #^†, x¹⁵_c0, a⁰₁, x_c⁰, c⁰, x_c⁰b⁰x_c⁰, x¹⁶_c0,

$^††, #^††, x¹⁹_c⁰, a⁰₂, xc⁰dxc⁰, b⁰, x²¹_c⁰

is a diverse palindromic factorizationP⁰⁰⁰ ofS_i⁰⁰which, concatenated with, e.g.,

$^†††, #^†††, x²³_c0, c⁰⁰, x_c⁰c⁰x_c⁰, c⁰, x_c⁰c⁰⁰x_c⁰, x²⁴_c0

is a diverse palindromic factorizationP^†ofS_i⁰⁰⁰ which, concatenated with

$^‡, #^‡, xc, c, xcc⁰⁰xc, c⁰⁰, xc¯cxc

is a diverse palindromic factorizationP^‡ofS_iin whichc,x_c¯cx_candx_care complete factors but

¯

c,x_ccx_candx^j_care not forj >1.

Case 3: τ makes the output of Ci−1 labelled a false but the output labelledb true. Then P⁰ concatenated with, e.g.,

$, #, x²_c0, x_c⁰a⁰₁x_c⁰, a₁, x_c⁰a₁x_c⁰, a⁰₁, x⁵_c0,

$⁰, #⁰, x⁶_c0, x_c⁰a⁰₂x_c⁰, a₂, x_c⁰a₂x_c⁰, a⁰₂, x⁹_c0,

$⁰⁰, #⁰⁰, x¹¹_c0, b⁰, x_c⁰bx_c⁰, ¯b, x_c⁰b⁰x_c⁰, x¹²_c0

is a diverse palindromic factorizationP⁰⁰ofS_i⁰which, concatenated with, e.g.,

$^†, #^†, x¹⁴_c⁰, xc⁰a⁰₁xc⁰, c⁰, xc⁰, b⁰, x¹⁷_c⁰,

$^††, #^††, x¹⁸_c0, x_c⁰a⁰₂x_c⁰, d, x_c⁰b⁰x_c⁰, x²⁰_c0

is a diverse palindromic factorizationP⁰⁰⁰ ofS_i⁰⁰which, concatenated with, e.g.,

$^†††, #^†††, x²³_c0, c⁰⁰, x_c⁰c⁰x_c⁰, c⁰, x_c⁰c⁰⁰x_c⁰, x²⁴_c0

is a diverse palindromic factorizationP^†ofS_i⁰⁰⁰ which, concatenated with

$^‡, #^‡, xc, c, xcc⁰⁰xc, c⁰⁰, xc¯cxc

is a diverse palindromic factorizationP^‡ofS_iin whichc,x_c¯cx_candx_care complete factors but

¯

c,x_ccx_candx^j_care not forj >1.

Case 4: τ makes the outputs of Ci−1 labelleda andb both false. Then P⁰ concatenated with,

e.g.,

$, #, x²_c0, x_c⁰a⁰₁x_c⁰, a₁, x_c⁰a₁x_c⁰, a⁰₁, x⁵_c0,

$⁰, #⁰, x⁶_c0, x_c⁰a⁰₂x_c⁰, a₂, x_c⁰a₂x_c⁰, a⁰₂, x⁹_c0,

$⁰⁰, #⁰⁰, x¹⁰_c⁰, xc⁰b⁰xc⁰, b, xc⁰¯bxc⁰, b⁰, x¹³_c⁰

is a diverse palindromic factorizationP⁰⁰ofS_i⁰which, concatenated with, e.g.,

$^†, #^†, x¹⁴_c0, x_c⁰a⁰₁x_c⁰, c⁰, x_c⁰b⁰x_c⁰, x¹⁶_c0,

$^††, #^††, x¹⁸_c0, x_c⁰a⁰₂x_c⁰, d, x_c⁰, b⁰, x²¹_c0

is a diverse palindromic factorizationP⁰⁰⁰ ofS_i⁰⁰which, concatenated with, e.g.,

$^†††, #^†††, x²³_c⁰, c⁰⁰, xc⁰c⁰xc⁰, c⁰, xc⁰c⁰⁰xc⁰, x²⁴_c⁰

is a diverse palindromic factorizationP^†ofS_i⁰⁰⁰ which, concatenated with

$^‡, #^‡, x_c, c, x_cc⁰⁰x_c, c⁰⁰, x_c¯cx_c

is a diverse palindromic factorizationP^‡ofS_iin whichc,x_c¯cx_candx_care complete factors but

¯

c,x_ccx_candx^j_care not forj >1.

Notice that in all casesP^‡encodes the assignment to the inputs ofCi that makes them true or false according toτ. SinceC_i−1 andC_i have the same inputs, each assignment to the inputs ofC_i is encoded by some diverse palindromic factorization ofS_i.

Now let P be a diverse palindromic factorization of S_i and let τ be the assignment to the inputs ofCi−1that is encoded by a prefix ofP. LetPˆ be a diverse palindromic factorization of S_i−1⁰ . Sincea₁anda₂ are obtained by splittingainSi−1, it follows thata₁ is a complete factor ofPˆif and only if a₂ is. Therefore, in what follows we only consider any diverse palindromic factorizationP ofS_iin which either botha₁ anda₂ are complete factors, or neithera₁nora₂is a complete factor.

LetP⁰ be the prefix ofP that is a diverse palindromic factorization ofS_i⁰⁰⁰. Case A:Suppose the factorization of

x²³_c0c⁰⁰x_c⁰c⁰x_c⁰c⁰x_c⁰c⁰⁰x²⁵_c0

in P⁰ includes c⁰⁰ as a complete factor, which is the case if and only if P includesc,¯ x_c and x_ccx_cas complete factors but notc,x_c¯cx_candx^j_cforj >1. We will show thatτ must make the outputs ofCi−1 labelledaandb true. Let P⁰⁰ be the prefix ofP⁰ that is a diverse palindromic factorization ofS_i⁰⁰. Sincec⁰⁰is a complete factor in the factorization of

x²³_c⁰c⁰⁰xc⁰c⁰xc⁰c⁰xc⁰c⁰⁰x²⁵_c⁰

inP⁰, so isc⁰. Therefore,c⁰ is not a complete factor in the factorization of x¹⁵_c0a⁰₁x_c⁰c⁰x_c⁰b⁰x¹⁷_c0

inP⁰⁰, soa⁰₁ andb⁰ are.

LetP⁰⁰⁰be the prefix ofP⁰⁰that is a diverse palindromic factorization ofS_i⁰. Sincea⁰₁ andb⁰ are complete factors later inP⁰⁰, they are not complete factors inP⁰⁰⁰. Therefore,a1 and¯bare complete factors in the factorizations of

x³_c0a⁰₁x_c⁰a₁x_c⁰a₁x_c⁰a⁰₁x⁵_c0 and x¹¹_c0b⁰x_c⁰bx_c⁰¯bx_c⁰b⁰x¹³_c0

in P⁰⁰⁰, so they are not complete factors in the prefix P^† of P that is a diverse palindromic factorization ofS_i−1⁰ . Since we builtS_i−1⁰ fromSi−1 with Lemma 15, it follows that a₁ and b are complete factors in the prefix ofP that encodesτ. Therefore,τ makes the outputs ofCi−1

labelledaandbtrue.

Case B:Suppose the factorization of

x²³_c0c⁰⁰x_c⁰c⁰x_c⁰c⁰x_c⁰c⁰⁰x²⁵_c0

inP⁰ does not includec⁰⁰ as a complete factor, which implies that it does includexc⁰c⁰⁰xc⁰ as a complete factor. Since, as noted earlier, we can assume thata₁ is a complete factor ofP if and only ifa₂ is, it follows that the factorization of

x²³_c0c⁰⁰x_c⁰c⁰x_c⁰c⁰x_c⁰c⁰⁰x²⁵_c0

must include

c⁰⁰, x_c⁰c⁰x_c⁰, c⁰, x_c⁰c⁰⁰x_c⁰.

Then,P must includexc,candc⁰⁰as complete factors. We will show thatτ must make at least

one of the outputs of C_i−1 labelled a or b false. LetP⁰⁰ be the prefix of P⁰ that is a diverse palindromic factorization ofS_i⁰⁰. Sincex_c⁰c⁰x_c⁰ is a complete factor in the factorization of

x²³_c⁰c⁰⁰x_c⁰c⁰x_c⁰c⁰x_c⁰c⁰⁰x²⁵_c⁰

inP⁰,c⁰ is a complete factor in the factorization of x¹⁵_c⁰a⁰₁xc⁰c⁰xc⁰b⁰x¹⁷_c⁰

inP⁰⁰. Then, the factorization of

x¹⁵_c0a⁰₁x_c⁰c⁰x_c⁰b⁰x¹⁷_c0

must include one of the following three:

x_c⁰a⁰₁x_c⁰, c⁰, x_c⁰b⁰x_c⁰, (5.1) x_c⁰a⁰₁x_c⁰, c⁰, x_c⁰, b⁰, (5.2) a⁰₁, xc⁰, c⁰, xc⁰b⁰xc⁰. (5.3) Case B-a: Assume the factorization ofx¹⁵_c0a⁰₁x_c⁰c⁰x_c⁰b⁰x¹⁷_c0 includes (5.1). LetP⁰⁰⁰ be the prefix ofP⁰⁰ that is a diverse palindromic factorization ofS_i⁰. Sincea⁰₁ and b⁰ are not complete factors later inP⁰⁰, they are complete factors inP⁰⁰⁰. Therefore, there are five combinations of factorizations of

x³_c0a⁰₁x_c⁰a₁x_c⁰a₁x_c⁰a⁰₁x⁵_c0 and x¹¹_c0b⁰x_c⁰bx_c⁰¯bx_c⁰b⁰x¹³_c0

inP⁰⁰⁰, as follows:

Case B-a1: The factorizations include

x_c⁰a⁰₁x_c⁰, a₁, x_c⁰a₁x_c⁰, a⁰₁ andx_c⁰b⁰x_c⁰, b, x_c⁰¯bx_c⁰, b⁰.

In this case, a1 and b are not complete factors in the prefix of P that encodes τ. Therefore,τ makes both the outputs ofC_i−1labelledaandbfalse.

Case B-a2: The factorizations include

x_c⁰a⁰₁x_c⁰, a₁, x_c⁰a₁x_c⁰, a⁰₁andb⁰, x_c⁰bx_c⁰, ¯b, x_c⁰, b⁰.

In this case,a₁ is not a complete factor andb is a complete factor in the prefix ofP that encodesτ. Therefore,τ makes the outputs ofCi−1labelledafalse andbtrue.

Case B-a3: The factorizations include

a⁰₁, x_c⁰a₁x_c⁰, a₁, x_c⁰, a⁰₁ andx_c⁰b⁰x_c⁰, b, x_c⁰¯bx_c⁰, b⁰.

In this case,a₁ is a complete factor andbis not a complete factor in the prefix ofP that encodesτ. Therefore,τ makes the outputs ofC_i−1labelledatrue andbfalse.

Case B-a4: The factorizations include

a⁰₁, x_c⁰, a₁, x_c⁰a₁x_c⁰, a⁰₁ andx_c⁰b⁰x_c⁰, b, x_c⁰¯bx_c⁰, b⁰.

In this case, a1 and b are not complete factors in the prefix of P that encodes τ. Therefore,τ makes both the outputs ofC_i−1labelledaandbfalse.

Case B-a5: The factorizations include

x_c⁰a⁰₁x_c⁰, a₁, x_c⁰a₁x_c⁰, a⁰₁andb⁰, x_c⁰, b, x_c⁰¯bx_c⁰, b⁰.

In this case, a1 and b are not complete factors in the prefix of P that encodes τ. Therefore,τ makes both the outputs ofCi−1labelledaandbfalse.

Case B-b: Assume the factorization ofx¹⁵_c0a⁰₁x_c⁰c⁰x_c⁰b⁰x¹⁷_c0 includes (5.2). Let P⁰⁰ be the prefix ofP⁰ that is a diverse palindromic factorization ofS_i⁰⁰. LetP⁰⁰⁰ be the prefix ofP⁰⁰that is a diverse palindromic factorization ofS_i⁰. Since a⁰₁ andxc⁰b⁰xc⁰ are not complete factors later inP⁰⁰, they are complete factors inP⁰⁰⁰. Therefore, the factorizations of

x³_c0a⁰₁x_c⁰a₁x_c⁰a₁x_c⁰a⁰₁x⁵_c0 and x¹¹_c0b⁰x_c⁰bx_c⁰¯bx_c⁰b⁰x¹³_c0

must include

x_c⁰a⁰₁x_c⁰, a₁, x_c⁰a₁x_c⁰, a⁰₁ andb⁰, x_c⁰bx_c⁰, ¯b, x_c⁰b⁰x_c⁰

inP⁰⁰⁰. Thena₁ is not a complete factor andbis a complete factor in the prefix ofP that encodesτ. Therefore,τ makes the outputs ofCi−1labelledafalse andbtrue.

Case B-c: Assume the factorization ofx¹⁵_c0a⁰₁x_c⁰c⁰x_c⁰b⁰x¹⁷_c0 includes (5.3). LetP⁰⁰ be the prefix ofP⁰ that is a diverse palindromic factorization ofS_i⁰⁰. LetP⁰⁰⁰ be the prefix ofP⁰⁰that is

a diverse palindromic factorization ofS_i⁰. Since x_c⁰a⁰₁x_c⁰ andb⁰ are not complete factors later inP⁰⁰, they are complete factors inP⁰⁰⁰. Therefore, the factorizations of

x³_c⁰a⁰₁x_c⁰a₁x_c⁰a₁x_c⁰a⁰₁x⁵_c⁰ and x¹¹_c⁰b⁰x_c⁰bx_c⁰¯bx_c⁰b⁰x¹³_c⁰ must include

a⁰₁, x_c⁰a₁x_c⁰, a₁, x_c⁰a⁰₁x_c⁰ andx_c⁰b⁰x_c⁰, b, x_c⁰¯bx_c⁰, b⁰

inP⁰⁰⁰. Thena1 is a complete factor andb is not a complete factor in the prefix ofP that encodesτ. Therefore,τ makes the outputs ofC_i−1labelledatrue andbfalse.

The above arguments give the following lemma.

Lemma 16. If we have a string Si−1 that represents Ci−1 and C_i is obtained from Ci−1 by making two outputs of Ci−1 the inputs of a new NAND gate, then in constant time we can append symbols toSi−1 to obtain a stringS_ithat representsC_i.

ドキュメント内 組合せ的文字列分解 (ページ 51-62)