/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.pl /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern transpose_aux(a,g,a) w.r.t. the given Prolog program could not be shown: (0) Prolog (1) PrologToPiTRSProof [SOUND, 0 ms] (2) PiTRS (3) DependencyPairsProof [EQUIVALENT, 0 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 3 ms] (6) PiDP (7) UsableRulesProof [EQUIVALENT, 0 ms] (8) PiDP (9) PiDPToQDPProof [SOUND, 0 ms] (10) QDP (11) TransformationProof [EQUIVALENT, 0 ms] (12) QDP (13) TransformationProof [EQUIVALENT, 0 ms] (14) QDP (15) NonTerminationLoopProof [COMPLETE, 0 ms] (16) NO (17) PrologToPiTRSProof [SOUND, 0 ms] (18) PiTRS (19) DependencyPairsProof [EQUIVALENT, 0 ms] (20) PiDP (21) DependencyGraphProof [EQUIVALENT, 0 ms] (22) PiDP (23) UsableRulesProof [EQUIVALENT, 0 ms] (24) PiDP (25) PiDPToQDPProof [SOUND, 0 ms] (26) QDP (27) TransformationProof [EQUIVALENT, 0 ms] (28) QDP (29) TransformationProof [EQUIVALENT, 0 ms] (30) QDP (31) NonTerminationLoopProof [COMPLETE, 0 ms] (32) NO (33) PrologToDTProblemTransformerProof [SOUND, 21 ms] (34) TRIPLES (35) TriplesToPiDPProof [SOUND, 13 ms] (36) PiDP (37) DependencyGraphProof [EQUIVALENT, 0 ms] (38) PiDP (39) PiDPToQDPProof [SOUND, 0 ms] (40) QDP (41) TransformationProof [EQUIVALENT, 0 ms] (42) QDP (43) TransformationProof [EQUIVALENT, 0 ms] (44) QDP (45) NonTerminationLoopProof [COMPLETE, 0 ms] (46) NO (47) PrologToTRSTransformerProof [SOUND, 58 ms] (48) QTRS (49) AAECC Innermost [EQUIVALENT, 0 ms] (50) QTRS (51) DependencyPairsProof [EQUIVALENT, 0 ms] (52) QDP (53) DependencyGraphProof [EQUIVALENT, 0 ms] (54) QDP (55) UsableRulesProof [EQUIVALENT, 0 ms] (56) QDP (57) QReductionProof [EQUIVALENT, 0 ms] (58) QDP (59) TransformationProof [EQUIVALENT, 0 ms] (60) QDP (61) TransformationProof [EQUIVALENT, 0 ms] (62) QDP (63) NonTerminationLoopProof [COMPLETE, 0 ms] (64) NO (65) PrologToIRSwTTransformerProof [SOUND, 44 ms] (66) IRSwT (67) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (68) IRSwT (69) IntTRSCompressionProof [EQUIVALENT, 49 ms] (70) IRSwT (71) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (72) IRSwT (73) IRSwTTerminationDigraphProof [EQUIVALENT, 6 ms] (74) IRSwT (75) IRSwTToIntTRSProof [SOUND, 10 ms] (76) IRSwT ---------------------------------------- (0) Obligation: Clauses: transpose_aux(.(R, Rs), X1, .(C, Cs)) :- row2col(R, .(C, Cs), Cols1, [], Accm). row2col(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) :- row2col(Xs, Cols, Cols1, .([], A), B). Query: transpose_aux(a,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_aux_in_3: (f,b,f) row2col_in_5: (f,f,f,b,f) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: transpose_aux_in_aga(.(R, Rs), X1, .(C, Cs)) -> U1_aga(R, Rs, X1, C, Cs, row2col_in_aaaga(R, .(C, Cs), Cols1, [], Accm)) row2col_in_aaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> U2_aaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_in_aaaga(Xs, Cols, Cols1, .([], A), B)) U2_aaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_out_aaaga(Xs, Cols, Cols1, .([], A), B)) -> row2col_out_aaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) U1_aga(R, Rs, X1, C, Cs, row2col_out_aaaga(R, .(C, Cs), Cols1, [], Accm)) -> transpose_aux_out_aga(.(R, Rs), X1, .(C, Cs)) The argument filtering Pi contains the following mapping: transpose_aux_in_aga(x1, x2, x3) = transpose_aux_in_aga(x2) U1_aga(x1, x2, x3, x4, x5, x6) = U1_aga(x6) row2col_in_aaaga(x1, x2, x3, x4, x5) = row2col_in_aaaga(x4) U2_aaaga(x1, x2, x3, x4, x5, x6, x7, x8) = U2_aaaga(x8) row2col_out_aaaga(x1, x2, x3, x4, x5) = row2col_out_aaaga(x5) .(x1, x2) = .(x1, x2) [] = [] transpose_aux_out_aga(x1, x2, x3) = transpose_aux_out_aga 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_aux_in_aga(.(R, Rs), X1, .(C, Cs)) -> U1_aga(R, Rs, X1, C, Cs, row2col_in_aaaga(R, .(C, Cs), Cols1, [], Accm)) row2col_in_aaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> U2_aaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_in_aaaga(Xs, Cols, Cols1, .([], A), B)) U2_aaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_out_aaaga(Xs, Cols, Cols1, .([], A), B)) -> row2col_out_aaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) U1_aga(R, Rs, X1, C, Cs, row2col_out_aaaga(R, .(C, Cs), Cols1, [], Accm)) -> transpose_aux_out_aga(.(R, Rs), X1, .(C, Cs)) The argument filtering Pi contains the following mapping: transpose_aux_in_aga(x1, x2, x3) = transpose_aux_in_aga(x2) U1_aga(x1, x2, x3, x4, x5, x6) = U1_aga(x6) row2col_in_aaaga(x1, x2, x3, x4, x5) = row2col_in_aaaga(x4) U2_aaaga(x1, x2, x3, x4, x5, x6, x7, x8) = U2_aaaga(x8) row2col_out_aaaga(x1, x2, x3, x4, x5) = row2col_out_aaaga(x5) .(x1, x2) = .(x1, x2) [] = [] transpose_aux_out_aga(x1, x2, x3) = transpose_aux_out_aga ---------------------------------------- (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_AUX_IN_AGA(.(R, Rs), X1, .(C, Cs)) -> U1_AGA(R, Rs, X1, C, Cs, row2col_in_aaaga(R, .(C, Cs), Cols1, [], Accm)) TRANSPOSE_AUX_IN_AGA(.(R, Rs), X1, .(C, Cs)) -> ROW2COL_IN_AAAGA(R, .(C, Cs), Cols1, [], Accm) ROW2COL_IN_AAAGA(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> U2_AAAGA(X, Xs, Ys, Cols, Cols1, A, B, row2col_in_aaaga(Xs, Cols, Cols1, .([], A), B)) ROW2COL_IN_AAAGA(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> ROW2COL_IN_AAAGA(Xs, Cols, Cols1, .([], A), B) The TRS R consists of the following rules: transpose_aux_in_aga(.(R, Rs), X1, .(C, Cs)) -> U1_aga(R, Rs, X1, C, Cs, row2col_in_aaaga(R, .(C, Cs), Cols1, [], Accm)) row2col_in_aaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> U2_aaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_in_aaaga(Xs, Cols, Cols1, .([], A), B)) U2_aaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_out_aaaga(Xs, Cols, Cols1, .([], A), B)) -> row2col_out_aaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) U1_aga(R, Rs, X1, C, Cs, row2col_out_aaaga(R, .(C, Cs), Cols1, [], Accm)) -> transpose_aux_out_aga(.(R, Rs), X1, .(C, Cs)) The argument filtering Pi contains the following mapping: transpose_aux_in_aga(x1, x2, x3) = transpose_aux_in_aga(x2) U1_aga(x1, x2, x3, x4, x5, x6) = U1_aga(x6) row2col_in_aaaga(x1, x2, x3, x4, x5) = row2col_in_aaaga(x4) U2_aaaga(x1, x2, x3, x4, x5, x6, x7, x8) = U2_aaaga(x8) row2col_out_aaaga(x1, x2, x3, x4, x5) = row2col_out_aaaga(x5) .(x1, x2) = .(x1, x2) [] = [] transpose_aux_out_aga(x1, x2, x3) = transpose_aux_out_aga TRANSPOSE_AUX_IN_AGA(x1, x2, x3) = TRANSPOSE_AUX_IN_AGA(x2) U1_AGA(x1, x2, x3, x4, x5, x6) = U1_AGA(x6) ROW2COL_IN_AAAGA(x1, x2, x3, x4, x5) = ROW2COL_IN_AAAGA(x4) U2_AAAGA(x1, x2, x3, x4, x5, x6, x7, x8) = U2_AAAGA(x8) We have to consider all (P,R,Pi)-chains ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: TRANSPOSE_AUX_IN_AGA(.(R, Rs), X1, .(C, Cs)) -> U1_AGA(R, Rs, X1, C, Cs, row2col_in_aaaga(R, .(C, Cs), Cols1, [], Accm)) TRANSPOSE_AUX_IN_AGA(.(R, Rs), X1, .(C, Cs)) -> ROW2COL_IN_AAAGA(R, .(C, Cs), Cols1, [], Accm) ROW2COL_IN_AAAGA(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> U2_AAAGA(X, Xs, Ys, Cols, Cols1, A, B, row2col_in_aaaga(Xs, Cols, Cols1, .([], A), B)) ROW2COL_IN_AAAGA(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> ROW2COL_IN_AAAGA(Xs, Cols, Cols1, .([], A), B) The TRS R consists of the following rules: transpose_aux_in_aga(.(R, Rs), X1, .(C, Cs)) -> U1_aga(R, Rs, X1, C, Cs, row2col_in_aaaga(R, .(C, Cs), Cols1, [], Accm)) row2col_in_aaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> U2_aaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_in_aaaga(Xs, Cols, Cols1, .([], A), B)) U2_aaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_out_aaaga(Xs, Cols, Cols1, .([], A), B)) -> row2col_out_aaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) U1_aga(R, Rs, X1, C, Cs, row2col_out_aaaga(R, .(C, Cs), Cols1, [], Accm)) -> transpose_aux_out_aga(.(R, Rs), X1, .(C, Cs)) The argument filtering Pi contains the following mapping: transpose_aux_in_aga(x1, x2, x3) = transpose_aux_in_aga(x2) U1_aga(x1, x2, x3, x4, x5, x6) = U1_aga(x6) row2col_in_aaaga(x1, x2, x3, x4, x5) = row2col_in_aaaga(x4) U2_aaaga(x1, x2, x3, x4, x5, x6, x7, x8) = U2_aaaga(x8) row2col_out_aaaga(x1, x2, x3, x4, x5) = row2col_out_aaaga(x5) .(x1, x2) = .(x1, x2) [] = [] transpose_aux_out_aga(x1, x2, x3) = transpose_aux_out_aga TRANSPOSE_AUX_IN_AGA(x1, x2, x3) = TRANSPOSE_AUX_IN_AGA(x2) U1_AGA(x1, x2, x3, x4, x5, x6) = U1_AGA(x6) ROW2COL_IN_AAAGA(x1, x2, x3, x4, x5) = ROW2COL_IN_AAAGA(x4) U2_AAAGA(x1, x2, x3, x4, x5, x6, x7, x8) = U2_AAAGA(x8) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 3 less nodes. ---------------------------------------- (6) Obligation: Pi DP problem: The TRS P consists of the following rules: ROW2COL_IN_AAAGA(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> ROW2COL_IN_AAAGA(Xs, Cols, Cols1, .([], A), B) The TRS R consists of the following rules: transpose_aux_in_aga(.(R, Rs), X1, .(C, Cs)) -> U1_aga(R, Rs, X1, C, Cs, row2col_in_aaaga(R, .(C, Cs), Cols1, [], Accm)) row2col_in_aaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> U2_aaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_in_aaaga(Xs, Cols, Cols1, .([], A), B)) U2_aaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_out_aaaga(Xs, Cols, Cols1, .([], A), B)) -> row2col_out_aaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) U1_aga(R, Rs, X1, C, Cs, row2col_out_aaaga(R, .(C, Cs), Cols1, [], Accm)) -> transpose_aux_out_aga(.(R, Rs), X1, .(C, Cs)) The argument filtering Pi contains the following mapping: transpose_aux_in_aga(x1, x2, x3) = transpose_aux_in_aga(x2) U1_aga(x1, x2, x3, x4, x5, x6) = U1_aga(x6) row2col_in_aaaga(x1, x2, x3, x4, x5) = row2col_in_aaaga(x4) U2_aaaga(x1, x2, x3, x4, x5, x6, x7, x8) = U2_aaaga(x8) row2col_out_aaaga(x1, x2, x3, x4, x5) = row2col_out_aaaga(x5) .(x1, x2) = .(x1, x2) [] = [] transpose_aux_out_aga(x1, x2, x3) = transpose_aux_out_aga ROW2COL_IN_AAAGA(x1, x2, x3, x4, x5) = ROW2COL_IN_AAAGA(x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (7) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (8) Obligation: Pi DP problem: The TRS P consists of the following rules: ROW2COL_IN_AAAGA(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> ROW2COL_IN_AAAGA(Xs, Cols, Cols1, .([], A), B) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) [] = [] ROW2COL_IN_AAAGA(x1, x2, x3, x4, x5) = ROW2COL_IN_AAAGA(x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (9) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: ROW2COL_IN_AAAGA(A) -> ROW2COL_IN_AAAGA(.([], A)) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (11) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule ROW2COL_IN_AAAGA(A) -> ROW2COL_IN_AAAGA(.([], A)) we obtained the following new rules [LPAR04]: (ROW2COL_IN_AAAGA(.([], z0)) -> ROW2COL_IN_AAAGA(.([], .([], z0))),ROW2COL_IN_AAAGA(.([], z0)) -> ROW2COL_IN_AAAGA(.([], .([], z0)))) ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: ROW2COL_IN_AAAGA(.([], z0)) -> ROW2COL_IN_AAAGA(.([], .([], z0))) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (13) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule ROW2COL_IN_AAAGA(.([], z0)) -> ROW2COL_IN_AAAGA(.([], .([], z0))) we obtained the following new rules [LPAR04]: (ROW2COL_IN_AAAGA(.([], .([], z0))) -> ROW2COL_IN_AAAGA(.([], .([], .([], z0)))),ROW2COL_IN_AAAGA(.([], .([], z0))) -> ROW2COL_IN_AAAGA(.([], .([], .([], z0))))) ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: ROW2COL_IN_AAAGA(.([], .([], z0))) -> ROW2COL_IN_AAAGA(.([], .([], .([], z0)))) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (15) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by semiunifying a rule from P directly. s = ROW2COL_IN_AAAGA(.([], .([], z0))) evaluates to t =ROW2COL_IN_AAAGA(.([], .([], .([], z0)))) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [z0 / .([], z0)] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence The DP semiunifies directly so there is only one rewrite step from ROW2COL_IN_AAAGA(.([], .([], z0))) to ROW2COL_IN_AAAGA(.([], .([], .([], z0)))). ---------------------------------------- (16) NO ---------------------------------------- (17) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: transpose_aux_in_3: (f,b,f) row2col_in_5: (f,f,f,b,f) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: transpose_aux_in_aga(.(R, Rs), X1, .(C, Cs)) -> U1_aga(R, Rs, X1, C, Cs, row2col_in_aaaga(R, .(C, Cs), Cols1, [], Accm)) row2col_in_aaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> U2_aaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_in_aaaga(Xs, Cols, Cols1, .([], A), B)) U2_aaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_out_aaaga(Xs, Cols, Cols1, .([], A), B)) -> row2col_out_aaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) U1_aga(R, Rs, X1, C, Cs, row2col_out_aaaga(R, .(C, Cs), Cols1, [], Accm)) -> transpose_aux_out_aga(.(R, Rs), X1, .(C, Cs)) The argument filtering Pi contains the following mapping: transpose_aux_in_aga(x1, x2, x3) = transpose_aux_in_aga(x2) U1_aga(x1, x2, x3, x4, x5, x6) = U1_aga(x3, x6) row2col_in_aaaga(x1, x2, x3, x4, x5) = row2col_in_aaaga(x4) U2_aaaga(x1, x2, x3, x4, x5, x6, x7, x8) = U2_aaaga(x6, x8) row2col_out_aaaga(x1, x2, x3, x4, x5) = row2col_out_aaaga(x4, x5) .(x1, x2) = .(x1, x2) [] = [] transpose_aux_out_aga(x1, x2, x3) = transpose_aux_out_aga(x2) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (18) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: transpose_aux_in_aga(.(R, Rs), X1, .(C, Cs)) -> U1_aga(R, Rs, X1, C, Cs, row2col_in_aaaga(R, .(C, Cs), Cols1, [], Accm)) row2col_in_aaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> U2_aaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_in_aaaga(Xs, Cols, Cols1, .([], A), B)) U2_aaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_out_aaaga(Xs, Cols, Cols1, .([], A), B)) -> row2col_out_aaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) U1_aga(R, Rs, X1, C, Cs, row2col_out_aaaga(R, .(C, Cs), Cols1, [], Accm)) -> transpose_aux_out_aga(.(R, Rs), X1, .(C, Cs)) The argument filtering Pi contains the following mapping: transpose_aux_in_aga(x1, x2, x3) = transpose_aux_in_aga(x2) U1_aga(x1, x2, x3, x4, x5, x6) = U1_aga(x3, x6) row2col_in_aaaga(x1, x2, x3, x4, x5) = row2col_in_aaaga(x4) U2_aaaga(x1, x2, x3, x4, x5, x6, x7, x8) = U2_aaaga(x6, x8) row2col_out_aaaga(x1, x2, x3, x4, x5) = row2col_out_aaaga(x4, x5) .(x1, x2) = .(x1, x2) [] = [] transpose_aux_out_aga(x1, x2, x3) = transpose_aux_out_aga(x2) ---------------------------------------- (19) 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_AUX_IN_AGA(.(R, Rs), X1, .(C, Cs)) -> U1_AGA(R, Rs, X1, C, Cs, row2col_in_aaaga(R, .(C, Cs), Cols1, [], Accm)) TRANSPOSE_AUX_IN_AGA(.(R, Rs), X1, .(C, Cs)) -> ROW2COL_IN_AAAGA(R, .(C, Cs), Cols1, [], Accm) ROW2COL_IN_AAAGA(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> U2_AAAGA(X, Xs, Ys, Cols, Cols1, A, B, row2col_in_aaaga(Xs, Cols, Cols1, .([], A), B)) ROW2COL_IN_AAAGA(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> ROW2COL_IN_AAAGA(Xs, Cols, Cols1, .([], A), B) The TRS R consists of the following rules: transpose_aux_in_aga(.(R, Rs), X1, .(C, Cs)) -> U1_aga(R, Rs, X1, C, Cs, row2col_in_aaaga(R, .(C, Cs), Cols1, [], Accm)) row2col_in_aaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> U2_aaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_in_aaaga(Xs, Cols, Cols1, .([], A), B)) U2_aaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_out_aaaga(Xs, Cols, Cols1, .([], A), B)) -> row2col_out_aaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) U1_aga(R, Rs, X1, C, Cs, row2col_out_aaaga(R, .(C, Cs), Cols1, [], Accm)) -> transpose_aux_out_aga(.(R, Rs), X1, .(C, Cs)) The argument filtering Pi contains the following mapping: transpose_aux_in_aga(x1, x2, x3) = transpose_aux_in_aga(x2) U1_aga(x1, x2, x3, x4, x5, x6) = U1_aga(x3, x6) row2col_in_aaaga(x1, x2, x3, x4, x5) = row2col_in_aaaga(x4) U2_aaaga(x1, x2, x3, x4, x5, x6, x7, x8) = U2_aaaga(x6, x8) row2col_out_aaaga(x1, x2, x3, x4, x5) = row2col_out_aaaga(x4, x5) .(x1, x2) = .(x1, x2) [] = [] transpose_aux_out_aga(x1, x2, x3) = transpose_aux_out_aga(x2) TRANSPOSE_AUX_IN_AGA(x1, x2, x3) = TRANSPOSE_AUX_IN_AGA(x2) U1_AGA(x1, x2, x3, x4, x5, x6) = U1_AGA(x3, x6) ROW2COL_IN_AAAGA(x1, x2, x3, x4, x5) = ROW2COL_IN_AAAGA(x4) U2_AAAGA(x1, x2, x3, x4, x5, x6, x7, x8) = U2_AAAGA(x6, x8) We have to consider all (P,R,Pi)-chains ---------------------------------------- (20) Obligation: Pi DP problem: The TRS P consists of the following rules: TRANSPOSE_AUX_IN_AGA(.(R, Rs), X1, .(C, Cs)) -> U1_AGA(R, Rs, X1, C, Cs, row2col_in_aaaga(R, .(C, Cs), Cols1, [], Accm)) TRANSPOSE_AUX_IN_AGA(.(R, Rs), X1, .(C, Cs)) -> ROW2COL_IN_AAAGA(R, .(C, Cs), Cols1, [], Accm) ROW2COL_IN_AAAGA(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> U2_AAAGA(X, Xs, Ys, Cols, Cols1, A, B, row2col_in_aaaga(Xs, Cols, Cols1, .([], A), B)) ROW2COL_IN_AAAGA(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> ROW2COL_IN_AAAGA(Xs, Cols, Cols1, .([], A), B) The TRS R consists of the following rules: transpose_aux_in_aga(.(R, Rs), X1, .(C, Cs)) -> U1_aga(R, Rs, X1, C, Cs, row2col_in_aaaga(R, .(C, Cs), Cols1, [], Accm)) row2col_in_aaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> U2_aaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_in_aaaga(Xs, Cols, Cols1, .([], A), B)) U2_aaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_out_aaaga(Xs, Cols, Cols1, .([], A), B)) -> row2col_out_aaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) U1_aga(R, Rs, X1, C, Cs, row2col_out_aaaga(R, .(C, Cs), Cols1, [], Accm)) -> transpose_aux_out_aga(.(R, Rs), X1, .(C, Cs)) The argument filtering Pi contains the following mapping: transpose_aux_in_aga(x1, x2, x3) = transpose_aux_in_aga(x2) U1_aga(x1, x2, x3, x4, x5, x6) = U1_aga(x3, x6) row2col_in_aaaga(x1, x2, x3, x4, x5) = row2col_in_aaaga(x4) U2_aaaga(x1, x2, x3, x4, x5, x6, x7, x8) = U2_aaaga(x6, x8) row2col_out_aaaga(x1, x2, x3, x4, x5) = row2col_out_aaaga(x4, x5) .(x1, x2) = .(x1, x2) [] = [] transpose_aux_out_aga(x1, x2, x3) = transpose_aux_out_aga(x2) TRANSPOSE_AUX_IN_AGA(x1, x2, x3) = TRANSPOSE_AUX_IN_AGA(x2) U1_AGA(x1, x2, x3, x4, x5, x6) = U1_AGA(x3, x6) ROW2COL_IN_AAAGA(x1, x2, x3, x4, x5) = ROW2COL_IN_AAAGA(x4) U2_AAAGA(x1, x2, x3, x4, x5, x6, x7, x8) = U2_AAAGA(x6, x8) We have to consider all (P,R,Pi)-chains ---------------------------------------- (21) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 3 less nodes. ---------------------------------------- (22) Obligation: Pi DP problem: The TRS P consists of the following rules: ROW2COL_IN_AAAGA(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> ROW2COL_IN_AAAGA(Xs, Cols, Cols1, .([], A), B) The TRS R consists of the following rules: transpose_aux_in_aga(.(R, Rs), X1, .(C, Cs)) -> U1_aga(R, Rs, X1, C, Cs, row2col_in_aaaga(R, .(C, Cs), Cols1, [], Accm)) row2col_in_aaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> U2_aaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_in_aaaga(Xs, Cols, Cols1, .([], A), B)) U2_aaaga(X, Xs, Ys, Cols, Cols1, A, B, row2col_out_aaaga(Xs, Cols, Cols1, .([], A), B)) -> row2col_out_aaaga(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) U1_aga(R, Rs, X1, C, Cs, row2col_out_aaaga(R, .(C, Cs), Cols1, [], Accm)) -> transpose_aux_out_aga(.(R, Rs), X1, .(C, Cs)) The argument filtering Pi contains the following mapping: transpose_aux_in_aga(x1, x2, x3) = transpose_aux_in_aga(x2) U1_aga(x1, x2, x3, x4, x5, x6) = U1_aga(x3, x6) row2col_in_aaaga(x1, x2, x3, x4, x5) = row2col_in_aaaga(x4) U2_aaaga(x1, x2, x3, x4, x5, x6, x7, x8) = U2_aaaga(x6, x8) row2col_out_aaaga(x1, x2, x3, x4, x5) = row2col_out_aaaga(x4, x5) .(x1, x2) = .(x1, x2) [] = [] transpose_aux_out_aga(x1, x2, x3) = transpose_aux_out_aga(x2) ROW2COL_IN_AAAGA(x1, x2, x3, x4, x5) = ROW2COL_IN_AAAGA(x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (23) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (24) Obligation: Pi DP problem: The TRS P consists of the following rules: ROW2COL_IN_AAAGA(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), A, B) -> ROW2COL_IN_AAAGA(Xs, Cols, Cols1, .([], A), B) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) [] = [] ROW2COL_IN_AAAGA(x1, x2, x3, x4, x5) = ROW2COL_IN_AAAGA(x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (25) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: ROW2COL_IN_AAAGA(A) -> ROW2COL_IN_AAAGA(.([], A)) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (27) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule ROW2COL_IN_AAAGA(A) -> ROW2COL_IN_AAAGA(.([], A)) we obtained the following new rules [LPAR04]: (ROW2COL_IN_AAAGA(.([], z0)) -> ROW2COL_IN_AAAGA(.([], .([], z0))),ROW2COL_IN_AAAGA(.([], z0)) -> ROW2COL_IN_AAAGA(.([], .([], z0)))) ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: ROW2COL_IN_AAAGA(.([], z0)) -> ROW2COL_IN_AAAGA(.([], .([], z0))) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (29) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule ROW2COL_IN_AAAGA(.([], z0)) -> ROW2COL_IN_AAAGA(.([], .([], z0))) we obtained the following new rules [LPAR04]: (ROW2COL_IN_AAAGA(.([], .([], z0))) -> ROW2COL_IN_AAAGA(.([], .([], .([], z0)))),ROW2COL_IN_AAAGA(.([], .([], z0))) -> ROW2COL_IN_AAAGA(.([], .([], .([], z0))))) ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: ROW2COL_IN_AAAGA(.([], .([], z0))) -> ROW2COL_IN_AAAGA(.([], .([], .([], z0)))) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (31) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by semiunifying a rule from P directly. s = ROW2COL_IN_AAAGA(.([], .([], z0))) evaluates to t =ROW2COL_IN_AAAGA(.([], .([], .([], z0)))) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [z0 / .([], z0)] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence The DP semiunifies directly so there is only one rewrite step from ROW2COL_IN_AAAGA(.([], .([], z0))) to ROW2COL_IN_AAAGA(.([], .([], .([], z0)))). ---------------------------------------- (32) NO ---------------------------------------- (33) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 2, "program": { "directives": [], "clauses": [ [ "(transpose_aux (. R Rs) X1 (. C Cs))", "(row2col R (. C Cs) Cols1 ([]) Accm)" ], [ "(row2col (. X Xs) (. (. X Ys) Cols) (. Ys Cols1) A B)", "(row2col Xs Cols Cols1 (. ([]) A) B)" ] ] }, "graph": { "nodes": { "type": "Nodes", "253": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T182 T183 X336 (. ([]) (. ([]) T181)) X337)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T181"], "free": [ "X336", "X337" ], "exprvars": [] } }, "210": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "232": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T119 T120 X219 (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) ([]))))))) X220)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X219", "X220" ], "exprvars": [] } }, "254": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "211": { "goal": [{ "clause": 1, "scope": 5, "term": "(row2col T65 T66 X111 (. ([]) (. ([]) (. ([]) ([])))) X112)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X111", "X112" ], "exprvars": [] } }, "212": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T83 T84 X147 (. ([]) (. ([]) (. ([]) (. ([]) ([]))))) X148)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X147", "X148" ], "exprvars": [] } }, "234": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "235": { "goal": [{ "clause": 1, "scope": 8, "term": "(row2col T119 T120 X219 (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) ([]))))))) X220)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X219", "X220" ], "exprvars": [] } }, "237": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T137 T138 X255 (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) ([])))))))) X256)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X255", "X256" ], "exprvars": [] } }, "238": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "217": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "218": { "goal": [{ "clause": 1, "scope": 6, "term": "(row2col T83 T84 X147 (. ([]) (. ([]) (. ([]) (. ([]) ([]))))) X148)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X147", "X148" ], "exprvars": [] } }, "10": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T14 (. T15 T16) X12 ([]) X13)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X12", "X13" ], "exprvars": [] } }, "13": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "14": { "goal": [{ "clause": 1, "scope": 2, "term": "(row2col T14 (. T15 T16) X12 ([]) X13)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X12", "X13" ], "exprvars": [] } }, "241": { "goal": [{ "clause": 1, "scope": 9, "term": "(row2col T137 T138 X255 (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) ([])))))))) X256)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X255", "X256" ], "exprvars": [] } }, "188": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T29 T30 X39 (. ([]) ([])) X40)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X39", "X40" ], "exprvars": [] } }, "243": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T155 T156 X291 (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) ([]))))))))) X292)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X291", "X292" ], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(transpose_aux T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "200": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "244": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "201": { "goal": [{ "clause": 1, "scope": 3, "term": "(row2col T29 T30 X39 (. ([]) ([])) X40)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X39", "X40" ], "exprvars": [] } }, "202": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T47 T48 X75 (. ([]) (. ([]) ([]))) X76)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X75", "X76" ], "exprvars": [] } }, "246": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T155 T156 X291 (. ([]) T161) X292)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T161"], "free": [ "X291", "X292" ], "exprvars": [] } }, "5": { "goal": [{ "clause": 0, "scope": 1, "term": "(transpose_aux T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "227": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T101 T102 X183 (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) ([])))))) X184)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X183", "X184" ], "exprvars": [] } }, "249": { "goal": [{ "clause": 1, "scope": 10, "term": "(row2col T155 T156 X291 (. ([]) T161) X292)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T161"], "free": [ "X291", "X292" ], "exprvars": [] } }, "228": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "207": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "229": { "goal": [{ "clause": 1, "scope": 7, "term": "(row2col T101 T102 X183 (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) ([])))))) X184)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X183", "X184" ], "exprvars": [] } }, "208": { "goal": [{ "clause": 1, "scope": 4, "term": "(row2col T47 T48 X75 (. ([]) (. ([]) ([]))) X76)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X75", "X76" ], "exprvars": [] } }, "209": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T65 T66 X111 (. ([]) (. ([]) (. ([]) ([])))) X112)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X111", "X112" ], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 5, "label": "CASE" }, { "from": 5, "to": 10, "label": "EVAL with clause\ntranspose_aux(.(X7, X8), X9, .(X10, X11)) :- row2col(X7, .(X10, X11), X12, [], X13).\nand substitutionX7 -> T14,\nX8 -> T10,\nT1 -> .(T14, T10),\nT2 -> T11,\nX9 -> T11,\nX10 -> T15,\nX11 -> T16,\nT3 -> .(T15, T16),\nT9 -> T14,\nT12 -> T15,\nT13 -> T16" }, { "from": 5, "to": 13, "label": "EVAL-BACKTRACK" }, { "from": 10, "to": 14, "label": "CASE" }, { "from": 14, "to": 188, "label": "EVAL with clause\nrow2col(.(X32, X33), .(.(X32, X34), X35), .(X34, X36), X37, X38) :- row2col(X33, X35, X36, .([], X37), X38).\nand substitutionX32 -> T25,\nX33 -> T29,\nT14 -> .(T25, T29),\nX34 -> T27,\nT15 -> .(T25, T27),\nT16 -> T30,\nX35 -> T30,\nX36 -> X39,\nX12 -> .(T27, X39),\nX37 -> [],\nX13 -> X40,\nX38 -> X40,\nT26 -> T29,\nT28 -> T30" }, { "from": 14, "to": 200, "label": "EVAL-BACKTRACK" }, { "from": 188, "to": 201, "label": "CASE" }, { "from": 201, "to": 202, "label": "EVAL with clause\nrow2col(.(X68, X69), .(.(X68, X70), X71), .(X70, X72), X73, X74) :- row2col(X69, X71, X72, .([], X73), X74).\nand substitutionX68 -> T43,\nX69 -> T47,\nT29 -> .(T43, T47),\nX70 -> T45,\nX71 -> T48,\nT30 -> .(.(T43, T45), T48),\nX72 -> X75,\nX39 -> .(T45, X75),\nX73 -> .([], []),\nX40 -> X76,\nX74 -> X76,\nT44 -> T47,\nT46 -> T48" }, { "from": 201, "to": 207, "label": "EVAL-BACKTRACK" }, { "from": 202, "to": 208, "label": "CASE" }, { "from": 208, "to": 209, "label": "EVAL with clause\nrow2col(.(X104, X105), .(.(X104, X106), X107), .(X106, X108), X109, X110) :- row2col(X105, X107, X108, .([], X109), X110).\nand substitutionX104 -> T61,\nX105 -> T65,\nT47 -> .(T61, T65),\nX106 -> T63,\nX107 -> T66,\nT48 -> .(.(T61, T63), T66),\nX108 -> X111,\nX75 -> .(T63, X111),\nX109 -> .([], .([], [])),\nX76 -> X112,\nX110 -> X112,\nT62 -> T65,\nT64 -> T66" }, { "from": 208, "to": 210, "label": "EVAL-BACKTRACK" }, { "from": 209, "to": 211, "label": "CASE" }, { "from": 211, "to": 212, "label": "EVAL with clause\nrow2col(.(X140, X141), .(.(X140, X142), X143), .(X142, X144), X145, X146) :- row2col(X141, X143, X144, .([], X145), X146).\nand substitutionX140 -> T79,\nX141 -> T83,\nT65 -> .(T79, T83),\nX142 -> T81,\nX143 -> T84,\nT66 -> .(.(T79, T81), T84),\nX144 -> X147,\nX111 -> .(T81, X147),\nX145 -> .([], .([], .([], []))),\nX112 -> X148,\nX146 -> X148,\nT80 -> T83,\nT82 -> T84" }, { "from": 211, "to": 217, "label": "EVAL-BACKTRACK" }, { "from": 212, "to": 218, "label": "CASE" }, { "from": 218, "to": 227, "label": "EVAL with clause\nrow2col(.(X176, X177), .(.(X176, X178), X179), .(X178, X180), X181, X182) :- row2col(X177, X179, X180, .([], X181), X182).\nand substitutionX176 -> T97,\nX177 -> T101,\nT83 -> .(T97, T101),\nX178 -> T99,\nX179 -> T102,\nT84 -> .(.(T97, T99), T102),\nX180 -> X183,\nX147 -> .(T99, X183),\nX181 -> .([], .([], .([], .([], [])))),\nX148 -> X184,\nX182 -> X184,\nT98 -> T101,\nT100 -> T102" }, { "from": 218, "to": 228, "label": "EVAL-BACKTRACK" }, { "from": 227, "to": 229, "label": "CASE" }, { "from": 229, "to": 232, "label": "EVAL with clause\nrow2col(.(X212, X213), .(.(X212, X214), X215), .(X214, X216), X217, X218) :- row2col(X213, X215, X216, .([], X217), X218).\nand substitutionX212 -> T115,\nX213 -> T119,\nT101 -> .(T115, T119),\nX214 -> T117,\nX215 -> T120,\nT102 -> .(.(T115, T117), T120),\nX216 -> X219,\nX183 -> .(T117, X219),\nX217 -> .([], .([], .([], .([], .([], []))))),\nX184 -> X220,\nX218 -> X220,\nT116 -> T119,\nT118 -> T120" }, { "from": 229, "to": 234, "label": "EVAL-BACKTRACK" }, { "from": 232, "to": 235, "label": "CASE" }, { "from": 235, "to": 237, "label": "EVAL with clause\nrow2col(.(X248, X249), .(.(X248, X250), X251), .(X250, X252), X253, X254) :- row2col(X249, X251, X252, .([], X253), X254).\nand substitutionX248 -> T133,\nX249 -> T137,\nT119 -> .(T133, T137),\nX250 -> T135,\nX251 -> T138,\nT120 -> .(.(T133, T135), T138),\nX252 -> X255,\nX219 -> .(T135, X255),\nX253 -> .([], .([], .([], .([], .([], .([], [])))))),\nX220 -> X256,\nX254 -> X256,\nT134 -> T137,\nT136 -> T138" }, { "from": 235, "to": 238, "label": "EVAL-BACKTRACK" }, { "from": 237, "to": 241, "label": "CASE" }, { "from": 241, "to": 243, "label": "EVAL with clause\nrow2col(.(X284, X285), .(.(X284, X286), X287), .(X286, X288), X289, X290) :- row2col(X285, X287, X288, .([], X289), X290).\nand substitutionX284 -> T151,\nX285 -> T155,\nT137 -> .(T151, T155),\nX286 -> T153,\nX287 -> T156,\nT138 -> .(.(T151, T153), T156),\nX288 -> X291,\nX255 -> .(T153, X291),\nX289 -> .([], .([], .([], .([], .([], .([], .([], []))))))),\nX256 -> X292,\nX290 -> X292,\nT152 -> T155,\nT154 -> T156" }, { "from": 241, "to": 244, "label": "EVAL-BACKTRACK" }, { "from": 243, "to": 246, "label": "GENERALIZATION\nT161 <-- .([], .([], .([], .([], .([], .([], .([], [])))))))\n\nNew Knowledge:\nT161 is ground" }, { "from": 246, "to": 249, "label": "CASE" }, { "from": 249, "to": 253, "label": "EVAL with clause\nrow2col(.(X329, X330), .(.(X329, X331), X332), .(X331, X333), X334, X335) :- row2col(X330, X332, X333, .([], X334), X335).\nand substitutionX329 -> T177,\nX330 -> T182,\nT155 -> .(T177, T182),\nX331 -> T179,\nX332 -> T183,\nT156 -> .(.(T177, T179), T183),\nX333 -> X336,\nX291 -> .(T179, X336),\nT161 -> T181,\nX334 -> .([], T181),\nX292 -> X337,\nX335 -> X337,\nT178 -> T182,\nT180 -> T183" }, { "from": 249, "to": 254, "label": "EVAL-BACKTRACK" }, { "from": 253, "to": 246, "label": "INSTANCE with matching:\nT155 -> T182\nT156 -> T183\nX291 -> X336\nT161 -> .([], T181)\nX292 -> X337" } ], "type": "Graph" } } ---------------------------------------- (34) Obligation: Triples: row2colA(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), X6, X7) :- row2colA(X2, X4, X5, .([], X6), X7). transpose_auxB(.(.(X1, .(X2, .(X3, .(X4, .(X5, .(X6, .(X7, .(X8, X9)))))))), X10), X11, .(.(X1, X12), .(.(X2, X13), .(.(X3, X14), .(.(X4, X15), .(.(X5, X16), .(.(X6, X17), .(.(X7, X18), .(.(X8, X19), X20))))))))) :- row2colA(X9, X20, X21, .([], .([], .([], .([], .([], .([], .([], []))))))), X22). Clauses: row2colcA(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), X6, X7) :- row2colcA(X2, X4, X5, .([], X6), X7). Afs: transpose_auxB(x1, x2, x3) = transpose_auxB(x2) ---------------------------------------- (35) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: transpose_auxB_in_3: (f,b,f) row2colA_in_5: (f,f,f,b,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: TRANSPOSE_AUXB_IN_AGA(.(.(X1, .(X2, .(X3, .(X4, .(X5, .(X6, .(X7, .(X8, X9)))))))), X10), X11, .(.(X1, X12), .(.(X2, X13), .(.(X3, X14), .(.(X4, X15), .(.(X5, X16), .(.(X6, X17), .(.(X7, X18), .(.(X8, X19), X20))))))))) -> U2_AGA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, X19, X20, row2colA_in_aaaga(X9, X20, X21, .([], .([], .([], .([], .([], .([], .([], []))))))), X22)) TRANSPOSE_AUXB_IN_AGA(.(.(X1, .(X2, .(X3, .(X4, .(X5, .(X6, .(X7, .(X8, X9)))))))), X10), X11, .(.(X1, X12), .(.(X2, X13), .(.(X3, X14), .(.(X4, X15), .(.(X5, X16), .(.(X6, X17), .(.(X7, X18), .(.(X8, X19), X20))))))))) -> ROW2COLA_IN_AAAGA(X9, X20, X21, .([], .([], .([], .([], .([], .([], .([], []))))))), X22) ROW2COLA_IN_AAAGA(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), X6, X7) -> U1_AAAGA(X1, X2, X3, X4, X5, X6, X7, row2colA_in_aaaga(X2, X4, X5, .([], X6), X7)) ROW2COLA_IN_AAAGA(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), X6, X7) -> ROW2COLA_IN_AAAGA(X2, X4, X5, .([], X6), X7) R is empty. The argument filtering Pi contains the following mapping: row2colA_in_aaaga(x1, x2, x3, x4, x5) = row2colA_in_aaaga(x4) .(x1, x2) = .(x1, x2) [] = [] TRANSPOSE_AUXB_IN_AGA(x1, x2, x3) = TRANSPOSE_AUXB_IN_AGA(x2) U2_AGA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21) = U2_AGA(x11, x21) ROW2COLA_IN_AAAGA(x1, x2, x3, x4, x5) = ROW2COLA_IN_AAAGA(x4) U1_AAAGA(x1, x2, x3, x4, x5, x6, x7, x8) = U1_AAAGA(x6, x8) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (36) Obligation: Pi DP problem: The TRS P consists of the following rules: TRANSPOSE_AUXB_IN_AGA(.(.(X1, .(X2, .(X3, .(X4, .(X5, .(X6, .(X7, .(X8, X9)))))))), X10), X11, .(.(X1, X12), .(.(X2, X13), .(.(X3, X14), .(.(X4, X15), .(.(X5, X16), .(.(X6, X17), .(.(X7, X18), .(.(X8, X19), X20))))))))) -> U2_AGA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, X19, X20, row2colA_in_aaaga(X9, X20, X21, .([], .([], .([], .([], .([], .([], .([], []))))))), X22)) TRANSPOSE_AUXB_IN_AGA(.(.(X1, .(X2, .(X3, .(X4, .(X5, .(X6, .(X7, .(X8, X9)))))))), X10), X11, .(.(X1, X12), .(.(X2, X13), .(.(X3, X14), .(.(X4, X15), .(.(X5, X16), .(.(X6, X17), .(.(X7, X18), .(.(X8, X19), X20))))))))) -> ROW2COLA_IN_AAAGA(X9, X20, X21, .([], .([], .([], .([], .([], .([], .([], []))))))), X22) ROW2COLA_IN_AAAGA(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), X6, X7) -> U1_AAAGA(X1, X2, X3, X4, X5, X6, X7, row2colA_in_aaaga(X2, X4, X5, .([], X6), X7)) ROW2COLA_IN_AAAGA(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), X6, X7) -> ROW2COLA_IN_AAAGA(X2, X4, X5, .([], X6), X7) R is empty. The argument filtering Pi contains the following mapping: row2colA_in_aaaga(x1, x2, x3, x4, x5) = row2colA_in_aaaga(x4) .(x1, x2) = .(x1, x2) [] = [] TRANSPOSE_AUXB_IN_AGA(x1, x2, x3) = TRANSPOSE_AUXB_IN_AGA(x2) U2_AGA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21) = U2_AGA(x11, x21) ROW2COLA_IN_AAAGA(x1, x2, x3, x4, x5) = ROW2COLA_IN_AAAGA(x4) U1_AAAGA(x1, x2, x3, x4, x5, x6, x7, x8) = U1_AAAGA(x6, x8) We have to consider all (P,R,Pi)-chains ---------------------------------------- (37) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 3 less nodes. ---------------------------------------- (38) Obligation: Pi DP problem: The TRS P consists of the following rules: ROW2COLA_IN_AAAGA(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), X6, X7) -> ROW2COLA_IN_AAAGA(X2, X4, X5, .([], X6), X7) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) [] = [] ROW2COLA_IN_AAAGA(x1, x2, x3, x4, x5) = ROW2COLA_IN_AAAGA(x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (39) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (40) Obligation: Q DP problem: The TRS P consists of the following rules: ROW2COLA_IN_AAAGA(X6) -> ROW2COLA_IN_AAAGA(.([], X6)) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (41) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule ROW2COLA_IN_AAAGA(X6) -> ROW2COLA_IN_AAAGA(.([], X6)) we obtained the following new rules [LPAR04]: (ROW2COLA_IN_AAAGA(.([], z0)) -> ROW2COLA_IN_AAAGA(.([], .([], z0))),ROW2COLA_IN_AAAGA(.([], z0)) -> ROW2COLA_IN_AAAGA(.([], .([], z0)))) ---------------------------------------- (42) Obligation: Q DP problem: The TRS P consists of the following rules: ROW2COLA_IN_AAAGA(.([], z0)) -> ROW2COLA_IN_AAAGA(.([], .([], z0))) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (43) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule ROW2COLA_IN_AAAGA(.([], z0)) -> ROW2COLA_IN_AAAGA(.([], .([], z0))) we obtained the following new rules [LPAR04]: (ROW2COLA_IN_AAAGA(.([], .([], z0))) -> ROW2COLA_IN_AAAGA(.([], .([], .([], z0)))),ROW2COLA_IN_AAAGA(.([], .([], z0))) -> ROW2COLA_IN_AAAGA(.([], .([], .([], z0))))) ---------------------------------------- (44) Obligation: Q DP problem: The TRS P consists of the following rules: ROW2COLA_IN_AAAGA(.([], .([], z0))) -> ROW2COLA_IN_AAAGA(.([], .([], .([], z0)))) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (45) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by semiunifying a rule from P directly. s = ROW2COLA_IN_AAAGA(.([], .([], z0))) evaluates to t =ROW2COLA_IN_AAAGA(.([], .([], .([], z0)))) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [z0 / .([], z0)] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence The DP semiunifies directly so there is only one rewrite step from ROW2COLA_IN_AAAGA(.([], .([], z0))) to ROW2COLA_IN_AAAGA(.([], .([], .([], z0)))). ---------------------------------------- (46) NO ---------------------------------------- (47) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 1, "program": { "directives": [], "clauses": [ [ "(transpose_aux (. R Rs) X1 (. C Cs))", "(row2col R (. C Cs) Cols1 ([]) Accm)" ], [ "(row2col (. X Xs) (. (. X Ys) Cols) (. Ys Cols1) A B)", "(row2col Xs Cols Cols1 (. ([]) A) B)" ] ] }, "graph": { "nodes": { "22": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T38 T39 X55 (. ([]) ([])) X56)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X55", "X56" ], "exprvars": [] } }, "24": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "26": { "goal": [{ "clause": 1, "scope": 3, "term": "(row2col T38 T39 X55 (. ([]) ([])) X56)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X55", "X56" ], "exprvars": [] } }, "190": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T92 T93 X163 (. ([]) (. ([]) (. ([]) (. ([]) ([]))))) X164)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X163", "X164" ], "exprvars": [] } }, "191": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "192": { "goal": [{ "clause": 1, "scope": 6, "term": "(row2col T92 T93 X163 (. ([]) (. ([]) (. ([]) (. ([]) ([]))))) X164)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X163", "X164" ], "exprvars": [] } }, "193": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T110 T111 X199 (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) ([])))))) X200)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X199", "X200" ], "exprvars": [] } }, "type": "Nodes", "194": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "195": { "goal": [{ "clause": 1, "scope": 7, "term": "(row2col T110 T111 X199 (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) ([])))))) X200)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X199", "X200" ], "exprvars": [] } }, "250": { "goal": [{ "clause": 1, "scope": 9, "term": "(row2col T146 T147 X271 (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) ([])))))))) X272)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X271", "X272" ], "exprvars": [] } }, "255": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T164 T165 X307 (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) ([]))))))))) X308)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X307", "X308" ], "exprvars": [] } }, "256": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "257": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T164 T165 X307 (. ([]) T170) X308)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T170"], "free": [ "X307", "X308" ], "exprvars": [] } }, "258": { "goal": [{ "clause": 1, "scope": 10, "term": "(row2col T164 T165 X307 (. ([]) T170) X308)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T170"], "free": [ "X307", "X308" ], "exprvars": [] } }, "259": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T191 T192 X352 (. ([]) (. ([]) T190)) X353)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T190"], "free": [ "X352", "X353" ], "exprvars": [] } }, "219": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T128 T129 X235 (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) ([]))))))) X236)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X235", "X236" ], "exprvars": [] } }, "33": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T56 T57 X91 (. ([]) (. ([]) ([]))) X92)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X91", "X92" ], "exprvars": [] } }, "35": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "37": { "goal": [{ "clause": 1, "scope": 4, "term": "(row2col T56 T57 X91 (. ([]) (. ([]) ([]))) X92)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X91", "X92" ], "exprvars": [] } }, "17": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T19 (. T20 T21) X19 ([]) X20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X19", "X20" ], "exprvars": [] } }, "18": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "260": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "220": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(transpose_aux T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "189": { "goal": [{ "clause": 1, "scope": 5, "term": "(row2col T74 T75 X127 (. ([]) (. ([]) (. ([]) ([])))) X128)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X127", "X128" ], "exprvars": [] } }, "223": { "goal": [{ "clause": 1, "scope": 8, "term": "(row2col T128 T129 X235 (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) ([]))))))) X236)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X235", "X236" ], "exprvars": [] } }, "104": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T74 T75 X127 (. ([]) (. ([]) (. ([]) ([])))) X128)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X127", "X128" ], "exprvars": [] } }, "247": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T146 T147 X271 (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) ([])))))))) X272)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X271", "X272" ], "exprvars": [] } }, "6": { "goal": [{ "clause": 0, "scope": 1, "term": "(transpose_aux T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "248": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "106": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "20": { "goal": [{ "clause": 1, "scope": 2, "term": "(row2col T19 (. T20 T21) X19 ([]) X20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X19", "X20" ], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 6, "label": "CASE" }, { "from": 6, "to": 17, "label": "EVAL with clause\ntranspose_aux(.(X14, X15), X16, .(X17, X18)) :- row2col(X14, .(X17, X18), X19, [], X20).\nand substitutionX14 -> T19,\nX15 -> T15,\nT1 -> .(T19, T15),\nT2 -> T16,\nX16 -> T16,\nX17 -> T20,\nX18 -> T21,\nT3 -> .(T20, T21),\nT14 -> T19,\nT17 -> T20,\nT18 -> T21" }, { "from": 6, "to": 18, "label": "EVAL-BACKTRACK" }, { "from": 17, "to": 20, "label": "CASE" }, { "from": 20, "to": 22, "label": "EVAL with clause\nrow2col(.(X48, X49), .(.(X48, X50), X51), .(X50, X52), X53, X54) :- row2col(X49, X51, X52, .([], X53), X54).\nand substitutionX48 -> T34,\nX49 -> T38,\nT19 -> .(T34, T38),\nX50 -> T36,\nT20 -> .(T34, T36),\nT21 -> T39,\nX51 -> T39,\nX52 -> X55,\nX19 -> .(T36, X55),\nX53 -> [],\nX20 -> X56,\nX54 -> X56,\nT35 -> T38,\nT37 -> T39" }, { "from": 20, "to": 24, "label": "EVAL-BACKTRACK" }, { "from": 22, "to": 26, "label": "CASE" }, { "from": 26, "to": 33, "label": "EVAL with clause\nrow2col(.(X84, X85), .(.(X84, X86), X87), .(X86, X88), X89, X90) :- row2col(X85, X87, X88, .([], X89), X90).\nand substitutionX84 -> T52,\nX85 -> T56,\nT38 -> .(T52, T56),\nX86 -> T54,\nX87 -> T57,\nT39 -> .(.(T52, T54), T57),\nX88 -> X91,\nX55 -> .(T54, X91),\nX89 -> .([], []),\nX56 -> X92,\nX90 -> X92,\nT53 -> T56,\nT55 -> T57" }, { "from": 26, "to": 35, "label": "EVAL-BACKTRACK" }, { "from": 33, "to": 37, "label": "CASE" }, { "from": 37, "to": 104, "label": "EVAL with clause\nrow2col(.(X120, X121), .(.(X120, X122), X123), .(X122, X124), X125, X126) :- row2col(X121, X123, X124, .([], X125), X126).\nand substitutionX120 -> T70,\nX121 -> T74,\nT56 -> .(T70, T74),\nX122 -> T72,\nX123 -> T75,\nT57 -> .(.(T70, T72), T75),\nX124 -> X127,\nX91 -> .(T72, X127),\nX125 -> .([], .([], [])),\nX92 -> X128,\nX126 -> X128,\nT71 -> T74,\nT73 -> T75" }, { "from": 37, "to": 106, "label": "EVAL-BACKTRACK" }, { "from": 104, "to": 189, "label": "CASE" }, { "from": 189, "to": 190, "label": "EVAL with clause\nrow2col(.(X156, X157), .(.(X156, X158), X159), .(X158, X160), X161, X162) :- row2col(X157, X159, X160, .([], X161), X162).\nand substitutionX156 -> T88,\nX157 -> T92,\nT74 -> .(T88, T92),\nX158 -> T90,\nX159 -> T93,\nT75 -> .(.(T88, T90), T93),\nX160 -> X163,\nX127 -> .(T90, X163),\nX161 -> .([], .([], .([], []))),\nX128 -> X164,\nX162 -> X164,\nT89 -> T92,\nT91 -> T93" }, { "from": 189, "to": 191, "label": "EVAL-BACKTRACK" }, { "from": 190, "to": 192, "label": "CASE" }, { "from": 192, "to": 193, "label": "EVAL with clause\nrow2col(.(X192, X193), .(.(X192, X194), X195), .(X194, X196), X197, X198) :- row2col(X193, X195, X196, .([], X197), X198).\nand substitutionX192 -> T106,\nX193 -> T110,\nT92 -> .(T106, T110),\nX194 -> T108,\nX195 -> T111,\nT93 -> .(.(T106, T108), T111),\nX196 -> X199,\nX163 -> .(T108, X199),\nX197 -> .([], .([], .([], .([], [])))),\nX164 -> X200,\nX198 -> X200,\nT107 -> T110,\nT109 -> T111" }, { "from": 192, "to": 194, "label": "EVAL-BACKTRACK" }, { "from": 193, "to": 195, "label": "CASE" }, { "from": 195, "to": 219, "label": "EVAL with clause\nrow2col(.(X228, X229), .(.(X228, X230), X231), .(X230, X232), X233, X234) :- row2col(X229, X231, X232, .([], X233), X234).\nand substitutionX228 -> T124,\nX229 -> T128,\nT110 -> .(T124, T128),\nX230 -> T126,\nX231 -> T129,\nT111 -> .(.(T124, T126), T129),\nX232 -> X235,\nX199 -> .(T126, X235),\nX233 -> .([], .([], .([], .([], .([], []))))),\nX200 -> X236,\nX234 -> X236,\nT125 -> T128,\nT127 -> T129" }, { "from": 195, "to": 220, "label": "EVAL-BACKTRACK" }, { "from": 219, "to": 223, "label": "CASE" }, { "from": 223, "to": 247, "label": "EVAL with clause\nrow2col(.(X264, X265), .(.(X264, X266), X267), .(X266, X268), X269, X270) :- row2col(X265, X267, X268, .([], X269), X270).\nand substitutionX264 -> T142,\nX265 -> T146,\nT128 -> .(T142, T146),\nX266 -> T144,\nX267 -> T147,\nT129 -> .(.(T142, T144), T147),\nX268 -> X271,\nX235 -> .(T144, X271),\nX269 -> .([], .([], .([], .([], .([], .([], [])))))),\nX236 -> X272,\nX270 -> X272,\nT143 -> T146,\nT145 -> T147" }, { "from": 223, "to": 248, "label": "EVAL-BACKTRACK" }, { "from": 247, "to": 250, "label": "CASE" }, { "from": 250, "to": 255, "label": "EVAL with clause\nrow2col(.(X300, X301), .(.(X300, X302), X303), .(X302, X304), X305, X306) :- row2col(X301, X303, X304, .([], X305), X306).\nand substitutionX300 -> T160,\nX301 -> T164,\nT146 -> .(T160, T164),\nX302 -> T162,\nX303 -> T165,\nT147 -> .(.(T160, T162), T165),\nX304 -> X307,\nX271 -> .(T162, X307),\nX305 -> .([], .([], .([], .([], .([], .([], .([], []))))))),\nX272 -> X308,\nX306 -> X308,\nT161 -> T164,\nT163 -> T165" }, { "from": 250, "to": 256, "label": "EVAL-BACKTRACK" }, { "from": 255, "to": 257, "label": "GENERALIZATION\nT170 <-- .([], .([], .([], .([], .([], .([], .([], [])))))))\n\nNew Knowledge:\nT170 is ground" }, { "from": 257, "to": 258, "label": "CASE" }, { "from": 258, "to": 259, "label": "EVAL with clause\nrow2col(.(X345, X346), .(.(X345, X347), X348), .(X347, X349), X350, X351) :- row2col(X346, X348, X349, .([], X350), X351).\nand substitutionX345 -> T186,\nX346 -> T191,\nT164 -> .(T186, T191),\nX347 -> T188,\nX348 -> T192,\nT165 -> .(.(T186, T188), T192),\nX349 -> X352,\nX307 -> .(T188, X352),\nT170 -> T190,\nX350 -> .([], T190),\nX308 -> X353,\nX351 -> X353,\nT187 -> T191,\nT189 -> T192" }, { "from": 258, "to": 260, "label": "EVAL-BACKTRACK" }, { "from": 259, "to": 257, "label": "INSTANCE with matching:\nT164 -> T191\nT165 -> T192\nX307 -> X352\nT170 -> .([], T190)\nX308 -> X353" } ], "type": "Graph" } } ---------------------------------------- (48) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f1_in(T16) -> U1(f257_in(.([], .([], .([], .([], .([], .([], .([], [])))))))), T16) U1(f257_out1(X308), T16) -> f1_out1 f257_in(T190) -> U2(f257_in(.([], T190)), T190) U2(f257_out1(X353), T190) -> f257_out1(X353) Q is empty. ---------------------------------------- (49) AAECC Innermost (EQUIVALENT) We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is f257_in(T190) -> U2(f257_in(.([], T190)), T190) U2(f257_out1(X353), T190) -> f257_out1(X353) The TRS R 2 is f1_in(T16) -> U1(f257_in(.([], .([], .([], .([], .([], .([], .([], [])))))))), T16) U1(f257_out1(X308), T16) -> f1_out1 The signature Sigma is {f1_in_1, U1_2, f1_out1} ---------------------------------------- (50) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f1_in(T16) -> U1(f257_in(.([], .([], .([], .([], .([], .([], .([], [])))))))), T16) U1(f257_out1(X308), T16) -> f1_out1 f257_in(T190) -> U2(f257_in(.([], T190)), T190) U2(f257_out1(X353), T190) -> f257_out1(X353) The set Q consists of the following terms: f1_in(x0) U1(f257_out1(x0), x1) f257_in(x0) U2(f257_out1(x0), x1) ---------------------------------------- (51) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (52) Obligation: Q DP problem: The TRS P consists of the following rules: F1_IN(T16) -> U1^1(f257_in(.([], .([], .([], .([], .([], .([], .([], [])))))))), T16) F1_IN(T16) -> F257_IN(.([], .([], .([], .([], .([], .([], .([], [])))))))) F257_IN(T190) -> U2^1(f257_in(.([], T190)), T190) F257_IN(T190) -> F257_IN(.([], T190)) The TRS R consists of the following rules: f1_in(T16) -> U1(f257_in(.([], .([], .([], .([], .([], .([], .([], [])))))))), T16) U1(f257_out1(X308), T16) -> f1_out1 f257_in(T190) -> U2(f257_in(.([], T190)), T190) U2(f257_out1(X353), T190) -> f257_out1(X353) The set Q consists of the following terms: f1_in(x0) U1(f257_out1(x0), x1) f257_in(x0) U2(f257_out1(x0), x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (53) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. ---------------------------------------- (54) Obligation: Q DP problem: The TRS P consists of the following rules: F257_IN(T190) -> F257_IN(.([], T190)) The TRS R consists of the following rules: f1_in(T16) -> U1(f257_in(.([], .([], .([], .([], .([], .([], .([], [])))))))), T16) U1(f257_out1(X308), T16) -> f1_out1 f257_in(T190) -> U2(f257_in(.([], T190)), T190) U2(f257_out1(X353), T190) -> f257_out1(X353) The set Q consists of the following terms: f1_in(x0) U1(f257_out1(x0), x1) f257_in(x0) U2(f257_out1(x0), x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (55) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (56) Obligation: Q DP problem: The TRS P consists of the following rules: F257_IN(T190) -> F257_IN(.([], T190)) R is empty. The set Q consists of the following terms: f1_in(x0) U1(f257_out1(x0), x1) f257_in(x0) U2(f257_out1(x0), x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (57) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. f1_in(x0) U1(f257_out1(x0), x1) f257_in(x0) U2(f257_out1(x0), x1) ---------------------------------------- (58) Obligation: Q DP problem: The TRS P consists of the following rules: F257_IN(T190) -> F257_IN(.([], T190)) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (59) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule F257_IN(T190) -> F257_IN(.([], T190)) we obtained the following new rules [LPAR04]: (F257_IN(.([], z0)) -> F257_IN(.([], .([], z0))),F257_IN(.([], z0)) -> F257_IN(.([], .([], z0)))) ---------------------------------------- (60) Obligation: Q DP problem: The TRS P consists of the following rules: F257_IN(.([], z0)) -> F257_IN(.([], .([], z0))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (61) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule F257_IN(.([], z0)) -> F257_IN(.([], .([], z0))) we obtained the following new rules [LPAR04]: (F257_IN(.([], .([], z0))) -> F257_IN(.([], .([], .([], z0)))),F257_IN(.([], .([], z0))) -> F257_IN(.([], .([], .([], z0))))) ---------------------------------------- (62) Obligation: Q DP problem: The TRS P consists of the following rules: F257_IN(.([], .([], z0))) -> F257_IN(.([], .([], .([], z0)))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (63) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by semiunifying a rule from P directly. s = F257_IN(.([], .([], z0))) evaluates to t =F257_IN(.([], .([], .([], z0)))) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [z0 / .([], z0)] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence The DP semiunifies directly so there is only one rewrite step from F257_IN(.([], .([], z0))) to F257_IN(.([], .([], .([], z0)))). ---------------------------------------- (64) NO ---------------------------------------- (65) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 3, "program": { "directives": [], "clauses": [ [ "(transpose_aux (. R Rs) X1 (. C Cs))", "(row2col R (. C Cs) Cols1 ([]) Accm)" ], [ "(row2col (. X Xs) (. (. X Ys) Cols) (. Ys Cols1) A B)", "(row2col Xs Cols Cols1 (. ([]) A) B)" ] ] }, "graph": { "nodes": { "23": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "25": { "goal": [{ "clause": 1, "scope": 3, "term": "(row2col T38 T39 X55 (. ([]) ([])) X56)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X55", "X56" ], "exprvars": [] } }, "type": "Nodes", "251": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T191 T192 X352 (. ([]) (. ([]) T190)) X353)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T190"], "free": [ "X352", "X353" ], "exprvars": [] } }, "230": { "goal": [{ "clause": 1, "scope": 8, "term": "(row2col T128 T129 X235 (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) ([]))))))) X236)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X235", "X236" ], "exprvars": [] } }, "252": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "231": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T146 T147 X271 (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) ([])))))))) X272)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X271", "X272" ], "exprvars": [] } }, "233": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "213": { "goal": [{ "clause": 1, "scope": 5, "term": "(row2col T74 T75 X127 (. ([]) (. ([]) (. ([]) ([])))) X128)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X127", "X128" ], "exprvars": [] } }, "214": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T92 T93 X163 (. ([]) (. ([]) (. ([]) (. ([]) ([]))))) X164)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X163", "X164" ], "exprvars": [] } }, "236": { "goal": [{ "clause": 1, "scope": 9, "term": "(row2col T146 T147 X271 (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) ([])))))))) X272)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X271", "X272" ], "exprvars": [] } }, "215": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "216": { "goal": [{ "clause": 1, "scope": 6, "term": "(row2col T92 T93 X163 (. ([]) (. ([]) (. ([]) (. ([]) ([]))))) X164)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X163", "X164" ], "exprvars": [] } }, "239": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T164 T165 X307 (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) ([]))))))))) X308)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X307", "X308" ], "exprvars": [] } }, "32": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T56 T57 X91 (. ([]) (. ([]) ([]))) X92)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X91", "X92" ], "exprvars": [] } }, "34": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "36": { "goal": [{ "clause": 1, "scope": 4, "term": "(row2col T56 T57 X91 (. ([]) (. ([]) ([]))) X92)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X91", "X92" ], "exprvars": [] } }, "19": { "goal": [{ "clause": 1, "scope": 2, "term": "(row2col T19 (. T20 T21) X19 ([]) X20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X19", "X20" ], "exprvars": [] } }, "240": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "242": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T164 T165 X307 (. ([]) T170) X308)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T170"], "free": [ "X307", "X308" ], "exprvars": [] } }, "221": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T110 T111 X199 (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) ([])))))) X200)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X199", "X200" ], "exprvars": [] } }, "222": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(transpose_aux T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "245": { "goal": [{ "clause": 1, "scope": 10, "term": "(row2col T164 T165 X307 (. ([]) T170) X308)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T170"], "free": [ "X307", "X308" ], "exprvars": [] } }, "4": { "goal": [{ "clause": 0, "scope": 1, "term": "(transpose_aux T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "103": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T74 T75 X127 (. ([]) (. ([]) (. ([]) ([])))) X128)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X127", "X128" ], "exprvars": [] } }, "224": { "goal": [{ "clause": 1, "scope": 7, "term": "(row2col T110 T111 X199 (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) ([])))))) X200)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X199", "X200" ], "exprvars": [] } }, "225": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T128 T129 X235 (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) (. ([]) ([]))))))) X236)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X235", "X236" ], "exprvars": [] } }, "226": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "7": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T19 (. T20 T21) X19 ([]) X20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X19", "X20" ], "exprvars": [] } }, "8": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "109": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "21": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T38 T39 X55 (. ([]) ([])) X56)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X55", "X56" ], "exprvars": [] } } }, "edges": [ { "from": 3, "to": 4, "label": "CASE" }, { "from": 4, "to": 7, "label": "EVAL with clause\ntranspose_aux(.(X14, X15), X16, .(X17, X18)) :- row2col(X14, .(X17, X18), X19, [], X20).\nand substitutionX14 -> T19,\nX15 -> T15,\nT1 -> .(T19, T15),\nT2 -> T16,\nX16 -> T16,\nX17 -> T20,\nX18 -> T21,\nT3 -> .(T20, T21),\nT14 -> T19,\nT17 -> T20,\nT18 -> T21" }, { "from": 4, "to": 8, "label": "EVAL-BACKTRACK" }, { "from": 7, "to": 19, "label": "CASE" }, { "from": 19, "to": 21, "label": "EVAL with clause\nrow2col(.(X48, X49), .(.(X48, X50), X51), .(X50, X52), X53, X54) :- row2col(X49, X51, X52, .([], X53), X54).\nand substitutionX48 -> T34,\nX49 -> T38,\nT19 -> .(T34, T38),\nX50 -> T36,\nT20 -> .(T34, T36),\nT21 -> T39,\nX51 -> T39,\nX52 -> X55,\nX19 -> .(T36, X55),\nX53 -> [],\nX20 -> X56,\nX54 -> X56,\nT35 -> T38,\nT37 -> T39" }, { "from": 19, "to": 23, "label": "EVAL-BACKTRACK" }, { "from": 21, "to": 25, "label": "CASE" }, { "from": 25, "to": 32, "label": "EVAL with clause\nrow2col(.(X84, X85), .(.(X84, X86), X87), .(X86, X88), X89, X90) :- row2col(X85, X87, X88, .([], X89), X90).\nand substitutionX84 -> T52,\nX85 -> T56,\nT38 -> .(T52, T56),\nX86 -> T54,\nX87 -> T57,\nT39 -> .(.(T52, T54), T57),\nX88 -> X91,\nX55 -> .(T54, X91),\nX89 -> .([], []),\nX56 -> X92,\nX90 -> X92,\nT53 -> T56,\nT55 -> T57" }, { "from": 25, "to": 34, "label": "EVAL-BACKTRACK" }, { "from": 32, "to": 36, "label": "CASE" }, { "from": 36, "to": 103, "label": "EVAL with clause\nrow2col(.(X120, X121), .(.(X120, X122), X123), .(X122, X124), X125, X126) :- row2col(X121, X123, X124, .([], X125), X126).\nand substitutionX120 -> T70,\nX121 -> T74,\nT56 -> .(T70, T74),\nX122 -> T72,\nX123 -> T75,\nT57 -> .(.(T70, T72), T75),\nX124 -> X127,\nX91 -> .(T72, X127),\nX125 -> .([], .([], [])),\nX92 -> X128,\nX126 -> X128,\nT71 -> T74,\nT73 -> T75" }, { "from": 36, "to": 109, "label": "EVAL-BACKTRACK" }, { "from": 103, "to": 213, "label": "CASE" }, { "from": 213, "to": 214, "label": "EVAL with clause\nrow2col(.(X156, X157), .(.(X156, X158), X159), .(X158, X160), X161, X162) :- row2col(X157, X159, X160, .([], X161), X162).\nand substitutionX156 -> T88,\nX157 -> T92,\nT74 -> .(T88, T92),\nX158 -> T90,\nX159 -> T93,\nT75 -> .(.(T88, T90), T93),\nX160 -> X163,\nX127 -> .(T90, X163),\nX161 -> .([], .([], .([], []))),\nX128 -> X164,\nX162 -> X164,\nT89 -> T92,\nT91 -> T93" }, { "from": 213, "to": 215, "label": "EVAL-BACKTRACK" }, { "from": 214, "to": 216, "label": "CASE" }, { "from": 216, "to": 221, "label": "EVAL with clause\nrow2col(.(X192, X193), .(.(X192, X194), X195), .(X194, X196), X197, X198) :- row2col(X193, X195, X196, .([], X197), X198).\nand substitutionX192 -> T106,\nX193 -> T110,\nT92 -> .(T106, T110),\nX194 -> T108,\nX195 -> T111,\nT93 -> .(.(T106, T108), T111),\nX196 -> X199,\nX163 -> .(T108, X199),\nX197 -> .([], .([], .([], .([], [])))),\nX164 -> X200,\nX198 -> X200,\nT107 -> T110,\nT109 -> T111" }, { "from": 216, "to": 222, "label": "EVAL-BACKTRACK" }, { "from": 221, "to": 224, "label": "CASE" }, { "from": 224, "to": 225, "label": "EVAL with clause\nrow2col(.(X228, X229), .(.(X228, X230), X231), .(X230, X232), X233, X234) :- row2col(X229, X231, X232, .([], X233), X234).\nand substitutionX228 -> T124,\nX229 -> T128,\nT110 -> .(T124, T128),\nX230 -> T126,\nX231 -> T129,\nT111 -> .(.(T124, T126), T129),\nX232 -> X235,\nX199 -> .(T126, X235),\nX233 -> .([], .([], .([], .([], .([], []))))),\nX200 -> X236,\nX234 -> X236,\nT125 -> T128,\nT127 -> T129" }, { "from": 224, "to": 226, "label": "EVAL-BACKTRACK" }, { "from": 225, "to": 230, "label": "CASE" }, { "from": 230, "to": 231, "label": "EVAL with clause\nrow2col(.(X264, X265), .(.(X264, X266), X267), .(X266, X268), X269, X270) :- row2col(X265, X267, X268, .([], X269), X270).\nand substitutionX264 -> T142,\nX265 -> T146,\nT128 -> .(T142, T146),\nX266 -> T144,\nX267 -> T147,\nT129 -> .(.(T142, T144), T147),\nX268 -> X271,\nX235 -> .(T144, X271),\nX269 -> .([], .([], .([], .([], .([], .([], [])))))),\nX236 -> X272,\nX270 -> X272,\nT143 -> T146,\nT145 -> T147" }, { "from": 230, "to": 233, "label": "EVAL-BACKTRACK" }, { "from": 231, "to": 236, "label": "CASE" }, { "from": 236, "to": 239, "label": "EVAL with clause\nrow2col(.(X300, X301), .(.(X300, X302), X303), .(X302, X304), X305, X306) :- row2col(X301, X303, X304, .([], X305), X306).\nand substitutionX300 -> T160,\nX301 -> T164,\nT146 -> .(T160, T164),\nX302 -> T162,\nX303 -> T165,\nT147 -> .(.(T160, T162), T165),\nX304 -> X307,\nX271 -> .(T162, X307),\nX305 -> .([], .([], .([], .([], .([], .([], .([], []))))))),\nX272 -> X308,\nX306 -> X308,\nT161 -> T164,\nT163 -> T165" }, { "from": 236, "to": 240, "label": "EVAL-BACKTRACK" }, { "from": 239, "to": 242, "label": "GENERALIZATION\nT170 <-- .([], .([], .([], .([], .([], .([], .([], [])))))))\n\nNew Knowledge:\nT170 is ground" }, { "from": 242, "to": 245, "label": "CASE" }, { "from": 245, "to": 251, "label": "EVAL with clause\nrow2col(.(X345, X346), .(.(X345, X347), X348), .(X347, X349), X350, X351) :- row2col(X346, X348, X349, .([], X350), X351).\nand substitutionX345 -> T186,\nX346 -> T191,\nT164 -> .(T186, T191),\nX347 -> T188,\nX348 -> T192,\nT165 -> .(.(T186, T188), T192),\nX349 -> X352,\nX307 -> .(T188, X352),\nT170 -> T190,\nX350 -> .([], T190),\nX308 -> X353,\nX351 -> X353,\nT187 -> T191,\nT189 -> T192" }, { "from": 245, "to": 252, "label": "EVAL-BACKTRACK" }, { "from": 251, "to": 242, "label": "INSTANCE with matching:\nT164 -> T191\nT165 -> T192\nX307 -> X352\nT170 -> .([], T190)\nX308 -> X353" } ], "type": "Graph" } } ---------------------------------------- (66) Obligation: Rules: f242_in(T170) -> f245_in(T170) :|: TRUE f245_out(x) -> f242_out(x) :|: TRUE f252_out -> f245_out(x1) :|: TRUE f245_in(T190) -> f251_in(T190) :|: TRUE f251_out(x2) -> f245_out(x2) :|: TRUE f245_in(x3) -> f252_in :|: TRUE f251_in(x4) -> f242_in(.([], x4)) :|: TRUE f242_out(.([], x5)) -> f251_out(x5) :|: TRUE f4_out(T2) -> f3_out(T2) :|: TRUE f3_in(x6) -> f4_in(x6) :|: TRUE f8_out -> f4_out(x7) :|: TRUE f7_out -> f4_out(T16) :|: TRUE f4_in(x8) -> f8_in :|: TRUE f4_in(x9) -> f7_in :|: TRUE f19_out -> f7_out :|: TRUE f7_in -> f19_in :|: TRUE f19_in -> f21_in :|: TRUE f21_out -> f19_out :|: TRUE f23_out -> f19_out :|: TRUE f19_in -> f23_in :|: TRUE f25_out -> f21_out :|: TRUE f21_in -> f25_in :|: TRUE f32_out -> f25_out :|: TRUE f25_in -> f34_in :|: TRUE f34_out -> f25_out :|: TRUE f25_in -> f32_in :|: TRUE f36_out -> f32_out :|: TRUE f32_in -> f36_in :|: TRUE f36_in -> f103_in :|: TRUE f36_in -> f109_in :|: TRUE f103_out -> f36_out :|: TRUE f109_out -> f36_out :|: TRUE f213_out -> f103_out :|: TRUE f103_in -> f213_in :|: TRUE f213_in -> f214_in :|: TRUE f213_in -> f215_in :|: TRUE f215_out -> f213_out :|: TRUE f214_out -> f213_out :|: TRUE f214_in -> f216_in :|: TRUE f216_out -> f214_out :|: TRUE f216_in -> f222_in :|: TRUE f222_out -> f216_out :|: TRUE f216_in -> f221_in :|: TRUE f221_out -> f216_out :|: TRUE f224_out -> f221_out :|: TRUE f221_in -> f224_in :|: TRUE f224_in -> f225_in :|: TRUE f226_out -> f224_out :|: TRUE f224_in -> f226_in :|: TRUE f225_out -> f224_out :|: TRUE f230_out -> f225_out :|: TRUE f225_in -> f230_in :|: TRUE f233_out -> f230_out :|: TRUE f231_out -> f230_out :|: TRUE f230_in -> f233_in :|: TRUE f230_in -> f231_in :|: TRUE f231_in -> f236_in :|: TRUE f236_out -> f231_out :|: TRUE f236_in -> f239_in :|: TRUE f240_out -> f236_out :|: TRUE f239_out -> f236_out :|: TRUE f236_in -> f240_in :|: TRUE f242_out(.([], .([], .([], .([], .([], .([], .([], [])))))))) -> f239_out :|: TRUE f239_in -> f242_in(.([], .([], .([], .([], .([], .([], .([], [])))))))) :|: TRUE Start term: f3_in(T2) ---------------------------------------- (67) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f242_in(T170) -> f245_in(T170) :|: TRUE f245_in(T190) -> f251_in(T190) :|: TRUE f251_in(x4) -> f242_in(.([], x4)) :|: TRUE ---------------------------------------- (68) Obligation: Rules: f242_in(T170) -> f245_in(T170) :|: TRUE f245_in(T190) -> f251_in(T190) :|: TRUE f251_in(x4) -> f242_in(.([], x4)) :|: TRUE ---------------------------------------- (69) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (70) Obligation: Rules: f242_in(T170:0) -> f242_in(.([], T170:0)) :|: TRUE ---------------------------------------- (71) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (72) Obligation: Rules: f242_in(T170:0) -> f242_in(.([], T170:0)) :|: TRUE ---------------------------------------- (73) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f242_in(T170:0) -> f242_in(.([], T170:0)) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (74) Obligation: Termination digraph: Nodes: (1) f242_in(T170:0) -> f242_in(.([], T170:0)) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (75) IRSwTToIntTRSProof (SOUND) Applied path-length measure to transform intTRS with terms to intTRS. ---------------------------------------- (76) Obligation: Rules: f242_in(x) -> f242_in(.([], x)) :|: TRUE