Folding by Simila i y
F. J. Gal´an and J. M. Ca˜ne e
Dep . de Lenguajes y Sis emas In o m´a icos.
Facul ad de In o m´a ica. A . Reina Me cedes s/n. 41012.
Se illa. Fax:34 954557139, Voice: 34 954552773
E-mail: [email p o ec ed]
Abs ac
A o mal speci ica ion can desc ibe so wa e models which a e di icul
o p og am. T ans o ma ional me hods based on old/un old s a egies ha e
been p oposed o pallia e his p oblem. The objec i e o applying ans o -
ma ions is o il e ou a new e sion o he speci ica ion whe e ecu sion may
be in oduced by a olding s ep. Among many p oblems, he ”eu eka” abou
when and how o de ine a new p edica e is di icul o ind au oma ically. We
p opose a new e sion o he olding ule which decides au oma ically how o
in oduce new p edica es in a speci ica ion. Ou me hod is based on inding
simila i ies be ween o mulas ep esen ed as pa sing ees and i cons i u es
an assis ance o he complex p oblem o de i ing ecu si e speci ica ions om
non ecu si e ones.
Keywo ds: speci ica ion ans o ma ion, p og am syn hesis, co ec ness
p ese a ion, p og am speci ica ion.
1 In oduc ion
Usually, a speci ica ion desc ibes so wa e models which a e di icul o p og am.
Sys ema ic cons uc ion o p og ams om speci ica ions is known as p og am syn-
hesis. A huge a ie y o syn hesis mechanisms ha e been de eloped [BSW90],
[BD77], [DeK94], [D o88], [Fle95], [Smi90], [AFM99]. In his wo k, we a e in e es ed
in ans o ma ional mechanisms; a sequence o meaning-p ese ing ans o ma ion
ules (e.g. un olding, olding, uni e sal ins an ia ion, abs ac ion, p edica e de ini-
ion, e c.) is applied o a speci ica ion un il a p og am is ob ained. The objec i e o
applying ans o ma ions is o il e ou a new e sion o he speci ica ion whe e e-
cu sion may be in oduced by a olding s ep. Howe e , among many o he s p oblems,
deciding abou when and how o de ine a new p edica e (i.e. ecu si e p edica e) is
di icul o ind au oma ically. Fold/un old ans o ma ions ep esen an impo an
in es iga ion subjec in he li e a u e [A D95], [BD77], [Pa 90], [P P93], [PeP94],
[TaS84]. Basically, un olding ep esen s he eplacemen o an a om by i s de ini-
ion and olding ep esen s he in e se ope a ion o eplacing a sub o mula by an
a om. In he ollowing example, he con ex Sde ines a (many-so ed) i s -o de
APPIA-GULP-PRODE 2001
language wi h ypes Na (na u al numbe s) cons uc ed om he unc ion symbols
0 and sand Seq(Na ) (sequences o na u al numbe s) cons uc ed om he unc ion
symbols emp y and conc. I de ines also he meaning o ela ion symbols such as =
(iden i y be ween na u al numbe s), nocc (numbe o occu ences o an elemen in
a sequence) and pe m (pe mu a ions o a sequence o na u al numbe s).
S={T ypes :Na gene a ed by 0, s Seq(Na ) gene a ed by emp y, conc
D=: 0 = 0 ⇔ ue 0 = s(x)⇔ alse
s(x) = 0 ⇔ alse s(x) = s(y)⇔x=y
Dnocc :nocc(e, emp y, z)⇔z= 0
nocc(e, conc(x, Y ), s(z)) ⇔x=e∧nocc(e, Y, z)
nocc(e, conc(x, Y ), z)⇔ ¬x=e∧nocc(e, Y, z)
Dpe m :pe m(L, S)⇔(nocc(a, L, z)⇔nocc(a, S, z))}
Dpe m is no closed o he s uc u e o a p og am (i.e. he e is no any explici
ecu sion). Following a ans o ma ional syn hesis p ocess o Dpe m (e.g. applying
uni e sal ins an ia ion on a iables L,Sand zin Dpe m, we ob ain D1and hen
un olding D1w. . . nocc(b, conc( , V ), s(k)) and nocc(b, conc(w, W ), s(k))) a oms
using second axiom in Dnocc) we each exp essions such as D2:
D1:pe m(conc( , V ), conc(w, W )) ⇔(nocc(b, conc( , V ), s(k))
⇔
nocc(b, conc(w, W ), s(k)))
D2:pe m(conc( , V ), conc(w, W )) ⇔(( =b∧nocc(b, V, k))
⇔
(w=b∧nocc(b, W, k)))
Two ques ions a ise a his poin , (a) Is i possible o in oduce ecu si e p e-
dica es in D2? and (b) How can we do i ? I is di icul o achie e an ”au oma ic
answe ” o hese ques ions. Ou me hod ollows a cons uc i e app oach. A compa i-
son based on he no ion o simila i y be ween D2and Dpe m is needed o decide abou
i s ques ion. Only i i s ques ion is answe ed a i ma i ely hen a simila i y-based
olding ule is applied o Din o de o answe second ques ion.
Ou wo k is explained in he ollowing manne . Sec ion 2 de ines he o m o ou
speci ica ions and a non-cons uc i e cha ac e iza ion o he olding ule is p esen ed.
Sec ion 3 de ines he concep o simila i y. Basically, i ep esen s an au oma ic
me hod o deciding which sub o mulas p oduce ecu sion. In sec ion 4, we desc ibe
a simila i y based olding ule which p ese es co ec ness, and inally, in sec ion 5
we es ablish conclusions.
2 P elimina y De ini ions
In his sec ion, he syn ax and seman ics o ou speci ica ions and a non-cons uc i e
de ini ion o he olding ule a e p esen ed. The use o he olding ule is in ended
o in oduce ecu sion in a speci ica ion.
Folding by Simila i y
De ini ion 2.1 (Syn ax o a Fo mula) A many-so ed ( yped) i s o de lan-
guage is assumed o w i e ou o mulas. A o mula Qτ1x1...QτnxnFwhe e Qτixi
is a uni e sal o exis en ial quan i ie de ined on a ype τi,xiis di e en om xj
o i6=j, and Fcon ains no quan i ie , is said o be in p enex no mal o m. We
conside ha , when possible, all quan i ie s in a o mula a e o de ed ollowing a
lexicog aphic o de de ined on he names o hei espec i e ypes.
Fo example, ∀Na a∀Na z∀Seq(Na )L∀Seq(Na )S(nocc(a, L, z)⇔nocc(a, S, z)) is in p e-
nex no mal o m whe e all quan i ie s ha e been o de ed ollowing a lexicog aphic
o de de ined on he names o hei espec i e ypes.
In he ollowing, we assume ha all ou o mulas a e in p enex no mal o m,
his does no ep esen any es ic ion due o he exis ence o an e ec i e p ocedu e
o ans o ming any i s -o de o mula in o an equi alen one in p enex no mal
o m [Men87]. Fo legibili y easons, we omi τsubsc ip s when a ype can be in-
duced clea ly in a o mula and exp essions such as Qτx...QτzF can be collapsed in o
equi alen exp essions Qτx, ..., zF . Fo example, he o mula ∀Na a∀Na z∀Seq(Na )L-
∀Seq(Na )S(nocc(a, L, z)⇔nocc(a, S, z)) can be collapse in o he equi alen o mula
∀Na a, z∀Seq(Na )L, S(nocc(a, L, z)⇔nocc(a, S, z)). In addi ion, when possible, uni-
e sal quan i ie s a e omi ed in he on o a o mula.
De ini ion 2.2 (Subs i u ion) A (g ound) a iable subs i u ion is he pai ( , )
whe e is a a iable and is a (g ound) e m. A subs i u ion σis a se o a iable
subs i u ions. Le X={x1, ..., xn}and Y={y1, ..., yn}be wo se s o a iables whe e
xiis di e en om xjand yiis di e en om yj o i6=j. Le QX={Qτx1, ...,-
Qτxn}and QY={Qτy1, ..., Qτyn}be wo se s o quan i ie s o a iables in Xand Y
espec i ely. We say ha σ={(x1, y1), ..., (xn, yn)}is a enaming subs i u ion which
ag ees w. . . quan i ica ions i (a) X∩Y=∅and (b) Qτxi=Qτyiwi h i= 1..n.
De ini ion 2.3 (Speci ica ion) An i -and-only-i axiom is a o mula o he o m
(x1, ..., xn)⇔R(y1, ..., ym)(e.g. axioms o =,nocc and pe m ela ion symbols in
S). The symbol is called he de ined symbol. The a om (x1, ..., xn)is called he
le -hand side o he axiom and he (sub) o mula R(y1, ..., ym)is called he igh -hand
side o he axiom. A speci ica ion o a ela ion symbol is he se D o all axioms
wi h he same de ined symbol. In he ollowing, we use D ,n o iden i y he n h axiom
in D .
De ini ion 2.4 (Con ex ) A con ex Cis a se o ypes and speci ica ions o e-
la ion symbols. Types a e cons uc ed om unc ion symbols appea ing in C.Cis
a omically comple e i , o e e y g ound a om ( 1, ..., n), ei he C ` ( 1, ..., n)
o C ` ¬ ( 1, ..., n).Chas isoini ial model Mi o e e y g ound li e al l,M|=
li C ` l. The e o e, he meaning o a ela ion in Cis he se o all g ound li e als
lde ined on such ha C ` l.
Some au ho s ha e s udied he p oblem o he exis ence o isoini ial models o
heo ies in gene al [BMM83] and some e ec i e c i e ia ha e been p oposed o con-
s uc consis en heo ies. Following [LaO94], a con ex Cadmi s an isoini ial model
i and only i i is a omically comple e. By hypo hesis, we assume ha ou con ex s
a e consis en in his way.
APPIA-GULP-PRODE 2001




za

,∀
SL
 
,

∀
1
211

⇔

),,( zLan o c c

),,( zSan o c c
Figu e 1: P a se(∀Na a, z∀Seq(Na )L, S(nocc(a, L, z)⇔nocc(a, S, z))).
De ini ion 2.5 (Folding Rule) A olding ule is a ans o ma ion ule in ended
o eplacing a sub o mula by an a om. Le Sbe a o mula and (xj)⇔Rj(yj)
be an axiom o in C. We say ha Sjis ob ained om S olding wi h espec
o (xj)⇔Rj(yj)i Sj=S|R
(xj)θjwhe e (a) The e exis sub o mula Rin S
and subs i u ion θsuch ha R=Rj(yj)θjand (b) S|R
(xj)θj ep esen s he ex ual
eplacemen o Rby (xj)θjin S.
Fo example, he o mula S≡(nocc(b, V, k)⇔nocc(b, W, k)) ∧ =b∧w=bcan
be olded wi h espec o Dpe m. Applying he subs i u ion θ1={(L, V ),(S, W ),-
(z, k),(a, b)} o he igh -hand side o he axiom in Dpe m we ob ain he sub o mula
R≡nocc(b, V, k)⇔nocc(b, W, k). Finally, applying ex ual eplacemen , we ob ain
pe m(V, W )∧ =b∧w=b.
3 Simila i y
This sec ion desc ibes an au oma ic me hod o in oduce ecu sion by a olding s ep.
I is based on he no ion o simila i y. Basically, simila i y ep esen s a decidable
ela ion be ween wo pa sed o mulas.
De ini ion 3.1 (Pa sing T ee) Le Sbe a o mula in p enex no mal o m. We
say ha P a se(S)(g aphical example in igu e 1) is he pa sing ee o Si i is a
ee ep esen a ion o Swhe e (a) each lea node in P a se(S) ep esen s a li e al in
S. (b) each non-lea node in P a se(S) ep esen s ei he a quan i ied se o a iables
Qτx, ..., z o a logical connec i e (∧,∨,⇒,⇔) in Sand (c) each node in P a se(S)
has unique iden i ica ion by means o a numbe wi h o ma lx ···xp. The digi l
ep esen s he le el whe e a node is loca ed in P a se(S). The digi pdecides i he
node is loca ed ei he a he le -hand side (p= 1) o a he igh -hand side (p= 2)
o i s pa en (i i exis s). By de aul , nodes wi hou b o he nodes ha e p= 1. The
digi s x···x ep esen he iden i ica ion o he pa en node. The oo node is an
excep ion, i has no any pa en he e o e we conside a ixed iden i ica ion o i
equal o 1. In his way, a node iden i ica ion de e mines uni ocally he posi ion o a
node in a pa sing ee. We say ha a p e e minal node in P a se(S)is any non-lea
node in P a se(S)wi h a leas one lea node as child.
Folding by Simila i y
Two o mulas can be compa ed by he s uc u e o hei quan i ie s and logical
connec i es. These measu es a e called simila i y wi h espec o quan i ica ion
and simila i y wi h espec o logical connec i es espec i ely. In he ollowing
de ini ions, we conside ha S1and S2a e wo o mulas in p enex no mal o m.
De ini ion 3.2 (Simila i y Func ion) We say ha is a simila i y unc ion om
he node iden i ica ion domain o P a se(S1) o he node iden i ica ion domain o
P a se(S2)i each non-lea n1∈P a se(S1)is mapped o a non-lea node n2=
(n1)∈P a se(S2)whe e quan i ie /connec i e in n1coincides wi h quan i ie /con-
nec i e in n2and he le el o n2is g ea e han o equal o he le el o n1.
De ini ion 3.3 (Simila i y w. . . Quan i ica ion) We say ha S2is simila o
S1w. . . quan i ica ion i o each non-lea node n1∈P a se(S1)con aining he
quan i ied se o a iables Qτx1, ..., xn he e exis s a non-lea node n2= (n1)∈
P a se(S2)con aining he quan i ied se o a iables Qτy1, ..., ymsuch ha (a) m≥
nand (b) he e exis wo sequences o nodes, M1 om P a se(S1)and M2 om
P a se(S2), wi h M1=M−1
2whe e M1con ains n1and i s p edecesso s ( om bo om
o up) and M2con ains n2and i s p edecesso s ( om bo om o up). (M−1
2is
ob ained by applying −1, when de ined, o elemen s in M2). I S2is simila o
S1w. . . quan i ica ion hen induces a se o possible enaming subs i u ions o
a iables in S1( om a iables in S2) which ag ees w. . . quan i ica ion. I QτX
is he se o quan i ied a iables in n1and QτYis he se o quan i ied a iables
in n2= (n1) hen induces subs i u ions o he o m {(xj, yk)}wi h xj∈Xand
yk∈Y.
In igu e 5, S2is simila o S1w. . . quan i ica ion:
Q=∀Na X={a, z}Y={b, k, , w}
Q=∀Seq(Na )X={L, S}Y={V, W }
and some examples o subs i u ions induced by a e:
{(a, b),(z, k),(L, V ),(S, W )} {(a, k),(z, ),(L, W ),(S, V )}...
De ini ion 3.4 (Simila i y w. . . Logical Connec i es) We say ha S2is in-
dep h simila o S1i o each non-lea node n1∈P a se(S1)con aining a logical
connec i e he e exis s a non-lea node n2= (n1)∈P a se(S2)and he e exis wo
sequences o nodes, M1 om P a se(S1)and M2 om P a se(S2), wi h M1=M−1
2
whe e M1con ains n1and i s p edecesso s ( om bo om o up) and M2con ains n2
and i s p edecesso s ( om bo om o up). We say ha S2is in-b ead h simila o S1
i o each le el l > 1o P a se(S1)wi h N1,l ={lx1p1, ..., lxkpk}as he se o all
nodes in lcon aining logical connec i es, he e exis s a se o nodes in P a se(S2),
possibly om se e al le els, say l1, ..., lj, o he o m N2,{l1,...,lj}={π1 (x1)p1ς1,...,-
πk (xk)pkςk}whe e πiand ςi(i= 1..k)a e (sub)sequences o numbe s. I he node
wi h iden i ica ion 1(le el l= 1) o P a se(S1)con ains a logical connec i e hen
he e exis s a node iden i ica ion in P a se(S2)o he o m π (1)ςin P a se(S2)
whe e πand ςa e (sub)sequences o numbe s. We say ha S2is simila o S1w. . .
logical connec i es i S2is in-dep h simila and in-b ead h simila o S1.

APPIA-GULP-PRODE 2001
1
⇔
1
⇔
2 1 1
∧
2 1 2
∨
2 1 1
∨
2 1 2
∨
3 2 1 1 1
∧
32112
∧
L e e l 1
L e e l 2
L e e l 3
Figu e 2: S2is simila o S1wi h espec o logical connec i es.
Fo example, in igu e 2 we show an example o simila i y wi h espec o logical
connec i es be ween he o mulas S1and S2( o legibili y easons, each i ep esen s
a g ound li e al):
S1: ( 1∧ 2)⇔( 3∨ 4)
S2: (( 5∧ 6)∨( 7∧ 8)) ⇔( 9∨ 10))
In-dep h simila i y:
(1) = 1 M1={1}M2={1}M−1
2={1}
(211) = 32111 M1={211,1}M2={32111,211,1}M−1
2={211,1}
(212) = 212 M1={212,1}M2={212,1}M−1
2={212,1}
In gene al, i exis s hen i may no be unique. Fo example, he node n211 ∈
P a se(S1) can also be mapped o he node n32112 ∈P a se(S2) ob aining in his way
ano he .
In-b ead h simila i y (in ela ion o he de ini ion 3.4, bold numbe s ha e been
used o xjpjin N1,l and o (xj)pjin N2,{l1,...,lj}):
l= 2 (le el 2), x1= 1, p1= 1, x2= 1, p2= 2, N1,2={211,212}
(1) = 1, π1= 32, ς1= 1, π2= 2, ς2=∅, N2,{2,3}={32111,212}
In igu e 3 we show an example o non-simila i y (non in-dep h simila i y) wi h
espec o logical connec i es be ween he o mulas S3and S4.
S3: ( 1∧ 2)⇔( 3∨ 4)
S4: (( 5∧ 6)∨( 7∧ 8)) ⇔ 9
Non in-dep h simila i y:
(1) = 1 M1={1}M2={1}M−1
2={1}
(212) = 211 M1={212,1}M2={211,1}M−1
2={212,1}
(211) = 32111 M1={211,1}M2={32111,211,1}M−1
2={211,212,1}
(211) = 32112 M1={211,1}M2={32112,211,1}M−1
2={211,212,1}
Folding by Simila i y
1
⇔
1
⇔
2 1 1
∧
2 1 2
∨
2 1 1
∨
3 2 1 1 1
∧
32112
∧
L e e l 1
L e e l 2
L e e l 3
Figu e 3: S4is no simila o S3wi h espec o logical connec i es.
The e is no any such ha M1=M−1
2 o he node n211 ∈P a se(S3).
In igu e 4 we show ano he example o non-simila i y (non in-b ead h simila i y)
wi h espec o logical connec i es be ween he o mulas S5and S6:
S5: ( 1∧ 2)⇔( 3∨ 4)
S6: ( 5∧ 6)∨( 7⇔(( 8∨ 9)∧( 10 ∧ 11)))
In-dep h simila i y:
(1) = 211,M1={1}M2={211},M−1
2={1}
(211) = 4321222,M1={211,1}M2={4321222,32122,212,1},M−1
2={211,1}
(212) = 4321221,M1={212,1}M2={4321221,32122,212,1},M−1
2={212,1}
Non in-b ead h simila i y:
l= 2 (le el 2), x1= 1, p1= 1, x2= 1, p2= 2, N1,2={211,212}
(1) = 212, π1= 43, ς1= 1, π2= 43, ς2= 2, N2,{4}={4321221,4321222}
De ini ion 3.5 (Simila i y) Le S2be simila o S1w. . . quan i ica ion and log-
ical connec i es by a unc ion . Le Lbe he se o all li e als in S1. Le NLea 1
be he se o all p e e minal nodes in P a se(S1). Le NLea 2be he se o nodes
n2∈P a se(S2)wi h n2= (n1)and n1∈NLea 1. Le Lea 2be he se o lea
nodes in sub ees o P a se(S2)wi h oo node n2∈NLea 2. We say ha S2is
simila o S1i he e exis a SLea 2⊆Lea 2, wi h Kas he se o li e als in nodes
o SLea 2, and a subs i u ion σinduced by such ha Lσ =K.
Fo example, in igu e 5, we show he simila i y be ween S1≡nocc(a, L, z)⇔
nocc(a, S, z) and S2≡( =b∧nocc(b, V, k))⇔(w=b∧nocc(b, W, k)).
Simila i y w. . o quan i ica ion:
(1) = 1 (211) = 211
Simila i y w. . . logical connec i es (In-dep h simila i y):
APPIA-GULP-PRODE 2001
1
⇔
1
∨
2 1 1
∧
2 1 2
∨
2 1 1
∧
2 1 2
⇔
4 3 2 1 2 2 1
∨
4321222
∧
L e e l 1
L e e l 2
L e e l 3
32122
∧
L e e l 4
Figu e 4: S6is no simila o S5wi h espec o logical connec i es.
1
za

,∀
2 11
SL


,

∀
3 2 111
⇔
4 3 2 1111 4 3 2 1112
),,( zLan o c c ),,( zSan o c c
1
w kb

,,,∀
2 11
WV


,

∀
3 2 111
⇔
4 3 2 1111 4 3 2 1112
∧
∧
5 4 3 2 11111


=
5 4 3 2 11112
),,( kVbn o c c
5 4 3 2 1112 1


=
5 4 3 2 1112 2
),,( kWbn o c c





Figu e 5: An example o simila i y.
Folding by Simila i y
(32111) = 32111 M1=M−1
2={32111,211,1}
Simila i y w. . . logical connec i es (In-b ead h simila i y):
l= 3 (211) = 211 N1,3={32111}N2,{3}={32111}
NLea 1={32111}NLea 2={32111}
Lea 2={543211111,543211112,543211121,543211122}
SLea 2={543211112,543211122}
Subs i u ion σinduced by :
σ={(a, b),(z, k),(L, V ),(S, W )}
L={nocc(a, L, z), nocc(a, S, z)}, K ={nocc(b, V, k), nocc(b, W, k)}, Lσ =K
3.1 Algo i hmic Jus i ica ion o Simila i y
The cons uc i e na u e o de ini ions 3.3, 3.4 and 3.5 can be jus i ied in an algo-
i hmic way. Di e en sea ching algo i hms can be p oposed o he cons uc ion o
he simila i y unc ion . We p opose a cons uc ion ollowing an inc emen al s yle.
Fi s , is cons uc ed in o de o decide only abou simila i y w. . . quan i ie s.
Then, we sea ch o a subs i u ion induced by ( his incomple e) . Finally, we sea ch
o a emaining pa o which decides abou simila i y w. . . logical connec i es.
Ou sea ching algo i hm ollows a gene a e-and- es s a egy. I is possible o ex-
plo e he comple e sea ch space due o he ini e numbe o quan i ie s and logical
connec i es in a o mula.
Ini ially, a sequence o non-lea node iden i ica ions is cons uc ed by a e sing
P a se(S1) in a b ead h- i s way. Fo example, o P a se(S1) in igu e 5 we ob ain
SeqS1:
SeqS1={1,211,32111}
F om his sequence, he subse o nodes con aining quan i ied se o a iables is
selec ed. Then, a gene a e and es s a egy is su ice o cons uc (an incomple e due
o he inc emen al cons uc ion) which decides abou simila i y w. . . quan i ie s.
The gene a e-pa gene a es a en a i e o each node in his subse . Hence,
each node con aining a quan i ied se o a iables o he o m QτXin P a se(S1) is
bounded o a node con aining a quan i ied se o a iables o he o m QτY. The
es pa decides abou condi ions (a) and (b) in de ini ion 3.3. I i is no possible o
cons uc an in hese e ms hen we conclude ha he e is no any simila i y w. . .
quan i ica ion and hen he e is no any simila i y . Fo example, o P a se(S1)
in igu e 5, he subse o nodes con aining quan i ied se o a iables is equal o
{1,211}.
(1) = 1 Qτ=∀Na X={a, z}Y={b, k, , w}
(211) = 211 Qτ=∀Seq(Na )X={L, S}Y={V, W }