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