Certification Problem

Input (TPDB TRS_Standard/HirokawaMiddeldorp_04/t009)

The rewrite relation of the following TRS is considered.

start(i) busy(F,closed,stop,false,false,false,i) (1)
busy(BF,d,stop,b1,b2,b3,i) incorrect (2)
busy(FS,d,stop,b1,b2,b3,i) incorrect (3)
busy(fl,open,up,b1,b2,b3,i) incorrect (4)
busy(fl,open,down,b1,b2,b3,i) incorrect (5)
busy(B,closed,stop,false,false,false,empty) correct (6)
busy(F,closed,stop,false,false,false,empty) correct (7)
busy(S,closed,stop,false,false,false,empty) correct (8)
busy(B,closed,stop,false,false,false,newbuttons(i1,i2,i3,i)) idle(B,closed,stop,false,false,false,newbuttons(i1,i2,i3,i)) (9)
busy(F,closed,stop,false,false,false,newbuttons(i1,i2,i3,i)) idle(F,closed,stop,false,false,false,newbuttons(i1,i2,i3,i)) (10)
busy(S,closed,stop,false,false,false,newbuttons(i1,i2,i3,i)) idle(S,closed,stop,false,false,false,newbuttons(i1,i2,i3,i)) (11)
busy(B,open,stop,false,b2,b3,i) idle(B,closed,stop,false,b2,b3,i) (12)
busy(F,open,stop,b1,false,b3,i) idle(F,closed,stop,b1,false,b3,i) (13)
busy(S,open,stop,b1,b2,false,i) idle(S,closed,stop,b1,b2,false,i) (14)
busy(B,d,stop,true,b2,b3,i) idle(B,open,stop,false,b2,b3,i) (15)
busy(F,d,stop,b1,true,b3,i) idle(F,open,stop,b1,false,b3,i) (16)
busy(S,d,stop,b1,b2,true,i) idle(S,open,stop,b1,b2,false,i) (17)
busy(B,closed,down,b1,b2,b3,i) idle(B,closed,stop,b1,b2,b3,i) (18)
busy(S,closed,up,b1,b2,b3,i) idle(S,closed,stop,b1,b2,b3,i) (19)
busy(B,closed,up,true,b2,b3,i) idle(B,closed,stop,true,b2,b3,i) (20)
busy(F,closed,up,b1,true,b3,i) idle(F,closed,stop,b1,true,b3,i) (21)
busy(F,closed,down,b1,true,b3,i) idle(F,closed,stop,b1,true,b3,i) (22)
busy(S,closed,down,b1,b2,true,i) idle(S,closed,stop,b1,b2,true,i) (23)
busy(B,closed,up,false,b2,b3,i) idle(BF,closed,up,false,b2,b3,i) (24)
busy(F,closed,up,b1,false,b3,i) idle(FS,closed,up,b1,false,b3,i) (25)
busy(F,closed,down,b1,false,b3,i) idle(BF,closed,down,b1,false,b3,i) (26)
busy(S,closed,down,b1,b2,false,i) idle(FS,closed,down,b1,b2,false,i) (27)
busy(BF,closed,up,b1,b2,b3,i) idle(F,closed,up,b1,b2,b3,i) (28)
busy(BF,closed,down,b1,b2,b3,i) idle(B,closed,down,b1,b2,b3,i) (29)
busy(FS,closed,up,b1,b2,b3,i) idle(S,closed,up,b1,b2,b3,i) (30)
busy(FS,closed,down,b1,b2,b3,i) idle(F,closed,down,b1,b2,b3,i) (31)
busy(B,closed,stop,false,true,b3,i) idle(B,closed,up,false,true,b3,i) (32)
busy(B,closed,stop,false,false,true,i) idle(B,closed,up,false,false,true,i) (33)
busy(F,closed,stop,true,false,b3,i) idle(F,closed,down,true,false,b3,i) (34)
busy(F,closed,stop,false,false,true,i) idle(F,closed,up,false,false,true,i) (35)
busy(S,closed,stop,b1,true,false,i) idle(S,closed,down,b1,true,false,i) (36)
busy(S,closed,stop,true,false,false,i) idle(S,closed,down,true,false,false,i) (37)
idle(fl,d,m,b1,b2,b3,empty) busy(fl,d,m,b1,b2,b3,empty) (38)
idle(fl,d,m,b1,b2,b3,newbuttons(i1,i2,i3,i)) busy(fl,d,m,or(b1,i1),or(b2,i2),or(b3,i3),i) (39)
or(true,b) true (40)
or(false,b) b (41)

Property / Task

Prove or disprove termination.

Answer / Result

Yes.

Proof (by NaTT @ termCOMP 2023)

1 Dependency Pair Transformation

The following set of initial dependency pairs has been identified.
busy#(F,closed,stop,false,false,true,i) idle#(F,closed,up,false,false,true,i) (42)
busy#(F,closed,down,b1,false,b3,i) idle#(BF,closed,down,b1,false,b3,i) (43)
busy#(B,closed,down,b1,b2,b3,i) idle#(B,closed,stop,b1,b2,b3,i) (44)
busy#(B,closed,stop,false,false,false,newbuttons(i1,i2,i3,i)) idle#(B,closed,stop,false,false,false,newbuttons(i1,i2,i3,i)) (45)
busy#(FS,closed,up,b1,b2,b3,i) idle#(S,closed,up,b1,b2,b3,i) (46)
busy#(S,closed,down,b1,b2,true,i) idle#(S,closed,stop,b1,b2,true,i) (47)
busy#(FS,closed,down,b1,b2,b3,i) idle#(F,closed,down,b1,b2,b3,i) (48)
busy#(F,closed,stop,true,false,b3,i) idle#(F,closed,down,true,false,b3,i) (49)
busy#(F,closed,down,b1,true,b3,i) idle#(F,closed,stop,b1,true,b3,i) (50)
busy#(S,open,stop,b1,b2,false,i) idle#(S,closed,stop,b1,b2,false,i) (51)
busy#(F,closed,up,b1,true,b3,i) idle#(F,closed,stop,b1,true,b3,i) (52)
busy#(F,closed,up,b1,false,b3,i) idle#(FS,closed,up,b1,false,b3,i) (53)
busy#(S,closed,stop,b1,true,false,i) idle#(S,closed,down,b1,true,false,i) (54)
busy#(S,closed,down,b1,b2,false,i) idle#(FS,closed,down,b1,b2,false,i) (55)
busy#(F,closed,stop,false,false,false,newbuttons(i1,i2,i3,i)) idle#(F,closed,stop,false,false,false,newbuttons(i1,i2,i3,i)) (56)
busy#(S,closed,stop,false,false,false,newbuttons(i1,i2,i3,i)) idle#(S,closed,stop,false,false,false,newbuttons(i1,i2,i3,i)) (57)
busy#(B,open,stop,false,b2,b3,i) idle#(B,closed,stop,false,b2,b3,i) (58)
start#(i) busy#(F,closed,stop,false,false,false,i) (59)
busy#(F,open,stop,b1,false,b3,i) idle#(F,closed,stop,b1,false,b3,i) (60)
busy#(S,closed,up,b1,b2,b3,i) idle#(S,closed,stop,b1,b2,b3,i) (61)
busy#(BF,closed,up,b1,b2,b3,i) idle#(F,closed,up,b1,b2,b3,i) (62)
busy#(B,d,stop,true,b2,b3,i) idle#(B,open,stop,false,b2,b3,i) (63)
busy#(B,closed,stop,false,true,b3,i) idle#(B,closed,up,false,true,b3,i) (64)
idle#(fl,d,m,b1,b2,b3,newbuttons(i1,i2,i3,i)) or#(b1,i1) (65)
busy#(F,d,stop,b1,true,b3,i) idle#(F,open,stop,b1,false,b3,i) (66)
idle#(fl,d,m,b1,b2,b3,newbuttons(i1,i2,i3,i)) or#(b3,i3) (67)
busy#(S,d,stop,b1,b2,true,i) idle#(S,open,stop,b1,b2,false,i) (68)
busy#(B,closed,stop,false,false,true,i) idle#(B,closed,up,false,false,true,i) (69)
idle#(fl,d,m,b1,b2,b3,newbuttons(i1,i2,i3,i)) busy#(fl,d,m,or(b1,i1),or(b2,i2),or(b3,i3),i) (70)
busy#(S,closed,stop,true,false,false,i) idle#(S,closed,down,true,false,false,i) (71)
busy#(BF,closed,down,b1,b2,b3,i) idle#(B,closed,down,b1,b2,b3,i) (72)
busy#(B,closed,up,false,b2,b3,i) idle#(BF,closed,up,false,b2,b3,i) (73)
busy#(B,closed,up,true,b2,b3,i) idle#(B,closed,stop,true,b2,b3,i) (74)
idle#(fl,d,m,b1,b2,b3,empty) busy#(fl,d,m,b1,b2,b3,empty) (75)
idle#(fl,d,m,b1,b2,b3,newbuttons(i1,i2,i3,i)) or#(b2,i2) (76)

1.1 Dependency Graph Processor

The dependency pairs are split into 1 component.