/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: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern in_order(a,g) w.r.t. the given Prolog program could not be shown: (0) Prolog (1) PrologToPiTRSProof [SOUND, 0 ms] (2) PiTRS (3) DependencyPairsProof [EQUIVALENT, 10 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [SOUND, 0 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 (21) PiDP (22) UsableRulesProof [EQUIVALENT, 0 ms] (23) PiDP (24) PiDPToQDPProof [SOUND, 0 ms] (25) QDP (26) PrologToPiTRSProof [SOUND, 0 ms] (27) PiTRS (28) DependencyPairsProof [EQUIVALENT, 4 ms] (29) PiDP (30) DependencyGraphProof [EQUIVALENT, 0 ms] (31) AND (32) PiDP (33) UsableRulesProof [EQUIVALENT, 0 ms] (34) PiDP (35) PiDPToQDPProof [SOUND, 0 ms] (36) QDP (37) QDPSizeChangeProof [EQUIVALENT, 0 ms] (38) YES (39) PiDP (40) UsableRulesProof [EQUIVALENT, 0 ms] (41) PiDP (42) PiDPToQDPProof [SOUND, 0 ms] (43) QDP (44) QDPSizeChangeProof [EQUIVALENT, 0 ms] (45) YES (46) PiDP (47) UsableRulesProof [EQUIVALENT, 0 ms] (48) PiDP (49) PiDPToQDPProof [SOUND, 1 ms] (50) QDP (51) PrologToTRSTransformerProof [SOUND, 22 ms] (52) QTRS (53) QTRSRRRProof [EQUIVALENT, 175 ms] (54) QTRS (55) PrologToIRSwTTransformerProof [SOUND, 22 ms] (56) AND (57) IRSwT (58) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (59) TRUE (60) IRSwT (61) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (62) TRUE (63) IRSwT (64) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (65) IRSwT (66) IntTRSCompressionProof [EQUIVALENT, 19 ms] (67) IRSwT (68) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (69) IRSwT (70) IRSwTTerminationDigraphProof [EQUIVALENT, 6 ms] (71) IRSwT (72) FilterProof [EQUIVALENT, 0 ms] (73) IntTRS (74) IntTRSNonPeriodicNontermProof [COMPLETE, 0 ms] (75) NO (76) PrologToDTProblemTransformerProof [SOUND, 30 ms] (77) TRIPLES (78) TriplesToPiDPProof [SOUND, 41 ms] (79) PiDP (80) DependencyGraphProof [EQUIVALENT, 0 ms] (81) AND (82) PiDP (83) UsableRulesProof [EQUIVALENT, 0 ms] (84) PiDP (85) PiDPToQDPProof [SOUND, 0 ms] (86) QDP (87) QDPSizeChangeProof [EQUIVALENT, 0 ms] (88) YES (89) PiDP (90) UsableRulesProof [EQUIVALENT, 0 ms] (91) PiDP (92) PiDPToQDPProof [SOUND, 0 ms] (93) QDP (94) QDPSizeChangeProof [EQUIVALENT, 0 ms] (95) YES (96) PiDP (97) PiDPToQDPProof [SOUND, 0 ms] (98) QDP ---------------------------------------- (0) Obligation: Clauses: in_order(void, []). in_order(tree(X, Left, Right), Xs) :- ','(in_order(Left, Ls), ','(in_order(Right, Rs), app(Ls, .(X, Rs), Xs))). app([], X, X). app(.(X, Xs), Ys, .(X, Zs)) :- app(Xs, Ys, Zs). Query: in_order(a,g) ---------------------------------------- (1) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: in_order_in_2: (f,b) (f,f) app_in_3: (b,b,f) (b,b,b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: in_order_in_ag(void, []) -> in_order_out_ag(void, []) in_order_in_ag(tree(X, Left, Right), Xs) -> U1_ag(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) in_order_in_aa(void, []) -> in_order_out_aa(void, []) in_order_in_aa(tree(X, Left, Right), Xs) -> U1_aa(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) U1_aa(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_aa(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_aa(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_aa(X, Left, Right, Xs, app_in_gga(Ls, .(X, Rs), Xs)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U4_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U4_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U3_aa(X, Left, Right, Xs, app_out_gga(Ls, .(X, Rs), Xs)) -> in_order_out_aa(tree(X, Left, Right), Xs) U1_ag(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_ag(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_ag(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_ag(X, Left, Right, Xs, app_in_ggg(Ls, .(X, Rs), Xs)) app_in_ggg([], X, X) -> app_out_ggg([], X, X) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U4_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) U4_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U3_ag(X, Left, Right, Xs, app_out_ggg(Ls, .(X, Rs), Xs)) -> in_order_out_ag(tree(X, Left, Right), Xs) The argument filtering Pi contains the following mapping: in_order_in_ag(x1, x2) = in_order_in_ag(x2) [] = [] in_order_out_ag(x1, x2) = in_order_out_ag(x1) U1_ag(x1, x2, x3, x4, x5) = U1_ag(x4, x5) in_order_in_aa(x1, x2) = in_order_in_aa in_order_out_aa(x1, x2) = in_order_out_aa(x1, x2) U1_aa(x1, x2, x3, x4, x5) = U1_aa(x5) U2_aa(x1, x2, x3, x4, x5, x6) = U2_aa(x2, x5, x6) U3_aa(x1, x2, x3, x4, x5) = U3_aa(x2, x3, x5) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x3) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x5) tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4, x5, x6) = U2_ag(x2, x4, x5, x6) U3_ag(x1, x2, x3, x4, x5) = U3_ag(x2, x3, x5) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) app_out_ggg(x1, x2, x3) = app_out_ggg U4_ggg(x1, x2, x3, x4, x5) = U4_ggg(x5) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (2) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: in_order_in_ag(void, []) -> in_order_out_ag(void, []) in_order_in_ag(tree(X, Left, Right), Xs) -> U1_ag(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) in_order_in_aa(void, []) -> in_order_out_aa(void, []) in_order_in_aa(tree(X, Left, Right), Xs) -> U1_aa(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) U1_aa(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_aa(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_aa(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_aa(X, Left, Right, Xs, app_in_gga(Ls, .(X, Rs), Xs)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U4_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U4_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U3_aa(X, Left, Right, Xs, app_out_gga(Ls, .(X, Rs), Xs)) -> in_order_out_aa(tree(X, Left, Right), Xs) U1_ag(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_ag(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_ag(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_ag(X, Left, Right, Xs, app_in_ggg(Ls, .(X, Rs), Xs)) app_in_ggg([], X, X) -> app_out_ggg([], X, X) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U4_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) U4_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U3_ag(X, Left, Right, Xs, app_out_ggg(Ls, .(X, Rs), Xs)) -> in_order_out_ag(tree(X, Left, Right), Xs) The argument filtering Pi contains the following mapping: in_order_in_ag(x1, x2) = in_order_in_ag(x2) [] = [] in_order_out_ag(x1, x2) = in_order_out_ag(x1) U1_ag(x1, x2, x3, x4, x5) = U1_ag(x4, x5) in_order_in_aa(x1, x2) = in_order_in_aa in_order_out_aa(x1, x2) = in_order_out_aa(x1, x2) U1_aa(x1, x2, x3, x4, x5) = U1_aa(x5) U2_aa(x1, x2, x3, x4, x5, x6) = U2_aa(x2, x5, x6) U3_aa(x1, x2, x3, x4, x5) = U3_aa(x2, x3, x5) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x3) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x5) tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4, x5, x6) = U2_ag(x2, x4, x5, x6) U3_ag(x1, x2, x3, x4, x5) = U3_ag(x2, x3, x5) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) app_out_ggg(x1, x2, x3) = app_out_ggg U4_ggg(x1, x2, x3, x4, x5) = U4_ggg(x5) ---------------------------------------- (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: IN_ORDER_IN_AG(tree(X, Left, Right), Xs) -> U1_AG(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) IN_ORDER_IN_AG(tree(X, Left, Right), Xs) -> IN_ORDER_IN_AA(Left, Ls) IN_ORDER_IN_AA(tree(X, Left, Right), Xs) -> U1_AA(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) IN_ORDER_IN_AA(tree(X, Left, Right), Xs) -> IN_ORDER_IN_AA(Left, Ls) U1_AA(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_AA(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U1_AA(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> IN_ORDER_IN_AA(Right, Rs) U2_AA(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_AA(X, Left, Right, Xs, app_in_gga(Ls, .(X, Rs), Xs)) U2_AA(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> APP_IN_GGA(Ls, .(X, Rs), Xs) APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> U4_GGA(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGA(Xs, Ys, Zs) U1_AG(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_AG(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U1_AG(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> IN_ORDER_IN_AA(Right, Rs) U2_AG(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_AG(X, Left, Right, Xs, app_in_ggg(Ls, .(X, Rs), Xs)) U2_AG(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> APP_IN_GGG(Ls, .(X, Rs), Xs) APP_IN_GGG(.(X, Xs), Ys, .(X, Zs)) -> U4_GGG(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) APP_IN_GGG(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGG(Xs, Ys, Zs) The TRS R consists of the following rules: in_order_in_ag(void, []) -> in_order_out_ag(void, []) in_order_in_ag(tree(X, Left, Right), Xs) -> U1_ag(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) in_order_in_aa(void, []) -> in_order_out_aa(void, []) in_order_in_aa(tree(X, Left, Right), Xs) -> U1_aa(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) U1_aa(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_aa(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_aa(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_aa(X, Left, Right, Xs, app_in_gga(Ls, .(X, Rs), Xs)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U4_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U4_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U3_aa(X, Left, Right, Xs, app_out_gga(Ls, .(X, Rs), Xs)) -> in_order_out_aa(tree(X, Left, Right), Xs) U1_ag(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_ag(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_ag(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_ag(X, Left, Right, Xs, app_in_ggg(Ls, .(X, Rs), Xs)) app_in_ggg([], X, X) -> app_out_ggg([], X, X) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U4_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) U4_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U3_ag(X, Left, Right, Xs, app_out_ggg(Ls, .(X, Rs), Xs)) -> in_order_out_ag(tree(X, Left, Right), Xs) The argument filtering Pi contains the following mapping: in_order_in_ag(x1, x2) = in_order_in_ag(x2) [] = [] in_order_out_ag(x1, x2) = in_order_out_ag(x1) U1_ag(x1, x2, x3, x4, x5) = U1_ag(x4, x5) in_order_in_aa(x1, x2) = in_order_in_aa in_order_out_aa(x1, x2) = in_order_out_aa(x1, x2) U1_aa(x1, x2, x3, x4, x5) = U1_aa(x5) U2_aa(x1, x2, x3, x4, x5, x6) = U2_aa(x2, x5, x6) U3_aa(x1, x2, x3, x4, x5) = U3_aa(x2, x3, x5) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x3) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x5) tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4, x5, x6) = U2_ag(x2, x4, x5, x6) U3_ag(x1, x2, x3, x4, x5) = U3_ag(x2, x3, x5) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) app_out_ggg(x1, x2, x3) = app_out_ggg U4_ggg(x1, x2, x3, x4, x5) = U4_ggg(x5) IN_ORDER_IN_AG(x1, x2) = IN_ORDER_IN_AG(x2) U1_AG(x1, x2, x3, x4, x5) = U1_AG(x4, x5) IN_ORDER_IN_AA(x1, x2) = IN_ORDER_IN_AA U1_AA(x1, x2, x3, x4, x5) = U1_AA(x5) U2_AA(x1, x2, x3, x4, x5, x6) = U2_AA(x2, x5, x6) U3_AA(x1, x2, x3, x4, x5) = U3_AA(x2, x3, x5) APP_IN_GGA(x1, x2, x3) = APP_IN_GGA(x1, x2) U4_GGA(x1, x2, x3, x4, x5) = U4_GGA(x5) U2_AG(x1, x2, x3, x4, x5, x6) = U2_AG(x2, x4, x5, x6) U3_AG(x1, x2, x3, x4, x5) = U3_AG(x2, x3, x5) APP_IN_GGG(x1, x2, x3) = APP_IN_GGG(x1, x2, x3) U4_GGG(x1, x2, x3, x4, x5) = U4_GGG(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: IN_ORDER_IN_AG(tree(X, Left, Right), Xs) -> U1_AG(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) IN_ORDER_IN_AG(tree(X, Left, Right), Xs) -> IN_ORDER_IN_AA(Left, Ls) IN_ORDER_IN_AA(tree(X, Left, Right), Xs) -> U1_AA(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) IN_ORDER_IN_AA(tree(X, Left, Right), Xs) -> IN_ORDER_IN_AA(Left, Ls) U1_AA(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_AA(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U1_AA(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> IN_ORDER_IN_AA(Right, Rs) U2_AA(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_AA(X, Left, Right, Xs, app_in_gga(Ls, .(X, Rs), Xs)) U2_AA(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> APP_IN_GGA(Ls, .(X, Rs), Xs) APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> U4_GGA(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGA(Xs, Ys, Zs) U1_AG(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_AG(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U1_AG(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> IN_ORDER_IN_AA(Right, Rs) U2_AG(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_AG(X, Left, Right, Xs, app_in_ggg(Ls, .(X, Rs), Xs)) U2_AG(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> APP_IN_GGG(Ls, .(X, Rs), Xs) APP_IN_GGG(.(X, Xs), Ys, .(X, Zs)) -> U4_GGG(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) APP_IN_GGG(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGG(Xs, Ys, Zs) The TRS R consists of the following rules: in_order_in_ag(void, []) -> in_order_out_ag(void, []) in_order_in_ag(tree(X, Left, Right), Xs) -> U1_ag(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) in_order_in_aa(void, []) -> in_order_out_aa(void, []) in_order_in_aa(tree(X, Left, Right), Xs) -> U1_aa(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) U1_aa(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_aa(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_aa(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_aa(X, Left, Right, Xs, app_in_gga(Ls, .(X, Rs), Xs)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U4_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U4_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U3_aa(X, Left, Right, Xs, app_out_gga(Ls, .(X, Rs), Xs)) -> in_order_out_aa(tree(X, Left, Right), Xs) U1_ag(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_ag(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_ag(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_ag(X, Left, Right, Xs, app_in_ggg(Ls, .(X, Rs), Xs)) app_in_ggg([], X, X) -> app_out_ggg([], X, X) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U4_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) U4_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U3_ag(X, Left, Right, Xs, app_out_ggg(Ls, .(X, Rs), Xs)) -> in_order_out_ag(tree(X, Left, Right), Xs) The argument filtering Pi contains the following mapping: in_order_in_ag(x1, x2) = in_order_in_ag(x2) [] = [] in_order_out_ag(x1, x2) = in_order_out_ag(x1) U1_ag(x1, x2, x3, x4, x5) = U1_ag(x4, x5) in_order_in_aa(x1, x2) = in_order_in_aa in_order_out_aa(x1, x2) = in_order_out_aa(x1, x2) U1_aa(x1, x2, x3, x4, x5) = U1_aa(x5) U2_aa(x1, x2, x3, x4, x5, x6) = U2_aa(x2, x5, x6) U3_aa(x1, x2, x3, x4, x5) = U3_aa(x2, x3, x5) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x3) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x5) tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4, x5, x6) = U2_ag(x2, x4, x5, x6) U3_ag(x1, x2, x3, x4, x5) = U3_ag(x2, x3, x5) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) app_out_ggg(x1, x2, x3) = app_out_ggg U4_ggg(x1, x2, x3, x4, x5) = U4_ggg(x5) IN_ORDER_IN_AG(x1, x2) = IN_ORDER_IN_AG(x2) U1_AG(x1, x2, x3, x4, x5) = U1_AG(x4, x5) IN_ORDER_IN_AA(x1, x2) = IN_ORDER_IN_AA U1_AA(x1, x2, x3, x4, x5) = U1_AA(x5) U2_AA(x1, x2, x3, x4, x5, x6) = U2_AA(x2, x5, x6) U3_AA(x1, x2, x3, x4, x5) = U3_AA(x2, x3, x5) APP_IN_GGA(x1, x2, x3) = APP_IN_GGA(x1, x2) U4_GGA(x1, x2, x3, x4, x5) = U4_GGA(x5) U2_AG(x1, x2, x3, x4, x5, x6) = U2_AG(x2, x4, x5, x6) U3_AG(x1, x2, x3, x4, x5) = U3_AG(x2, x3, x5) APP_IN_GGG(x1, x2, x3) = APP_IN_GGG(x1, x2, x3) U4_GGG(x1, x2, x3, x4, x5) = U4_GGG(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 11 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_GGG(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGG(Xs, Ys, Zs) The TRS R consists of the following rules: in_order_in_ag(void, []) -> in_order_out_ag(void, []) in_order_in_ag(tree(X, Left, Right), Xs) -> U1_ag(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) in_order_in_aa(void, []) -> in_order_out_aa(void, []) in_order_in_aa(tree(X, Left, Right), Xs) -> U1_aa(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) U1_aa(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_aa(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_aa(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_aa(X, Left, Right, Xs, app_in_gga(Ls, .(X, Rs), Xs)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U4_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U4_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U3_aa(X, Left, Right, Xs, app_out_gga(Ls, .(X, Rs), Xs)) -> in_order_out_aa(tree(X, Left, Right), Xs) U1_ag(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_ag(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_ag(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_ag(X, Left, Right, Xs, app_in_ggg(Ls, .(X, Rs), Xs)) app_in_ggg([], X, X) -> app_out_ggg([], X, X) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U4_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) U4_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U3_ag(X, Left, Right, Xs, app_out_ggg(Ls, .(X, Rs), Xs)) -> in_order_out_ag(tree(X, Left, Right), Xs) The argument filtering Pi contains the following mapping: in_order_in_ag(x1, x2) = in_order_in_ag(x2) [] = [] in_order_out_ag(x1, x2) = in_order_out_ag(x1) U1_ag(x1, x2, x3, x4, x5) = U1_ag(x4, x5) in_order_in_aa(x1, x2) = in_order_in_aa in_order_out_aa(x1, x2) = in_order_out_aa(x1, x2) U1_aa(x1, x2, x3, x4, x5) = U1_aa(x5) U2_aa(x1, x2, x3, x4, x5, x6) = U2_aa(x2, x5, x6) U3_aa(x1, x2, x3, x4, x5) = U3_aa(x2, x3, x5) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x3) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x5) tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4, x5, x6) = U2_ag(x2, x4, x5, x6) U3_ag(x1, x2, x3, x4, x5) = U3_ag(x2, x3, x5) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) app_out_ggg(x1, x2, x3) = app_out_ggg U4_ggg(x1, x2, x3, x4, x5) = U4_ggg(x5) APP_IN_GGG(x1, x2, x3) = APP_IN_GGG(x1, x2, x3) 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: APP_IN_GGG(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGG(Xs, Ys, Zs) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) APP_IN_GGG(x1, x2, x3) = APP_IN_GGG(x1, x2, x3) 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: APP_IN_GGG(.(Xs), Ys, .(Zs)) -> APP_IN_GGG(Xs, Ys, Zs) 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: *APP_IN_GGG(.(Xs), Ys, .(Zs)) -> APP_IN_GGG(Xs, Ys, Zs) The graph contains the following edges 1 > 1, 2 >= 2, 3 > 3 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGA(Xs, Ys, Zs) The TRS R consists of the following rules: in_order_in_ag(void, []) -> in_order_out_ag(void, []) in_order_in_ag(tree(X, Left, Right), Xs) -> U1_ag(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) in_order_in_aa(void, []) -> in_order_out_aa(void, []) in_order_in_aa(tree(X, Left, Right), Xs) -> U1_aa(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) U1_aa(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_aa(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_aa(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_aa(X, Left, Right, Xs, app_in_gga(Ls, .(X, Rs), Xs)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U4_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U4_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U3_aa(X, Left, Right, Xs, app_out_gga(Ls, .(X, Rs), Xs)) -> in_order_out_aa(tree(X, Left, Right), Xs) U1_ag(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_ag(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_ag(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_ag(X, Left, Right, Xs, app_in_ggg(Ls, .(X, Rs), Xs)) app_in_ggg([], X, X) -> app_out_ggg([], X, X) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U4_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) U4_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U3_ag(X, Left, Right, Xs, app_out_ggg(Ls, .(X, Rs), Xs)) -> in_order_out_ag(tree(X, Left, Right), Xs) The argument filtering Pi contains the following mapping: in_order_in_ag(x1, x2) = in_order_in_ag(x2) [] = [] in_order_out_ag(x1, x2) = in_order_out_ag(x1) U1_ag(x1, x2, x3, x4, x5) = U1_ag(x4, x5) in_order_in_aa(x1, x2) = in_order_in_aa in_order_out_aa(x1, x2) = in_order_out_aa(x1, x2) U1_aa(x1, x2, x3, x4, x5) = U1_aa(x5) U2_aa(x1, x2, x3, x4, x5, x6) = U2_aa(x2, x5, x6) U3_aa(x1, x2, x3, x4, x5) = U3_aa(x2, x3, x5) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x3) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x5) tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4, x5, x6) = U2_ag(x2, x4, x5, x6) U3_ag(x1, x2, x3, x4, x5) = U3_ag(x2, x3, x5) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) app_out_ggg(x1, x2, x3) = app_out_ggg U4_ggg(x1, x2, x3, x4, x5) = U4_ggg(x5) APP_IN_GGA(x1, x2, x3) = APP_IN_GGA(x1, x2) 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: APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGA(Xs, Ys, Zs) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) APP_IN_GGA(x1, x2, x3) = APP_IN_GGA(x1, x2) 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: APP_IN_GGA(.(Xs), Ys) -> APP_IN_GGA(Xs, Ys) R is empty. Q is empty. 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: *APP_IN_GGA(.(Xs), Ys) -> APP_IN_GGA(Xs, Ys) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (20) YES ---------------------------------------- (21) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_AA(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> IN_ORDER_IN_AA(Right, Rs) IN_ORDER_IN_AA(tree(X, Left, Right), Xs) -> U1_AA(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) IN_ORDER_IN_AA(tree(X, Left, Right), Xs) -> IN_ORDER_IN_AA(Left, Ls) The TRS R consists of the following rules: in_order_in_ag(void, []) -> in_order_out_ag(void, []) in_order_in_ag(tree(X, Left, Right), Xs) -> U1_ag(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) in_order_in_aa(void, []) -> in_order_out_aa(void, []) in_order_in_aa(tree(X, Left, Right), Xs) -> U1_aa(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) U1_aa(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_aa(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_aa(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_aa(X, Left, Right, Xs, app_in_gga(Ls, .(X, Rs), Xs)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U4_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U4_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U3_aa(X, Left, Right, Xs, app_out_gga(Ls, .(X, Rs), Xs)) -> in_order_out_aa(tree(X, Left, Right), Xs) U1_ag(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_ag(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_ag(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_ag(X, Left, Right, Xs, app_in_ggg(Ls, .(X, Rs), Xs)) app_in_ggg([], X, X) -> app_out_ggg([], X, X) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U4_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) U4_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U3_ag(X, Left, Right, Xs, app_out_ggg(Ls, .(X, Rs), Xs)) -> in_order_out_ag(tree(X, Left, Right), Xs) The argument filtering Pi contains the following mapping: in_order_in_ag(x1, x2) = in_order_in_ag(x2) [] = [] in_order_out_ag(x1, x2) = in_order_out_ag(x1) U1_ag(x1, x2, x3, x4, x5) = U1_ag(x4, x5) in_order_in_aa(x1, x2) = in_order_in_aa in_order_out_aa(x1, x2) = in_order_out_aa(x1, x2) U1_aa(x1, x2, x3, x4, x5) = U1_aa(x5) U2_aa(x1, x2, x3, x4, x5, x6) = U2_aa(x2, x5, x6) U3_aa(x1, x2, x3, x4, x5) = U3_aa(x2, x3, x5) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x3) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x5) tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4, x5, x6) = U2_ag(x2, x4, x5, x6) U3_ag(x1, x2, x3, x4, x5) = U3_ag(x2, x3, x5) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) app_out_ggg(x1, x2, x3) = app_out_ggg U4_ggg(x1, x2, x3, x4, x5) = U4_ggg(x5) IN_ORDER_IN_AA(x1, x2) = IN_ORDER_IN_AA U1_AA(x1, x2, x3, x4, x5) = U1_AA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (22) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (23) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_AA(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> IN_ORDER_IN_AA(Right, Rs) IN_ORDER_IN_AA(tree(X, Left, Right), Xs) -> U1_AA(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) IN_ORDER_IN_AA(tree(X, Left, Right), Xs) -> IN_ORDER_IN_AA(Left, Ls) The TRS R consists of the following rules: in_order_in_aa(void, []) -> in_order_out_aa(void, []) in_order_in_aa(tree(X, Left, Right), Xs) -> U1_aa(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) U1_aa(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_aa(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_aa(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_aa(X, Left, Right, Xs, app_in_gga(Ls, .(X, Rs), Xs)) U3_aa(X, Left, Right, Xs, app_out_gga(Ls, .(X, Rs), Xs)) -> in_order_out_aa(tree(X, Left, Right), Xs) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U4_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U4_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) The argument filtering Pi contains the following mapping: [] = [] in_order_in_aa(x1, x2) = in_order_in_aa in_order_out_aa(x1, x2) = in_order_out_aa(x1, x2) U1_aa(x1, x2, x3, x4, x5) = U1_aa(x5) U2_aa(x1, x2, x3, x4, x5, x6) = U2_aa(x2, x5, x6) U3_aa(x1, x2, x3, x4, x5) = U3_aa(x2, x3, x5) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x3) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x5) tree(x1, x2, x3) = tree(x2, x3) IN_ORDER_IN_AA(x1, x2) = IN_ORDER_IN_AA U1_AA(x1, x2, x3, x4, x5) = U1_AA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (24) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: U1_AA(in_order_out_aa(Left, Ls)) -> IN_ORDER_IN_AA IN_ORDER_IN_AA -> U1_AA(in_order_in_aa) IN_ORDER_IN_AA -> IN_ORDER_IN_AA The TRS R consists of the following rules: in_order_in_aa -> in_order_out_aa(void, []) in_order_in_aa -> U1_aa(in_order_in_aa) U1_aa(in_order_out_aa(Left, Ls)) -> U2_aa(Left, Ls, in_order_in_aa) U2_aa(Left, Ls, in_order_out_aa(Right, Rs)) -> U3_aa(Left, Right, app_in_gga(Ls, .(Rs))) U3_aa(Left, Right, app_out_gga(Xs)) -> in_order_out_aa(tree(Left, Right), Xs) app_in_gga([], X) -> app_out_gga(X) app_in_gga(.(Xs), Ys) -> U4_gga(app_in_gga(Xs, Ys)) U4_gga(app_out_gga(Zs)) -> app_out_gga(.(Zs)) The set Q consists of the following terms: in_order_in_aa U1_aa(x0) U2_aa(x0, x1, x2) U3_aa(x0, x1, x2) app_in_gga(x0, x1) U4_gga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (26) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: in_order_in_2: (f,b) (f,f) app_in_3: (b,b,f) (b,b,b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: in_order_in_ag(void, []) -> in_order_out_ag(void, []) in_order_in_ag(tree(X, Left, Right), Xs) -> U1_ag(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) in_order_in_aa(void, []) -> in_order_out_aa(void, []) in_order_in_aa(tree(X, Left, Right), Xs) -> U1_aa(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) U1_aa(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_aa(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_aa(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_aa(X, Left, Right, Xs, app_in_gga(Ls, .(X, Rs), Xs)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U4_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U4_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U3_aa(X, Left, Right, Xs, app_out_gga(Ls, .(X, Rs), Xs)) -> in_order_out_aa(tree(X, Left, Right), Xs) U1_ag(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_ag(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_ag(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_ag(X, Left, Right, Xs, app_in_ggg(Ls, .(X, Rs), Xs)) app_in_ggg([], X, X) -> app_out_ggg([], X, X) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U4_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) U4_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U3_ag(X, Left, Right, Xs, app_out_ggg(Ls, .(X, Rs), Xs)) -> in_order_out_ag(tree(X, Left, Right), Xs) The argument filtering Pi contains the following mapping: in_order_in_ag(x1, x2) = in_order_in_ag(x2) [] = [] in_order_out_ag(x1, x2) = in_order_out_ag(x1, x2) U1_ag(x1, x2, x3, x4, x5) = U1_ag(x4, x5) in_order_in_aa(x1, x2) = in_order_in_aa in_order_out_aa(x1, x2) = in_order_out_aa(x1, x2) U1_aa(x1, x2, x3, x4, x5) = U1_aa(x5) U2_aa(x1, x2, x3, x4, x5, x6) = U2_aa(x2, x5, x6) U3_aa(x1, x2, x3, x4, x5) = U3_aa(x2, x3, x5) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x1, x2, x3) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x2, x3, x5) tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4, x5, x6) = U2_ag(x2, x4, x5, x6) U3_ag(x1, x2, x3, x4, x5) = U3_ag(x2, x3, x4, x5) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) app_out_ggg(x1, x2, x3) = app_out_ggg(x1, x2, x3) U4_ggg(x1, x2, x3, x4, x5) = U4_ggg(x2, x3, x4, x5) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (27) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: in_order_in_ag(void, []) -> in_order_out_ag(void, []) in_order_in_ag(tree(X, Left, Right), Xs) -> U1_ag(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) in_order_in_aa(void, []) -> in_order_out_aa(void, []) in_order_in_aa(tree(X, Left, Right), Xs) -> U1_aa(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) U1_aa(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_aa(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_aa(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_aa(X, Left, Right, Xs, app_in_gga(Ls, .(X, Rs), Xs)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U4_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U4_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U3_aa(X, Left, Right, Xs, app_out_gga(Ls, .(X, Rs), Xs)) -> in_order_out_aa(tree(X, Left, Right), Xs) U1_ag(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_ag(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_ag(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_ag(X, Left, Right, Xs, app_in_ggg(Ls, .(X, Rs), Xs)) app_in_ggg([], X, X) -> app_out_ggg([], X, X) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U4_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) U4_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U3_ag(X, Left, Right, Xs, app_out_ggg(Ls, .(X, Rs), Xs)) -> in_order_out_ag(tree(X, Left, Right), Xs) The argument filtering Pi contains the following mapping: in_order_in_ag(x1, x2) = in_order_in_ag(x2) [] = [] in_order_out_ag(x1, x2) = in_order_out_ag(x1, x2) U1_ag(x1, x2, x3, x4, x5) = U1_ag(x4, x5) in_order_in_aa(x1, x2) = in_order_in_aa in_order_out_aa(x1, x2) = in_order_out_aa(x1, x2) U1_aa(x1, x2, x3, x4, x5) = U1_aa(x5) U2_aa(x1, x2, x3, x4, x5, x6) = U2_aa(x2, x5, x6) U3_aa(x1, x2, x3, x4, x5) = U3_aa(x2, x3, x5) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x1, x2, x3) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x2, x3, x5) tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4, x5, x6) = U2_ag(x2, x4, x5, x6) U3_ag(x1, x2, x3, x4, x5) = U3_ag(x2, x3, x4, x5) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) app_out_ggg(x1, x2, x3) = app_out_ggg(x1, x2, x3) U4_ggg(x1, x2, x3, x4, x5) = U4_ggg(x2, x3, x4, x5) ---------------------------------------- (28) 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: IN_ORDER_IN_AG(tree(X, Left, Right), Xs) -> U1_AG(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) IN_ORDER_IN_AG(tree(X, Left, Right), Xs) -> IN_ORDER_IN_AA(Left, Ls) IN_ORDER_IN_AA(tree(X, Left, Right), Xs) -> U1_AA(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) IN_ORDER_IN_AA(tree(X, Left, Right), Xs) -> IN_ORDER_IN_AA(Left, Ls) U1_AA(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_AA(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U1_AA(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> IN_ORDER_IN_AA(Right, Rs) U2_AA(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_AA(X, Left, Right, Xs, app_in_gga(Ls, .(X, Rs), Xs)) U2_AA(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> APP_IN_GGA(Ls, .(X, Rs), Xs) APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> U4_GGA(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGA(Xs, Ys, Zs) U1_AG(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_AG(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U1_AG(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> IN_ORDER_IN_AA(Right, Rs) U2_AG(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_AG(X, Left, Right, Xs, app_in_ggg(Ls, .(X, Rs), Xs)) U2_AG(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> APP_IN_GGG(Ls, .(X, Rs), Xs) APP_IN_GGG(.(X, Xs), Ys, .(X, Zs)) -> U4_GGG(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) APP_IN_GGG(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGG(Xs, Ys, Zs) The TRS R consists of the following rules: in_order_in_ag(void, []) -> in_order_out_ag(void, []) in_order_in_ag(tree(X, Left, Right), Xs) -> U1_ag(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) in_order_in_aa(void, []) -> in_order_out_aa(void, []) in_order_in_aa(tree(X, Left, Right), Xs) -> U1_aa(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) U1_aa(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_aa(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_aa(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_aa(X, Left, Right, Xs, app_in_gga(Ls, .(X, Rs), Xs)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U4_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U4_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U3_aa(X, Left, Right, Xs, app_out_gga(Ls, .(X, Rs), Xs)) -> in_order_out_aa(tree(X, Left, Right), Xs) U1_ag(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_ag(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_ag(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_ag(X, Left, Right, Xs, app_in_ggg(Ls, .(X, Rs), Xs)) app_in_ggg([], X, X) -> app_out_ggg([], X, X) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U4_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) U4_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U3_ag(X, Left, Right, Xs, app_out_ggg(Ls, .(X, Rs), Xs)) -> in_order_out_ag(tree(X, Left, Right), Xs) The argument filtering Pi contains the following mapping: in_order_in_ag(x1, x2) = in_order_in_ag(x2) [] = [] in_order_out_ag(x1, x2) = in_order_out_ag(x1, x2) U1_ag(x1, x2, x3, x4, x5) = U1_ag(x4, x5) in_order_in_aa(x1, x2) = in_order_in_aa in_order_out_aa(x1, x2) = in_order_out_aa(x1, x2) U1_aa(x1, x2, x3, x4, x5) = U1_aa(x5) U2_aa(x1, x2, x3, x4, x5, x6) = U2_aa(x2, x5, x6) U3_aa(x1, x2, x3, x4, x5) = U3_aa(x2, x3, x5) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x1, x2, x3) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x2, x3, x5) tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4, x5, x6) = U2_ag(x2, x4, x5, x6) U3_ag(x1, x2, x3, x4, x5) = U3_ag(x2, x3, x4, x5) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) app_out_ggg(x1, x2, x3) = app_out_ggg(x1, x2, x3) U4_ggg(x1, x2, x3, x4, x5) = U4_ggg(x2, x3, x4, x5) IN_ORDER_IN_AG(x1, x2) = IN_ORDER_IN_AG(x2) U1_AG(x1, x2, x3, x4, x5) = U1_AG(x4, x5) IN_ORDER_IN_AA(x1, x2) = IN_ORDER_IN_AA U1_AA(x1, x2, x3, x4, x5) = U1_AA(x5) U2_AA(x1, x2, x3, x4, x5, x6) = U2_AA(x2, x5, x6) U3_AA(x1, x2, x3, x4, x5) = U3_AA(x2, x3, x5) APP_IN_GGA(x1, x2, x3) = APP_IN_GGA(x1, x2) U4_GGA(x1, x2, x3, x4, x5) = U4_GGA(x2, x3, x5) U2_AG(x1, x2, x3, x4, x5, x6) = U2_AG(x2, x4, x5, x6) U3_AG(x1, x2, x3, x4, x5) = U3_AG(x2, x3, x4, x5) APP_IN_GGG(x1, x2, x3) = APP_IN_GGG(x1, x2, x3) U4_GGG(x1, x2, x3, x4, x5) = U4_GGG(x2, x3, x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (29) Obligation: Pi DP problem: The TRS P consists of the following rules: IN_ORDER_IN_AG(tree(X, Left, Right), Xs) -> U1_AG(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) IN_ORDER_IN_AG(tree(X, Left, Right), Xs) -> IN_ORDER_IN_AA(Left, Ls) IN_ORDER_IN_AA(tree(X, Left, Right), Xs) -> U1_AA(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) IN_ORDER_IN_AA(tree(X, Left, Right), Xs) -> IN_ORDER_IN_AA(Left, Ls) U1_AA(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_AA(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U1_AA(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> IN_ORDER_IN_AA(Right, Rs) U2_AA(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_AA(X, Left, Right, Xs, app_in_gga(Ls, .(X, Rs), Xs)) U2_AA(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> APP_IN_GGA(Ls, .(X, Rs), Xs) APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> U4_GGA(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGA(Xs, Ys, Zs) U1_AG(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_AG(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U1_AG(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> IN_ORDER_IN_AA(Right, Rs) U2_AG(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_AG(X, Left, Right, Xs, app_in_ggg(Ls, .(X, Rs), Xs)) U2_AG(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> APP_IN_GGG(Ls, .(X, Rs), Xs) APP_IN_GGG(.(X, Xs), Ys, .(X, Zs)) -> U4_GGG(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) APP_IN_GGG(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGG(Xs, Ys, Zs) The TRS R consists of the following rules: in_order_in_ag(void, []) -> in_order_out_ag(void, []) in_order_in_ag(tree(X, Left, Right), Xs) -> U1_ag(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) in_order_in_aa(void, []) -> in_order_out_aa(void, []) in_order_in_aa(tree(X, Left, Right), Xs) -> U1_aa(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) U1_aa(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_aa(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_aa(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_aa(X, Left, Right, Xs, app_in_gga(Ls, .(X, Rs), Xs)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U4_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U4_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U3_aa(X, Left, Right, Xs, app_out_gga(Ls, .(X, Rs), Xs)) -> in_order_out_aa(tree(X, Left, Right), Xs) U1_ag(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_ag(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_ag(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_ag(X, Left, Right, Xs, app_in_ggg(Ls, .(X, Rs), Xs)) app_in_ggg([], X, X) -> app_out_ggg([], X, X) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U4_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) U4_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U3_ag(X, Left, Right, Xs, app_out_ggg(Ls, .(X, Rs), Xs)) -> in_order_out_ag(tree(X, Left, Right), Xs) The argument filtering Pi contains the following mapping: in_order_in_ag(x1, x2) = in_order_in_ag(x2) [] = [] in_order_out_ag(x1, x2) = in_order_out_ag(x1, x2) U1_ag(x1, x2, x3, x4, x5) = U1_ag(x4, x5) in_order_in_aa(x1, x2) = in_order_in_aa in_order_out_aa(x1, x2) = in_order_out_aa(x1, x2) U1_aa(x1, x2, x3, x4, x5) = U1_aa(x5) U2_aa(x1, x2, x3, x4, x5, x6) = U2_aa(x2, x5, x6) U3_aa(x1, x2, x3, x4, x5) = U3_aa(x2, x3, x5) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x1, x2, x3) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x2, x3, x5) tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4, x5, x6) = U2_ag(x2, x4, x5, x6) U3_ag(x1, x2, x3, x4, x5) = U3_ag(x2, x3, x4, x5) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) app_out_ggg(x1, x2, x3) = app_out_ggg(x1, x2, x3) U4_ggg(x1, x2, x3, x4, x5) = U4_ggg(x2, x3, x4, x5) IN_ORDER_IN_AG(x1, x2) = IN_ORDER_IN_AG(x2) U1_AG(x1, x2, x3, x4, x5) = U1_AG(x4, x5) IN_ORDER_IN_AA(x1, x2) = IN_ORDER_IN_AA U1_AA(x1, x2, x3, x4, x5) = U1_AA(x5) U2_AA(x1, x2, x3, x4, x5, x6) = U2_AA(x2, x5, x6) U3_AA(x1, x2, x3, x4, x5) = U3_AA(x2, x3, x5) APP_IN_GGA(x1, x2, x3) = APP_IN_GGA(x1, x2) U4_GGA(x1, x2, x3, x4, x5) = U4_GGA(x2, x3, x5) U2_AG(x1, x2, x3, x4, x5, x6) = U2_AG(x2, x4, x5, x6) U3_AG(x1, x2, x3, x4, x5) = U3_AG(x2, x3, x4, x5) APP_IN_GGG(x1, x2, x3) = APP_IN_GGG(x1, x2, x3) U4_GGG(x1, x2, x3, x4, x5) = U4_GGG(x2, x3, x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (30) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 11 less nodes. ---------------------------------------- (31) Complex Obligation (AND) ---------------------------------------- (32) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_GGG(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGG(Xs, Ys, Zs) The TRS R consists of the following rules: in_order_in_ag(void, []) -> in_order_out_ag(void, []) in_order_in_ag(tree(X, Left, Right), Xs) -> U1_ag(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) in_order_in_aa(void, []) -> in_order_out_aa(void, []) in_order_in_aa(tree(X, Left, Right), Xs) -> U1_aa(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) U1_aa(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_aa(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_aa(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_aa(X, Left, Right, Xs, app_in_gga(Ls, .(X, Rs), Xs)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U4_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U4_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U3_aa(X, Left, Right, Xs, app_out_gga(Ls, .(X, Rs), Xs)) -> in_order_out_aa(tree(X, Left, Right), Xs) U1_ag(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_ag(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_ag(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_ag(X, Left, Right, Xs, app_in_ggg(Ls, .(X, Rs), Xs)) app_in_ggg([], X, X) -> app_out_ggg([], X, X) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U4_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) U4_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U3_ag(X, Left, Right, Xs, app_out_ggg(Ls, .(X, Rs), Xs)) -> in_order_out_ag(tree(X, Left, Right), Xs) The argument filtering Pi contains the following mapping: in_order_in_ag(x1, x2) = in_order_in_ag(x2) [] = [] in_order_out_ag(x1, x2) = in_order_out_ag(x1, x2) U1_ag(x1, x2, x3, x4, x5) = U1_ag(x4, x5) in_order_in_aa(x1, x2) = in_order_in_aa in_order_out_aa(x1, x2) = in_order_out_aa(x1, x2) U1_aa(x1, x2, x3, x4, x5) = U1_aa(x5) U2_aa(x1, x2, x3, x4, x5, x6) = U2_aa(x2, x5, x6) U3_aa(x1, x2, x3, x4, x5) = U3_aa(x2, x3, x5) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x1, x2, x3) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x2, x3, x5) tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4, x5, x6) = U2_ag(x2, x4, x5, x6) U3_ag(x1, x2, x3, x4, x5) = U3_ag(x2, x3, x4, x5) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) app_out_ggg(x1, x2, x3) = app_out_ggg(x1, x2, x3) U4_ggg(x1, x2, x3, x4, x5) = U4_ggg(x2, x3, x4, x5) APP_IN_GGG(x1, x2, x3) = APP_IN_GGG(x1, x2, x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (33) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (34) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_GGG(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGG(Xs, Ys, Zs) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) APP_IN_GGG(x1, x2, x3) = APP_IN_GGG(x1, x2, x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (35) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: APP_IN_GGG(.(Xs), Ys, .(Zs)) -> APP_IN_GGG(Xs, Ys, Zs) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (37) 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: *APP_IN_GGG(.(Xs), Ys, .(Zs)) -> APP_IN_GGG(Xs, Ys, Zs) The graph contains the following edges 1 > 1, 2 >= 2, 3 > 3 ---------------------------------------- (38) YES ---------------------------------------- (39) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGA(Xs, Ys, Zs) The TRS R consists of the following rules: in_order_in_ag(void, []) -> in_order_out_ag(void, []) in_order_in_ag(tree(X, Left, Right), Xs) -> U1_ag(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) in_order_in_aa(void, []) -> in_order_out_aa(void, []) in_order_in_aa(tree(X, Left, Right), Xs) -> U1_aa(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) U1_aa(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_aa(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_aa(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_aa(X, Left, Right, Xs, app_in_gga(Ls, .(X, Rs), Xs)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U4_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U4_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U3_aa(X, Left, Right, Xs, app_out_gga(Ls, .(X, Rs), Xs)) -> in_order_out_aa(tree(X, Left, Right), Xs) U1_ag(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_ag(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_ag(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_ag(X, Left, Right, Xs, app_in_ggg(Ls, .(X, Rs), Xs)) app_in_ggg([], X, X) -> app_out_ggg([], X, X) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U4_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) U4_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U3_ag(X, Left, Right, Xs, app_out_ggg(Ls, .(X, Rs), Xs)) -> in_order_out_ag(tree(X, Left, Right), Xs) The argument filtering Pi contains the following mapping: in_order_in_ag(x1, x2) = in_order_in_ag(x2) [] = [] in_order_out_ag(x1, x2) = in_order_out_ag(x1, x2) U1_ag(x1, x2, x3, x4, x5) = U1_ag(x4, x5) in_order_in_aa(x1, x2) = in_order_in_aa in_order_out_aa(x1, x2) = in_order_out_aa(x1, x2) U1_aa(x1, x2, x3, x4, x5) = U1_aa(x5) U2_aa(x1, x2, x3, x4, x5, x6) = U2_aa(x2, x5, x6) U3_aa(x1, x2, x3, x4, x5) = U3_aa(x2, x3, x5) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x1, x2, x3) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x2, x3, x5) tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4, x5, x6) = U2_ag(x2, x4, x5, x6) U3_ag(x1, x2, x3, x4, x5) = U3_ag(x2, x3, x4, x5) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) app_out_ggg(x1, x2, x3) = app_out_ggg(x1, x2, x3) U4_ggg(x1, x2, x3, x4, x5) = U4_ggg(x2, x3, x4, x5) APP_IN_GGA(x1, x2, x3) = APP_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (40) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (41) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGA(Xs, Ys, Zs) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) APP_IN_GGA(x1, x2, x3) = APP_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (42) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (43) Obligation: Q DP problem: The TRS P consists of the following rules: APP_IN_GGA(.(Xs), Ys) -> APP_IN_GGA(Xs, Ys) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (44) 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: *APP_IN_GGA(.(Xs), Ys) -> APP_IN_GGA(Xs, Ys) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (45) YES ---------------------------------------- (46) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_AA(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> IN_ORDER_IN_AA(Right, Rs) IN_ORDER_IN_AA(tree(X, Left, Right), Xs) -> U1_AA(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) IN_ORDER_IN_AA(tree(X, Left, Right), Xs) -> IN_ORDER_IN_AA(Left, Ls) The TRS R consists of the following rules: in_order_in_ag(void, []) -> in_order_out_ag(void, []) in_order_in_ag(tree(X, Left, Right), Xs) -> U1_ag(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) in_order_in_aa(void, []) -> in_order_out_aa(void, []) in_order_in_aa(tree(X, Left, Right), Xs) -> U1_aa(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) U1_aa(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_aa(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_aa(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_aa(X, Left, Right, Xs, app_in_gga(Ls, .(X, Rs), Xs)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U4_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U4_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U3_aa(X, Left, Right, Xs, app_out_gga(Ls, .(X, Rs), Xs)) -> in_order_out_aa(tree(X, Left, Right), Xs) U1_ag(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_ag(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_ag(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_ag(X, Left, Right, Xs, app_in_ggg(Ls, .(X, Rs), Xs)) app_in_ggg([], X, X) -> app_out_ggg([], X, X) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U4_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) U4_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U3_ag(X, Left, Right, Xs, app_out_ggg(Ls, .(X, Rs), Xs)) -> in_order_out_ag(tree(X, Left, Right), Xs) The argument filtering Pi contains the following mapping: in_order_in_ag(x1, x2) = in_order_in_ag(x2) [] = [] in_order_out_ag(x1, x2) = in_order_out_ag(x1, x2) U1_ag(x1, x2, x3, x4, x5) = U1_ag(x4, x5) in_order_in_aa(x1, x2) = in_order_in_aa in_order_out_aa(x1, x2) = in_order_out_aa(x1, x2) U1_aa(x1, x2, x3, x4, x5) = U1_aa(x5) U2_aa(x1, x2, x3, x4, x5, x6) = U2_aa(x2, x5, x6) U3_aa(x1, x2, x3, x4, x5) = U3_aa(x2, x3, x5) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x1, x2, x3) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x2, x3, x5) tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4, x5, x6) = U2_ag(x2, x4, x5, x6) U3_ag(x1, x2, x3, x4, x5) = U3_ag(x2, x3, x4, x5) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) app_out_ggg(x1, x2, x3) = app_out_ggg(x1, x2, x3) U4_ggg(x1, x2, x3, x4, x5) = U4_ggg(x2, x3, x4, x5) IN_ORDER_IN_AA(x1, x2) = IN_ORDER_IN_AA U1_AA(x1, x2, x3, x4, x5) = U1_AA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (47) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (48) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_AA(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> IN_ORDER_IN_AA(Right, Rs) IN_ORDER_IN_AA(tree(X, Left, Right), Xs) -> U1_AA(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) IN_ORDER_IN_AA(tree(X, Left, Right), Xs) -> IN_ORDER_IN_AA(Left, Ls) The TRS R consists of the following rules: in_order_in_aa(void, []) -> in_order_out_aa(void, []) in_order_in_aa(tree(X, Left, Right), Xs) -> U1_aa(X, Left, Right, Xs, in_order_in_aa(Left, Ls)) U1_aa(X, Left, Right, Xs, in_order_out_aa(Left, Ls)) -> U2_aa(X, Left, Right, Xs, Ls, in_order_in_aa(Right, Rs)) U2_aa(X, Left, Right, Xs, Ls, in_order_out_aa(Right, Rs)) -> U3_aa(X, Left, Right, Xs, app_in_gga(Ls, .(X, Rs), Xs)) U3_aa(X, Left, Right, Xs, app_out_gga(Ls, .(X, Rs), Xs)) -> in_order_out_aa(tree(X, Left, Right), Xs) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U4_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U4_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) The argument filtering Pi contains the following mapping: [] = [] in_order_in_aa(x1, x2) = in_order_in_aa in_order_out_aa(x1, x2) = in_order_out_aa(x1, x2) U1_aa(x1, x2, x3, x4, x5) = U1_aa(x5) U2_aa(x1, x2, x3, x4, x5, x6) = U2_aa(x2, x5, x6) U3_aa(x1, x2, x3, x4, x5) = U3_aa(x2, x3, x5) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x1, x2, x3) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x2, x3, x5) tree(x1, x2, x3) = tree(x2, x3) IN_ORDER_IN_AA(x1, x2) = IN_ORDER_IN_AA U1_AA(x1, x2, x3, x4, x5) = U1_AA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (49) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (50) Obligation: Q DP problem: The TRS P consists of the following rules: U1_AA(in_order_out_aa(Left, Ls)) -> IN_ORDER_IN_AA IN_ORDER_IN_AA -> U1_AA(in_order_in_aa) IN_ORDER_IN_AA -> IN_ORDER_IN_AA The TRS R consists of the following rules: in_order_in_aa -> in_order_out_aa(void, []) in_order_in_aa -> U1_aa(in_order_in_aa) U1_aa(in_order_out_aa(Left, Ls)) -> U2_aa(Left, Ls, in_order_in_aa) U2_aa(Left, Ls, in_order_out_aa(Right, Rs)) -> U3_aa(Left, Right, app_in_gga(Ls, .(Rs))) U3_aa(Left, Right, app_out_gga(Ls, .(Rs), Xs)) -> in_order_out_aa(tree(Left, Right), Xs) app_in_gga([], X) -> app_out_gga([], X, X) app_in_gga(.(Xs), Ys) -> U4_gga(Xs, Ys, app_in_gga(Xs, Ys)) U4_gga(Xs, Ys, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(Xs), Ys, .(Zs)) The set Q consists of the following terms: in_order_in_aa U1_aa(x0) U2_aa(x0, x1, x2) U3_aa(x0, x1, x2) app_in_gga(x0, x1) U4_gga(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (51) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 1, "program": { "directives": [], "clauses": [ [ "(in_order (void) ([]))", null ], [ "(in_order (tree X Left Right) Xs)", "(',' (in_order Left Ls) (',' (in_order Right Rs) (app Ls (. X Rs) Xs)))" ], [ "(app ([]) X X)", null ], [ "(app (. X Xs) Ys (. X Zs))", "(app Xs Ys Zs)" ] ] }, "graph": { "nodes": { "23": { "goal": [ { "clause": 0, "scope": 1, "term": "(in_order T1 T2)" }, { "clause": 1, "scope": 1, "term": "(in_order T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "48": { "goal": [{ "clause": 0, "scope": 1, "term": "(in_order T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "type": "Nodes", "370": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T104 (. T105 T106) T103)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T103"], "free": [], "exprvars": [] } }, "250": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (in_order T19 X16) (app T18 (. T20 X16) T14))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": ["X16"], "exprvars": [] } }, "371": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "350": { "goal": [{ "clause": 2, "scope": 4, "term": "(app T73 (. T74 T72) T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": [], "exprvars": [] } }, "351": { "goal": [{ "clause": 3, "scope": 4, "term": "(app T73 (. T74 T72) T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": [], "exprvars": [] } }, "231": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "352": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "255": { "goal": [ { "clause": 0, "scope": 2, "term": "(in_order T15 X15)" }, { "clause": 1, "scope": 2, "term": "(in_order T15 X15)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X15"], "exprvars": [] } }, "277": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (in_order T30 X33) (',' (in_order T31 X34) (app X33 (. T32 X34) X35)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X35", "X33", "X34" ], "exprvars": [] } }, "354": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "234": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "278": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "355": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "313": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T34 X34)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X34"], "exprvars": [] } }, "237": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "259": { "goal": [{ "clause": 0, "scope": 2, "term": "(in_order T15 X15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X15"], "exprvars": [] } }, "314": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T37 (. T38 T36) X35)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X35"], "exprvars": [] } }, "315": { "goal": [ { "clause": 2, "scope": 3, "term": "(app T37 (. T38 T36) X35)" }, { "clause": 3, "scope": 3, "term": "(app T37 (. T38 T36) X35)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X35"], "exprvars": [] } }, "337": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T65 (. T66 T67) X57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X57"], "exprvars": [] } }, "316": { "goal": [{ "clause": 2, "scope": 3, "term": "(app T37 (. T38 T36) X35)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X35"], "exprvars": [] } }, "338": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "317": { "goal": [{ "clause": 3, "scope": 3, "term": "(app T37 (. T38 T36) X35)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X35"], "exprvars": [] } }, "318": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "319": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "51": { "goal": [{ "clause": 1, "scope": 1, "term": "(in_order T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "281": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T30 X33)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X33"], "exprvars": [] } }, "260": { "goal": [{ "clause": 1, "scope": 2, "term": "(in_order T15 X15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X15"], "exprvars": [] } }, "282": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (in_order T34 X34) (app T33 (. T35 X34) X35))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X35", "X34" ], "exprvars": [] } }, "262": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "241": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (in_order T15 X15) (',' (in_order T16 X16) (app X15 (. T17 X16) T14)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": [ "X15", "X16" ], "exprvars": [] } }, "263": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "264": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "243": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "320": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "345": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T19 X16)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X16"], "exprvars": [] } }, "346": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T73 (. T74 T72) T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": [], "exprvars": [] } }, "249": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T15 X15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X15"], "exprvars": [] } }, "349": { "goal": [ { "clause": 2, "scope": 4, "term": "(app T73 (. T74 T72) T14)" }, { "clause": 3, "scope": 4, "term": "(app T73 (. T74 T72) T14)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 23, "label": "CASE" }, { "from": 23, "to": 48, "label": "PARALLEL" }, { "from": 23, "to": 51, "label": "PARALLEL" }, { "from": 48, "to": 231, "label": "EVAL with clause\nin_order(void, []).\nand substitutionT1 -> void,\nT2 -> []" }, { "from": 48, "to": 234, "label": "EVAL-BACKTRACK" }, { "from": 51, "to": 241, "label": "EVAL with clause\nin_order(tree(X11, X12, X13), X14) :- ','(in_order(X12, X15), ','(in_order(X13, X16), app(X15, .(X11, X16), X14))).\nand substitutionX11 -> T17,\nX12 -> T15,\nX13 -> T16,\nT1 -> tree(T17, T15, T16),\nT2 -> T14,\nX14 -> T14,\nT12 -> T15,\nT13 -> T16,\nT11 -> T17" }, { "from": 51, "to": 243, "label": "EVAL-BACKTRACK" }, { "from": 231, "to": 237, "label": "SUCCESS" }, { "from": 241, "to": 249, "label": "SPLIT 1" }, { "from": 241, "to": 250, "label": "SPLIT 2\nreplacements:X15 -> T18,\nT16 -> T19,\nT17 -> T20" }, { "from": 249, "to": 255, "label": "CASE" }, { "from": 250, "to": 345, "label": "SPLIT 1" }, { "from": 250, "to": 346, "label": "SPLIT 2\nreplacements:X16 -> T72,\nT18 -> T73,\nT20 -> T74" }, { "from": 255, "to": 259, "label": "PARALLEL" }, { "from": 255, "to": 260, "label": "PARALLEL" }, { "from": 259, "to": 262, "label": "EVAL with clause\nin_order(void, []).\nand substitutionT15 -> void,\nX15 -> []" }, { "from": 259, "to": 263, "label": "EVAL-BACKTRACK" }, { "from": 260, "to": 277, "label": "EVAL with clause\nin_order(tree(X29, X30, X31), X32) :- ','(in_order(X30, X33), ','(in_order(X31, X34), app(X33, .(X29, X34), X32))).\nand substitutionX29 -> T32,\nX30 -> T30,\nX31 -> T31,\nT15 -> tree(T32, T30, T31),\nX15 -> X35,\nX32 -> X35,\nT28 -> T30,\nT29 -> T31,\nT27 -> T32" }, { "from": 260, "to": 278, "label": "EVAL-BACKTRACK" }, { "from": 262, "to": 264, "label": "SUCCESS" }, { "from": 277, "to": 281, "label": "SPLIT 1" }, { "from": 277, "to": 282, "label": "SPLIT 2\nreplacements:X33 -> T33,\nT31 -> T34,\nT32 -> T35" }, { "from": 281, "to": 249, "label": "INSTANCE with matching:\nT15 -> T30\nX15 -> X33" }, { "from": 282, "to": 313, "label": "SPLIT 1" }, { "from": 282, "to": 314, "label": "SPLIT 2\nreplacements:X34 -> T36,\nT33 -> T37,\nT35 -> T38" }, { "from": 313, "to": 249, "label": "INSTANCE with matching:\nT15 -> T34\nX15 -> X34" }, { "from": 314, "to": 315, "label": "CASE" }, { "from": 315, "to": 316, "label": "PARALLEL" }, { "from": 315, "to": 317, "label": "PARALLEL" }, { "from": 316, "to": 318, "label": "EVAL with clause\napp([], X42, X42).\nand substitutionT37 -> [],\nT38 -> T51,\nT36 -> T52,\nX42 -> .(T51, T52),\nX35 -> .(T51, T52)" }, { "from": 316, "to": 319, "label": "EVAL-BACKTRACK" }, { "from": 317, "to": 337, "label": "EVAL with clause\napp(.(X53, X54), X55, .(X53, X56)) :- app(X54, X55, X56).\nand substitutionX53 -> T61,\nX54 -> T65,\nT37 -> .(T61, T65),\nT38 -> T66,\nT36 -> T67,\nX55 -> .(T66, T67),\nX56 -> X57,\nX35 -> .(T61, X57),\nT62 -> T65,\nT63 -> T66,\nT64 -> T67" }, { "from": 317, "to": 338, "label": "EVAL-BACKTRACK" }, { "from": 318, "to": 320, "label": "SUCCESS" }, { "from": 337, "to": 314, "label": "INSTANCE with matching:\nT37 -> T65\nT38 -> T66\nT36 -> T67\nX35 -> X57" }, { "from": 345, "to": 249, "label": "INSTANCE with matching:\nT15 -> T19\nX15 -> X16" }, { "from": 346, "to": 349, "label": "CASE" }, { "from": 349, "to": 350, "label": "PARALLEL" }, { "from": 349, "to": 351, "label": "PARALLEL" }, { "from": 350, "to": 352, "label": "EVAL with clause\napp([], X66, X66).\nand substitutionT73 -> [],\nT74 -> T87,\nT72 -> T88,\nX66 -> .(T87, T88),\nT14 -> .(T87, T88)" }, { "from": 350, "to": 354, "label": "EVAL-BACKTRACK" }, { "from": 351, "to": 370, "label": "EVAL with clause\napp(.(X75, X76), X77, .(X75, X78)) :- app(X76, X77, X78).\nand substitutionX75 -> T99,\nX76 -> T104,\nT73 -> .(T99, T104),\nT74 -> T105,\nT72 -> T106,\nX77 -> .(T105, T106),\nX78 -> T103,\nT14 -> .(T99, T103),\nT100 -> T104,\nT101 -> T105,\nT102 -> T106" }, { "from": 351, "to": 371, "label": "EVAL-BACKTRACK" }, { "from": 352, "to": 355, "label": "SUCCESS" }, { "from": 370, "to": 346, "label": "INSTANCE with matching:\nT73 -> T104\nT74 -> T105\nT72 -> T106\nT14 -> T103" } ], "type": "Graph" } } ---------------------------------------- (52) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f1_in([]) -> f1_out1 f1_in(T14) -> U1(f241_in(T14), T14) U1(f241_out1(X15, T17, X16), T14) -> f1_out1 f249_in -> f249_out1 f249_in -> U2(f277_in) U2(f277_out1) -> f249_out1 f314_in -> f314_out1 f314_in -> U3(f314_in) U3(f314_out1) -> f314_out1 f346_in(.(T87, T88)) -> f346_out1([], T87, T88) f346_in(.(T99, T103)) -> U4(f346_in(T103), .(T99, T103)) U4(f346_out1(T104, T105, T106), .(T99, T103)) -> f346_out1(.(T99, T104), T105, T106) f241_in(T14) -> U5(f249_in, T14) U5(f249_out1, T14) -> U6(f250_in(T14), T14) U6(f250_out1(T18, T20, X16), T14) -> f241_out1(T18, T20, X16) f250_in(T14) -> U7(f249_in, T14) U7(f249_out1, T14) -> U8(f346_in(T14), T14) U8(f346_out1(T73, T74, T72), T14) -> f250_out1(T73, T74, T72) f277_in -> U9(f249_in) U9(f249_out1) -> U10(f282_in) U10(f282_out1) -> f277_out1 f282_in -> U11(f249_in) U11(f249_out1) -> U12(f314_in) U12(f314_out1) -> f282_out1 Q is empty. ---------------------------------------- (53) QTRSRRRProof (EQUIVALENT) Used ordering: f1_in/1(YES) []/0) f1_out1/0) U1/2(YES,YES) f241_in/1(YES) f241_out1/3(YES,YES,YES) f249_in/0) f249_out1/0) U2/1)YES( f277_in/0) f277_out1/0) f314_in/0) f314_out1/0) U3/1)YES( f346_in/1(YES) ./2(YES,YES) f346_out1/3(YES,YES,YES) U4/2(YES,YES) U5/2(YES,YES) U6/2(YES,YES) f250_in/1(YES) f250_out1/3(YES,YES,YES) U7/2(YES,YES) U8/2(YES,YES) U9/1)YES( U10/1)YES( f282_in/0) f282_out1/0) U11/1)YES( U12/1)YES( Quasi precedence: f1_in_1 > U1_2 > [f1_out1, f241_out1_3] f1_in_1 > f241_in_1 > U5_2 > U6_2 > [f1_out1, f241_out1_3] f1_in_1 > f241_in_1 > U5_2 > f250_in_1 > [f249_in, f249_out1, f277_in, f277_out1, f314_in, f314_out1, f282_in, f282_out1] f1_in_1 > f241_in_1 > U5_2 > f250_in_1 > [f346_in_1, U7_2] > [] > [f1_out1, f241_out1_3] f1_in_1 > f241_in_1 > U5_2 > f250_in_1 > [f346_in_1, U7_2] > U4_2 > ._2 > f346_out1_3 > f250_out1_3 > [f1_out1, f241_out1_3] f1_in_1 > f241_in_1 > U5_2 > f250_in_1 > [f346_in_1, U7_2] > U8_2 > f250_out1_3 > [f1_out1, f241_out1_3] Status: f1_in_1: multiset status []: multiset status f1_out1: multiset status U1_2: multiset status f241_in_1: multiset status f241_out1_3: multiset status f249_in: multiset status f249_out1: multiset status f277_in: multiset status f277_out1: multiset status f314_in: multiset status f314_out1: multiset status f346_in_1: multiset status ._2: multiset status f346_out1_3: multiset status U4_2: multiset status U5_2: multiset status U6_2: multiset status f250_in_1: multiset status f250_out1_3: multiset status U7_2: multiset status U8_2: multiset status f282_in: multiset status f282_out1: multiset status With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: f1_in([]) -> f1_out1 f1_in(T14) -> U1(f241_in(T14), T14) U1(f241_out1(X15, T17, X16), T14) -> f1_out1 f346_in(.(T87, T88)) -> f346_out1([], T87, T88) f346_in(.(T99, T103)) -> U4(f346_in(T103), .(T99, T103)) U4(f346_out1(T104, T105, T106), .(T99, T103)) -> f346_out1(.(T99, T104), T105, T106) f241_in(T14) -> U5(f249_in, T14) U5(f249_out1, T14) -> U6(f250_in(T14), T14) U6(f250_out1(T18, T20, X16), T14) -> f241_out1(T18, T20, X16) f250_in(T14) -> U7(f249_in, T14) U7(f249_out1, T14) -> U8(f346_in(T14), T14) U8(f346_out1(T73, T74, T72), T14) -> f250_out1(T73, T74, T72) ---------------------------------------- (54) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f249_in -> f249_out1 f249_in -> U2(f277_in) U2(f277_out1) -> f249_out1 f314_in -> f314_out1 f314_in -> U3(f314_in) U3(f314_out1) -> f314_out1 f277_in -> U9(f249_in) U9(f249_out1) -> U10(f282_in) U10(f282_out1) -> f277_out1 f282_in -> U11(f249_in) U11(f249_out1) -> U12(f314_in) U12(f314_out1) -> f282_out1 Q is empty. ---------------------------------------- (55) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 7, "program": { "directives": [], "clauses": [ [ "(in_order (void) ([]))", null ], [ "(in_order (tree X Left Right) Xs)", "(',' (in_order Left Ls) (',' (in_order Right Rs) (app Ls (. X Rs) Xs)))" ], [ "(app ([]) X X)", null ], [ "(app (. X Xs) Ys (. X Zs))", "(app Xs Ys Zs)" ] ] }, "graph": { "nodes": { "22": { "goal": [ { "clause": 0, "scope": 1, "term": "(in_order T1 T2)" }, { "clause": 1, "scope": 1, "term": "(in_order T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "290": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "291": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "292": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "293": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T65 (. T66 T67) X57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X57"], "exprvars": [] } }, "294": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "251": { "goal": [ { "clause": 0, "scope": 2, "term": "(in_order T15 X15)" }, { "clause": 1, "scope": 2, "term": "(in_order T15 X15)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X15"], "exprvars": [] } }, "230": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "252": { "goal": [{ "clause": 0, "scope": 2, "term": "(in_order T15 X15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X15"], "exprvars": [] } }, "253": { "goal": [{ "clause": 1, "scope": 2, "term": "(in_order T15 X15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X15"], "exprvars": [] } }, "233": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "256": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "279": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T30 X33)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X33"], "exprvars": [] } }, "236": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "258": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "280": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (in_order T34 X34) (app T33 (. T35 X34) X35))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X35", "X34" ], "exprvars": [] } }, "261": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "360": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T19 X16)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X16"], "exprvars": [] } }, "361": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T73 (. T74 T72) T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": [], "exprvars": [] } }, "285": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T34 X34)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X34"], "exprvars": [] } }, "362": { "goal": [ { "clause": 2, "scope": 4, "term": "(app T73 (. T74 T72) T14)" }, { "clause": 3, "scope": 4, "term": "(app T73 (. T74 T72) T14)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": [], "exprvars": [] } }, "242": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (in_order T15 X15) (',' (in_order T16 X16) (app X15 (. T17 X16) T14)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": [ "X15", "X16" ], "exprvars": [] } }, "286": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T37 (. T38 T36) X35)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X35"], "exprvars": [] } }, "363": { "goal": [{ "clause": 2, "scope": 4, "term": "(app T73 (. T74 T72) T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": [], "exprvars": [] } }, "287": { "goal": [ { "clause": 2, "scope": 3, "term": "(app T37 (. T38 T36) X35)" }, { "clause": 3, "scope": 3, "term": "(app T37 (. T38 T36) X35)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X35"], "exprvars": [] } }, "364": { "goal": [{ "clause": 3, "scope": 4, "term": "(app T73 (. T74 T72) T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": [], "exprvars": [] } }, "244": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "288": { "goal": [{ "clause": 2, "scope": 3, "term": "(app T37 (. T38 T36) X35)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X35"], "exprvars": [] } }, "365": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "267": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (in_order T30 X33) (',' (in_order T31 X34) (app X33 (. T32 X34) X35)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X35", "X33", "X34" ], "exprvars": [] } }, "289": { "goal": [{ "clause": 3, "scope": 3, "term": "(app T37 (. T38 T36) X35)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X35"], "exprvars": [] } }, "366": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "367": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "247": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T15 X15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X15"], "exprvars": [] } }, "269": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "368": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T104 (. T105 T106) T103)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T103"], "free": [], "exprvars": [] } }, "248": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (in_order T19 X16) (app T18 (. T20 X16) T14))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": ["X16"], "exprvars": [] } }, "369": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "7": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "60": { "goal": [{ "clause": 0, "scope": 1, "term": "(in_order T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "62": { "goal": [{ "clause": 1, "scope": 1, "term": "(in_order T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 7, "to": 22, "label": "CASE" }, { "from": 22, "to": 60, "label": "PARALLEL" }, { "from": 22, "to": 62, "label": "PARALLEL" }, { "from": 60, "to": 230, "label": "EVAL with clause\nin_order(void, []).\nand substitutionT1 -> void,\nT2 -> []" }, { "from": 60, "to": 233, "label": "EVAL-BACKTRACK" }, { "from": 62, "to": 242, "label": "EVAL with clause\nin_order(tree(X11, X12, X13), X14) :- ','(in_order(X12, X15), ','(in_order(X13, X16), app(X15, .(X11, X16), X14))).\nand substitutionX11 -> T17,\nX12 -> T15,\nX13 -> T16,\nT1 -> tree(T17, T15, T16),\nT2 -> T14,\nX14 -> T14,\nT12 -> T15,\nT13 -> T16,\nT11 -> T17" }, { "from": 62, "to": 244, "label": "EVAL-BACKTRACK" }, { "from": 230, "to": 236, "label": "SUCCESS" }, { "from": 242, "to": 247, "label": "SPLIT 1" }, { "from": 242, "to": 248, "label": "SPLIT 2\nreplacements:X15 -> T18,\nT16 -> T19,\nT17 -> T20" }, { "from": 247, "to": 251, "label": "CASE" }, { "from": 248, "to": 360, "label": "SPLIT 1" }, { "from": 248, "to": 361, "label": "SPLIT 2\nreplacements:X16 -> T72,\nT18 -> T73,\nT20 -> T74" }, { "from": 251, "to": 252, "label": "PARALLEL" }, { "from": 251, "to": 253, "label": "PARALLEL" }, { "from": 252, "to": 256, "label": "EVAL with clause\nin_order(void, []).\nand substitutionT15 -> void,\nX15 -> []" }, { "from": 252, "to": 258, "label": "EVAL-BACKTRACK" }, { "from": 253, "to": 267, "label": "EVAL with clause\nin_order(tree(X29, X30, X31), X32) :- ','(in_order(X30, X33), ','(in_order(X31, X34), app(X33, .(X29, X34), X32))).\nand substitutionX29 -> T32,\nX30 -> T30,\nX31 -> T31,\nT15 -> tree(T32, T30, T31),\nX15 -> X35,\nX32 -> X35,\nT28 -> T30,\nT29 -> T31,\nT27 -> T32" }, { "from": 253, "to": 269, "label": "EVAL-BACKTRACK" }, { "from": 256, "to": 261, "label": "SUCCESS" }, { "from": 267, "to": 279, "label": "SPLIT 1" }, { "from": 267, "to": 280, "label": "SPLIT 2\nreplacements:X33 -> T33,\nT31 -> T34,\nT32 -> T35" }, { "from": 279, "to": 247, "label": "INSTANCE with matching:\nT15 -> T30\nX15 -> X33" }, { "from": 280, "to": 285, "label": "SPLIT 1" }, { "from": 280, "to": 286, "label": "SPLIT 2\nreplacements:X34 -> T36,\nT33 -> T37,\nT35 -> T38" }, { "from": 285, "to": 247, "label": "INSTANCE with matching:\nT15 -> T34\nX15 -> X34" }, { "from": 286, "to": 287, "label": "CASE" }, { "from": 287, "to": 288, "label": "PARALLEL" }, { "from": 287, "to": 289, "label": "PARALLEL" }, { "from": 288, "to": 290, "label": "EVAL with clause\napp([], X42, X42).\nand substitutionT37 -> [],\nT38 -> T51,\nT36 -> T52,\nX42 -> .(T51, T52),\nX35 -> .(T51, T52)" }, { "from": 288, "to": 291, "label": "EVAL-BACKTRACK" }, { "from": 289, "to": 293, "label": "EVAL with clause\napp(.(X53, X54), X55, .(X53, X56)) :- app(X54, X55, X56).\nand substitutionX53 -> T61,\nX54 -> T65,\nT37 -> .(T61, T65),\nT38 -> T66,\nT36 -> T67,\nX55 -> .(T66, T67),\nX56 -> X57,\nX35 -> .(T61, X57),\nT62 -> T65,\nT63 -> T66,\nT64 -> T67" }, { "from": 289, "to": 294, "label": "EVAL-BACKTRACK" }, { "from": 290, "to": 292, "label": "SUCCESS" }, { "from": 293, "to": 286, "label": "INSTANCE with matching:\nT37 -> T65\nT38 -> T66\nT36 -> T67\nX35 -> X57" }, { "from": 360, "to": 247, "label": "INSTANCE with matching:\nT15 -> T19\nX15 -> X16" }, { "from": 361, "to": 362, "label": "CASE" }, { "from": 362, "to": 363, "label": "PARALLEL" }, { "from": 362, "to": 364, "label": "PARALLEL" }, { "from": 363, "to": 365, "label": "EVAL with clause\napp([], X66, X66).\nand substitutionT73 -> [],\nT74 -> T87,\nT72 -> T88,\nX66 -> .(T87, T88),\nT14 -> .(T87, T88)" }, { "from": 363, "to": 366, "label": "EVAL-BACKTRACK" }, { "from": 364, "to": 368, "label": "EVAL with clause\napp(.(X75, X76), X77, .(X75, X78)) :- app(X76, X77, X78).\nand substitutionX75 -> T99,\nX76 -> T104,\nT73 -> .(T99, T104),\nT74 -> T105,\nT72 -> T106,\nX77 -> .(T105, T106),\nX78 -> T103,\nT14 -> .(T99, T103),\nT100 -> T104,\nT101 -> T105,\nT102 -> T106" }, { "from": 364, "to": 369, "label": "EVAL-BACKTRACK" }, { "from": 365, "to": 367, "label": "SUCCESS" }, { "from": 368, "to": 361, "label": "INSTANCE with matching:\nT73 -> T104\nT74 -> T105\nT72 -> T106\nT14 -> T103" } ], "type": "Graph" } } ---------------------------------------- (56) Complex Obligation (AND) ---------------------------------------- (57) Obligation: Rules: f363_out(T14) -> f362_out(T14) :|: TRUE f364_out(x) -> f362_out(x) :|: TRUE f362_in(x1) -> f364_in(x1) :|: TRUE f362_in(x2) -> f363_in(x2) :|: TRUE f361_out(T103) -> f368_out(T103) :|: TRUE f368_in(x3) -> f361_in(x3) :|: TRUE f364_in(.(x4, x5)) -> f368_in(x5) :|: TRUE f369_out -> f364_out(x6) :|: TRUE f368_out(x7) -> f364_out(.(x8, x7)) :|: TRUE f364_in(x9) -> f369_in :|: TRUE f361_in(x10) -> f362_in(x10) :|: TRUE f362_out(x11) -> f361_out(x11) :|: TRUE f7_in(T2) -> f22_in(T2) :|: TRUE f22_out(x12) -> f7_out(x12) :|: TRUE f62_out(x13) -> f22_out(x13) :|: TRUE f60_out(x14) -> f22_out(x14) :|: TRUE f22_in(x15) -> f62_in(x15) :|: TRUE f22_in(x16) -> f60_in(x16) :|: TRUE f244_out -> f62_out(x17) :|: TRUE f62_in(x18) -> f244_in :|: TRUE f62_in(x19) -> f242_in(x19) :|: TRUE f242_out(x20) -> f62_out(x20) :|: TRUE f242_in(x21) -> f247_in :|: TRUE f248_out(x22) -> f242_out(x22) :|: TRUE f247_out -> f248_in(x23) :|: TRUE f361_out(x24) -> f248_out(x24) :|: TRUE f360_out -> f361_in(x25) :|: TRUE f248_in(x26) -> f360_in :|: TRUE Start term: f7_in(T2) ---------------------------------------- (58) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (59) TRUE ---------------------------------------- (60) Obligation: Rules: f294_out -> f289_out :|: TRUE f293_out -> f289_out :|: TRUE f289_in -> f294_in :|: TRUE f289_in -> f293_in :|: TRUE f286_in -> f287_in :|: TRUE f287_out -> f286_out :|: TRUE f293_in -> f286_in :|: TRUE f286_out -> f293_out :|: TRUE f288_out -> f287_out :|: TRUE f289_out -> f287_out :|: TRUE f287_in -> f289_in :|: TRUE f287_in -> f288_in :|: TRUE f7_in(T2) -> f22_in(T2) :|: TRUE f22_out(x) -> f7_out(x) :|: TRUE f62_out(x1) -> f22_out(x1) :|: TRUE f60_out(x2) -> f22_out(x2) :|: TRUE f22_in(x3) -> f62_in(x3) :|: TRUE f22_in(x4) -> f60_in(x4) :|: TRUE f244_out -> f62_out(x5) :|: TRUE f62_in(x6) -> f244_in :|: TRUE f62_in(T14) -> f242_in(T14) :|: TRUE f242_out(x7) -> f62_out(x7) :|: TRUE f242_in(x8) -> f247_in :|: TRUE f248_out(x9) -> f242_out(x9) :|: TRUE f247_out -> f248_in(x10) :|: TRUE f247_in -> f251_in :|: TRUE f251_out -> f247_out :|: TRUE f251_in -> f253_in :|: TRUE f251_in -> f252_in :|: TRUE f252_out -> f251_out :|: TRUE f253_out -> f251_out :|: TRUE f267_out -> f253_out :|: TRUE f269_out -> f253_out :|: TRUE f253_in -> f269_in :|: TRUE f253_in -> f267_in :|: TRUE f267_in -> f279_in :|: TRUE f280_out -> f267_out :|: TRUE f279_out -> f280_in :|: TRUE f285_out -> f286_in :|: TRUE f286_out -> f280_out :|: TRUE f280_in -> f285_in :|: TRUE f361_out(x11) -> f248_out(x11) :|: TRUE f360_out -> f361_in(x12) :|: TRUE f248_in(x13) -> f360_in :|: TRUE f247_out -> f360_out :|: TRUE f360_in -> f247_in :|: TRUE Start term: f7_in(T2) ---------------------------------------- (61) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (62) TRUE ---------------------------------------- (63) Obligation: Rules: f279_in -> f247_in :|: TRUE f247_out -> f279_out :|: TRUE f293_in -> f286_in :|: TRUE f286_out -> f293_out :|: TRUE f290_in -> f290_out :|: TRUE f285_in -> f247_in :|: TRUE f247_out -> f285_out :|: TRUE f251_in -> f253_in :|: TRUE f251_in -> f252_in :|: TRUE f252_out -> f251_out :|: TRUE f253_out -> f251_out :|: TRUE f247_in -> f251_in :|: TRUE f251_out -> f247_out :|: TRUE f294_out -> f289_out :|: TRUE f293_out -> f289_out :|: TRUE f289_in -> f294_in :|: TRUE f289_in -> f293_in :|: TRUE f286_in -> f287_in :|: TRUE f287_out -> f286_out :|: TRUE f267_out -> f253_out :|: TRUE f269_out -> f253_out :|: TRUE f253_in -> f269_in :|: TRUE f253_in -> f267_in :|: TRUE f288_in -> f290_in :|: TRUE f291_out -> f288_out :|: TRUE f290_out -> f288_out :|: TRUE f288_in -> f291_in :|: TRUE f267_in -> f279_in :|: TRUE f280_out -> f267_out :|: TRUE f279_out -> f280_in :|: TRUE f288_out -> f287_out :|: TRUE f289_out -> f287_out :|: TRUE f287_in -> f289_in :|: TRUE f287_in -> f288_in :|: TRUE f285_out -> f286_in :|: TRUE f286_out -> f280_out :|: TRUE f280_in -> f285_in :|: TRUE f7_in(T2) -> f22_in(T2) :|: TRUE f22_out(x) -> f7_out(x) :|: TRUE f62_out(x1) -> f22_out(x1) :|: TRUE f60_out(x2) -> f22_out(x2) :|: TRUE f22_in(x3) -> f62_in(x3) :|: TRUE f22_in(x4) -> f60_in(x4) :|: TRUE f244_out -> f62_out(x5) :|: TRUE f62_in(x6) -> f244_in :|: TRUE f62_in(T14) -> f242_in(T14) :|: TRUE f242_out(x7) -> f62_out(x7) :|: TRUE f242_in(x8) -> f247_in :|: TRUE f248_out(x9) -> f242_out(x9) :|: TRUE f247_out -> f248_in(x10) :|: TRUE f361_out(x11) -> f248_out(x11) :|: TRUE f360_out -> f361_in(x12) :|: TRUE f248_in(x13) -> f360_in :|: TRUE f247_out -> f360_out :|: TRUE f360_in -> f247_in :|: TRUE Start term: f7_in(T2) ---------------------------------------- (64) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f279_in -> f247_in :|: TRUE f251_in -> f253_in :|: TRUE f247_in -> f251_in :|: TRUE f253_in -> f267_in :|: TRUE f267_in -> f279_in :|: TRUE ---------------------------------------- (65) Obligation: Rules: f279_in -> f247_in :|: TRUE f251_in -> f253_in :|: TRUE f247_in -> f251_in :|: TRUE f253_in -> f267_in :|: TRUE f267_in -> f279_in :|: TRUE ---------------------------------------- (66) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (67) Obligation: Rules: f279_in -> f279_in :|: TRUE ---------------------------------------- (68) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (69) Obligation: Rules: f279_in -> f279_in :|: TRUE ---------------------------------------- (70) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f279_in -> f279_in :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (71) Obligation: Termination digraph: Nodes: (1) f279_in -> f279_in :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (72) FilterProof (EQUIVALENT) Used the following sort dictionary for filtering: f279_in() Replaced non-predefined constructor symbols by 0. ---------------------------------------- (73) Obligation: Rules: f279_in -> f279_in :|: TRUE ---------------------------------------- (74) IntTRSNonPeriodicNontermProof (COMPLETE) Normalized system to the following form: f(pc) -> f(1) :|: pc = 1 && TRUE Proved unsatisfiability of the following formula, indicating that the system is never left after entering: ((run2_0 = ((1 * 1)) and (((run1_0 * 1)) = ((1 * 1)) and T)) and !(((run2_0 * 1)) = ((1 * 1)) and T)) Proved satisfiability of the following formula, indicating that the system is entered at least once: (run2_0 = ((1 * 1)) and (((run1_0 * 1)) = ((1 * 1)) and T)) ---------------------------------------- (75) NO ---------------------------------------- (76) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 4, "program": { "directives": [], "clauses": [ [ "(in_order (void) ([]))", null ], [ "(in_order (tree X Left Right) Xs)", "(',' (in_order Left Ls) (',' (in_order Right Rs) (app Ls (. X Rs) Xs)))" ], [ "(app ([]) X X)", null ], [ "(app (. X Xs) Ys (. X Zs))", "(app Xs Ys Zs)" ] ] }, "graph": { "nodes": { "390": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T132 X100)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X100"], "exprvars": [] } }, "270": { "goal": [{ "clause": 0, "scope": 3, "term": "(in_order T12 X10)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X10"], "exprvars": [] } }, "391": { "goal": [{ "clause": -1, "scope": -1, "term": "(app ([]) (. T135 T134) T128)" }], "kb": { "nonunifying": [[ "(in_order T136 T128)", "(in_order (void) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T128"], "free": [], "exprvars": [] } }, "type": "Nodes", "271": { "goal": [{ "clause": 1, "scope": 3, "term": "(in_order T12 X10)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X10"], "exprvars": [] } }, "392": { "goal": [ { "clause": 2, "scope": 8, "term": "(app ([]) (. T135 T134) T128)" }, { "clause": 3, "scope": 8, "term": "(app ([]) (. T135 T134) T128)" } ], "kb": { "nonunifying": [[ "(in_order T136 T128)", "(in_order (void) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T128"], "free": [], "exprvars": [] } }, "272": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "393": { "goal": [{ "clause": 2, "scope": 8, "term": "(app ([]) (. T135 T134) T128)" }], "kb": { "nonunifying": [[ "(in_order T136 T128)", "(in_order (void) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T128"], "free": [], "exprvars": [] } }, "273": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "394": { "goal": [{ "clause": 3, "scope": 8, "term": "(app ([]) (. T135 T134) T128)" }], "kb": { "nonunifying": [[ "(in_order T136 T128)", "(in_order (void) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T128"], "free": [], "exprvars": [] } }, "274": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "395": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "275": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (in_order T25 X27) (',' (in_order T26 X28) (app X27 (. T27 X28) X29)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X29", "X27", "X28" ], "exprvars": [] } }, "396": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "199": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 1, "scope": 1, "term": "(in_order T1 ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "276": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "353": { "goal": [ { "clause": 2, "scope": 5, "term": "(app ([]) (. T15 T14) ([]))" }, { "clause": 3, "scope": 5, "term": "(app ([]) (. T15 T14) ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "397": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "398": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "311": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T29 X28)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X28"], "exprvars": [] } }, "399": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (in_order T160 X128) (',' (in_order T161 X129) (app X128 (. T162 X129) X130))) (',' (in_order T163 X100) (app X130 (. T164 X100) T128)))" }], "kb": { "nonunifying": [[ "(in_order T1 T128)", "(in_order (void) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T128"], "free": [ "X100", "X130", "X128", "X129" ], "exprvars": [] } }, "312": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T32 (. T33 T31) X29)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X29"], "exprvars": [] } }, "356": { "goal": [{ "clause": 3, "scope": 5, "term": "(app ([]) (. T15 T14) ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "357": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "358": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (in_order T82 X77) (',' (in_order T83 X78) (app X77 (. T84 X78) X79))) (',' (in_order T85 X10) (app X79 (. T86 X10) ([]))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X10", "X79", "X77", "X78" ], "exprvars": [] } }, "359": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "283": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T25 X27)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X27"], "exprvars": [] } }, "284": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (in_order T29 X28) (app T28 (. T30 X28) X29))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X29", "X28" ], "exprvars": [] } }, "201": { "goal": [{ "clause": 1, "scope": 1, "term": "(in_order T1 T2)" }], "kb": { "nonunifying": [[ "(in_order T1 T2)", "(in_order (void) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "245": { "goal": [{ "clause": 0, "scope": 2, "term": "(',' (in_order T9 X9) (',' (in_order T10 X10) (app X9 (. T11 X10) ([]))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X9", "X10" ], "exprvars": [] } }, "4": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "246": { "goal": [{ "clause": 1, "scope": 2, "term": "(',' (in_order T9 X9) (',' (in_order T10 X10) (app X9 (. T11 X10) ([]))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X9", "X10" ], "exprvars": [] } }, "400": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "401": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T160 X128)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X128"], "exprvars": [] } }, "402": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (in_order T166 X129) (app T165 (. T167 X129) X130)) (',' (in_order T168 X100) (app X130 (. T169 X100) T128)))" }], "kb": { "nonunifying": [[ "(in_order T170 T128)", "(in_order (void) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T128"], "free": [ "X100", "X130", "X129" ], "exprvars": [] } }, "403": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T166 X129)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X129"], "exprvars": [] } }, "404": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (app T172 (. T173 T171) X130) (',' (in_order T174 X100) (app X130 (. T175 X100) T128)))" }], "kb": { "nonunifying": [[ "(in_order T176 T128)", "(in_order (void) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T128"], "free": [ "X100", "X130" ], "exprvars": [] } }, "405": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T172 (. T173 T171) X130)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X130"], "exprvars": [] } }, "406": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (in_order T182 X100) (app T181 (. T183 X100) T128))" }], "kb": { "nonunifying": [[ "(in_order T184 T128)", "(in_order (void) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T128"], "free": ["X100"], "exprvars": [] } }, "209": { "goal": [{ "clause": 1, "scope": 1, "term": "(in_order T1 ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "407": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T182 X100)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X100"], "exprvars": [] } }, "408": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T190 (. T191 T189) T128)" }], "kb": { "nonunifying": [[ "(in_order T192 T128)", "(in_order (void) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T128"], "free": [], "exprvars": [] } }, "409": { "goal": [ { "clause": 2, "scope": 9, "term": "(app T190 (. T191 T189) T128)" }, { "clause": 3, "scope": 9, "term": "(app T190 (. T191 T189) T128)" } ], "kb": { "nonunifying": [[ "(in_order T192 T128)", "(in_order (void) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T128"], "free": [], "exprvars": [] } }, "24": { "goal": [ { "clause": 0, "scope": 1, "term": "(in_order T1 T2)" }, { "clause": 1, "scope": 1, "term": "(in_order T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "372": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T82 X77)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X77"], "exprvars": [] } }, "373": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (in_order T88 X78) (app T87 (. T89 X78) X79)) (',' (in_order T90 X10) (app X79 (. T91 X10) ([]))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X10", "X79", "X78" ], "exprvars": [] } }, "374": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T88 X78)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X78"], "exprvars": [] } }, "254": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (in_order T12 X10) (app ([]) (. T13 X10) ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X10"], "exprvars": [] } }, "375": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (app T93 (. T94 T92) X79) (',' (in_order T95 X10) (app X79 (. T96 X10) ([]))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X10", "X79" ], "exprvars": [] } }, "376": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T93 (. T94 T92) X79)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X79"], "exprvars": [] } }, "377": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (in_order T102 X10) (app T101 (. T103 X10) ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X10"], "exprvars": [] } }, "410": { "goal": [{ "clause": 2, "scope": 9, "term": "(app T190 (. T191 T189) T128)" }], "kb": { "nonunifying": [[ "(in_order T192 T128)", "(in_order (void) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T128"], "free": [], "exprvars": [] } }, "257": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "378": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T102 X10)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X10"], "exprvars": [] } }, "411": { "goal": [{ "clause": 3, "scope": 9, "term": "(app T190 (. T191 T189) T128)" }], "kb": { "nonunifying": [[ "(in_order T192 T128)", "(in_order (void) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T128"], "free": [], "exprvars": [] } }, "379": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T109 (. T110 T108) ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "412": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "413": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "414": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "415": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T222 (. T223 T224) T221)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T221"], "free": [], "exprvars": [] } }, "339": { "goal": [ { "clause": 2, "scope": 4, "term": "(app T32 (. T33 T31) X29)" }, { "clause": 3, "scope": 4, "term": "(app T32 (. T33 T31) X29)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X29"], "exprvars": [] } }, "416": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "418": { "goal": [ { "clause": 2, "scope": 10, "term": "(app T222 (. T223 T224) T221)" }, { "clause": 3, "scope": 10, "term": "(app T222 (. T223 T224) T221)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T221"], "free": [], "exprvars": [] } }, "419": { "goal": [{ "clause": 2, "scope": 10, "term": "(app T222 (. T223 T224) T221)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T221"], "free": [], "exprvars": [] } }, "380": { "goal": [ { "clause": 2, "scope": 6, "term": "(app T109 (. T110 T108) ([]))" }, { "clause": 3, "scope": 6, "term": "(app T109 (. T110 T108) ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "381": { "goal": [{ "clause": 3, "scope": 6, "term": "(app T109 (. T110 T108) ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "382": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "383": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (in_order T129 X99) (',' (in_order T130 X100) (app X99 (. T131 X100) T128)))" }], "kb": { "nonunifying": [[ "(in_order T1 T128)", "(in_order (void) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T128"], "free": [ "X99", "X100" ], "exprvars": [] } }, "340": { "goal": [{ "clause": 2, "scope": 4, "term": "(app T32 (. T33 T31) X29)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X29"], "exprvars": [] } }, "384": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "220": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (in_order T9 X9) (',' (in_order T10 X10) (app X9 (. T11 X10) ([]))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X9", "X10" ], "exprvars": [] } }, "341": { "goal": [{ "clause": 3, "scope": 4, "term": "(app T32 (. T33 T31) X29)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X29"], "exprvars": [] } }, "385": { "goal": [ { "clause": 0, "scope": 7, "term": "(',' (in_order T129 X99) (',' (in_order T130 X100) (app X99 (. T131 X100) T128)))" }, { "clause": 1, "scope": 7, "term": "(',' (in_order T129 X99) (',' (in_order T130 X100) (app X99 (. T131 X100) T128)))" } ], "kb": { "nonunifying": [[ "(in_order T1 T128)", "(in_order (void) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T128"], "free": [ "X99", "X100" ], "exprvars": [] } }, "265": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T12 X10)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X10"], "exprvars": [] } }, "342": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "386": { "goal": [{ "clause": 0, "scope": 7, "term": "(',' (in_order T129 X99) (',' (in_order T130 X100) (app X99 (. T131 X100) T128)))" }], "kb": { "nonunifying": [[ "(in_order T1 T128)", "(in_order (void) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T128"], "free": [ "X99", "X100" ], "exprvars": [] } }, "222": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "266": { "goal": [{ "clause": -1, "scope": -1, "term": "(app ([]) (. T15 T14) ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "343": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "387": { "goal": [{ "clause": 1, "scope": 7, "term": "(',' (in_order T129 X99) (',' (in_order T130 X100) (app X99 (. T131 X100) T128)))" }], "kb": { "nonunifying": [[ "(in_order T1 T128)", "(in_order (void) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T128"], "free": [ "X99", "X100" ], "exprvars": [] } }, "420": { "goal": [{ "clause": 3, "scope": 10, "term": "(app T222 (. T223 T224) T221)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T221"], "free": [], "exprvars": [] } }, "344": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "388": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (in_order T132 X100) (app ([]) (. T133 X100) T128))" }], "kb": { "nonunifying": [[ "(in_order T1 T128)", "(in_order (void) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T128"], "free": ["X100"], "exprvars": [] } }, "268": { "goal": [ { "clause": 0, "scope": 3, "term": "(in_order T12 X10)" }, { "clause": 1, "scope": 3, "term": "(in_order T12 X10)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X10"], "exprvars": [] } }, "389": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "422": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "423": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "226": { "goal": [ { "clause": 0, "scope": 2, "term": "(',' (in_order T9 X9) (',' (in_order T10 X10) (app X9 (. T11 X10) ([]))))" }, { "clause": 1, "scope": 2, "term": "(',' (in_order T9 X9) (',' (in_order T10 X10) (app X9 (. T11 X10) ([]))))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X9", "X10" ], "exprvars": [] } }, "347": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T60 (. T61 T62) X51)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X51"], "exprvars": [] } }, "424": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "348": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "425": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T254 (. T255 T256) T253)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T253"], "free": [], "exprvars": [] } }, "426": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 4, "to": 24, "label": "CASE" }, { "from": 24, "to": 199, "label": "EVAL with clause\nin_order(void, []).\nand substitutionT1 -> void,\nT2 -> []" }, { "from": 24, "to": 201, "label": "EVAL-BACKTRACK" }, { "from": 199, "to": 209, "label": "SUCCESS" }, { "from": 201, "to": 383, "label": "EVAL with clause\nin_order(tree(X95, X96, X97), X98) :- ','(in_order(X96, X99), ','(in_order(X97, X100), app(X99, .(X95, X100), X98))).\nand substitutionX95 -> T131,\nX96 -> T129,\nX97 -> T130,\nT1 -> tree(T131, T129, T130),\nT2 -> T128,\nX98 -> T128,\nT126 -> T129,\nT127 -> T130,\nT125 -> T131" }, { "from": 201, "to": 384, "label": "EVAL-BACKTRACK" }, { "from": 209, "to": 220, "label": "EVAL with clause\nin_order(tree(X5, X6, X7), X8) :- ','(in_order(X6, X9), ','(in_order(X7, X10), app(X9, .(X5, X10), X8))).\nand substitutionX5 -> T11,\nX6 -> T9,\nX7 -> T10,\nT1 -> tree(T11, T9, T10),\nX8 -> [],\nT7 -> T9,\nT8 -> T10,\nT6 -> T11" }, { "from": 209, "to": 222, "label": "EVAL-BACKTRACK" }, { "from": 220, "to": 226, "label": "CASE" }, { "from": 226, "to": 245, "label": "PARALLEL" }, { "from": 226, "to": 246, "label": "PARALLEL" }, { "from": 245, "to": 254, "label": "EVAL with clause\nin_order(void, []).\nand substitutionT9 -> void,\nX9 -> [],\nT10 -> T12,\nT11 -> T13" }, { "from": 245, "to": 257, "label": "EVAL-BACKTRACK" }, { "from": 246, "to": 358, "label": "EVAL with clause\nin_order(tree(X73, X74, X75), X76) :- ','(in_order(X74, X77), ','(in_order(X75, X78), app(X77, .(X73, X78), X76))).\nand substitutionX73 -> T84,\nX74 -> T82,\nX75 -> T83,\nT9 -> tree(T84, T82, T83),\nX9 -> X79,\nX76 -> X79,\nT80 -> T82,\nT81 -> T83,\nT79 -> T84,\nT10 -> T85,\nT11 -> T86" }, { "from": 246, "to": 359, "label": "EVAL-BACKTRACK" }, { "from": 254, "to": 265, "label": "SPLIT 1" }, { "from": 254, "to": 266, "label": "SPLIT 2\nreplacements:X10 -> T14,\nT13 -> T15" }, { "from": 265, "to": 268, "label": "CASE" }, { "from": 266, "to": 353, "label": "CASE" }, { "from": 268, "to": 270, "label": "PARALLEL" }, { "from": 268, "to": 271, "label": "PARALLEL" }, { "from": 270, "to": 272, "label": "EVAL with clause\nin_order(void, []).\nand substitutionT12 -> void,\nX10 -> []" }, { "from": 270, "to": 273, "label": "EVAL-BACKTRACK" }, { "from": 271, "to": 275, "label": "EVAL with clause\nin_order(tree(X23, X24, X25), X26) :- ','(in_order(X24, X27), ','(in_order(X25, X28), app(X27, .(X23, X28), X26))).\nand substitutionX23 -> T27,\nX24 -> T25,\nX25 -> T26,\nT12 -> tree(T27, T25, T26),\nX10 -> X29,\nX26 -> X29,\nT23 -> T25,\nT24 -> T26,\nT22 -> T27" }, { "from": 271, "to": 276, "label": "EVAL-BACKTRACK" }, { "from": 272, "to": 274, "label": "SUCCESS" }, { "from": 275, "to": 283, "label": "SPLIT 1" }, { "from": 275, "to": 284, "label": "SPLIT 2\nreplacements:X27 -> T28,\nT26 -> T29,\nT27 -> T30" }, { "from": 283, "to": 265, "label": "INSTANCE with matching:\nT12 -> T25\nX10 -> X27" }, { "from": 284, "to": 311, "label": "SPLIT 1" }, { "from": 284, "to": 312, "label": "SPLIT 2\nreplacements:X28 -> T31,\nT28 -> T32,\nT30 -> T33" }, { "from": 311, "to": 265, "label": "INSTANCE with matching:\nT12 -> T29\nX10 -> X28" }, { "from": 312, "to": 339, "label": "CASE" }, { "from": 339, "to": 340, "label": "PARALLEL" }, { "from": 339, "to": 341, "label": "PARALLEL" }, { "from": 340, "to": 342, "label": "EVAL with clause\napp([], X36, X36).\nand substitutionT32 -> [],\nT33 -> T46,\nT31 -> T47,\nX36 -> .(T46, T47),\nX29 -> .(T46, T47)" }, { "from": 340, "to": 343, "label": "EVAL-BACKTRACK" }, { "from": 341, "to": 347, "label": "EVAL with clause\napp(.(X47, X48), X49, .(X47, X50)) :- app(X48, X49, X50).\nand substitutionX47 -> T56,\nX48 -> T60,\nT32 -> .(T56, T60),\nT33 -> T61,\nT31 -> T62,\nX49 -> .(T61, T62),\nX50 -> X51,\nX29 -> .(T56, X51),\nT57 -> T60,\nT58 -> T61,\nT59 -> T62" }, { "from": 341, "to": 348, "label": "EVAL-BACKTRACK" }, { "from": 342, "to": 344, "label": "SUCCESS" }, { "from": 347, "to": 312, "label": "INSTANCE with matching:\nT32 -> T60\nT33 -> T61\nT31 -> T62\nX29 -> X51" }, { "from": 353, "to": 356, "label": "BACKTRACK\nfor clause: app([], X, X)because of non-unification" }, { "from": 356, "to": 357, "label": "BACKTRACK\nfor clause: app(.(X, Xs), Ys, .(X, Zs)) :- app(Xs, Ys, Zs)because of non-unification" }, { "from": 358, "to": 372, "label": "SPLIT 1" }, { "from": 358, "to": 373, "label": "SPLIT 2\nreplacements:X77 -> T87,\nT83 -> T88,\nT84 -> T89,\nT85 -> T90,\nT86 -> T91" }, { "from": 372, "to": 265, "label": "INSTANCE with matching:\nT12 -> T82\nX10 -> X77" }, { "from": 373, "to": 374, "label": "SPLIT 1" }, { "from": 373, "to": 375, "label": "SPLIT 2\nreplacements:X78 -> T92,\nT87 -> T93,\nT89 -> T94,\nT90 -> T95,\nT91 -> T96" }, { "from": 374, "to": 265, "label": "INSTANCE with matching:\nT12 -> T88\nX10 -> X78" }, { "from": 375, "to": 376, "label": "SPLIT 1" }, { "from": 375, "to": 377, "label": "SPLIT 2\nreplacements:X79 -> T101,\nT95 -> T102,\nT96 -> T103" }, { "from": 376, "to": 312, "label": "INSTANCE with matching:\nT32 -> T93\nT33 -> T94\nT31 -> T92\nX29 -> X79" }, { "from": 377, "to": 378, "label": "SPLIT 1" }, { "from": 377, "to": 379, "label": "SPLIT 2\nreplacements:X10 -> T108,\nT101 -> T109,\nT103 -> T110" }, { "from": 378, "to": 265, "label": "INSTANCE with matching:\nT12 -> T102" }, { "from": 379, "to": 380, "label": "CASE" }, { "from": 380, "to": 381, "label": "BACKTRACK\nfor clause: app([], X, X)because of non-unification" }, { "from": 381, "to": 382, "label": "BACKTRACK\nfor clause: app(.(X, Xs), Ys, .(X, Zs)) :- app(Xs, Ys, Zs)because of non-unification" }, { "from": 383, "to": 385, "label": "CASE" }, { "from": 385, "to": 386, "label": "PARALLEL" }, { "from": 385, "to": 387, "label": "PARALLEL" }, { "from": 386, "to": 388, "label": "EVAL with clause\nin_order(void, []).\nand substitutionT129 -> void,\nX99 -> [],\nT130 -> T132,\nT131 -> T133" }, { "from": 386, "to": 389, "label": "EVAL-BACKTRACK" }, { "from": 387, "to": 399, "label": "EVAL with clause\nin_order(tree(X124, X125, X126), X127) :- ','(in_order(X125, X128), ','(in_order(X126, X129), app(X128, .(X124, X129), X127))).\nand substitutionX124 -> T162,\nX125 -> T160,\nX126 -> T161,\nT129 -> tree(T162, T160, T161),\nX99 -> X130,\nX127 -> X130,\nT158 -> T160,\nT159 -> T161,\nT157 -> T162,\nT130 -> T163,\nT131 -> T164" }, { "from": 387, "to": 400, "label": "EVAL-BACKTRACK" }, { "from": 388, "to": 390, "label": "SPLIT 1" }, { "from": 388, "to": 391, "label": "SPLIT 2\nreplacements:X100 -> T134,\nT133 -> T135,\nT1 -> T136" }, { "from": 390, "to": 265, "label": "INSTANCE with matching:\nT12 -> T132\nX10 -> X100" }, { "from": 391, "to": 392, "label": "CASE" }, { "from": 392, "to": 393, "label": "PARALLEL" }, { "from": 392, "to": 394, "label": "PARALLEL" }, { "from": 393, "to": 395, "label": "EVAL with clause\napp([], X107, X107).\nand substitutionT135 -> T149,\nT134 -> T150,\nX107 -> .(T149, T150),\nT128 -> .(T149, T150)" }, { "from": 393, "to": 396, "label": "EVAL-BACKTRACK" }, { "from": 394, "to": 398, "label": "BACKTRACK\nfor clause: app(.(X, Xs), Ys, .(X, Zs)) :- app(Xs, Ys, Zs)because of non-unification" }, { "from": 395, "to": 397, "label": "SUCCESS" }, { "from": 399, "to": 401, "label": "SPLIT 1" }, { "from": 399, "to": 402, "label": "SPLIT 2\nreplacements:X128 -> T165,\nT161 -> T166,\nT162 -> T167,\nT163 -> T168,\nT164 -> T169,\nT1 -> T170" }, { "from": 401, "to": 265, "label": "INSTANCE with matching:\nT12 -> T160\nX10 -> X128" }, { "from": 402, "to": 403, "label": "SPLIT 1" }, { "from": 402, "to": 404, "label": "SPLIT 2\nreplacements:X129 -> T171,\nT165 -> T172,\nT167 -> T173,\nT168 -> T174,\nT169 -> T175,\nT170 -> T176" }, { "from": 403, "to": 265, "label": "INSTANCE with matching:\nT12 -> T166\nX10 -> X129" }, { "from": 404, "to": 405, "label": "SPLIT 1" }, { "from": 404, "to": 406, "label": "SPLIT 2\nreplacements:X130 -> T181,\nT174 -> T182,\nT175 -> T183,\nT176 -> T184" }, { "from": 405, "to": 312, "label": "INSTANCE with matching:\nT32 -> T172\nT33 -> T173\nT31 -> T171\nX29 -> X130" }, { "from": 406, "to": 407, "label": "SPLIT 1" }, { "from": 406, "to": 408, "label": "SPLIT 2\nreplacements:X100 -> T189,\nT181 -> T190,\nT183 -> T191,\nT184 -> T192" }, { "from": 407, "to": 265, "label": "INSTANCE with matching:\nT12 -> T182\nX10 -> X100" }, { "from": 408, "to": 409, "label": "CASE" }, { "from": 409, "to": 410, "label": "PARALLEL" }, { "from": 409, "to": 411, "label": "PARALLEL" }, { "from": 410, "to": 412, "label": "EVAL with clause\napp([], X141, X141).\nand substitutionT190 -> [],\nT191 -> T205,\nT189 -> T206,\nX141 -> .(T205, T206),\nT128 -> .(T205, T206)" }, { "from": 410, "to": 413, "label": "EVAL-BACKTRACK" }, { "from": 411, "to": 415, "label": "EVAL with clause\napp(.(X150, X151), X152, .(X150, X153)) :- app(X151, X152, X153).\nand substitutionX150 -> T217,\nX151 -> T222,\nT190 -> .(T217, T222),\nT191 -> T223,\nT189 -> T224,\nX152 -> .(T223, T224),\nX153 -> T221,\nT128 -> .(T217, T221),\nT218 -> T222,\nT219 -> T223,\nT220 -> T224" }, { "from": 411, "to": 416, "label": "EVAL-BACKTRACK" }, { "from": 412, "to": 414, "label": "SUCCESS" }, { "from": 415, "to": 418, "label": "CASE" }, { "from": 418, "to": 419, "label": "PARALLEL" }, { "from": 418, "to": 420, "label": "PARALLEL" }, { "from": 419, "to": 422, "label": "EVAL with clause\napp([], X160, X160).\nand substitutionT222 -> [],\nT223 -> T237,\nT224 -> T238,\nX160 -> .(T237, T238),\nT221 -> .(T237, T238)" }, { "from": 419, "to": 423, "label": "EVAL-BACKTRACK" }, { "from": 420, "to": 425, "label": "EVAL with clause\napp(.(X169, X170), X171, .(X169, X172)) :- app(X170, X171, X172).\nand substitutionX169 -> T249,\nX170 -> T254,\nT222 -> .(T249, T254),\nT223 -> T255,\nT224 -> T256,\nX171 -> .(T255, T256),\nX172 -> T253,\nT221 -> .(T249, T253),\nT250 -> T254,\nT251 -> T255,\nT252 -> T256" }, { "from": 420, "to": 426, "label": "EVAL-BACKTRACK" }, { "from": 422, "to": 424, "label": "SUCCESS" }, { "from": 425, "to": 415, "label": "INSTANCE with matching:\nT222 -> T254\nT223 -> T255\nT224 -> T256\nT221 -> T253" } ], "type": "Graph" } } ---------------------------------------- (77) Obligation: Triples: in_orderA(tree(X1, X2, X3), X4) :- in_orderA(X2, X5). in_orderA(tree(X1, X2, X3), X4) :- ','(in_ordercA(X2, X5), in_orderA(X3, X6)). in_orderA(tree(X1, X2, X3), X4) :- ','(in_ordercA(X2, X5), ','(in_ordercA(X3, X6), appB(X5, X1, X6, X4))). appB(.(X1, X2), X3, X4, .(X1, X5)) :- appB(X2, X3, X4, X5). appC(.(X1, X2), X3, X4, .(X1, X5)) :- appC(X2, X3, X4, X5). in_orderD(tree(X1, void, X2), []) :- in_orderA(X2, X3). in_orderD(tree(X1, tree(X2, X3, X4), X5), []) :- in_orderA(X3, X6). in_orderD(tree(X1, tree(X2, X3, X4), X5), []) :- ','(in_ordercA(X3, X6), in_orderA(X4, X7)). in_orderD(tree(X1, tree(X2, X3, X4), X5), []) :- ','(in_ordercA(X3, X6), ','(in_ordercA(X4, X7), appB(X6, X2, X7, X8))). in_orderD(tree(X1, tree(X2, X3, X4), X5), []) :- ','(in_ordercA(X3, X6), ','(in_ordercA(X4, X7), ','(appcB(X6, X2, X7, X8), in_orderA(X5, X9)))). in_orderD(tree(X1, void, X2), X3) :- in_orderA(X2, X4). in_orderD(tree(X1, tree(X2, X3, X4), X5), X6) :- in_orderA(X3, X7). in_orderD(tree(X1, tree(X2, X3, X4), X5), X6) :- ','(in_ordercA(X3, X7), in_orderA(X4, X8)). in_orderD(tree(X1, tree(X2, X3, X4), X5), X6) :- ','(in_ordercA(X3, X7), ','(in_ordercA(X4, X8), appB(X7, X2, X8, X9))). in_orderD(tree(X1, tree(X2, X3, X4), X5), X6) :- ','(in_ordercA(X3, X7), ','(in_ordercA(X4, X8), ','(appcB(X7, X2, X8, X9), in_orderA(X5, X10)))). in_orderD(tree(X1, tree(X2, X3, X4), X5), .(X6, X7)) :- ','(in_ordercA(X3, X8), ','(in_ordercA(X4, X9), ','(appcB(X8, X2, X9, .(X6, X10)), ','(in_ordercA(X5, X11), appC(X10, X1, X11, X7))))). Clauses: in_ordercA(void, []). in_ordercA(tree(X1, X2, X3), X4) :- ','(in_ordercA(X2, X5), ','(in_ordercA(X3, X6), appcB(X5, X1, X6, X4))). appcB([], X1, X2, .(X1, X2)). appcB(.(X1, X2), X3, X4, .(X1, X5)) :- appcB(X2, X3, X4, X5). appcC([], X1, X2, .(X1, X2)). appcC(.(X1, X2), X3, X4, .(X1, X5)) :- appcC(X2, X3, X4, X5). Afs: in_orderD(x1, x2) = in_orderD(x2) ---------------------------------------- (78) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: in_orderD_in_2: (f,b) in_orderA_in_2: (f,f) in_ordercA_in_2: (f,f) appcB_in_4: (b,f,b,f) appB_in_4: (b,f,b,f) appC_in_4: (b,f,b,b) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: IN_ORDERD_IN_AG(tree(X1, void, X2), []) -> U8_AG(X1, X2, in_orderA_in_aa(X2, X3)) IN_ORDERD_IN_AG(tree(X1, void, X2), []) -> IN_ORDERA_IN_AA(X2, X3) IN_ORDERA_IN_AA(tree(X1, X2, X3), X4) -> U1_AA(X1, X2, X3, X4, in_orderA_in_aa(X2, X5)) IN_ORDERA_IN_AA(tree(X1, X2, X3), X4) -> IN_ORDERA_IN_AA(X2, X5) IN_ORDERA_IN_AA(tree(X1, X2, X3), X4) -> U2_AA(X1, X2, X3, X4, in_ordercA_in_aa(X2, X5)) U2_AA(X1, X2, X3, X4, in_ordercA_out_aa(X2, X5)) -> U3_AA(X1, X2, X3, X4, in_orderA_in_aa(X3, X6)) U2_AA(X1, X2, X3, X4, in_ordercA_out_aa(X2, X5)) -> IN_ORDERA_IN_AA(X3, X6) U2_AA(X1, X2, X3, X4, in_ordercA_out_aa(X2, X5)) -> U4_AA(X1, X2, X3, X4, X5, in_ordercA_in_aa(X3, X6)) U4_AA(X1, X2, X3, X4, X5, in_ordercA_out_aa(X3, X6)) -> U5_AA(X1, X2, X3, X4, appB_in_gaga(X5, X1, X6, X4)) U4_AA(X1, X2, X3, X4, X5, in_ordercA_out_aa(X3, X6)) -> APPB_IN_GAGA(X5, X1, X6, X4) APPB_IN_GAGA(.(X1, X2), X3, X4, .(X1, X5)) -> U6_GAGA(X1, X2, X3, X4, X5, appB_in_gaga(X2, X3, X4, X5)) APPB_IN_GAGA(.(X1, X2), X3, X4, .(X1, X5)) -> APPB_IN_GAGA(X2, X3, X4, X5) IN_ORDERD_IN_AG(tree(X1, tree(X2, X3, X4), X5), []) -> U9_AG(X1, X2, X3, X4, X5, in_orderA_in_aa(X3, X6)) IN_ORDERD_IN_AG(tree(X1, tree(X2, X3, X4), X5), []) -> IN_ORDERA_IN_AA(X3, X6) IN_ORDERD_IN_AG(tree(X1, tree(X2, X3, X4), X5), []) -> U10_AG(X1, X2, X3, X4, X5, in_ordercA_in_aa(X3, X6)) U10_AG(X1, X2, X3, X4, X5, in_ordercA_out_aa(X3, X6)) -> U11_AG(X1, X2, X3, X4, X5, in_orderA_in_aa(X4, X7)) U10_AG(X1, X2, X3, X4, X5, in_ordercA_out_aa(X3, X6)) -> IN_ORDERA_IN_AA(X4, X7) U10_AG(X1, X2, X3, X4, X5, in_ordercA_out_aa(X3, X6)) -> U12_AG(X1, X2, X3, X4, X5, X6, in_ordercA_in_aa(X4, X7)) U12_AG(X1, X2, X3, X4, X5, X6, in_ordercA_out_aa(X4, X7)) -> U13_AG(X1, X2, X3, X4, X5, appB_in_gaga(X6, X2, X7, X8)) U12_AG(X1, X2, X3, X4, X5, X6, in_ordercA_out_aa(X4, X7)) -> APPB_IN_GAGA(X6, X2, X7, X8) U12_AG(X1, X2, X3, X4, X5, X6, in_ordercA_out_aa(X4, X7)) -> U14_AG(X1, X2, X3, X4, X5, appcB_in_gaga(X6, X2, X7, X8)) U14_AG(X1, X2, X3, X4, X5, appcB_out_gaga(X6, X2, X7, X8)) -> U15_AG(X1, X2, X3, X4, X5, in_orderA_in_aa(X5, X9)) U14_AG(X1, X2, X3, X4, X5, appcB_out_gaga(X6, X2, X7, X8)) -> IN_ORDERA_IN_AA(X5, X9) IN_ORDERD_IN_AG(tree(X1, void, X2), X3) -> U16_AG(X1, X2, X3, in_orderA_in_aa(X2, X4)) IN_ORDERD_IN_AG(tree(X1, void, X2), X3) -> IN_ORDERA_IN_AA(X2, X4) IN_ORDERD_IN_AG(tree(X1, tree(X2, X3, X4), X5), X6) -> U17_AG(X1, X2, X3, X4, X5, X6, in_orderA_in_aa(X3, X7)) IN_ORDERD_IN_AG(tree(X1, tree(X2, X3, X4), X5), X6) -> IN_ORDERA_IN_AA(X3, X7) IN_ORDERD_IN_AG(tree(X1, tree(X2, X3, X4), X5), X6) -> U18_AG(X1, X2, X3, X4, X5, X6, in_ordercA_in_aa(X3, X7)) U18_AG(X1, X2, X3, X4, X5, X6, in_ordercA_out_aa(X3, X7)) -> U19_AG(X1, X2, X3, X4, X5, X6, in_orderA_in_aa(X4, X8)) U18_AG(X1, X2, X3, X4, X5, X6, in_ordercA_out_aa(X3, X7)) -> IN_ORDERA_IN_AA(X4, X8) U18_AG(X1, X2, X3, X4, X5, X6, in_ordercA_out_aa(X3, X7)) -> U20_AG(X1, X2, X3, X4, X5, X6, X7, in_ordercA_in_aa(X4, X8)) U20_AG(X1, X2, X3, X4, X5, X6, X7, in_ordercA_out_aa(X4, X8)) -> U21_AG(X1, X2, X3, X4, X5, X6, appB_in_gaga(X7, X2, X8, X9)) U20_AG(X1, X2, X3, X4, X5, X6, X7, in_ordercA_out_aa(X4, X8)) -> APPB_IN_GAGA(X7, X2, X8, X9) U20_AG(X1, X2, X3, X4, X5, X6, X7, in_ordercA_out_aa(X4, X8)) -> U22_AG(X1, X2, X3, X4, X5, X6, appcB_in_gaga(X7, X2, X8, X9)) U22_AG(X1, X2, X3, X4, X5, X6, appcB_out_gaga(X7, X2, X8, X9)) -> U23_AG(X1, X2, X3, X4, X5, X6, in_orderA_in_aa(X5, X10)) U22_AG(X1, X2, X3, X4, X5, X6, appcB_out_gaga(X7, X2, X8, X9)) -> IN_ORDERA_IN_AA(X5, X10) IN_ORDERD_IN_AG(tree(X1, tree(X2, X3, X4), X5), .(X6, X7)) -> U24_AG(X1, X2, X3, X4, X5, X6, X7, in_ordercA_in_aa(X3, X8)) U24_AG(X1, X2, X3, X4, X5, X6, X7, in_ordercA_out_aa(X3, X8)) -> U25_AG(X1, X2, X3, X4, X5, X6, X7, X8, in_ordercA_in_aa(X4, X9)) U25_AG(X1, X2, X3, X4, X5, X6, X7, X8, in_ordercA_out_aa(X4, X9)) -> U26_AG(X1, X2, X3, X4, X5, X6, X7, appcB_in_gaga(X8, X2, X9, .(X6, X10))) U26_AG(X1, X2, X3, X4, X5, X6, X7, appcB_out_gaga(X8, X2, X9, .(X6, X10))) -> U27_AG(X1, X2, X3, X4, X5, X6, X7, X10, in_ordercA_in_aa(X5, X11)) U27_AG(X1, X2, X3, X4, X5, X6, X7, X10, in_ordercA_out_aa(X5, X11)) -> U28_AG(X1, X2, X3, X4, X5, X6, X7, appC_in_gagg(X10, X1, X11, X7)) U27_AG(X1, X2, X3, X4, X5, X6, X7, X10, in_ordercA_out_aa(X5, X11)) -> APPC_IN_GAGG(X10, X1, X11, X7) APPC_IN_GAGG(.(X1, X2), X3, X4, .(X1, X5)) -> U7_GAGG(X1, X2, X3, X4, X5, appC_in_gagg(X2, X3, X4, X5)) APPC_IN_GAGG(.(X1, X2), X3, X4, .(X1, X5)) -> APPC_IN_GAGG(X2, X3, X4, X5) The TRS R consists of the following rules: in_ordercA_in_aa(void, []) -> in_ordercA_out_aa(void, []) in_ordercA_in_aa(tree(X1, X2, X3), X4) -> U30_aa(X1, X2, X3, X4, in_ordercA_in_aa(X2, X5)) U30_aa(X1, X2, X3, X4, in_ordercA_out_aa(X2, X5)) -> U31_aa(X1, X2, X3, X4, X5, in_ordercA_in_aa(X3, X6)) U31_aa(X1, X2, X3, X4, X5, in_ordercA_out_aa(X3, X6)) -> U32_aa(X1, X2, X3, X4, appcB_in_gaga(X5, X1, X6, X4)) appcB_in_gaga([], X1, X2, .(X1, X2)) -> appcB_out_gaga([], X1, X2, .(X1, X2)) appcB_in_gaga(.(X1, X2), X3, X4, .(X1, X5)) -> U33_gaga(X1, X2, X3, X4, X5, appcB_in_gaga(X2, X3, X4, X5)) U33_gaga(X1, X2, X3, X4, X5, appcB_out_gaga(X2, X3, X4, X5)) -> appcB_out_gaga(.(X1, X2), X3, X4, .(X1, X5)) U32_aa(X1, X2, X3, X4, appcB_out_gaga(X5, X1, X6, X4)) -> in_ordercA_out_aa(tree(X1, X2, X3), X4) The argument filtering Pi contains the following mapping: [] = [] in_orderA_in_aa(x1, x2) = in_orderA_in_aa in_ordercA_in_aa(x1, x2) = in_ordercA_in_aa in_ordercA_out_aa(x1, x2) = in_ordercA_out_aa(x1, x2) U30_aa(x1, x2, x3, x4, x5) = U30_aa(x5) U31_aa(x1, x2, x3, x4, x5, x6) = U31_aa(x2, x5, x6) U32_aa(x1, x2, x3, x4, x5) = U32_aa(x2, x3, x5) appcB_in_gaga(x1, x2, x3, x4) = appcB_in_gaga(x1, x3) appcB_out_gaga(x1, x2, x3, x4) = appcB_out_gaga(x1, x3, x4) .(x1, x2) = .(x2) U33_gaga(x1, x2, x3, x4, x5, x6) = U33_gaga(x2, x4, x6) tree(x1, x2, x3) = tree(x2, x3) appB_in_gaga(x1, x2, x3, x4) = appB_in_gaga(x1, x3) appC_in_gagg(x1, x2, x3, x4) = appC_in_gagg(x1, x3, x4) IN_ORDERD_IN_AG(x1, x2) = IN_ORDERD_IN_AG(x2) U8_AG(x1, x2, x3) = U8_AG(x3) IN_ORDERA_IN_AA(x1, x2) = IN_ORDERA_IN_AA U1_AA(x1, x2, x3, x4, x5) = U1_AA(x5) U2_AA(x1, x2, x3, x4, x5) = U2_AA(x5) U3_AA(x1, x2, x3, x4, x5) = U3_AA(x5) U4_AA(x1, x2, x3, x4, x5, x6) = U4_AA(x5, x6) U5_AA(x1, x2, x3, x4, x5) = U5_AA(x5) APPB_IN_GAGA(x1, x2, x3, x4) = APPB_IN_GAGA(x1, x3) U6_GAGA(x1, x2, x3, x4, x5, x6) = U6_GAGA(x2, x4, x6) U9_AG(x1, x2, x3, x4, x5, x6) = U9_AG(x6) U10_AG(x1, x2, x3, x4, x5, x6) = U10_AG(x6) U11_AG(x1, x2, x3, x4, x5, x6) = U11_AG(x6) U12_AG(x1, x2, x3, x4, x5, x6, x7) = U12_AG(x6, x7) U13_AG(x1, x2, x3, x4, x5, x6) = U13_AG(x6) U14_AG(x1, x2, x3, x4, x5, x6) = U14_AG(x6) U15_AG(x1, x2, x3, x4, x5, x6) = U15_AG(x6) U16_AG(x1, x2, x3, x4) = U16_AG(x3, x4) U17_AG(x1, x2, x3, x4, x5, x6, x7) = U17_AG(x6, x7) U18_AG(x1, x2, x3, x4, x5, x6, x7) = U18_AG(x6, x7) U19_AG(x1, x2, x3, x4, x5, x6, x7) = U19_AG(x6, x7) U20_AG(x1, x2, x3, x4, x5, x6, x7, x8) = U20_AG(x6, x7, x8) U21_AG(x1, x2, x3, x4, x5, x6, x7) = U21_AG(x6, x7) U22_AG(x1, x2, x3, x4, x5, x6, x7) = U22_AG(x6, x7) U23_AG(x1, x2, x3, x4, x5, x6, x7) = U23_AG(x6, x7) U24_AG(x1, x2, x3, x4, x5, x6, x7, x8) = U24_AG(x7, x8) U25_AG(x1, x2, x3, x4, x5, x6, x7, x8, x9) = U25_AG(x7, x8, x9) U26_AG(x1, x2, x3, x4, x5, x6, x7, x8) = U26_AG(x7, x8) U27_AG(x1, x2, x3, x4, x5, x6, x7, x8, x9) = U27_AG(x7, x8, x9) U28_AG(x1, x2, x3, x4, x5, x6, x7, x8) = U28_AG(x7, x8) APPC_IN_GAGG(x1, x2, x3, x4) = APPC_IN_GAGG(x1, x3, x4) U7_GAGG(x1, x2, x3, x4, x5, x6) = U7_GAGG(x2, x4, x5, x6) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (79) Obligation: Pi DP problem: The TRS P consists of the following rules: IN_ORDERD_IN_AG(tree(X1, void, X2), []) -> U8_AG(X1, X2, in_orderA_in_aa(X2, X3)) IN_ORDERD_IN_AG(tree(X1, void, X2), []) -> IN_ORDERA_IN_AA(X2, X3) IN_ORDERA_IN_AA(tree(X1, X2, X3), X4) -> U1_AA(X1, X2, X3, X4, in_orderA_in_aa(X2, X5)) IN_ORDERA_IN_AA(tree(X1, X2, X3), X4) -> IN_ORDERA_IN_AA(X2, X5) IN_ORDERA_IN_AA(tree(X1, X2, X3), X4) -> U2_AA(X1, X2, X3, X4, in_ordercA_in_aa(X2, X5)) U2_AA(X1, X2, X3, X4, in_ordercA_out_aa(X2, X5)) -> U3_AA(X1, X2, X3, X4, in_orderA_in_aa(X3, X6)) U2_AA(X1, X2, X3, X4, in_ordercA_out_aa(X2, X5)) -> IN_ORDERA_IN_AA(X3, X6) U2_AA(X1, X2, X3, X4, in_ordercA_out_aa(X2, X5)) -> U4_AA(X1, X2, X3, X4, X5, in_ordercA_in_aa(X3, X6)) U4_AA(X1, X2, X3, X4, X5, in_ordercA_out_aa(X3, X6)) -> U5_AA(X1, X2, X3, X4, appB_in_gaga(X5, X1, X6, X4)) U4_AA(X1, X2, X3, X4, X5, in_ordercA_out_aa(X3, X6)) -> APPB_IN_GAGA(X5, X1, X6, X4) APPB_IN_GAGA(.(X1, X2), X3, X4, .(X1, X5)) -> U6_GAGA(X1, X2, X3, X4, X5, appB_in_gaga(X2, X3, X4, X5)) APPB_IN_GAGA(.(X1, X2), X3, X4, .(X1, X5)) -> APPB_IN_GAGA(X2, X3, X4, X5) IN_ORDERD_IN_AG(tree(X1, tree(X2, X3, X4), X5), []) -> U9_AG(X1, X2, X3, X4, X5, in_orderA_in_aa(X3, X6)) IN_ORDERD_IN_AG(tree(X1, tree(X2, X3, X4), X5), []) -> IN_ORDERA_IN_AA(X3, X6) IN_ORDERD_IN_AG(tree(X1, tree(X2, X3, X4), X5), []) -> U10_AG(X1, X2, X3, X4, X5, in_ordercA_in_aa(X3, X6)) U10_AG(X1, X2, X3, X4, X5, in_ordercA_out_aa(X3, X6)) -> U11_AG(X1, X2, X3, X4, X5, in_orderA_in_aa(X4, X7)) U10_AG(X1, X2, X3, X4, X5, in_ordercA_out_aa(X3, X6)) -> IN_ORDERA_IN_AA(X4, X7) U10_AG(X1, X2, X3, X4, X5, in_ordercA_out_aa(X3, X6)) -> U12_AG(X1, X2, X3, X4, X5, X6, in_ordercA_in_aa(X4, X7)) U12_AG(X1, X2, X3, X4, X5, X6, in_ordercA_out_aa(X4, X7)) -> U13_AG(X1, X2, X3, X4, X5, appB_in_gaga(X6, X2, X7, X8)) U12_AG(X1, X2, X3, X4, X5, X6, in_ordercA_out_aa(X4, X7)) -> APPB_IN_GAGA(X6, X2, X7, X8) U12_AG(X1, X2, X3, X4, X5, X6, in_ordercA_out_aa(X4, X7)) -> U14_AG(X1, X2, X3, X4, X5, appcB_in_gaga(X6, X2, X7, X8)) U14_AG(X1, X2, X3, X4, X5, appcB_out_gaga(X6, X2, X7, X8)) -> U15_AG(X1, X2, X3, X4, X5, in_orderA_in_aa(X5, X9)) U14_AG(X1, X2, X3, X4, X5, appcB_out_gaga(X6, X2, X7, X8)) -> IN_ORDERA_IN_AA(X5, X9) IN_ORDERD_IN_AG(tree(X1, void, X2), X3) -> U16_AG(X1, X2, X3, in_orderA_in_aa(X2, X4)) IN_ORDERD_IN_AG(tree(X1, void, X2), X3) -> IN_ORDERA_IN_AA(X2, X4) IN_ORDERD_IN_AG(tree(X1, tree(X2, X3, X4), X5), X6) -> U17_AG(X1, X2, X3, X4, X5, X6, in_orderA_in_aa(X3, X7)) IN_ORDERD_IN_AG(tree(X1, tree(X2, X3, X4), X5), X6) -> IN_ORDERA_IN_AA(X3, X7) IN_ORDERD_IN_AG(tree(X1, tree(X2, X3, X4), X5), X6) -> U18_AG(X1, X2, X3, X4, X5, X6, in_ordercA_in_aa(X3, X7)) U18_AG(X1, X2, X3, X4, X5, X6, in_ordercA_out_aa(X3, X7)) -> U19_AG(X1, X2, X3, X4, X5, X6, in_orderA_in_aa(X4, X8)) U18_AG(X1, X2, X3, X4, X5, X6, in_ordercA_out_aa(X3, X7)) -> IN_ORDERA_IN_AA(X4, X8) U18_AG(X1, X2, X3, X4, X5, X6, in_ordercA_out_aa(X3, X7)) -> U20_AG(X1, X2, X3, X4, X5, X6, X7, in_ordercA_in_aa(X4, X8)) U20_AG(X1, X2, X3, X4, X5, X6, X7, in_ordercA_out_aa(X4, X8)) -> U21_AG(X1, X2, X3, X4, X5, X6, appB_in_gaga(X7, X2, X8, X9)) U20_AG(X1, X2, X3, X4, X5, X6, X7, in_ordercA_out_aa(X4, X8)) -> APPB_IN_GAGA(X7, X2, X8, X9) U20_AG(X1, X2, X3, X4, X5, X6, X7, in_ordercA_out_aa(X4, X8)) -> U22_AG(X1, X2, X3, X4, X5, X6, appcB_in_gaga(X7, X2, X8, X9)) U22_AG(X1, X2, X3, X4, X5, X6, appcB_out_gaga(X7, X2, X8, X9)) -> U23_AG(X1, X2, X3, X4, X5, X6, in_orderA_in_aa(X5, X10)) U22_AG(X1, X2, X3, X4, X5, X6, appcB_out_gaga(X7, X2, X8, X9)) -> IN_ORDERA_IN_AA(X5, X10) IN_ORDERD_IN_AG(tree(X1, tree(X2, X3, X4), X5), .(X6, X7)) -> U24_AG(X1, X2, X3, X4, X5, X6, X7, in_ordercA_in_aa(X3, X8)) U24_AG(X1, X2, X3, X4, X5, X6, X7, in_ordercA_out_aa(X3, X8)) -> U25_AG(X1, X2, X3, X4, X5, X6, X7, X8, in_ordercA_in_aa(X4, X9)) U25_AG(X1, X2, X3, X4, X5, X6, X7, X8, in_ordercA_out_aa(X4, X9)) -> U26_AG(X1, X2, X3, X4, X5, X6, X7, appcB_in_gaga(X8, X2, X9, .(X6, X10))) U26_AG(X1, X2, X3, X4, X5, X6, X7, appcB_out_gaga(X8, X2, X9, .(X6, X10))) -> U27_AG(X1, X2, X3, X4, X5, X6, X7, X10, in_ordercA_in_aa(X5, X11)) U27_AG(X1, X2, X3, X4, X5, X6, X7, X10, in_ordercA_out_aa(X5, X11)) -> U28_AG(X1, X2, X3, X4, X5, X6, X7, appC_in_gagg(X10, X1, X11, X7)) U27_AG(X1, X2, X3, X4, X5, X6, X7, X10, in_ordercA_out_aa(X5, X11)) -> APPC_IN_GAGG(X10, X1, X11, X7) APPC_IN_GAGG(.(X1, X2), X3, X4, .(X1, X5)) -> U7_GAGG(X1, X2, X3, X4, X5, appC_in_gagg(X2, X3, X4, X5)) APPC_IN_GAGG(.(X1, X2), X3, X4, .(X1, X5)) -> APPC_IN_GAGG(X2, X3, X4, X5) The TRS R consists of the following rules: in_ordercA_in_aa(void, []) -> in_ordercA_out_aa(void, []) in_ordercA_in_aa(tree(X1, X2, X3), X4) -> U30_aa(X1, X2, X3, X4, in_ordercA_in_aa(X2, X5)) U30_aa(X1, X2, X3, X4, in_ordercA_out_aa(X2, X5)) -> U31_aa(X1, X2, X3, X4, X5, in_ordercA_in_aa(X3, X6)) U31_aa(X1, X2, X3, X4, X5, in_ordercA_out_aa(X3, X6)) -> U32_aa(X1, X2, X3, X4, appcB_in_gaga(X5, X1, X6, X4)) appcB_in_gaga([], X1, X2, .(X1, X2)) -> appcB_out_gaga([], X1, X2, .(X1, X2)) appcB_in_gaga(.(X1, X2), X3, X4, .(X1, X5)) -> U33_gaga(X1, X2, X3, X4, X5, appcB_in_gaga(X2, X3, X4, X5)) U33_gaga(X1, X2, X3, X4, X5, appcB_out_gaga(X2, X3, X4, X5)) -> appcB_out_gaga(.(X1, X2), X3, X4, .(X1, X5)) U32_aa(X1, X2, X3, X4, appcB_out_gaga(X5, X1, X6, X4)) -> in_ordercA_out_aa(tree(X1, X2, X3), X4) The argument filtering Pi contains the following mapping: [] = [] in_orderA_in_aa(x1, x2) = in_orderA_in_aa in_ordercA_in_aa(x1, x2) = in_ordercA_in_aa in_ordercA_out_aa(x1, x2) = in_ordercA_out_aa(x1, x2) U30_aa(x1, x2, x3, x4, x5) = U30_aa(x5) U31_aa(x1, x2, x3, x4, x5, x6) = U31_aa(x2, x5, x6) U32_aa(x1, x2, x3, x4, x5) = U32_aa(x2, x3, x5) appcB_in_gaga(x1, x2, x3, x4) = appcB_in_gaga(x1, x3) appcB_out_gaga(x1, x2, x3, x4) = appcB_out_gaga(x1, x3, x4) .(x1, x2) = .(x2) U33_gaga(x1, x2, x3, x4, x5, x6) = U33_gaga(x2, x4, x6) tree(x1, x2, x3) = tree(x2, x3) appB_in_gaga(x1, x2, x3, x4) = appB_in_gaga(x1, x3) appC_in_gagg(x1, x2, x3, x4) = appC_in_gagg(x1, x3, x4) IN_ORDERD_IN_AG(x1, x2) = IN_ORDERD_IN_AG(x2) U8_AG(x1, x2, x3) = U8_AG(x3) IN_ORDERA_IN_AA(x1, x2) = IN_ORDERA_IN_AA U1_AA(x1, x2, x3, x4, x5) = U1_AA(x5) U2_AA(x1, x2, x3, x4, x5) = U2_AA(x5) U3_AA(x1, x2, x3, x4, x5) = U3_AA(x5) U4_AA(x1, x2, x3, x4, x5, x6) = U4_AA(x5, x6) U5_AA(x1, x2, x3, x4, x5) = U5_AA(x5) APPB_IN_GAGA(x1, x2, x3, x4) = APPB_IN_GAGA(x1, x3) U6_GAGA(x1, x2, x3, x4, x5, x6) = U6_GAGA(x2, x4, x6) U9_AG(x1, x2, x3, x4, x5, x6) = U9_AG(x6) U10_AG(x1, x2, x3, x4, x5, x6) = U10_AG(x6) U11_AG(x1, x2, x3, x4, x5, x6) = U11_AG(x6) U12_AG(x1, x2, x3, x4, x5, x6, x7) = U12_AG(x6, x7) U13_AG(x1, x2, x3, x4, x5, x6) = U13_AG(x6) U14_AG(x1, x2, x3, x4, x5, x6) = U14_AG(x6) U15_AG(x1, x2, x3, x4, x5, x6) = U15_AG(x6) U16_AG(x1, x2, x3, x4) = U16_AG(x3, x4) U17_AG(x1, x2, x3, x4, x5, x6, x7) = U17_AG(x6, x7) U18_AG(x1, x2, x3, x4, x5, x6, x7) = U18_AG(x6, x7) U19_AG(x1, x2, x3, x4, x5, x6, x7) = U19_AG(x6, x7) U20_AG(x1, x2, x3, x4, x5, x6, x7, x8) = U20_AG(x6, x7, x8) U21_AG(x1, x2, x3, x4, x5, x6, x7) = U21_AG(x6, x7) U22_AG(x1, x2, x3, x4, x5, x6, x7) = U22_AG(x6, x7) U23_AG(x1, x2, x3, x4, x5, x6, x7) = U23_AG(x6, x7) U24_AG(x1, x2, x3, x4, x5, x6, x7, x8) = U24_AG(x7, x8) U25_AG(x1, x2, x3, x4, x5, x6, x7, x8, x9) = U25_AG(x7, x8, x9) U26_AG(x1, x2, x3, x4, x5, x6, x7, x8) = U26_AG(x7, x8) U27_AG(x1, x2, x3, x4, x5, x6, x7, x8, x9) = U27_AG(x7, x8, x9) U28_AG(x1, x2, x3, x4, x5, x6, x7, x8) = U28_AG(x7, x8) APPC_IN_GAGG(x1, x2, x3, x4) = APPC_IN_GAGG(x1, x3, x4) U7_GAGG(x1, x2, x3, x4, x5, x6) = U7_GAGG(x2, x4, x5, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (80) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 39 less nodes. ---------------------------------------- (81) Complex Obligation (AND) ---------------------------------------- (82) Obligation: Pi DP problem: The TRS P consists of the following rules: APPC_IN_GAGG(.(X1, X2), X3, X4, .(X1, X5)) -> APPC_IN_GAGG(X2, X3, X4, X5) The TRS R consists of the following rules: in_ordercA_in_aa(void, []) -> in_ordercA_out_aa(void, []) in_ordercA_in_aa(tree(X1, X2, X3), X4) -> U30_aa(X1, X2, X3, X4, in_ordercA_in_aa(X2, X5)) U30_aa(X1, X2, X3, X4, in_ordercA_out_aa(X2, X5)) -> U31_aa(X1, X2, X3, X4, X5, in_ordercA_in_aa(X3, X6)) U31_aa(X1, X2, X3, X4, X5, in_ordercA_out_aa(X3, X6)) -> U32_aa(X1, X2, X3, X4, appcB_in_gaga(X5, X1, X6, X4)) appcB_in_gaga([], X1, X2, .(X1, X2)) -> appcB_out_gaga([], X1, X2, .(X1, X2)) appcB_in_gaga(.(X1, X2), X3, X4, .(X1, X5)) -> U33_gaga(X1, X2, X3, X4, X5, appcB_in_gaga(X2, X3, X4, X5)) U33_gaga(X1, X2, X3, X4, X5, appcB_out_gaga(X2, X3, X4, X5)) -> appcB_out_gaga(.(X1, X2), X3, X4, .(X1, X5)) U32_aa(X1, X2, X3, X4, appcB_out_gaga(X5, X1, X6, X4)) -> in_ordercA_out_aa(tree(X1, X2, X3), X4) The argument filtering Pi contains the following mapping: [] = [] in_ordercA_in_aa(x1, x2) = in_ordercA_in_aa in_ordercA_out_aa(x1, x2) = in_ordercA_out_aa(x1, x2) U30_aa(x1, x2, x3, x4, x5) = U30_aa(x5) U31_aa(x1, x2, x3, x4, x5, x6) = U31_aa(x2, x5, x6) U32_aa(x1, x2, x3, x4, x5) = U32_aa(x2, x3, x5) appcB_in_gaga(x1, x2, x3, x4) = appcB_in_gaga(x1, x3) appcB_out_gaga(x1, x2, x3, x4) = appcB_out_gaga(x1, x3, x4) .(x1, x2) = .(x2) U33_gaga(x1, x2, x3, x4, x5, x6) = U33_gaga(x2, x4, x6) tree(x1, x2, x3) = tree(x2, x3) APPC_IN_GAGG(x1, x2, x3, x4) = APPC_IN_GAGG(x1, x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (83) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (84) Obligation: Pi DP problem: The TRS P consists of the following rules: APPC_IN_GAGG(.(X1, X2), X3, X4, .(X1, X5)) -> APPC_IN_GAGG(X2, X3, X4, X5) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) APPC_IN_GAGG(x1, x2, x3, x4) = APPC_IN_GAGG(x1, x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (85) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (86) Obligation: Q DP problem: The TRS P consists of the following rules: APPC_IN_GAGG(.(X2), X4, .(X5)) -> APPC_IN_GAGG(X2, X4, X5) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (87) 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: *APPC_IN_GAGG(.(X2), X4, .(X5)) -> APPC_IN_GAGG(X2, X4, X5) The graph contains the following edges 1 > 1, 2 >= 2, 3 > 3 ---------------------------------------- (88) YES ---------------------------------------- (89) Obligation: Pi DP problem: The TRS P consists of the following rules: APPB_IN_GAGA(.(X1, X2), X3, X4, .(X1, X5)) -> APPB_IN_GAGA(X2, X3, X4, X5) The TRS R consists of the following rules: in_ordercA_in_aa(void, []) -> in_ordercA_out_aa(void, []) in_ordercA_in_aa(tree(X1, X2, X3), X4) -> U30_aa(X1, X2, X3, X4, in_ordercA_in_aa(X2, X5)) U30_aa(X1, X2, X3, X4, in_ordercA_out_aa(X2, X5)) -> U31_aa(X1, X2, X3, X4, X5, in_ordercA_in_aa(X3, X6)) U31_aa(X1, X2, X3, X4, X5, in_ordercA_out_aa(X3, X6)) -> U32_aa(X1, X2, X3, X4, appcB_in_gaga(X5, X1, X6, X4)) appcB_in_gaga([], X1, X2, .(X1, X2)) -> appcB_out_gaga([], X1, X2, .(X1, X2)) appcB_in_gaga(.(X1, X2), X3, X4, .(X1, X5)) -> U33_gaga(X1, X2, X3, X4, X5, appcB_in_gaga(X2, X3, X4, X5)) U33_gaga(X1, X2, X3, X4, X5, appcB_out_gaga(X2, X3, X4, X5)) -> appcB_out_gaga(.(X1, X2), X3, X4, .(X1, X5)) U32_aa(X1, X2, X3, X4, appcB_out_gaga(X5, X1, X6, X4)) -> in_ordercA_out_aa(tree(X1, X2, X3), X4) The argument filtering Pi contains the following mapping: [] = [] in_ordercA_in_aa(x1, x2) = in_ordercA_in_aa in_ordercA_out_aa(x1, x2) = in_ordercA_out_aa(x1, x2) U30_aa(x1, x2, x3, x4, x5) = U30_aa(x5) U31_aa(x1, x2, x3, x4, x5, x6) = U31_aa(x2, x5, x6) U32_aa(x1, x2, x3, x4, x5) = U32_aa(x2, x3, x5) appcB_in_gaga(x1, x2, x3, x4) = appcB_in_gaga(x1, x3) appcB_out_gaga(x1, x2, x3, x4) = appcB_out_gaga(x1, x3, x4) .(x1, x2) = .(x2) U33_gaga(x1, x2, x3, x4, x5, x6) = U33_gaga(x2, x4, x6) tree(x1, x2, x3) = tree(x2, x3) APPB_IN_GAGA(x1, x2, x3, x4) = APPB_IN_GAGA(x1, x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (90) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (91) Obligation: Pi DP problem: The TRS P consists of the following rules: APPB_IN_GAGA(.(X1, X2), X3, X4, .(X1, X5)) -> APPB_IN_GAGA(X2, X3, X4, X5) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) APPB_IN_GAGA(x1, x2, x3, x4) = APPB_IN_GAGA(x1, x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (92) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (93) Obligation: Q DP problem: The TRS P consists of the following rules: APPB_IN_GAGA(.(X2), X4) -> APPB_IN_GAGA(X2, X4) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (94) 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: *APPB_IN_GAGA(.(X2), X4) -> APPB_IN_GAGA(X2, X4) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (95) YES ---------------------------------------- (96) Obligation: Pi DP problem: The TRS P consists of the following rules: IN_ORDERA_IN_AA(tree(X1, X2, X3), X4) -> U2_AA(X1, X2, X3, X4, in_ordercA_in_aa(X2, X5)) U2_AA(X1, X2, X3, X4, in_ordercA_out_aa(X2, X5)) -> IN_ORDERA_IN_AA(X3, X6) IN_ORDERA_IN_AA(tree(X1, X2, X3), X4) -> IN_ORDERA_IN_AA(X2, X5) The TRS R consists of the following rules: in_ordercA_in_aa(void, []) -> in_ordercA_out_aa(void, []) in_ordercA_in_aa(tree(X1, X2, X3), X4) -> U30_aa(X1, X2, X3, X4, in_ordercA_in_aa(X2, X5)) U30_aa(X1, X2, X3, X4, in_ordercA_out_aa(X2, X5)) -> U31_aa(X1, X2, X3, X4, X5, in_ordercA_in_aa(X3, X6)) U31_aa(X1, X2, X3, X4, X5, in_ordercA_out_aa(X3, X6)) -> U32_aa(X1, X2, X3, X4, appcB_in_gaga(X5, X1, X6, X4)) appcB_in_gaga([], X1, X2, .(X1, X2)) -> appcB_out_gaga([], X1, X2, .(X1, X2)) appcB_in_gaga(.(X1, X2), X3, X4, .(X1, X5)) -> U33_gaga(X1, X2, X3, X4, X5, appcB_in_gaga(X2, X3, X4, X5)) U33_gaga(X1, X2, X3, X4, X5, appcB_out_gaga(X2, X3, X4, X5)) -> appcB_out_gaga(.(X1, X2), X3, X4, .(X1, X5)) U32_aa(X1, X2, X3, X4, appcB_out_gaga(X5, X1, X6, X4)) -> in_ordercA_out_aa(tree(X1, X2, X3), X4) The argument filtering Pi contains the following mapping: [] = [] in_ordercA_in_aa(x1, x2) = in_ordercA_in_aa in_ordercA_out_aa(x1, x2) = in_ordercA_out_aa(x1, x2) U30_aa(x1, x2, x3, x4, x5) = U30_aa(x5) U31_aa(x1, x2, x3, x4, x5, x6) = U31_aa(x2, x5, x6) U32_aa(x1, x2, x3, x4, x5) = U32_aa(x2, x3, x5) appcB_in_gaga(x1, x2, x3, x4) = appcB_in_gaga(x1, x3) appcB_out_gaga(x1, x2, x3, x4) = appcB_out_gaga(x1, x3, x4) .(x1, x2) = .(x2) U33_gaga(x1, x2, x3, x4, x5, x6) = U33_gaga(x2, x4, x6) tree(x1, x2, x3) = tree(x2, x3) IN_ORDERA_IN_AA(x1, x2) = IN_ORDERA_IN_AA U2_AA(x1, x2, x3, x4, x5) = U2_AA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (97) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (98) Obligation: Q DP problem: The TRS P consists of the following rules: IN_ORDERA_IN_AA -> U2_AA(in_ordercA_in_aa) U2_AA(in_ordercA_out_aa(X2, X5)) -> IN_ORDERA_IN_AA IN_ORDERA_IN_AA -> IN_ORDERA_IN_AA The TRS R consists of the following rules: in_ordercA_in_aa -> in_ordercA_out_aa(void, []) in_ordercA_in_aa -> U30_aa(in_ordercA_in_aa) U30_aa(in_ordercA_out_aa(X2, X5)) -> U31_aa(X2, X5, in_ordercA_in_aa) U31_aa(X2, X5, in_ordercA_out_aa(X3, X6)) -> U32_aa(X2, X3, appcB_in_gaga(X5, X6)) appcB_in_gaga([], X2) -> appcB_out_gaga([], X2, .(X2)) appcB_in_gaga(.(X2), X4) -> U33_gaga(X2, X4, appcB_in_gaga(X2, X4)) U33_gaga(X2, X4, appcB_out_gaga(X2, X4, X5)) -> appcB_out_gaga(.(X2), X4, .(X5)) U32_aa(X2, X3, appcB_out_gaga(X5, X6, X4)) -> in_ordercA_out_aa(tree(X2, X3), X4) The set Q consists of the following terms: in_ordercA_in_aa U30_aa(x0) U31_aa(x0, x1, x2) appcB_in_gaga(x0, x1) U33_gaga(x0, x1, x2) U32_aa(x0, x1, x2) We have to consider all (P,Q,R)-chains.