Variants of Extension Problem

Let

o:

and (3 b any strings. By �( ^o:,

(3),

we denote the number of occurrences of (3 in o:. The 1 ngth of a. string

o:

is d noted by I

o:

_{J. The}

i

th symbol of o: from the left is denoted by

o:[i].

_Letx be a symbol not belonging to any finite alphabet

�.

_Every

1r E

(

.:..J U

{

}

)+ is called a. one-variable pattern and ^x is referred to as the pattern

va.ria.bl of ^1r. If � ( ^1r,x

) � 1

then th pat tern ^1r i called proper. The set of all one

variable pattern is denoted by P1, and for any pattern ^1r,the language* of ^1ris already defined.

Let * be a sp cial symbol not belonging to

�

_U_{_x}. A string

w E (�

_U_{*}

)

₊ _is

called incomplete if �(

w,

_*)

� 1 .

_L_t_T_and_Fb finit subsets of (�

U

{ *} )+ such that T n F ⁼

0.

A m mber of T is called a po itive xample and a 1nemb r of F is said to be a negative example. Th ind finite value of a string containing* is assigned by the following function.

DEFINITION 5.2.1. For any alphabet

�'

the expression E denotes the set of all

c.p:

(� U

{*})+ -+�+ such that c.p

E

E iff for each

wE (� U

_{{*})+, if}

�(w,*)

= 0,

then

c.p(w)

w,

and if �(w,*)

� 1,

_then

c.p(w)

is a string

w' E �lwl

such that for any

1 :::; i:::;

_{Jwl and}

w[i] =1-

_*,

w'[i]

w[i].

*Note that no erasing substitution is assumed in this study.

Let T,

F �

L.J +. A pattern 1r E

P1

is said to be consistent with the T U F if T

� L(

)

_{and F}_n

L(

)

0.

Thus, if there is a consistent pattern for T U F, then such a pattern can be thought of as explaining th data given. Moreover, since every pattern language generated by a proper pattern is infinite, a consistent pattern for T U F can b also regard d as a generalization or extension of the data sets T and F.

Following Boros t

al. [14],

w next give the semantics of*·

DEFINITION 5.2.2. LetT and F be any finit subsets of (�U {*})+such that TnF ⁼

0.

There is an extension for T U F iff there exists a pattern 1r E

P1

such that ^1r is consistent with T U F. There is a consistent extension for T U F iff there exists a pattern

1r

P1

and a r.p E <l>r; such that 1r is consistent with r.p(T) U r.p( F). Moreover, there is a 1obust extension for T U F iff there exists a pattern ^1r E

P1

such that

1r

is consist n t with r.p(T) U r.p( F) for all r.p E r;.

PROBLEM 5.2.1. The extension p1oblem, denoted by E, is to decide, on input any sets T, F

�

�+ wheth r there exists an extension for T U F. The con i tent extension p1oblem, denoted by CE is to decide, on input any sets T, F

�

(� U { *}

)+,

_whether

there exists a consistent extension for T U F. F inally, the Tobust extension problem, denoted by RE, is to de ide, on consistent ext nsion ( abbr. CE) is the problem to decid d on input any ts T, F

�

_{(� U { *}

}

)+ wh ther there exists a robust extension forTUF.

Clearly, the complexity of th s problems i m asured in the length of the input.

Next we x mplify these probl rns.

EXAMPLE 5.2.1. Let � = {

a

b,

}

, T =

{abacababacacabaca abacabaca }

and F =

{

aabaacabaca}.

Then, there are thre patterns 1r1 = x

1r2

xbxcabaca

and 1r3 =

abacabxcx

that are consist nt with T, but

1r1

and

1r2

ar not consistent with F because

Jri[aabaacabacajx]

1r2[aajx]

aabaacabaca.

On the other hand, 1r3 is consist nt with T U F, and thus, there exists an extension ofT U F.

Next, let T =

{ abacababacacabaca, abacabaca }

and let F = { *

abb

cabaca } .

Then, the answer to CE is "yes," since

1r

xbxcabaca

is consistent with T U r.p( F) for r.p( *abb*

a

aca

) =

aabbacabaca

such that

1r2

is consistent with T and r.p(F).

Finally, let T

= {a* b, ab * aba * cb}

and F =

{ bb * cba}.

Then, the ^7f

= axb

is consistent with <p(T) and <p(F) for every E. Thus, in this case, there exists a robust extension.

In this study, w generally assume that

11�11 ^{2: 2}

because of the following reasons.

L t ^LJ consi t of on symbol, say �

= {a}.

Then, there exist trivial reductions from

CE

to E and from RE to

E

by replacing all ^*in giv n strings by the same symbol

a.

For each wE�+ let

Lw(i,j) = {1r

E P1

I �(1r,a) = i, �(1r,x)

⁼

j, 1r[ujx] =

lui=

(lwl- i)/ j}

. Sin e

11�11 =

^1,for any w,w' E �+and 1:::;

i,j:::;

min{lwl,

lw'l},

it holds that

Lw(i,j) = Lw'(i,j)

iff

Lw(i,j)nLw'(i,j) =/- ^0.

Thus, if

11�11 =

1, then the problem

E,

CE and RE ar d cidable in time polynomial in th size of the sum of the length of given strings.

We first study th complexity of problems E and

CE.

First of all, we would like to establish an upp r bound for the complexity of these problems (i.e., we aim to show that both ar in NP). This is straightforward for

E,

since membership for one-variable patterns is in P

(

cf.

[1]).

Thus, we may just guess a pattern ^7r and check whether or not all strings from T ar contained in

L( 1r),

and none of the strings from F does behave thus. Therefore, it is only natural to try the same approach for

CE.

However, this imm diat ly l ad us to the following version of th membership problem.

PROBLEM 5.2.2. For any given w E (� U

{ *} ⁾

+ and ^7rE P1 th existential mem

bership probl m denoted by

3M EM (

^7r,w), is to d ide whether there exi ts a E such that <p

(

)

L(1r).

LEMMA 5.2.1.

3MEM(7r,

_{w) E}_P.

PROOF. L t ^7r

= v1xv2x

^{· ·}^·VnXVn+I be th input pattern, where

vi

E �* for all

1 ^:::;

ⁱ

^:::; n

^{+ 1.} First, w che k whether or not

lwl ^2: l1rl

O(l1rl

⁺

lwl)

time.

lwl

l1rl,

then <p

(

) rJ_ L(1r)

_{for all} E· If

lwl ^2: l1rl,

then we compute

m = lwl-

LI�i�n+I

lvil

and test wh ther or not

m/n

is a positive integer. This can be done in

O(lwl)

time. If

m/n

is not a positive integ r, then ther exists no substitution

u such that

1r[ujx] =

w. Now, let k ₌

m/n

be a positive integ r. Th n, w is of the form w

=

w1s1w2s2 ^{· · ·}WnSnWn+I such that for each 1

:::; i :::; n

⁺^1,

lwil = lvil

and

ls1l =

^·^·^· ⁼

l

I

= k.

We can ch ck wh ther or not there exists an 1

:::; i :::;

n +

1

and a 1

:::; j :::; lvil

such that

vi [j] # wi [j]

and

wi [j] #

*in

O(lwl).

If there exists such

i

and

j,

then

c.p( w) �

L( 1r) for any

c.p

_EL:. If not for each 1

:::; j :::;

^n,we next compute the string CXj ⁼ ^si

[j]

^s2

[j]

^·^·^·^sn

[j]

^. If an a1 contains two different constants, then there exists no L: that maps all

si [j],

. .. , sn

[j]

to the same constant. Thus,

c.p( w) �

L( 1r) for any _{c.p E} L:. Conversely, if for each

j,

the _a1 contains at most one constant, then there exists a _{c.p E} L: such that

c.p

₍

w

) _E L(1r). The time to check all the _aj is

O

(

k

ⁿ ) ⁼

O(m) _:::; O(lwl).

Hence, the time to decid whether ther exists

c.p

_EL: such

that

c.p

₍

w)

E L(1r) is O(max{l1rl +

lwl}

Q.E.D.

Cons quently Lemma 5.2.1 implies that, with respect to polynomial-time, incom

plete strings do not make the membership problem for one-variable patterns difficult.

Moreover, L mma 5.2.1 directly allows the following corollary.

COROLLARY 5.2.1. ^CEE NP.

Cl arly, th next question arising naturally is whether or not ^CEis even in P or NP-complete. However, while we must leave this problem open our next result will shed some additional light on the question which problem is more difficult, E or CE. For that purpose w assume th restriction to CE that the given sets of positive examples T contain only constant strings (i.e. T

<;;;;;; L:+).

Th r stricted probl m is denoted by

RCE. The next th orem clarifi s th r lation between RCE and E.

THEOREM 5.2.1. ^Eis equival nt to RCE with r spect to polynomial-time reductions.

PROOF. Cl arly, E is polynomial-time reducible to RCE. For the opposite direction, suppose a finite set T

<;;;;;;

_L:+and a finit set F

<;;;;;; (

U {*

} )+,

wher IIL:II � 2. We want to construct sets T' and F' such that the answ r to E on input T' and F', is "yes" iff

RCE is answ r d thus on input T and F. We set T' ⁼ T and L:' ⁼

L:

{0, 1},

where L: n

{0, 1}

⁼

0.

For each

w

E F, define

w'

over L:' such that for each 1

:::; i :::; lwl, w' [i]

⁼

w[i]

w [i]

L:, w' [i]

⁼

0 w [j]

L:

_{for all}

j

i

and

w' [i]

⁼1 otherwise. That is if

w

L:+,

_then

w'

⁼

w

and if�(

w,

*) � 1, then

w'

is obtained by replacing the first

* in

w

0

and by replacing all other * in

w

by 1. Finally, we defin F' to be the set of all

w'

obtained.

Since T

=

^T'�

I:+,

any pattern containing 0 or 1 is not consistent with T'. Thus, it is suffici nt to show that ther exist a

1r E (I:

^U{

x} )+

and a <.p

E

E such that

'P(F) n L( 1r) =

⁰iff there exists a

1r' E (I:

^U{

x} )+

such that

F' n L( 1r') =

^0. Moreover, since for any

w E

^F,

w E I:+

iff

w E F',

we can assume that each string in

F

contains at least one*· Thus, for ach

w' E F', �(w',O) =

First, assum that there are a <.p

E

E and a pattern

1r E (I:

^U{

x} )+

such that

'P(F)

ⁿ

L(1r) =

Let

�(1r,x)

� 2. Since

�(1r,O) =

�(1r,1)

=

0 and for each

w' E F', �(w',O) =

1, then, ther xists no sub titution

u E I:'+

such that

1r[ujx]

F'.

Thus, in this case,

F' n L ( 1r) =

Let

�(1r,x) =

1. Then

1r

is of the form

1r = ax{3,

where

a{3

I:+.

Since

rp(F) n L( 1r) =

0, _{for any}

w E F,

th r xist the following three cases.

Case

lwl

l1rl, Case

^2: There exists a prefix

a'

w

such that

la'l = lal

and

a' -/: a

and

Case 3:

There exists a suffix

{3'

w

such that

1!3'1 = 1!31

and

{3' -/: {3.

Let the string

wE F

be reduced to a

w' E F'.

Case

1, since

lw'l =

lwl it is clear that

tf_ L(1r).

In Case ^2, _either

a'

I:+

�(a',*)

� _{1. If}

a'

I:+,

then it is also a prefix of

w'.

Thus,

1r[ujx] -/: w'

for any

u E I:'+.

�(a',*)

^�1, then there exists an 1 � i �

la'l

such that

w'[i] E

{0,

1}.

Thus,

1r[ujx]-/: w'

for any

u E I:'+. Case 3

is analogous. Hence, there exists a

1r E (2.:

^U{

x

}

)+

such that

F' n L(1r) =

^0.

Conver ely a sume that there is a

1r E (I:

{ x} )+

such that for any

w' E

^F'

w' rf_

L(1r).

Let the string

w' E

^F'be reduced from

awE F.

Let

1r = v1xv2x

^·

· · VnXVn+l,

where

Vi E

^2.:*for each 1 � i � _n+ 1. Since

lw'l = lwl,

if m

= (lw' l

(l1rl-

))/

n is not a positive integer, then

rp(w) rf_ L(1r)

for any <.p

E

E. If m is a positive integer, then

w = w1s1w2s2 · · · WnSnWn+l

and

w' = w�s�w; ; · · · w�s�w�+l

such that for each 1 � i � n +

1, lwil = lw�l = lvil

and

ls1l =···= I nl =I ��=···=I �� =

If ther exist an 1 � ⁱ � n + 1 and a 1 �

j

�

lw�l

such that

w�[j] E

^2.:and

w� [j] -/: vi[j],

th n, since

Wi [j] = wi[j],

for any <p

E

E,

rp( w) rf_ L( 1r).

If there exist an 1 � ⁱ� n + 1 and a 1 �

j

�

lw�l

such that

w�[j] E

{0,1}, then

wi[j] =

*· Thus, there exists a E such that it maps the

wi[j]

to a symbol not equal to the

vi[j] E

^2.:. It follows that

rp(w) tf_ L(1r).

Thus, we can assume that

Vi = w� = Wi

for all 1 � i � n + 1. The remaining parts are

Case

(a):

�(1r, x) =

1 and

Case

(b):

�(1r, x)

� 2.

Case

(a),

w' = w�s�w;.

It follows that

w'

L(1r);

a contradiction. In

Case

(b), th re exist

s�,sj

{s�,s;, ... ,s�}

such that i

=f- _j

_and

_{s�[k] =}

_0, _where

_1:::; k:::; ls�l·

Since

si[k] =*,if j[k]

E ^LJ' then there exists a

c.p

E E such that it maps the

si[k]

^to

a symbol not qual to the

sj[k],

^{and if}

sj[k]

⁼^*,th n there exists a

c.p

E E such that it maps the

i[k]

^and

sj[k]

to different symbols. Hence, there exist a

1r

(2::: U _{x})+

and a

c.p

E E such that

c.p(F) _n _{L(1r) =} _0.

Th r fore, there exist a

1r

(2::: U _{x})+

and a

c.p

E E such that c.p(F)

n L( 1r) = ⁰

iff there exists a

1r1

(I:

_{{ x} )+}

such that

F' _n _L(1r') ₌ _0. _Q.E.D.

From this Th or n1, it seems that incomplete strings as negative examples cause the difficulty of the consi tency problem. However, it is open whether there is a gap between R E and

CE.

Moreover, there is a chance that

E

^and

RCE

are members inside NP (e.g.,

E

^and^R ar in RP or

P).

The next aim of this s ction is to show the NP-completeness of problem

RE.

^Again,

we begin with a version of membership adapted to RE as follows.

PROBLEM 5.2.3. For any given

w

( U { *} )+

_and

_1r

_P1,

_the

universal membership problem,

denoted by

VMEM(1r, w),

is to decide whether for each

c.p

E E

c.p(w)

L(1r).

LEMMA 5.2.2.

VMEM(1r,w)

E P.

PROOF. Let

1r = v1xv2x · · · VnXVn+l

be the input pattern where

vi

E 2:::* for all 1

:::;

n + 1. The test wh ther or not

lwl ^� l1rl

can be done in

O(l1rl

lwl)

^time.

lwl ^� l1rl,

then similarly to Lemma

5.2.1

we compute m

= lwl- l:::1::;i::;n+l lvil

^and

check wheth r or not m

/

_nis a positive integ r in

O(lwl)

time. Let m

/

_{= k}

_{be a}

positive integer. Th n,

w

^{is of}^th ^form

w = ^{w1 1w2} 2 · · · Wn nWn+l

^{such that}^for^each

1 :::;

:::;

n + 1,

I _Wi I ₌ I _Vi _I

_and

I _1l ₌ _{· · ·} ₌ _Is _n I ₌

_k.

We can check whether or not there xists an

1 :::;

:::;

n + 1 such that

vi =/- _wi

_in

O(lwl)

^time. If there exist such

Vi

^and

wi,

^{th n}

c.p(w) rf_ _L(1r)

_{for a}

_c.p

_EE. If not, for each

1 :::; ^j ^:::;

n, we next compute th string

O'j = si[j]s2[j] · · · sn[j].

Since we have

vi= wi,

^{for each}c.p E E,

c.p(w)

L(1r)

iff for ach

1 :::; ^j:::;

si[j] = · · · = sn[j].

The time to check all the O'j is O

(

_kn

) ₌ _O(m) _:::; _O(lwl).

Herre , the time to decide whether

c.p(w)

L(1r)

^{for all}

c.p

E E is

O (

_max

_{l 1

_l

₊

_lwl}). _Q.E.D.

We recall th problen1 of the robust extension RE for one-variable patterns in Def

inition

5.2.2

and Problem

5.2.1.

This problem requires the universal consistency of a one-variable patt rn for every cp E ....,. Now, we give a log-space reduction from SAT to RE. For simplicity, in this reduction, SAT is restricted to 3-SAT, given a 3-CNF, to decid wh th r it is satisfiabl (for the NP-completeness of 3-SAT, see, e.g.,

[50]).

LEMMA 5.2.3. 3-SAT is log-space reducible to RE.

PROOF. L t

c

⁼

cl

^1\

c

^{2 1\}^...^1\

Cm

^{be a}^{3-CNF of}ⁿ^variables

X},

X2, ... 'Xn such that

Ci = ( ei1

ei2

ei3)

¹ where each

ei1

denotes a positive Or negative literal of

Xi1

that i

, Ri1

{ Xi1, --.xi1}, 1 ^::;

ⁱ

^::;

ⁿ^and

1 ::; j ::;

3. Let us fix an alphabet consisting of

n + 3 symbols such that E =

{

^{a1 a2,}^...^{, an+}

I} U {A, B}.

First, we compute the strings

a1, a2, a3

^and

a4

as follows.

ext, for each clause

ci = ( eil

ei2

ei3)

and i ⁼ 1' .

.

^.^'n we compute the corresponding string

f3i =

a111a2r2a3···an1nan+I such that for each

1::; ^j::;

^n,

rj =

BA

^if

x

^{j E}

{ ei1, fi2, ei3},

^rj ⁼

AB

^if

--.x

^{j E}

{ ei1, fi2, ei3}

^and^rj ⁼ ^** otherwise.

Finally, we output T

= {a3,a4}

as the set of positive exan1ples and F =

{a1,a2}U{f3k I 1 ^::;

::; m}

as the set of negative xamples. The idea for the string f3k E F is illustrated in Figure

5.1.

We first prove the following claim.

CLAIM 5.2.1. If a pattern

1r

^{E P1}is consistent with the strings

a1,a2,a3,

^and

a4,

then the

1r

is of the form

1r =

a1X1a2X2a3 ^·^·^·anXnan+l, where Xi E

{Ax, xA}

^and

1 ^::;

::;

Suppose that there exists a pattern 1r E P1 consistent with the

a1, a2, a3,

and

a4.

There are the following cases for a substitution

u

E E+ such that

1r[ujx]

c ⁼c1 A c2 A c3 A c4

\

Negativ examples

F igure 5.1: Negative examples computed from a 3-CNF

C

of n variables.

Case

^1: ^Asubstitution u contains an

ai

{a1,a2, ... ,an+I}

such that

1r[ujx]

E T.

Sine any

ai

appears in the strings at most once, the

1r

must be of the form wxw' such that wE

{a1,a1A,a1AA}

^{and w' E}

{an+1,Aan+l,AAan+1}.

For any possible wand w', the

1r

is not consistent with the negative example

a1.

Thus,

Case

1 is removed.

Case

7r[AA/x] ⁼ a3.

Then, 1f

= a1Xla2X2a3 ... anXnan+I,

where

xi

{AA, X}

and 1

�

n. If

Xj ⁼ AA

for a 1

� j �

n, then the

1r

contains

ajAAaj+I·

Since

ij(a4, ajAAaj+,) =

0, it is a contradiction. Thus, in this case the

1r

is of the form

a1xa2xa3 · · · anxan+I·

This pattern is inconsistent with the negative example

a2.

Case

1r[AAjx] ⁼ a4.

Then the

1r

contains one of the strings

aiA3ai+I, aiAxai+I

and

aixAai+I·

In case of

aiA3ai+I,

the

1r

is not consistent with the

a3.

It is a contradiction.

Thus, for each 1

�

n, the substring of

1r

between

ai

and

ai+l

must be

Ax

xA.

This

1r

satisfies Claim 5.2.1 and it is consistent with all

a1, a2, a3,

and

a4.

Case

1r[A/ x] ⁼ a3.

If the

1r

contains a substring

aiAAai+I,

then it is not consistent with

a4.

Thus, the

1r

satisfies Claim 5.2.1.

Case

1r[Ajx] ⁼ a4.

In this ca , th 1r contains one of

aiA3ai+I, aixA2ai+I

and

aiA2xai+I·

Since it is not consistent with

a3,

this case is removed. Thus, Claim 5.2.1 is true.

We set

II= {1r

E P1

I a3, a4

L(1r), a1,a2 rf_ L(1r)}.

By Claim 5.2.1, the proof of the theorem is now reduced to the consistency that the 3-CNF

C

is satisfiable iff there exists a

1r

E II such that

cp( F)

L( 1r) ^{= 0}

for all cp E q>I:.

Assume that the Cis s;atisfiable. There exists a truth assignment

f : {xi, ... , xn}

^---+

{0, 1}

such that for each clause

ci = (eil

ei2

ei3) (1 _�

_�

)

_, at least one

e'

{ ei1, ei2, ei3}

fulfills xactly one of the following conditions.

Cas

(a) ^:

e' =

j

{xI

^,^{. . .}^{, x}

n}

and

f (

^xj )

= 1

, or

Case (b)

e' = ---, x j

and

f ( x j) = 0.

Ther exists a one-to-one mapping fron1 truth assignments

f

for

x1, ... , Xn

to the set II such that for each]

�

f(xi) = 0

iff

1r

contains

aixAai+I

and

f(xi ) = 1

_iff

1r

contains

aiAXai+I·

If an

f

satisfi s ach clause Ci, th n there exists a negative example

f3i

F

con truct d from th

ci

such that

Xj

{ eil 'ci2' ci3}

iff

f3i

contains

ajBAaj+l

and

--.xj

{ei1 f!i2 f!i3}

iff

f3i

contains

ajABaj+I·

Case

_{(a), a}

1r

E II corresponding to the f contains

ajAXaj+I

and the

f3i

con

structed froin

ci

contains

ajBAaj+I·

We note that for any 7r E II and

f3i

F'

_{17r I}₌

lf3i ,

. Thus, as compared with the

strings ajAXaj+l and ajBAaj+I

no substitution ^u E E+

and no

cp

E ^Esatisfy

1r [

/ x] = cp({3i).

Case

(b), analogously a

1r

corresponding to the

f

contains

ajxAaj+I

and the

f3i

constructed from Ci contain

ajABaj+I·

Thus, th re is no substitution

u

and

cp

for

1r[uj x] = cp(f3i).

Hence, if C is atisfiable, then ther xist a

1r

E II such that

cp( F) n L( 1r) = ⁰

for

all

cp

E ^{E .}

Conversely, l t the CNF C b unsatisfiabl . Then for any truth assignm nt f there xists a clause

ci

of c uch that for any literal

C'

ci,

ither

C' = Xj

{x

ⁱ,

... ' Xn}

and

f(xj) = 0

C' = --.xj

and

f(xj) =

Th n, for each

C'

{ ei1, ei2, ei3},

1r

contain

ajxAaj+I

and the

f3i

E F contains

ajBAaj+I

C' = x

j E

{XI

... , Xn}

and th

1r

contains

ajAXaj+I

and the

f3i

contains

ajABaj+I

C' = --.xj.

Finally, we define

cp(f3i) = w

such that for each 1

�

� if3il,

1r[k] = x

and otherwise.

It follows

<p({3i)

L ( 1r)

for the substitution

B.

Hence, if C is unsatisfiable, then for any ^7rE

II,

there exists a

<p

E E such that

<p(F)

L(1r)-=/:- 0.

Thus, we conclude that the 3-CNF C is satisfiable iff there exists a robust extension for T and

F. Q.E.D.

THEOREM 5.2.2. RE is NP-complete, even if

jjEjj = 2.

PROOF. Analogously we reduce a 3-CNF C to ^RE. Let C consist of ^m clauses cl'

c2'

... ' Cm and d fined by

n

variables

xl' x2' . . . Xn-

Initially, we set

E = {A, B}

and T

= { a1 = A 2n, a2 = A 3n}.

_{The set} F of n gati ve examples over E is the sum of th sets

N1 N2

and

N3

defined as follows.

N1 = {An}

{f3i = A 2n+i I i

{ 1, ... , 2n} \ { n, 2n}},

{ ^BA,

1 ::::; Vk ::::;

^mand

1 ::::; Vj ::::; n,

{k1

= AB

**,

if Xj is a literal of Ck

-.x j

is a literal of C ^k, and otherwise.

We define th s t

II� P1

such that ^1rE II iff

1r = X1X2···Xn,

_where

Xi

{Ax xA}

and 1

::::; i ::::; n.

Th n, we prove the following claim.

CLAIM 5.2.2.

1r

^EI

I

_iff

1r

P1

is consistent with T and

N1

<p(N2)

_{for all}

<p

E E.

First, assume

1r

^E II. Th n, cl arly, T

� L(1r).

For each

A2n+i

N1, 1r[ujx]-=/:- A2n+i

because

i

{1, ... ,2n} \ {n,2n}

and

�(1r,A) = �(1r,x) = n.

Thus,

N1 nL(1r) = 0.

_For

each odd number

i

such that 1

::::; i ::::; 2n- 1, 1r[i]1r[i

⁺

1] =Ax

1r[i]1r[i

⁺

1] = x A.

On the other hand, for any

{3j

N2,

there xists xactly one odd number

i

such that

{3j[i]f3j[i

⁺

1] = BB.

Since

j1rj = !f3j!,

there exists no

<p

E E such that

<p((3j)

L(1r).

Thus, if

1r

^EII, then ^1ris consistent with

<p(T)

_and

<p(N1

N2)

_{for all}

<p

E E.

Suppose to the contrary that ther xists a

1r

P1

and

1r

rt II such that

1r

is consistent with T and

N1

<p(N2)

_{for all}

<p

E E. If

1r

contains a

B,

then clearly, T n

L(1r) = 0.

Thus, we can assume

1r

{A,x}+.

We first show that

1r

must satisfy

1r[Ajx] = a1

⁼

A2n.

Assume that

1r[ujx] = A2n

and

u =

^N·,where

2 � r � 2n.

Then,

�(1r,x)

⁼

n' �n

and

�(1r,A) = 2n-rn'. Ifn' =

rz,

then

7r = xn.

Since

xn[A/x] =An

N1,

it is a contradiction. Thus,

n' � n- 1.

For each

1 � n' � n - 1,

there exists a

f3n'

N1

such that

f3n'

⁼

A 2n+n' = A (r+1)n' A 2n-rn'.

It follows th contradiction

1r[Ar+1jx] = f3n'·

Thus

7r[A/x] = A2n.

Second, we show that

1r

must satisfy

�( 1r, x) = n.

Assume that

�( 7r, x) = n' # n.

In case of

n' � n - 1,

there exists

f3n'

N1

such that

f3n'

⁼

A 2n+n' = A 2n' A 2n-n'.

Thus,

f3n'

L(1r)

for the substitution

A2.

In case of

�(1r, x)

⁼

n'

2::

n+1,

since

a1 a2

L(1r),

it holds that

n' � 2n -1.

Thus, there exists

f3n'

N1

such that

f3n' = A 2n+n' = A 2n' A 2n-n'.

It follows th contradiction

1r [A 2/ x] = f3n'.

Thus,

�( 1r, x) = n.

By the condition that

1r[Ajx]

⁼

A2n

and

�(1r,x) = n

1r

must satisfy that

�(1r,A) = �(1r A)= n.

Sine

7r

{A x}+, 1r

tf. IT and

�(1r,A) = �(1r,A) = n,

there exists an odd num

b r

i

and

1 � i � 2n- 1

such that

1r[i]1r[i + 1] = xx.

On the other hand sine

(i +

)/2

i a positive integer, there is a the string

f3(i+1);2

N2

such that it is of the form

i-1BB2n-i-1.

Thus, there exists a

cp

^E <l>r; such that for each

1 � k � 2n, cp(,B(i+1)/2)[k] = B

1r[k] = x

and

cp(f3(i+1);2)[k] =A

otherwise. It follows the contra

diction

1r[Bjx] = f3(i+1);2.

Hence if a

1r

P1

is consistent with T and

N1

cp(N2)

for

all

cp

^Er;, then

7r = X1X2

^·^·^·

Xn

such that

Xe

{Ax, xA}

and

1 �

� n.

This follows

that the laim

5.2.2

is true.

Similarly to the proof of Le1nma 5.2.3 we can see that the 3-CNF is satisfiable iff there exists a

1r

^{E IT}consi tent with

cp(N3)

for all

cp

^Er;. Thus w conclude that the

RE is NP-complete, even if

11�11 = 2.

Q.E.D.

EXAMPLE ^5.2.2. Let C b a 3-CNF of

5

variables. Th n, T

= {A10, A15}.

The

N1

and

N2

in Theorem

5.2.2

are d fined as follows.

N1 = {As' A 11, A 12' ... ' A 14, A 16, ... , A 19}

and

Let us take a 1r E

P1

such that

1r[ujx] = A10

for a substitution u E

{A}+. Ifu #A,

then

u =An

for some

2 � n �

^10. Let

�(7r, x) =

^m,where

1 �

� 5.

If m

= 5,

then

7r =

x5

and

A5

L(1r).

Thus, this

1r

is inconsistent with

N1.

For each

2 � n � 1

⁰and

1::; m::; ⁴such that

1r[Anjx]

A10

and

�(1r,x)

= m, there exists awE /\1 such that

1r[An+1jx]

= w. Thus, if a 7r is consistent with

N1,

then

1r[Ajx]

A10.

�( 1r x)

< 5, then there exists 1 ::; n' ::; ⁴ such that

A lO+n'

^E ^N

1 n L( 1r)

and if

�( 1r, x)

> 5, then there exists 6 ::; ^n'::; 9 such that

A lO+n'

E N1 n

L( 1r).

Thus, these

1r

are inconsistent with N1. It follows that if a

1r

is consistent with N1, then

�( 1r, x)

= 5.

Hence,

�(1r,x)

⁼

�(1r,A)

= 5.

For xample, 1 _t

1r

xAxxAAxAAx tf.

II. _Then,there exists a E and w =

2BB6

^EN

2

such that c.p( w

)

BABBAABAAB

L( 1r).

Let

1r

xAxAAxAxxA

^E^II. Then, there xists now E _N

2

and E such that c.p(w) E

L(1r).

By r sult in h or m 5.2.2, the restricted robust extension is also NP-complete, indeed, any positive exampl in the reduction contains no

*·

However, we could not prove the NP-completeness of the restricted consistent extension which is equivalent to the extension in the sense of polynomial-time.

Finally, we discuss the consistent extension itself. Since CE is in NP, its NP

complet ness is d rived by a reduction from

3-colorability of graphs

(abbr.

3-CLR):

given a graph G =

(V, E),

to decide whether th G is

3-colorable

that is, there exists a function

f: V

^-t

{a,

^b,

c}

such that

f(u) -1- f(v)

whenever

(u, v)

E

(cf., e.g.,

[23]).

THEOREM 5.2.3. _{(St phan}

[68]).

CE is NP-complete even if

IIEII

2.

PROOF. W show the outlin of th reduction from

3-CLR

to CE. Let G =

(V, E)

be any graph of n node . Th alphab t is fixed to

E

{0,

}.

One can produce a problem CE such that, wh nev r there is a pattern

1r

then

1r

{OOx OxO, xOO}n

wher for all i = 1, .. . , n, each ith block is

OOx

for the first

OxO

for the s cond and

xOO

for the third color.

The positiv and negative examples are the following:

Positive:

(OOO)n

in order to get that the pattern has at most length 3n.

Negative:

Oi

for all i <

3

n in order to have that the pattern has xactly length 3n.

The previous string enforces that

0

is the only constant in the pattern, and thus, taking

[0/x],

the string oe is in th language generated by the pattern, where f is the length of the pattern.

Positive:

(OOOO)n

in order to get that there are at most n occurrences of

x

in a pattern.

Th variable

x

has to satisfy

OJ

_{with j} >

1

to generate

(OOOO)n,

_{and so}

x

_can

occur at most n times; otherwise the string would have length 3n +

(

k _-

1 _)h

_for

h

^>ⁿoccurrences and this would be larg r than 4n.

N gativ ^:

Ok

_fork ₌3n +

1,

3n + 2, ... , 4n _-

1

in order to get that there are not less than ⁿoccurrences of

x.

Thes positiv and negative strings show that the pattern consists of 2n symbols

0

and n o currences of the variables

x.

Moreover, we set the following examples.

Positiv :

(

_{* *}1 * * )n. This word has length 5n, so to satisfy it, we have to assign a string of l ngth 3 to th variable

x.

_Since

0

does not occur in this string, we can most easily satisfy this condition by taking

[111/x].

This allows now to localize the positions of the

x

in the pattern and we obtain that the pattern consists of n blocks from

{OOx, OxO, xOO}.

This further string enforces that neighboring nodes have different colors. There exists a one-to-one mapping between the functions f ^:V _---+

{

a, b, c

}

and the patterns in

{OOx,OxO,xOO}n.

For each edge (i,j) of G, we takes a string with

0

in the middle position in the ith part and 1 in the middle position in the jth part. Thus, for each edge

(

i j) w take the string: *5 · · · *5

(

_{* *}

0

* *) *5 ... *5

(

_{* *}

1

* *) *5 ... *5.

If, for exampl , part i of the pattern is

OxO

and part j is

OOx,

then we have

[100/x]

such that

0(100)0

is satisfied by**

0

_{** and}

00(100)

_by**1 * *· If i and j have the same part, say

OOx,

_{then the}

OOx

must satisfy both * *

0

* * and * *

1

* * which is a contradiction because

0

_and1 can not be assigned at the same time. Since 3 colors

a, b, and ^care corresponding to the codes

OOx OxO,

_and

xOO,

resp ctively, there is a pattern satisfying all the abov conditions iff G is 3-colorable. Thus, 3-CLR is log-space

reducible to ^C

E

_Q.E.D.

ドキュメント内質問に基づく形式言語の機械学習に関する研究 (ページ 39-51)

o:

(3),

o:

o:

i

o:[i].

�.

(

{

}

) � 1

�

w E (�

)

w,

� 1 .

U

0.

�'

(� U

E

wE (� U

�(w,*)

c.p(w)

w,

� 1,

c.p(w)

w' E �lwl

1 :::; i:::;

w[i] =1-

w'[i]

w[i].

F �

P1

� L(

)

L(

)

0.

al. [14],

0.

P1

1r

P1

P1

1r

�

�

)+,

�

}

a

b,

}

{abacababacacabaca abacabaca }

aabaacabaca}.

1r2

xbxcabaca

abacabxcx

1r1

1r2

Jri[aabaacabacajx]

1r2[aajx]

aabaacabaca.

{ abacababacacabaca, abacabaca }

abb

cabaca } .

1r

xbxcabaca

a

aca

aabbacabaca

1r2

= {a* b, ab * aba * cb}

{ bb * cba}.

= axb

11�11 2: 2

= {a}.

CE

11�11 ^{2: 2}

Lw(i,j)nLw'(i,j) =/- ^0.

{ *} ⁾

1 ^:::;

^:::; n

lwl ^2: l1rl

lwl ^2: l1rl,