- : unit = () - : unit = () h : heuristic = - : unit = () APPLY CRITERIA (Marked dependency pairs) TRS termination of: [1] eq(0,0) -> true [2] eq(0,s(x)) -> false [3] eq(s(x),0) -> false [4] eq(s(x),s(y)) -> eq(x,y) [5] le(0,y) -> true [6] le(s(x),0) -> false [7] le(s(x),s(y)) -> le(x,y) [8] app(nil,y) -> y [9] app(add(n,x),y) -> add(n,app(x,y)) [10] min(add(n,nil)) -> n [11] min(add(n,add(m,x))) -> if_min(le(n,m),add(n,add(m,x))) [12] if_min(true,add(n,add(m,x))) -> min(add(n,x)) [13] if_min(false,add(n,add(m,x))) -> min(add(m,x)) [14] rm(n,nil) -> nil [15] rm(n,add(m,x)) -> if_rm(eq(n,m),n,add(m,x)) [16] if_rm(true,n,add(m,x)) -> rm(n,x) [17] if_rm(false,n,add(m,x)) -> add(m,rm(n,x)) [18] minsort(nil,nil) -> nil [19] minsort(add(n,x),y) -> if_minsort(eq(n,min(add(n,x))),add(n,x),y) [20] if_minsort(true,add(n,x),y) -> add(n,minsort(app(rm(n,x),y),nil)) [21] if_minsort(false,add(n,x),y) -> minsort(x,add(n,y)) Sub problem: guided: DP termination of: END GUIDED APPLY CRITERIA (Graph splitting) Found 6 components: { --> --> --> --> } { --> } { --> --> --> --> } { --> } { --> --> --> --> } { --> } APPLY CRITERIA (Subterm criterion) APPLY CRITERIA (Choosing graph) Trying to solve the following constraints: { eq(0,0) >= true ; eq(0,s(x)) >= false ; eq(s(x),0) >= false ; eq(s(x),s(y)) >= eq(x,y) ; le(0,y) >= true ; le(s(x),0) >= false ; le(s(x),s(y)) >= le(x,y) ; app(nil,y) >= y ; app(add(n,x),y) >= add(n,app(x,y)) ; min(add(n,nil)) >= n ; min(add(n,add(m,x))) >= if_min(le(n,m),add(n,add(m,x))) ; if_min(true,add(n,add(m,x))) >= min(add(n,x)) ; if_min(false,add(n,add(m,x))) >= min(add(m,x)) ; rm(n,nil) >= nil ; rm(n,add(m,x)) >= if_rm(eq(n,m),n,add(m,x)) ; if_rm(true,n,add(m,x)) >= rm(n,x) ; if_rm(false,n,add(m,x)) >= add(m,rm(n,x)) ; minsort(nil,nil) >= nil ; minsort(add(n,x),y) >= if_minsort(eq(n,min(add(n,x))),add(n,x),y) ; if_minsort(true,add(n,x),y) >= add(n,minsort(app(rm(n,x),y),nil)) ; if_minsort(false,add(n,x),y) >= minsort(x,add(n,y)) ; Marked_if_minsort(true,add(n,x),y) >= Marked_minsort(app(rm(n,x),y),nil) ; Marked_if_minsort(false,add(n,x),y) >= Marked_minsort(x,add(n,y)) ; Marked_minsort(add(n,x),y) >= Marked_if_minsort(eq(n,min(add(n,x))), add(n,x),y) ; } + Disjunctions:{ { Marked_if_minsort(true,add(n,x),y) > Marked_minsort(app(rm(n,x),y),nil) ; } { Marked_if_minsort(false,add(n,x),y) > Marked_minsort(x,add(n,y)) ; } { Marked_minsort(add(n,x),y) > Marked_if_minsort(eq(n,min(add(n,x))), add(n,x),y) ; } } === TIMER virtual : 10.000000 === Entering poly_solver Starting Sat solver initialization Calling Sat solver... === STOPING TIMER virtual === === TIMER real : 10.000000 === === STOPING TIMER real === Sat solver returned Sat solver result read === STOPING TIMER real === === STOPING TIMER virtual === constraint: eq(0,0) >= true constraint: eq(0,s(x)) >= false constraint: eq(s(x),0) >= false constraint: eq(s(x),s(y)) >= eq(x,y) constraint: le(0,y) >= true constraint: le(s(x),0) >= false constraint: le(s(x),s(y)) >= le(x,y) constraint: app(nil,y) >= y constraint: app(add(n,x),y) >= add(n,app(x,y)) constraint: min(add(n,nil)) >= n constraint: min(add(n,add(m,x))) >= if_min(le(n,m),add(n,add(m,x))) constraint: if_min(true,add(n,add(m,x))) >= min(add(n,x)) constraint: if_min(false,add(n,add(m,x))) >= min(add(m,x)) constraint: rm(n,nil) >= nil constraint: rm(n,add(m,x)) >= if_rm(eq(n,m),n,add(m,x)) constraint: if_rm(true,n,add(m,x)) >= rm(n,x) constraint: if_rm(false,n,add(m,x)) >= add(m,rm(n,x)) constraint: minsort(nil,nil) >= nil constraint: minsort(add(n,x),y) >= if_minsort(eq(n,min(add(n,x))),add(n,x),y) constraint: if_minsort(true,add(n,x),y) >= add(n,minsort(app(rm(n,x),y),nil)) constraint: if_minsort(false,add(n,x),y) >= minsort(x,add(n,y)) constraint: Marked_if_minsort(true,add(n,x),y) >= Marked_minsort(app(rm(n,x),y), nil) constraint: Marked_if_minsort(false,add(n,x),y) >= Marked_minsort(x,add(n,y)) constraint: Marked_minsort(add(n,x),y) >= Marked_if_minsort(eq(n,min(add(n,x))), add(n,x),y) APPLY CRITERIA (Subterm criterion) ST: Marked_app -> 1 APPLY CRITERIA (Subterm criterion) ST: Marked_if_rm -> 3 Marked_rm -> 2 APPLY CRITERIA (Subterm criterion) ST: Marked_eq -> 1 APPLY CRITERIA (Subterm criterion) APPLY CRITERIA (Choosing graph) Trying to solve the following constraints: { eq(0,0) >= true ; eq(0,s(x)) >= false ; eq(s(x),0) >= false ; eq(s(x),s(y)) >= eq(x,y) ; le(0,y) >= true ; le(s(x),0) >= false ; le(s(x),s(y)) >= le(x,y) ; app(nil,y) >= y ; app(add(n,x),y) >= add(n,app(x,y)) ; min(add(n,nil)) >= n ; min(add(n,add(m,x))) >= if_min(le(n,m),add(n,add(m,x))) ; if_min(true,add(n,add(m,x))) >= min(add(n,x)) ; if_min(false,add(n,add(m,x))) >= min(add(m,x)) ; rm(n,nil) >= nil ; rm(n,add(m,x)) >= if_rm(eq(n,m),n,add(m,x)) ; if_rm(true,n,add(m,x)) >= rm(n,x) ; if_rm(false,n,add(m,x)) >= add(m,rm(n,x)) ; minsort(nil,nil) >= nil ; minsort(add(n,x),y) >= if_minsort(eq(n,min(add(n,x))),add(n,x),y) ; if_minsort(true,add(n,x),y) >= add(n,minsort(app(rm(n,x),y),nil)) ; if_minsort(false,add(n,x),y) >= minsort(x,add(n,y)) ; Marked_min(add(n,add(m,x))) >= Marked_if_min(le(n,m),add(n,add(m,x))) ; Marked_if_min(true,add(n,add(m,x))) >= Marked_min(add(n,x)) ; Marked_if_min(false,add(n,add(m,x))) >= Marked_min(add(m,x)) ; } + Disjunctions:{ { Marked_min(add(n,add(m,x))) > Marked_if_min(le(n,m),add(n,add(m,x))) ; } { Marked_if_min(true,add(n,add(m,x))) > Marked_min(add(n,x)) ; } { Marked_if_min(false,add(n,add(m,x))) > Marked_min(add(m,x)) ; } } === TIMER virtual : 10.000000 === Entering poly_solver Starting Sat solver initialization Calling Sat solver... === STOPING TIMER virtual === === TIMER real : 10.000000 === === STOPING TIMER real === Sat solver returned Sat solver result read === STOPING TIMER real === === STOPING TIMER virtual === constraint: eq(0,0) >= true constraint: eq(0,s(x)) >= false constraint: eq(s(x),0) >= false constraint: eq(s(x),s(y)) >= eq(x,y) constraint: le(0,y) >= true constraint: le(s(x),0) >= false constraint: le(s(x),s(y)) >= le(x,y) constraint: app(nil,y) >= y constraint: app(add(n,x),y) >= add(n,app(x,y)) constraint: min(add(n,nil)) >= n constraint: min(add(n,add(m,x))) >= if_min(le(n,m),add(n,add(m,x))) constraint: if_min(true,add(n,add(m,x))) >= min(add(n,x)) constraint: if_min(false,add(n,add(m,x))) >= min(add(m,x)) constraint: rm(n,nil) >= nil constraint: rm(n,add(m,x)) >= if_rm(eq(n,m),n,add(m,x)) constraint: if_rm(true,n,add(m,x)) >= rm(n,x) constraint: if_rm(false,n,add(m,x)) >= add(m,rm(n,x)) constraint: minsort(nil,nil) >= nil constraint: minsort(add(n,x),y) >= if_minsort(eq(n,min(add(n,x))),add(n,x),y) constraint: if_minsort(true,add(n,x),y) >= add(n,minsort(app(rm(n,x),y),nil)) constraint: if_minsort(false,add(n,x),y) >= minsort(x,add(n,y)) constraint: Marked_min(add(n,add(m,x))) >= Marked_if_min(le(n,m), add(n,add(m,x))) constraint: Marked_if_min(true,add(n,add(m,x))) >= Marked_min(add(n,x)) constraint: Marked_if_min(false,add(n,add(m,x))) >= Marked_min(add(m,x)) APPLY CRITERIA (Subterm criterion) ST: Marked_le -> 1 APPLY CRITERIA (Graph splitting) Found 1 components: { --> --> } APPLY CRITERIA (Subterm criterion) ST: Marked_if_minsort -> 2 Marked_minsort -> 1 APPLY CRITERIA (Graph splitting) Found 0 components: APPLY CRITERIA (Graph splitting) Found 0 components: APPLY CRITERIA (Graph splitting) Found 0 components: APPLY CRITERIA (Graph splitting) Found 0 components: APPLY CRITERIA (Graph splitting) Found 0 components: APPLY CRITERIA (Graph splitting) Found 0 components: SOLVED { TRS termination of: [1] eq(0,0) -> true [2] eq(0,s(x)) -> false [3] eq(s(x),0) -> false [4] eq(s(x),s(y)) -> eq(x,y) [5] le(0,y) -> true [6] le(s(x),0) -> false [7] le(s(x),s(y)) -> le(x,y) [8] app(nil,y) -> y [9] app(add(n,x),y) -> add(n,app(x,y)) [10] min(add(n,nil)) -> n [11] min(add(n,add(m,x))) -> if_min(le(n,m),add(n,add(m,x))) [12] if_min(true,add(n,add(m,x))) -> min(add(n,x)) [13] if_min(false,add(n,add(m,x))) -> min(add(m,x)) [14] rm(n,nil) -> nil [15] rm(n,add(m,x)) -> if_rm(eq(n,m),n,add(m,x)) [16] if_rm(true,n,add(m,x)) -> rm(n,x) [17] if_rm(false,n,add(m,x)) -> add(m,rm(n,x)) [18] minsort(nil,nil) -> nil [19] minsort(add(n,x),y) -> if_minsort(eq(n,min(add(n,x))),add(n,x),y) [20] if_minsort(true,add(n,x),y) -> add(n,minsort(app(rm(n,x),y),nil)) [21] if_minsort(false,add(n,x),y) -> minsort(x,add(n,y)) , CRITERION: MDP [ { DP termination of: , CRITERION: SG [ { DP termination of: , CRITERION: CG using polynomial interpretation = [ true ] () = 0; [ Marked_minsort ] (X0,X1) = 2*X1 + 2*X0; [ add ] (X0,X1) = 1*X1 + 2*X0 + 1; [ s ] (X0) = 3*X0; [ if_rm ] (X0,X1,X2) = 1*X2 + 1*X1; [ 0 ] () = 0; [ if_min ] (X0,X1) = 2*X1; [ app ] (X0,X1) = 1*X1 + 1*X0; [ if_minsort ] (X0,X1,X2) = 2*X2 + 2*X1; [ eq ] (X0,X1) = 0; [ min ] (X0) = 2*X0 + 2; [ le ] (X0,X1) = 0; [ minsort ] (X0,X1) = 2*X1 + 2*X0; [ false ] () = 0; [ rm ] (X0,X1) = 1*X1 + 1*X0; [ nil ] () = 0; [ Marked_if_minsort ] (X0,X1,X2) = 2*X2 + 2*X1; removing [ { DP termination of: , CRITERION: SG [ { DP termination of: , CRITERION: ST [ { DP termination of: , CRITERION: SG [ ]} ]} ]} ]} { DP termination of: , CRITERION: ST [ { DP termination of: , CRITERION: SG [ ]} ]} { DP termination of: , CRITERION: ST [ { DP termination of: , CRITERION: SG [ ]} ]} { DP termination of: , CRITERION: ST [ { DP termination of: , CRITERION: SG [ ]} ]} { DP termination of: , CRITERION: CG using polynomial interpretation = [ true ] () = 0; [ add ] (X0,X1) = 1*X1 + 2*X0 + 2; [ s ] (X0) = 3*X0; [ Marked_min ] (X0) = 2*X0; [ if_rm ] (X0,X1,X2) = 1*X2; [ 0 ] () = 0; [ if_min ] (X0,X1) = 2*X1; [ app ] (X0,X1) = 1*X1 + 1*X0; [ Marked_if_min ] (X0,X1) = 2*X1; [ if_minsort ] (X0,X1,X2) = 1*X2 + 1*X1; [ eq ] (X0,X1) = 0; [ min ] (X0) = 2*X0; [ le ] (X0,X1) = 0; [ minsort ] (X0,X1) = 1*X1 + 1*X0; [ false ] () = 0; [ rm ] (X0,X1) = 1*X1; [ nil ] () = 0; removing < Marked_if_min(false,add(n,add(m,x))),Marked_min(add(m,x))> [ { DP termination of: , CRITERION: SG [ ]} ]} { DP termination of: , CRITERION: ST [ { DP termination of: , CRITERION: SG [ ]} ]} ]} ]} Cime worked for 0.341982 seconds (real time) Cime Exit Status: 0