4.92/2.13 YES 4.92/2.14 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 4.92/2.14 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.92/2.14 4.92/2.14 4.92/2.14 Left Termination of the query pattern 4.92/2.14 4.92/2.14 transpose(g,a) 4.92/2.14 4.92/2.14 w.r.t. the given Prolog program could successfully be proven: 4.92/2.14 4.92/2.14 (0) Prolog 4.92/2.14 (1) PrologToPiTRSProof [SOUND, 0 ms] 4.92/2.14 (2) PiTRS 4.92/2.14 (3) DependencyPairsProof [EQUIVALENT, 2 ms] 4.92/2.14 (4) PiDP 4.92/2.14 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 4.92/2.14 (6) AND 4.92/2.14 (7) PiDP 4.92/2.14 (8) UsableRulesProof [EQUIVALENT, 0 ms] 4.92/2.14 (9) PiDP 4.92/2.14 (10) PiDPToQDPProof [SOUND, 0 ms] 4.92/2.14 (11) QDP 4.92/2.14 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.92/2.14 (13) YES 4.92/2.14 (14) PiDP 4.92/2.14 (15) UsableRulesProof [EQUIVALENT, 0 ms] 4.92/2.14 (16) PiDP 4.92/2.14 (17) PiDPToQDPProof [SOUND, 0 ms] 4.92/2.14 (18) QDP 4.92/2.14 (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.92/2.14 (20) YES 4.92/2.14 4.92/2.14 4.92/2.14 ---------------------------------------- 4.92/2.14 4.92/2.14 (0) 4.92/2.14 Obligation: 4.92/2.14 Clauses: 4.92/2.14 4.92/2.14 transpose(A, B) :- transpose_aux(A, [], B). 4.92/2.14 transpose_aux(.(R, Rs), X1, .(C, Cs)) :- ','(row2col(R, .(C, Cs), Cols1, [], Accm), transpose_aux(Rs, Accm, Cols1)). 4.92/2.14 transpose_aux([], X, X). 4.92/2.14 row2col(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) :- row2col(Xs, Cols, Cols1, .([], A), B). 4.92/2.14 row2col([], [], [], A, A). 4.92/2.14 4.92/2.14 4.92/2.14 Query: transpose(g,a) 4.92/2.14 ---------------------------------------- 4.92/2.14 4.92/2.14 (1) PrologToPiTRSProof (SOUND) 4.92/2.14 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 4.92/2.14 4.92/2.14 transpose_in_2: (b,f) 4.92/2.14 4.92/2.14 transpose_aux_in_3: (b,b,f) 4.92/2.14 4.92/2.14 row2col_in_5: (b,f,f,b,f) 4.92/2.14 4.92/2.14 Transforming Prolog into the following Term Rewriting System: 4.92/2.14 4.92/2.14 Pi-finite rewrite system: 4.92/2.14 The TRS R consists of the following rules: 4.92/2.14 4.92/2.14 transpose_in_ga(A, B) -> U1_ga(A, B, transpose_aux_in_gga(A, [], B)) 4.92/2.14 transpose_aux_in_gga(.(R, Rs), X1, .(C, Cs)) -> U2_gga(R, Rs, X1, C, Cs, row2col_in_gaaga(R, .(C, Cs), Cols1, [], Accm)) 4.92/2.14 row2col_in_gaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> U4_gaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_in_gaaga(Xs, Cols, Cols1, .([], A), B)) 4.92/2.14 row2col_in_gaaga([], [], [], A, A) -> row2col_out_gaaga([], [], [], A, A) 4.92/2.14 U4_gaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_out_gaaga(Xs, Cols, Cols1, .([], A), B)) -> row2col_out_gaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) 4.92/2.14 U2_gga(R, Rs, X1, C, Cs, row2col_out_gaaga(R, .(C, Cs), Cols1, [], Accm)) -> U3_gga(R, Rs, X1, C, Cs, transpose_aux_in_gga(Rs, Accm, Cols1)) 4.92/2.14 transpose_aux_in_gga([], X, X) -> transpose_aux_out_gga([], X, X) 4.92/2.14 U3_gga(R, Rs, X1, C, Cs, transpose_aux_out_gga(Rs, Accm, Cols1)) -> transpose_aux_out_gga(.(R, Rs), X1, .(C, Cs)) 4.92/2.14 U1_ga(A, B, transpose_aux_out_gga(A, [], B)) -> transpose_out_ga(A, B) 4.92/2.14 4.92/2.14 The argument filtering Pi contains the following mapping: 4.92/2.14 transpose_in_ga(x1, x2) = transpose_in_ga(x1) 4.92/2.14 4.92/2.14 U1_ga(x1, x2, x3) = U1_ga(x3) 4.92/2.14 4.92/2.14 transpose_aux_in_gga(x1, x2, x3) = transpose_aux_in_gga(x1, x2) 4.92/2.14 4.92/2.14 .(x1, x2) = .(x1, x2) 4.92/2.14 4.92/2.14 U2_gga(x1, x2, x3, x4, x5, x6) = U2_gga(x2, x6) 4.92/2.14 4.92/2.14 row2col_in_gaaga(x1, x2, x3, x4, x5) = row2col_in_gaaga(x1, x4) 4.92/2.14 4.92/2.14 U4_gaaga(x1, x2, x3, x4, x5, x6, x7, x8) = U4_gaaga(x8) 4.92/2.14 4.92/2.14 [] = [] 4.92/2.14 4.92/2.14 row2col_out_gaaga(x1, x2, x3, x4, x5) = row2col_out_gaaga(x5) 4.92/2.14 4.92/2.14 U3_gga(x1, x2, x3, x4, x5, x6) = U3_gga(x6) 4.92/2.14 4.92/2.14 transpose_aux_out_gga(x1, x2, x3) = transpose_aux_out_gga 4.92/2.14 4.92/2.14 transpose_out_ga(x1, x2) = transpose_out_ga 4.92/2.14 4.92/2.14 4.92/2.14 4.92/2.14 4.92/2.14 4.92/2.14 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 4.92/2.14 4.92/2.14 4.92/2.14 4.92/2.14 ---------------------------------------- 4.92/2.14 4.92/2.14 (2) 4.92/2.14 Obligation: 4.92/2.14 Pi-finite rewrite system: 4.92/2.14 The TRS R consists of the following rules: 4.92/2.14 4.92/2.14 transpose_in_ga(A, B) -> U1_ga(A, B, transpose_aux_in_gga(A, [], B)) 4.92/2.14 transpose_aux_in_gga(.(R, Rs), X1, .(C, Cs)) -> U2_gga(R, Rs, X1, C, Cs, row2col_in_gaaga(R, .(C, Cs), Cols1, [], Accm)) 4.92/2.14 row2col_in_gaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> U4_gaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_in_gaaga(Xs, Cols, Cols1, .([], A), B)) 4.92/2.14 row2col_in_gaaga([], [], [], A, A) -> row2col_out_gaaga([], [], [], A, A) 4.92/2.14 U4_gaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_out_gaaga(Xs, Cols, Cols1, .([], A), B)) -> row2col_out_gaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) 4.92/2.14 U2_gga(R, Rs, X1, C, Cs, row2col_out_gaaga(R, .(C, Cs), Cols1, [], Accm)) -> U3_gga(R, Rs, X1, C, Cs, transpose_aux_in_gga(Rs, Accm, Cols1)) 4.92/2.14 transpose_aux_in_gga([], X, X) -> transpose_aux_out_gga([], X, X) 4.92/2.14 U3_gga(R, Rs, X1, C, Cs, transpose_aux_out_gga(Rs, Accm, Cols1)) -> transpose_aux_out_gga(.(R, Rs), X1, .(C, Cs)) 4.92/2.14 U1_ga(A, B, transpose_aux_out_gga(A, [], B)) -> transpose_out_ga(A, B) 4.92/2.14 4.92/2.14 The argument filtering Pi contains the following mapping: 4.92/2.14 transpose_in_ga(x1, x2) = transpose_in_ga(x1) 4.92/2.14 4.92/2.14 U1_ga(x1, x2, x3) = U1_ga(x3) 4.92/2.14 4.92/2.14 transpose_aux_in_gga(x1, x2, x3) = transpose_aux_in_gga(x1, x2) 4.92/2.14 4.92/2.14 .(x1, x2) = .(x1, x2) 4.92/2.14 4.92/2.14 U2_gga(x1, x2, x3, x4, x5, x6) = U2_gga(x2, x6) 4.92/2.14 4.92/2.14 row2col_in_gaaga(x1, x2, x3, x4, x5) = row2col_in_gaaga(x1, x4) 4.92/2.14 4.92/2.14 U4_gaaga(x1, x2, x3, x4, x5, x6, x7, x8) = U4_gaaga(x8) 4.92/2.14 4.92/2.14 [] = [] 4.92/2.14 4.92/2.14 row2col_out_gaaga(x1, x2, x3, x4, x5) = row2col_out_gaaga(x5) 4.92/2.14 4.92/2.14 U3_gga(x1, x2, x3, x4, x5, x6) = U3_gga(x6) 4.92/2.14 4.92/2.14 transpose_aux_out_gga(x1, x2, x3) = transpose_aux_out_gga 4.92/2.14 4.92/2.14 transpose_out_ga(x1, x2) = transpose_out_ga 4.92/2.14 4.92/2.14 4.92/2.14 4.92/2.14 ---------------------------------------- 4.92/2.14 4.92/2.14 (3) DependencyPairsProof (EQUIVALENT) 4.92/2.14 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 4.92/2.14 Pi DP problem: 4.92/2.14 The TRS P consists of the following rules: 4.92/2.14 4.92/2.14 TRANSPOSE_IN_GA(A, B) -> U1_GA(A, B, transpose_aux_in_gga(A, [], B)) 4.92/2.14 TRANSPOSE_IN_GA(A, B) -> TRANSPOSE_AUX_IN_GGA(A, [], B) 4.92/2.14 TRANSPOSE_AUX_IN_GGA(.(R, Rs), X1, .(C, Cs)) -> U2_GGA(R, Rs, X1, C, Cs, row2col_in_gaaga(R, .(C, Cs), Cols1, [], Accm)) 4.92/2.14 TRANSPOSE_AUX_IN_GGA(.(R, Rs), X1, .(C, Cs)) -> ROW2COL_IN_GAAGA(R, .(C, Cs), Cols1, [], Accm) 4.92/2.14 ROW2COL_IN_GAAGA(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> U4_GAAGA(X, Xs, Ys, Cols, Cols1, A, B, row2col_in_gaaga(Xs, Cols, Cols1, .([], A), B)) 4.92/2.14 ROW2COL_IN_GAAGA(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> ROW2COL_IN_GAAGA(Xs, Cols, Cols1, .([], A), B) 4.92/2.14 U2_GGA(R, Rs, X1, C, Cs, row2col_out_gaaga(R, .(C, Cs), Cols1, [], Accm)) -> U3_GGA(R, Rs, X1, C, Cs, transpose_aux_in_gga(Rs, Accm, Cols1)) 4.92/2.14 U2_GGA(R, Rs, X1, C, Cs, row2col_out_gaaga(R, .(C, Cs), Cols1, [], Accm)) -> TRANSPOSE_AUX_IN_GGA(Rs, Accm, Cols1) 4.92/2.14 4.92/2.14 The TRS R consists of the following rules: 4.92/2.14 4.92/2.14 transpose_in_ga(A, B) -> U1_ga(A, B, transpose_aux_in_gga(A, [], B)) 4.92/2.14 transpose_aux_in_gga(.(R, Rs), X1, .(C, Cs)) -> U2_gga(R, Rs, X1, C, Cs, row2col_in_gaaga(R, .(C, Cs), Cols1, [], Accm)) 4.92/2.14 row2col_in_gaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> U4_gaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_in_gaaga(Xs, Cols, Cols1, .([], A), B)) 4.92/2.14 row2col_in_gaaga([], [], [], A, A) -> row2col_out_gaaga([], [], [], A, A) 4.92/2.14 U4_gaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_out_gaaga(Xs, Cols, Cols1, .([], A), B)) -> row2col_out_gaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) 4.92/2.14 U2_gga(R, Rs, X1, C, Cs, row2col_out_gaaga(R, .(C, Cs), Cols1, [], Accm)) -> U3_gga(R, Rs, X1, C, Cs, transpose_aux_in_gga(Rs, Accm, Cols1)) 4.92/2.14 transpose_aux_in_gga([], X, X) -> transpose_aux_out_gga([], X, X) 4.92/2.14 U3_gga(R, Rs, X1, C, Cs, transpose_aux_out_gga(Rs, Accm, Cols1)) -> transpose_aux_out_gga(.(R, Rs), X1, .(C, Cs)) 4.92/2.14 U1_ga(A, B, transpose_aux_out_gga(A, [], B)) -> transpose_out_ga(A, B) 4.92/2.14 4.92/2.14 The argument filtering Pi contains the following mapping: 4.92/2.14 transpose_in_ga(x1, x2) = transpose_in_ga(x1) 4.92/2.14 4.92/2.14 U1_ga(x1, x2, x3) = U1_ga(x3) 4.92/2.14 4.92/2.14 transpose_aux_in_gga(x1, x2, x3) = transpose_aux_in_gga(x1, x2) 4.92/2.14 4.92/2.14 .(x1, x2) = .(x1, x2) 4.92/2.14 4.92/2.14 U2_gga(x1, x2, x3, x4, x5, x6) = U2_gga(x2, x6) 4.92/2.14 4.92/2.14 row2col_in_gaaga(x1, x2, x3, x4, x5) = row2col_in_gaaga(x1, x4) 4.92/2.14 4.92/2.14 U4_gaaga(x1, x2, x3, x4, x5, x6, x7, x8) = U4_gaaga(x8) 4.92/2.14 4.92/2.14 [] = [] 4.92/2.14 4.92/2.14 row2col_out_gaaga(x1, x2, x3, x4, x5) = row2col_out_gaaga(x5) 4.92/2.14 4.92/2.14 U3_gga(x1, x2, x3, x4, x5, x6) = U3_gga(x6) 4.92/2.14 4.92/2.14 transpose_aux_out_gga(x1, x2, x3) = transpose_aux_out_gga 4.92/2.14 4.92/2.14 transpose_out_ga(x1, x2) = transpose_out_ga 4.92/2.14 4.92/2.14 TRANSPOSE_IN_GA(x1, x2) = TRANSPOSE_IN_GA(x1) 4.92/2.14 4.92/2.14 U1_GA(x1, x2, x3) = U1_GA(x3) 4.92/2.14 4.92/2.14 TRANSPOSE_AUX_IN_GGA(x1, x2, x3) = TRANSPOSE_AUX_IN_GGA(x1, x2) 4.92/2.14 4.92/2.14 U2_GGA(x1, x2, x3, x4, x5, x6) = U2_GGA(x2, x6) 4.92/2.14 4.92/2.14 ROW2COL_IN_GAAGA(x1, x2, x3, x4, x5) = ROW2COL_IN_GAAGA(x1, x4) 4.92/2.14 4.92/2.14 U4_GAAGA(x1, x2, x3, x4, x5, x6, x7, x8) = U4_GAAGA(x8) 4.92/2.14 4.92/2.14 U3_GGA(x1, x2, x3, x4, x5, x6) = U3_GGA(x6) 4.92/2.14 4.92/2.14 4.92/2.14 We have to consider all (P,R,Pi)-chains 4.92/2.14 ---------------------------------------- 4.92/2.14 4.92/2.14 (4) 4.92/2.14 Obligation: 4.92/2.14 Pi DP problem: 4.92/2.14 The TRS P consists of the following rules: 4.92/2.14 4.92/2.14 TRANSPOSE_IN_GA(A, B) -> U1_GA(A, B, transpose_aux_in_gga(A, [], B)) 4.92/2.14 TRANSPOSE_IN_GA(A, B) -> TRANSPOSE_AUX_IN_GGA(A, [], B) 4.92/2.14 TRANSPOSE_AUX_IN_GGA(.(R, Rs), X1, .(C, Cs)) -> U2_GGA(R, Rs, X1, C, Cs, row2col_in_gaaga(R, .(C, Cs), Cols1, [], Accm)) 4.92/2.14 TRANSPOSE_AUX_IN_GGA(.(R, Rs), X1, .(C, Cs)) -> ROW2COL_IN_GAAGA(R, .(C, Cs), Cols1, [], Accm) 4.92/2.14 ROW2COL_IN_GAAGA(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> U4_GAAGA(X, Xs, Ys, Cols, Cols1, A, B, row2col_in_gaaga(Xs, Cols, Cols1, .([], A), B)) 4.92/2.14 ROW2COL_IN_GAAGA(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> ROW2COL_IN_GAAGA(Xs, Cols, Cols1, .([], A), B) 4.92/2.14 U2_GGA(R, Rs, X1, C, Cs, row2col_out_gaaga(R, .(C, Cs), Cols1, [], Accm)) -> U3_GGA(R, Rs, X1, C, Cs, transpose_aux_in_gga(Rs, Accm, Cols1)) 4.92/2.14 U2_GGA(R, Rs, X1, C, Cs, row2col_out_gaaga(R, .(C, Cs), Cols1, [], Accm)) -> TRANSPOSE_AUX_IN_GGA(Rs, Accm, Cols1) 4.92/2.14 4.92/2.14 The TRS R consists of the following rules: 4.92/2.14 4.92/2.14 transpose_in_ga(A, B) -> U1_ga(A, B, transpose_aux_in_gga(A, [], B)) 4.92/2.14 transpose_aux_in_gga(.(R, Rs), X1, .(C, Cs)) -> U2_gga(R, Rs, X1, C, Cs, row2col_in_gaaga(R, .(C, Cs), Cols1, [], Accm)) 4.92/2.14 row2col_in_gaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> U4_gaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_in_gaaga(Xs, Cols, Cols1, .([], A), B)) 4.92/2.14 row2col_in_gaaga([], [], [], A, A) -> row2col_out_gaaga([], [], [], A, A) 4.92/2.14 U4_gaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_out_gaaga(Xs, Cols, Cols1, .([], A), B)) -> row2col_out_gaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) 4.92/2.14 U2_gga(R, Rs, X1, C, Cs, row2col_out_gaaga(R, .(C, Cs), Cols1, [], Accm)) -> U3_gga(R, Rs, X1, C, Cs, transpose_aux_in_gga(Rs, Accm, Cols1)) 4.92/2.14 transpose_aux_in_gga([], X, X) -> transpose_aux_out_gga([], X, X) 4.92/2.14 U3_gga(R, Rs, X1, C, Cs, transpose_aux_out_gga(Rs, Accm, Cols1)) -> transpose_aux_out_gga(.(R, Rs), X1, .(C, Cs)) 4.92/2.14 U1_ga(A, B, transpose_aux_out_gga(A, [], B)) -> transpose_out_ga(A, B) 4.92/2.14 4.92/2.14 The argument filtering Pi contains the following mapping: 4.92/2.14 transpose_in_ga(x1, x2) = transpose_in_ga(x1) 4.92/2.14 4.92/2.14 U1_ga(x1, x2, x3) = U1_ga(x3) 4.92/2.14 4.92/2.14 transpose_aux_in_gga(x1, x2, x3) = transpose_aux_in_gga(x1, x2) 4.92/2.14 4.92/2.14 .(x1, x2) = .(x1, x2) 4.92/2.14 4.92/2.14 U2_gga(x1, x2, x3, x4, x5, x6) = U2_gga(x2, x6) 4.92/2.14 4.92/2.14 row2col_in_gaaga(x1, x2, x3, x4, x5) = row2col_in_gaaga(x1, x4) 4.92/2.14 4.92/2.14 U4_gaaga(x1, x2, x3, x4, x5, x6, x7, x8) = U4_gaaga(x8) 4.92/2.14 4.92/2.14 [] = [] 4.92/2.14 4.92/2.14 row2col_out_gaaga(x1, x2, x3, x4, x5) = row2col_out_gaaga(x5) 4.92/2.14 4.92/2.14 U3_gga(x1, x2, x3, x4, x5, x6) = U3_gga(x6) 4.92/2.14 4.92/2.14 transpose_aux_out_gga(x1, x2, x3) = transpose_aux_out_gga 4.92/2.14 4.92/2.14 transpose_out_ga(x1, x2) = transpose_out_ga 4.92/2.14 4.92/2.14 TRANSPOSE_IN_GA(x1, x2) = TRANSPOSE_IN_GA(x1) 4.92/2.14 4.92/2.14 U1_GA(x1, x2, x3) = U1_GA(x3) 4.92/2.14 4.92/2.14 TRANSPOSE_AUX_IN_GGA(x1, x2, x3) = TRANSPOSE_AUX_IN_GGA(x1, x2) 4.92/2.14 4.92/2.14 U2_GGA(x1, x2, x3, x4, x5, x6) = U2_GGA(x2, x6) 4.92/2.14 4.92/2.14 ROW2COL_IN_GAAGA(x1, x2, x3, x4, x5) = ROW2COL_IN_GAAGA(x1, x4) 4.92/2.14 4.92/2.14 U4_GAAGA(x1, x2, x3, x4, x5, x6, x7, x8) = U4_GAAGA(x8) 4.92/2.14 4.92/2.14 U3_GGA(x1, x2, x3, x4, x5, x6) = U3_GGA(x6) 4.92/2.14 4.92/2.14 4.92/2.14 We have to consider all (P,R,Pi)-chains 4.92/2.14 ---------------------------------------- 4.92/2.14 4.92/2.14 (5) DependencyGraphProof (EQUIVALENT) 4.92/2.14 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 5 less nodes. 4.92/2.14 ---------------------------------------- 4.92/2.14 4.92/2.14 (6) 4.92/2.14 Complex Obligation (AND) 4.92/2.14 4.92/2.14 ---------------------------------------- 4.92/2.14 4.92/2.14 (7) 4.92/2.14 Obligation: 4.92/2.14 Pi DP problem: 4.92/2.14 The TRS P consists of the following rules: 4.92/2.14 4.92/2.14 ROW2COL_IN_GAAGA(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> ROW2COL_IN_GAAGA(Xs, Cols, Cols1, .([], A), B) 4.92/2.14 4.92/2.14 The TRS R consists of the following rules: 4.92/2.14 4.92/2.14 transpose_in_ga(A, B) -> U1_ga(A, B, transpose_aux_in_gga(A, [], B)) 4.92/2.14 transpose_aux_in_gga(.(R, Rs), X1, .(C, Cs)) -> U2_gga(R, Rs, X1, C, Cs, row2col_in_gaaga(R, .(C, Cs), Cols1, [], Accm)) 4.92/2.14 row2col_in_gaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> U4_gaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_in_gaaga(Xs, Cols, Cols1, .([], A), B)) 4.92/2.14 row2col_in_gaaga([], [], [], A, A) -> row2col_out_gaaga([], [], [], A, A) 4.92/2.14 U4_gaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_out_gaaga(Xs, Cols, Cols1, .([], A), B)) -> row2col_out_gaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) 4.92/2.14 U2_gga(R, Rs, X1, C, Cs, row2col_out_gaaga(R, .(C, Cs), Cols1, [], Accm)) -> U3_gga(R, Rs, X1, C, Cs, transpose_aux_in_gga(Rs, Accm, Cols1)) 4.92/2.14 transpose_aux_in_gga([], X, X) -> transpose_aux_out_gga([], X, X) 4.92/2.14 U3_gga(R, Rs, X1, C, Cs, transpose_aux_out_gga(Rs, Accm, Cols1)) -> transpose_aux_out_gga(.(R, Rs), X1, .(C, Cs)) 4.92/2.14 U1_ga(A, B, transpose_aux_out_gga(A, [], B)) -> transpose_out_ga(A, B) 4.92/2.14 4.92/2.14 The argument filtering Pi contains the following mapping: 4.92/2.14 transpose_in_ga(x1, x2) = transpose_in_ga(x1) 4.92/2.14 4.92/2.14 U1_ga(x1, x2, x3) = U1_ga(x3) 4.92/2.14 4.92/2.14 transpose_aux_in_gga(x1, x2, x3) = transpose_aux_in_gga(x1, x2) 4.92/2.14 4.92/2.14 .(x1, x2) = .(x1, x2) 4.92/2.14 4.92/2.14 U2_gga(x1, x2, x3, x4, x5, x6) = U2_gga(x2, x6) 4.92/2.14 4.92/2.14 row2col_in_gaaga(x1, x2, x3, x4, x5) = row2col_in_gaaga(x1, x4) 4.92/2.14 4.92/2.14 U4_gaaga(x1, x2, x3, x4, x5, x6, x7, x8) = U4_gaaga(x8) 4.92/2.14 4.92/2.14 [] = [] 4.92/2.14 4.92/2.14 row2col_out_gaaga(x1, x2, x3, x4, x5) = row2col_out_gaaga(x5) 4.92/2.14 4.92/2.14 U3_gga(x1, x2, x3, x4, x5, x6) = U3_gga(x6) 4.92/2.14 4.92/2.14 transpose_aux_out_gga(x1, x2, x3) = transpose_aux_out_gga 4.92/2.14 4.92/2.14 transpose_out_ga(x1, x2) = transpose_out_ga 4.92/2.14 4.92/2.14 ROW2COL_IN_GAAGA(x1, x2, x3, x4, x5) = ROW2COL_IN_GAAGA(x1, x4) 4.92/2.14 4.92/2.14 4.92/2.14 We have to consider all (P,R,Pi)-chains 4.92/2.14 ---------------------------------------- 4.92/2.14 4.92/2.14 (8) UsableRulesProof (EQUIVALENT) 4.92/2.14 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.92/2.14 ---------------------------------------- 4.92/2.14 4.92/2.14 (9) 4.92/2.14 Obligation: 4.92/2.14 Pi DP problem: 4.92/2.14 The TRS P consists of the following rules: 4.92/2.14 4.92/2.14 ROW2COL_IN_GAAGA(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> ROW2COL_IN_GAAGA(Xs, Cols, Cols1, .([], A), B) 4.92/2.14 4.92/2.14 R is empty. 4.92/2.14 The argument filtering Pi contains the following mapping: 4.92/2.14 .(x1, x2) = .(x1, x2) 4.92/2.14 4.92/2.14 [] = [] 4.92/2.14 4.92/2.14 ROW2COL_IN_GAAGA(x1, x2, x3, x4, x5) = ROW2COL_IN_GAAGA(x1, x4) 4.92/2.14 4.92/2.14 4.92/2.14 We have to consider all (P,R,Pi)-chains 4.92/2.15 ---------------------------------------- 4.92/2.15 4.92/2.15 (10) PiDPToQDPProof (SOUND) 4.92/2.15 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.92/2.15 ---------------------------------------- 4.92/2.15 4.92/2.15 (11) 4.92/2.15 Obligation: 4.92/2.15 Q DP problem: 4.92/2.15 The TRS P consists of the following rules: 4.92/2.15 4.92/2.15 ROW2COL_IN_GAAGA(.(X, Xs), A) -> ROW2COL_IN_GAAGA(Xs, .([], A)) 4.92/2.15 4.92/2.15 R is empty. 4.92/2.15 Q is empty. 4.92/2.15 We have to consider all (P,Q,R)-chains. 4.92/2.15 ---------------------------------------- 4.92/2.15 4.92/2.15 (12) QDPSizeChangeProof (EQUIVALENT) 4.92/2.15 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 4.92/2.15 4.92/2.15 From the DPs we obtained the following set of size-change graphs: 4.92/2.15 *ROW2COL_IN_GAAGA(.(X, Xs), A) -> ROW2COL_IN_GAAGA(Xs, .([], A)) 4.92/2.15 The graph contains the following edges 1 > 1 4.92/2.15 4.92/2.15 4.92/2.15 ---------------------------------------- 4.92/2.15 4.92/2.15 (13) 4.92/2.15 YES 4.92/2.15 4.92/2.15 ---------------------------------------- 4.92/2.15 4.92/2.15 (14) 4.92/2.15 Obligation: 4.92/2.15 Pi DP problem: 4.92/2.15 The TRS P consists of the following rules: 4.92/2.15 4.92/2.15 U2_GGA(R, Rs, X1, C, Cs, row2col_out_gaaga(R, .(C, Cs), Cols1, [], Accm)) -> TRANSPOSE_AUX_IN_GGA(Rs, Accm, Cols1) 4.92/2.15 TRANSPOSE_AUX_IN_GGA(.(R, Rs), X1, .(C, Cs)) -> U2_GGA(R, Rs, X1, C, Cs, row2col_in_gaaga(R, .(C, Cs), Cols1, [], Accm)) 4.92/2.15 4.92/2.15 The TRS R consists of the following rules: 4.92/2.15 4.92/2.15 transpose_in_ga(A, B) -> U1_ga(A, B, transpose_aux_in_gga(A, [], B)) 4.92/2.15 transpose_aux_in_gga(.(R, Rs), X1, .(C, Cs)) -> U2_gga(R, Rs, X1, C, Cs, row2col_in_gaaga(R, .(C, Cs), Cols1, [], Accm)) 4.92/2.15 row2col_in_gaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> U4_gaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_in_gaaga(Xs, Cols, Cols1, .([], A), B)) 4.92/2.15 row2col_in_gaaga([], [], [], A, A) -> row2col_out_gaaga([], [], [], A, A) 4.92/2.15 U4_gaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_out_gaaga(Xs, Cols, Cols1, .([], A), B)) -> row2col_out_gaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) 4.92/2.15 U2_gga(R, Rs, X1, C, Cs, row2col_out_gaaga(R, .(C, Cs), Cols1, [], Accm)) -> U3_gga(R, Rs, X1, C, Cs, transpose_aux_in_gga(Rs, Accm, Cols1)) 4.92/2.15 transpose_aux_in_gga([], X, X) -> transpose_aux_out_gga([], X, X) 4.92/2.15 U3_gga(R, Rs, X1, C, Cs, transpose_aux_out_gga(Rs, Accm, Cols1)) -> transpose_aux_out_gga(.(R, Rs), X1, .(C, Cs)) 4.92/2.15 U1_ga(A, B, transpose_aux_out_gga(A, [], B)) -> transpose_out_ga(A, B) 4.92/2.15 4.92/2.15 The argument filtering Pi contains the following mapping: 4.92/2.15 transpose_in_ga(x1, x2) = transpose_in_ga(x1) 4.92/2.15 4.92/2.15 U1_ga(x1, x2, x3) = U1_ga(x3) 4.92/2.15 4.92/2.15 transpose_aux_in_gga(x1, x2, x3) = transpose_aux_in_gga(x1, x2) 4.92/2.15 4.92/2.15 .(x1, x2) = .(x1, x2) 4.92/2.15 4.92/2.15 U2_gga(x1, x2, x3, x4, x5, x6) = U2_gga(x2, x6) 4.92/2.15 4.92/2.15 row2col_in_gaaga(x1, x2, x3, x4, x5) = row2col_in_gaaga(x1, x4) 4.92/2.15 4.92/2.15 U4_gaaga(x1, x2, x3, x4, x5, x6, x7, x8) = U4_gaaga(x8) 4.92/2.15 4.92/2.15 [] = [] 4.92/2.15 4.92/2.15 row2col_out_gaaga(x1, x2, x3, x4, x5) = row2col_out_gaaga(x5) 4.92/2.15 4.92/2.15 U3_gga(x1, x2, x3, x4, x5, x6) = U3_gga(x6) 4.92/2.15 4.92/2.15 transpose_aux_out_gga(x1, x2, x3) = transpose_aux_out_gga 4.92/2.15 4.92/2.15 transpose_out_ga(x1, x2) = transpose_out_ga 4.92/2.15 4.92/2.15 TRANSPOSE_AUX_IN_GGA(x1, x2, x3) = TRANSPOSE_AUX_IN_GGA(x1, x2) 4.92/2.15 4.92/2.15 U2_GGA(x1, x2, x3, x4, x5, x6) = U2_GGA(x2, x6) 4.92/2.15 4.92/2.15 4.92/2.15 We have to consider all (P,R,Pi)-chains 4.92/2.15 ---------------------------------------- 4.92/2.15 4.92/2.15 (15) UsableRulesProof (EQUIVALENT) 4.92/2.15 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.92/2.15 ---------------------------------------- 4.92/2.15 4.92/2.15 (16) 4.92/2.15 Obligation: 4.92/2.15 Pi DP problem: 4.92/2.15 The TRS P consists of the following rules: 4.92/2.15 4.92/2.15 U2_GGA(R, Rs, X1, C, Cs, row2col_out_gaaga(R, .(C, Cs), Cols1, [], Accm)) -> TRANSPOSE_AUX_IN_GGA(Rs, Accm, Cols1) 4.92/2.15 TRANSPOSE_AUX_IN_GGA(.(R, Rs), X1, .(C, Cs)) -> U2_GGA(R, Rs, X1, C, Cs, row2col_in_gaaga(R, .(C, Cs), Cols1, [], Accm)) 4.92/2.15 4.92/2.15 The TRS R consists of the following rules: 4.92/2.15 4.92/2.15 row2col_in_gaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> U4_gaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_in_gaaga(Xs, Cols, Cols1, .([], A), B)) 4.92/2.15 U4_gaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_out_gaaga(Xs, Cols, Cols1, .([], A), B)) -> row2col_out_gaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) 4.92/2.15 row2col_in_gaaga([], [], [], A, A) -> row2col_out_gaaga([], [], [], A, A) 4.92/2.15 4.92/2.15 The argument filtering Pi contains the following mapping: 4.92/2.15 .(x1, x2) = .(x1, x2) 4.92/2.15 4.92/2.15 row2col_in_gaaga(x1, x2, x3, x4, x5) = row2col_in_gaaga(x1, x4) 4.92/2.15 4.92/2.15 U4_gaaga(x1, x2, x3, x4, x5, x6, x7, x8) = U4_gaaga(x8) 4.92/2.15 4.92/2.15 [] = [] 4.92/2.15 4.92/2.15 row2col_out_gaaga(x1, x2, x3, x4, x5) = row2col_out_gaaga(x5) 4.92/2.15 4.92/2.15 TRANSPOSE_AUX_IN_GGA(x1, x2, x3) = TRANSPOSE_AUX_IN_GGA(x1, x2) 4.92/2.15 4.92/2.15 U2_GGA(x1, x2, x3, x4, x5, x6) = U2_GGA(x2, x6) 4.92/2.15 4.92/2.15 4.92/2.15 We have to consider all (P,R,Pi)-chains 4.92/2.15 ---------------------------------------- 4.92/2.15 4.92/2.15 (17) PiDPToQDPProof (SOUND) 4.92/2.15 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.92/2.15 ---------------------------------------- 4.92/2.15 4.92/2.15 (18) 4.92/2.15 Obligation: 4.92/2.15 Q DP problem: 4.92/2.15 The TRS P consists of the following rules: 4.92/2.15 4.92/2.15 U2_GGA(Rs, row2col_out_gaaga(Accm)) -> TRANSPOSE_AUX_IN_GGA(Rs, Accm) 4.92/2.15 TRANSPOSE_AUX_IN_GGA(.(R, Rs), X1) -> U2_GGA(Rs, row2col_in_gaaga(R, [])) 4.92/2.15 4.92/2.15 The TRS R consists of the following rules: 4.92/2.15 4.92/2.15 row2col_in_gaaga(.(X, Xs), A) -> U4_gaaga(row2col_in_gaaga(Xs, .([], A))) 4.92/2.15 U4_gaaga(row2col_out_gaaga(B)) -> row2col_out_gaaga(B) 4.92/2.15 row2col_in_gaaga([], A) -> row2col_out_gaaga(A) 4.92/2.15 4.92/2.15 The set Q consists of the following terms: 4.92/2.15 4.92/2.15 row2col_in_gaaga(x0, x1) 4.92/2.15 U4_gaaga(x0) 4.92/2.15 4.92/2.15 We have to consider all (P,Q,R)-chains. 4.92/2.15 ---------------------------------------- 4.92/2.15 4.92/2.15 (19) QDPSizeChangeProof (EQUIVALENT) 4.92/2.15 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 4.92/2.15 4.92/2.15 From the DPs we obtained the following set of size-change graphs: 4.92/2.15 *TRANSPOSE_AUX_IN_GGA(.(R, Rs), X1) -> U2_GGA(Rs, row2col_in_gaaga(R, [])) 4.92/2.15 The graph contains the following edges 1 > 1 4.92/2.15 4.92/2.15 4.92/2.15 *U2_GGA(Rs, row2col_out_gaaga(Accm)) -> TRANSPOSE_AUX_IN_GGA(Rs, Accm) 4.92/2.15 The graph contains the following edges 1 >= 1, 2 > 2 4.92/2.15 4.92/2.15 4.92/2.15 ---------------------------------------- 4.92/2.15 4.92/2.15 (20) 4.92/2.15 YES 5.05/2.18 EOF