MAYBE Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

begin(end(x0)) → rewrite(end(x0))
begin(1(x0)) → rotate(cut(C1(guess(x0))))
begin(2(x0)) → rotate(cut(C2(guess(x0))))
begin(0(x0)) → rotate(cut(C0(guess(x0))))
begin(L(x0)) → rotate(cut(CL(guess(x0))))
begin(R(x0)) → rotate(cut(CR(guess(x0))))
guess(1(x0)) → C1(guess(x0))
guess(2(x0)) → C2(guess(x0))
guess(0(x0)) → C0(guess(x0))
guess(L(x0)) → CL(guess(x0))
guess(R(x0)) → CR(guess(x0))
guess(1(x0)) → moveleft(B1(wait(x0)))
guess(2(x0)) → moveleft(B2(wait(x0)))
guess(0(x0)) → moveleft(B0(wait(x0)))
guess(L(x0)) → moveleft(BL(wait(x0)))
guess(R(x0)) → moveleft(BR(wait(x0)))
guess(end(x0)) → finish(end(x0))
C1(moveleft(B1(x0))) → moveleft(B1(A1(x0)))
C2(moveleft(B1(x0))) → moveleft(B1(A2(x0)))
C0(moveleft(B1(x0))) → moveleft(B1(A0(x0)))
CL(moveleft(B1(x0))) → moveleft(B1(AL(x0)))
CR(moveleft(B1(x0))) → moveleft(B1(AR(x0)))
C1(moveleft(B2(x0))) → moveleft(B2(A1(x0)))
C2(moveleft(B2(x0))) → moveleft(B2(A2(x0)))
C0(moveleft(B2(x0))) → moveleft(B2(A0(x0)))
CL(moveleft(B2(x0))) → moveleft(B2(AL(x0)))
CR(moveleft(B2(x0))) → moveleft(B2(AR(x0)))
C1(moveleft(B0(x0))) → moveleft(B0(A1(x0)))
C2(moveleft(B0(x0))) → moveleft(B0(A2(x0)))
C0(moveleft(B0(x0))) → moveleft(B0(A0(x0)))
CL(moveleft(B0(x0))) → moveleft(B0(AL(x0)))
CR(moveleft(B0(x0))) → moveleft(B0(AR(x0)))
C1(moveleft(BL(x0))) → moveleft(BL(A1(x0)))
C2(moveleft(BL(x0))) → moveleft(BL(A2(x0)))
C0(moveleft(BL(x0))) → moveleft(BL(A0(x0)))
CL(moveleft(BL(x0))) → moveleft(BL(AL(x0)))
CR(moveleft(BL(x0))) → moveleft(BL(AR(x0)))
C1(moveleft(BR(x0))) → moveleft(BR(A1(x0)))
C2(moveleft(BR(x0))) → moveleft(BR(A2(x0)))
C0(moveleft(BR(x0))) → moveleft(BR(A0(x0)))
CL(moveleft(BR(x0))) → moveleft(BR(AL(x0)))
CR(moveleft(BR(x0))) → moveleft(BR(AR(x0)))
cut(moveleft(B1(x0))) → D1(cut(goright(x0)))
cut(moveleft(B2(x0))) → D2(cut(goright(x0)))
cut(moveleft(B0(x0))) → D0(cut(goright(x0)))
cut(moveleft(BL(x0))) → DL(cut(goright(x0)))
cut(moveleft(BR(x0))) → DR(cut(goright(x0)))
goright(A1(x0)) → C1(goright(x0))
goright(A2(x0)) → C2(goright(x0))
goright(A0(x0)) → C0(goright(x0))
goright(AL(x0)) → CL(goright(x0))
goright(AR(x0)) → CR(goright(x0))
goright(wait(1(x0))) → moveleft(B1(wait(x0)))
goright(wait(2(x0))) → moveleft(B2(wait(x0)))
goright(wait(0(x0))) → moveleft(B0(wait(x0)))
goright(wait(L(x0))) → moveleft(BL(wait(x0)))
goright(wait(R(x0))) → moveleft(BR(wait(x0)))
goright(wait(end(x0))) → finish(end(x0))
C1(finish(x0)) → finish(1(x0))
C2(finish(x0)) → finish(2(x0))
C0(finish(x0)) → finish(0(x0))
CL(finish(x0)) → finish(L(x0))
CR(finish(x0)) → finish(R(x0))
cut(finish(x0)) → finish2(x0)
D1(finish2(x0)) → finish2(1(x0))
D2(finish2(x0)) → finish2(2(x0))
D0(finish2(x0)) → finish2(0(x0))
DL(finish2(x0)) → finish2(L(x0))
DR(finish2(x0)) → finish2(R(x0))
rotate(finish2(x0)) → rewrite(x0)
rewrite(1(2(1(x0)))) → begin(2(0(2(x0))))
rewrite(0(2(1(x0)))) → begin(1(0(2(x0))))
rewrite(L(2(1(x0)))) → begin(L(1(0(2(x0)))))
rewrite(1(2(0(x0)))) → begin(2(0(1(x0))))
rewrite(1(2(R(x0)))) → begin(2(0(1(R(x0)))))
rewrite(0(2(0(x0)))) → begin(1(0(1(x0))))
rewrite(L(2(0(x0)))) → begin(L(1(0(1(x0)))))
rewrite(0(2(R(x0)))) → begin(1(0(1(R(x0)))))

Proof

1 Termination Assumption

We assume termination of the following TRS
begin(end(x0)) → rewrite(end(x0))
begin(1(x0)) → rotate(cut(C1(guess(x0))))
begin(2(x0)) → rotate(cut(C2(guess(x0))))
begin(0(x0)) → rotate(cut(C0(guess(x0))))
begin(L(x0)) → rotate(cut(CL(guess(x0))))
begin(R(x0)) → rotate(cut(CR(guess(x0))))
guess(1(x0)) → C1(guess(x0))
guess(2(x0)) → C2(guess(x0))
guess(0(x0)) → C0(guess(x0))
guess(L(x0)) → CL(guess(x0))
guess(R(x0)) → CR(guess(x0))
guess(1(x0)) → moveleft(B1(wait(x0)))
guess(2(x0)) → moveleft(B2(wait(x0)))
guess(0(x0)) → moveleft(B0(wait(x0)))
guess(L(x0)) → moveleft(BL(wait(x0)))
guess(R(x0)) → moveleft(BR(wait(x0)))
guess(end(x0)) → finish(end(x0))
C1(moveleft(B1(x0))) → moveleft(B1(A1(x0)))
C2(moveleft(B1(x0))) → moveleft(B1(A2(x0)))
C0(moveleft(B1(x0))) → moveleft(B1(A0(x0)))
CL(moveleft(B1(x0))) → moveleft(B1(AL(x0)))
CR(moveleft(B1(x0))) → moveleft(B1(AR(x0)))
C1(moveleft(B2(x0))) → moveleft(B2(A1(x0)))
C2(moveleft(B2(x0))) → moveleft(B2(A2(x0)))
C0(moveleft(B2(x0))) → moveleft(B2(A0(x0)))
CL(moveleft(B2(x0))) → moveleft(B2(AL(x0)))
CR(moveleft(B2(x0))) → moveleft(B2(AR(x0)))
C1(moveleft(B0(x0))) → moveleft(B0(A1(x0)))
C2(moveleft(B0(x0))) → moveleft(B0(A2(x0)))
C0(moveleft(B0(x0))) → moveleft(B0(A0(x0)))
CL(moveleft(B0(x0))) → moveleft(B0(AL(x0)))
CR(moveleft(B0(x0))) → moveleft(B0(AR(x0)))
C1(moveleft(BL(x0))) → moveleft(BL(A1(x0)))
C2(moveleft(BL(x0))) → moveleft(BL(A2(x0)))
C0(moveleft(BL(x0))) → moveleft(BL(A0(x0)))
CL(moveleft(BL(x0))) → moveleft(BL(AL(x0)))
CR(moveleft(BL(x0))) → moveleft(BL(AR(x0)))
C1(moveleft(BR(x0))) → moveleft(BR(A1(x0)))
C2(moveleft(BR(x0))) → moveleft(BR(A2(x0)))
C0(moveleft(BR(x0))) → moveleft(BR(A0(x0)))
CL(moveleft(BR(x0))) → moveleft(BR(AL(x0)))
CR(moveleft(BR(x0))) → moveleft(BR(AR(x0)))
cut(moveleft(B1(x0))) → D1(cut(goright(x0)))
cut(moveleft(B2(x0))) → D2(cut(goright(x0)))
cut(moveleft(B0(x0))) → D0(cut(goright(x0)))
cut(moveleft(BL(x0))) → DL(cut(goright(x0)))
cut(moveleft(BR(x0))) → DR(cut(goright(x0)))
goright(A1(x0)) → C1(goright(x0))
goright(A2(x0)) → C2(goright(x0))
goright(A0(x0)) → C0(goright(x0))
goright(AL(x0)) → CL(goright(x0))
goright(AR(x0)) → CR(goright(x0))
goright(wait(1(x0))) → moveleft(B1(wait(x0)))
goright(wait(2(x0))) → moveleft(B2(wait(x0)))
goright(wait(0(x0))) → moveleft(B0(wait(x0)))
goright(wait(L(x0))) → moveleft(BL(wait(x0)))
goright(wait(R(x0))) → moveleft(BR(wait(x0)))
goright(wait(end(x0))) → finish(end(x0))
C1(finish(x0)) → finish(1(x0))
C2(finish(x0)) → finish(2(x0))
C0(finish(x0)) → finish(0(x0))
CL(finish(x0)) → finish(L(x0))
CR(finish(x0)) → finish(R(x0))
cut(finish(x0)) → finish2(x0)
D1(finish2(x0)) → finish2(1(x0))
D2(finish2(x0)) → finish2(2(x0))
D0(finish2(x0)) → finish2(0(x0))
DL(finish2(x0)) → finish2(L(x0))
DR(finish2(x0)) → finish2(R(x0))
rotate(finish2(x0)) → rewrite(x0)
rewrite(1(2(1(x0)))) → begin(2(0(2(x0))))
rewrite(0(2(1(x0)))) → begin(1(0(2(x0))))
rewrite(L(2(1(x0)))) → begin(L(1(0(2(x0)))))
rewrite(1(2(0(x0)))) → begin(2(0(1(x0))))
rewrite(1(2(R(x0)))) → begin(2(0(1(R(x0)))))
rewrite(0(2(0(x0)))) → begin(1(0(1(x0))))
rewrite(L(2(0(x0)))) → begin(L(1(0(1(x0)))))
rewrite(0(2(R(x0)))) → begin(1(0(1(R(x0)))))