/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.pl /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern 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, 7 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, 14 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, 0 ms] (50) QDP (51) PrologToTRSTransformerProof [SOUND, 20 ms] (52) QTRS (53) QTRSRRRProof [EQUIVALENT, 170 ms] (54) QTRS (55) DependencyPairsProof [EQUIVALENT, 0 ms] (56) QDP (57) DependencyGraphProof [EQUIVALENT, 0 ms] (58) AND (59) QDP (60) QDP (61) PrologToIRSwTTransformerProof [SOUND, 38 ms] (62) AND (63) IRSwT (64) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (65) TRUE (66) IRSwT (67) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (68) TRUE (69) IRSwT (70) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (71) IRSwT (72) IntTRSCompressionProof [EQUIVALENT, 26 ms] (73) IRSwT (74) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (75) IRSwT (76) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (77) IRSwT (78) FilterProof [EQUIVALENT, 0 ms] (79) IntTRS (80) IntTRSNonPeriodicNontermProof [COMPLETE, 5 ms] (81) NO (82) PrologToDTProblemTransformerProof [SOUND, 54 ms] (83) TRIPLES (84) TriplesToPiDPProof [SOUND, 49 ms] (85) PiDP (86) DependencyGraphProof [EQUIVALENT, 0 ms] (87) AND (88) PiDP (89) UsableRulesProof [EQUIVALENT, 0 ms] (90) PiDP (91) PiDPToQDPProof [SOUND, 0 ms] (92) QDP (93) QDPSizeChangeProof [EQUIVALENT, 0 ms] (94) YES (95) PiDP (96) UsableRulesProof [EQUIVALENT, 0 ms] (97) PiDP (98) PiDPToQDPProof [SOUND, 0 ms] (99) QDP (100) QDPSizeChangeProof [EQUIVALENT, 0 ms] (101) YES (102) PiDP (103) PiDPToQDPProof [SOUND, 0 ms] (104) 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, 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 ---------------------------------------- (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, 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) ---------------------------------------- (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, 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 ---------------------------------------- (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, 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 ---------------------------------------- (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, 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 ---------------------------------------- (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, 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 ---------------------------------------- (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, 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 ---------------------------------------- (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(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 ---------------------------------------- (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(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. ---------------------------------------- (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) 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 ---------------------------------------- (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) 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) ---------------------------------------- (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) 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 ---------------------------------------- (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) 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 ---------------------------------------- (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) 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 ---------------------------------------- (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) 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 ---------------------------------------- (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) 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 ---------------------------------------- (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(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 ---------------------------------------- (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(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. ---------------------------------------- (51) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 19, "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": { "28": { "goal": [{ "clause": 0, "scope": 1, "term": "(in_order T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "291": { "goal": [{ "clause": 2, "scope": 3, "term": "(app T37 (. T38 T36) X35)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X35"], "exprvars": [] } }, "270": { "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": [] } }, "type": "Nodes", "293": { "goal": [{ "clause": 3, "scope": 3, "term": "(app T37 (. T38 T36) X35)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X35"], "exprvars": [] } }, "272": { "goal": [{ "clause": 0, "scope": 2, "term": "(in_order T15 X15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X15"], "exprvars": [] } }, "273": { "goal": [{ "clause": 1, "scope": 2, "term": "(in_order T15 X15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X15"], "exprvars": [] } }, "295": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "274": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "275": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "297": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "374": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T104 (. T105 T106) T103)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T103"], "free": [], "exprvars": [] } }, "276": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "375": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "299": { "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": [] } }, "257": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "279": { "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": [] } }, "258": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "335": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "259": { "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": [] } }, "336": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "337": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "30": { "goal": [{ "clause": 1, "scope": 1, "term": "(in_order T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "19": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "280": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "260": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "283": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T30 X33)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X33"], "exprvars": [] } }, "284": { "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": [] } }, "285": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T34 X34)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X34"], "exprvars": [] } }, "287": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T37 (. T38 T36) X35)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X35"], "exprvars": [] } }, "266": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T15 X15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X15"], "exprvars": [] } }, "267": { "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": [] } }, "289": { "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": [] } }, "303": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T65 (. T66 T67) X57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X57"], "exprvars": [] } }, "304": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "305": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T19 X16)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X16"], "exprvars": [] } }, "306": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T73 (. T74 T72) T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": [], "exprvars": [] } }, "307": { "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": [] } }, "308": { "goal": [{ "clause": 2, "scope": 4, "term": "(app T73 (. T74 T72) T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": [], "exprvars": [] } }, "309": { "goal": [{ "clause": 3, "scope": 4, "term": "(app T73 (. T74 T72) T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": [], "exprvars": [] } }, "20": { "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": [] } } }, "edges": [ { "from": 19, "to": 20, "label": "CASE" }, { "from": 20, "to": 28, "label": "PARALLEL" }, { "from": 20, "to": 30, "label": "PARALLEL" }, { "from": 28, "to": 256, "label": "EVAL with clause\nin_order(void, []).\nand substitutionT1 -> void,\nT2 -> []" }, { "from": 28, "to": 257, "label": "EVAL-BACKTRACK" }, { "from": 30, "to": 259, "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": 30, "to": 260, "label": "EVAL-BACKTRACK" }, { "from": 256, "to": 258, "label": "SUCCESS" }, { "from": 259, "to": 266, "label": "SPLIT 1" }, { "from": 259, "to": 267, "label": "SPLIT 2\nreplacements:X15 -> T18,\nT16 -> T19,\nT17 -> T20" }, { "from": 266, "to": 270, "label": "CASE" }, { "from": 267, "to": 305, "label": "SPLIT 1" }, { "from": 267, "to": 306, "label": "SPLIT 2\nreplacements:X16 -> T72,\nT18 -> T73,\nT20 -> T74" }, { "from": 270, "to": 272, "label": "PARALLEL" }, { "from": 270, "to": 273, "label": "PARALLEL" }, { "from": 272, "to": 274, "label": "EVAL with clause\nin_order(void, []).\nand substitutionT15 -> void,\nX15 -> []" }, { "from": 272, "to": 275, "label": "EVAL-BACKTRACK" }, { "from": 273, "to": 279, "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": 273, "to": 280, "label": "EVAL-BACKTRACK" }, { "from": 274, "to": 276, "label": "SUCCESS" }, { "from": 279, "to": 283, "label": "SPLIT 1" }, { "from": 279, "to": 284, "label": "SPLIT 2\nreplacements:X33 -> T33,\nT31 -> T34,\nT32 -> T35" }, { "from": 283, "to": 266, "label": "INSTANCE with matching:\nT15 -> T30\nX15 -> X33" }, { "from": 284, "to": 285, "label": "SPLIT 1" }, { "from": 284, "to": 287, "label": "SPLIT 2\nreplacements:X34 -> T36,\nT33 -> T37,\nT35 -> T38" }, { "from": 285, "to": 266, "label": "INSTANCE with matching:\nT15 -> T34\nX15 -> X34" }, { "from": 287, "to": 289, "label": "CASE" }, { "from": 289, "to": 291, "label": "PARALLEL" }, { "from": 289, "to": 293, "label": "PARALLEL" }, { "from": 291, "to": 295, "label": "EVAL with clause\napp([], X42, X42).\nand substitutionT37 -> [],\nT38 -> T51,\nT36 -> T52,\nX42 -> .(T51, T52),\nX35 -> .(T51, T52)" }, { "from": 291, "to": 297, "label": "EVAL-BACKTRACK" }, { "from": 293, "to": 303, "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": 293, "to": 304, "label": "EVAL-BACKTRACK" }, { "from": 295, "to": 299, "label": "SUCCESS" }, { "from": 303, "to": 287, "label": "INSTANCE with matching:\nT37 -> T65\nT38 -> T66\nT36 -> T67\nX35 -> X57" }, { "from": 305, "to": 266, "label": "INSTANCE with matching:\nT15 -> T19\nX15 -> X16" }, { "from": 306, "to": 307, "label": "CASE" }, { "from": 307, "to": 308, "label": "PARALLEL" }, { "from": 307, "to": 309, "label": "PARALLEL" }, { "from": 308, "to": 335, "label": "EVAL with clause\napp([], X66, X66).\nand substitutionT73 -> [],\nT74 -> T87,\nT72 -> T88,\nX66 -> .(T87, T88),\nT14 -> .(T87, T88)" }, { "from": 308, "to": 336, "label": "EVAL-BACKTRACK" }, { "from": 309, "to": 374, "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": 309, "to": 375, "label": "EVAL-BACKTRACK" }, { "from": 335, "to": 337, "label": "SUCCESS" }, { "from": 374, "to": 306, "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: f19_in([]) -> f19_out1 f19_in(T14) -> U1(f259_in(T14), T14) U1(f259_out1(X15, T17, X16), T14) -> f19_out1 f266_in -> f266_out1 f266_in -> U2(f279_in) U2(f279_out1) -> f266_out1 f287_in -> f287_out1 f287_in -> U3(f287_in) U3(f287_out1) -> f287_out1 f306_in(.(T87, T88)) -> f306_out1([], T87, T88) f306_in(.(T99, T103)) -> U4(f306_in(T103), .(T99, T103)) U4(f306_out1(T104, T105, T106), .(T99, T103)) -> f306_out1(.(T99, T104), T105, T106) f259_in(T14) -> U5(f266_in, T14) U5(f266_out1, T14) -> U6(f267_in(T14), T14) U6(f267_out1(T18, T20, X16), T14) -> f259_out1(T18, T20, X16) f267_in(T14) -> U7(f266_in, T14) U7(f266_out1, T14) -> U8(f306_in(T14), T14) U8(f306_out1(T73, T74, T72), T14) -> f267_out1(T73, T74, T72) f279_in -> U9(f266_in) U9(f266_out1) -> U10(f284_in) U10(f284_out1) -> f279_out1 f284_in -> U11(f266_in) U11(f266_out1) -> U12(f287_in) U12(f287_out1) -> f284_out1 Q is empty. ---------------------------------------- (53) QTRSRRRProof (EQUIVALENT) Used ordering: f19_in/1(YES) []/0) f19_out1/0) U1/2(YES,YES) f259_in/1(YES) f259_out1/3(YES,YES,YES) f266_in/0) f266_out1/0) U2/1)YES( f279_in/0) f279_out1/0) f287_in/0) f287_out1/0) U3/1)YES( f306_in/1(YES) ./2(YES,YES) f306_out1/3(YES,YES,YES) U4/2(YES,YES) U5/2(YES,YES) U6/2(YES,YES) f267_in/1(YES) f267_out1/3(YES,YES,YES) U7/2(YES,YES) U8/2(YES,YES) U9/1)YES( U10/1)YES( f284_in/0) f284_out1/0) U11/1)YES( U12/1)YES( Quasi precedence: f19_in_1 > U1_2 > f19_out1 > f306_out1_3 f19_in_1 > f259_in_1 > U5_2 > [f266_in, f266_out1, f279_in, f279_out1, f287_in, f287_out1, f267_in_1, f284_in, f284_out1] > U7_2 > f306_in_1 > [] > f306_out1_3 f19_in_1 > f259_in_1 > U5_2 > [f266_in, f266_out1, f279_in, f279_out1, f287_in, f287_out1, f267_in_1, f284_in, f284_out1] > U7_2 > f306_in_1 > U4_2 > ._2 > f306_out1_3 f19_in_1 > f259_in_1 > U5_2 > [f266_in, f266_out1, f279_in, f279_out1, f287_in, f287_out1, f267_in_1, f284_in, f284_out1] > U7_2 > [f267_out1_3, U8_2] > f306_out1_3 f19_in_1 > f259_in_1 > U5_2 > U6_2 > f259_out1_3 > f19_out1 > f306_out1_3 Status: f19_in_1: multiset status []: multiset status f19_out1: multiset status U1_2: multiset status f259_in_1: multiset status f259_out1_3: [3,2,1] f266_in: multiset status f266_out1: multiset status f279_in: multiset status f279_out1: multiset status f287_in: multiset status f287_out1: multiset status f306_in_1: [1] ._2: multiset status f306_out1_3: multiset status U4_2: multiset status U5_2: multiset status U6_2: multiset status f267_in_1: [1] f267_out1_3: multiset status U7_2: multiset status U8_2: multiset status f284_in: multiset status f284_out1: multiset status With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: f19_in([]) -> f19_out1 f19_in(T14) -> U1(f259_in(T14), T14) U1(f259_out1(X15, T17, X16), T14) -> f19_out1 f306_in(.(T87, T88)) -> f306_out1([], T87, T88) f306_in(.(T99, T103)) -> U4(f306_in(T103), .(T99, T103)) U4(f306_out1(T104, T105, T106), .(T99, T103)) -> f306_out1(.(T99, T104), T105, T106) f259_in(T14) -> U5(f266_in, T14) U5(f266_out1, T14) -> U6(f267_in(T14), T14) U6(f267_out1(T18, T20, X16), T14) -> f259_out1(T18, T20, X16) f267_in(T14) -> U7(f266_in, T14) U7(f266_out1, T14) -> U8(f306_in(T14), T14) U8(f306_out1(T73, T74, T72), T14) -> f267_out1(T73, T74, T72) ---------------------------------------- (54) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f266_in -> f266_out1 f266_in -> U2(f279_in) U2(f279_out1) -> f266_out1 f287_in -> f287_out1 f287_in -> U3(f287_in) U3(f287_out1) -> f287_out1 f279_in -> U9(f266_in) U9(f266_out1) -> U10(f284_in) U10(f284_out1) -> f279_out1 f284_in -> U11(f266_in) U11(f266_out1) -> U12(f287_in) U12(f287_out1) -> f284_out1 Q is empty. ---------------------------------------- (55) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (56) Obligation: Q DP problem: The TRS P consists of the following rules: F266_IN -> U2^1(f279_in) F266_IN -> F279_IN F287_IN -> U3^1(f287_in) F287_IN -> F287_IN F279_IN -> U9^1(f266_in) F279_IN -> F266_IN U9^1(f266_out1) -> U10^1(f284_in) U9^1(f266_out1) -> F284_IN F284_IN -> U11^1(f266_in) F284_IN -> F266_IN U11^1(f266_out1) -> U12^1(f287_in) U11^1(f266_out1) -> F287_IN The TRS R consists of the following rules: f266_in -> f266_out1 f266_in -> U2(f279_in) U2(f279_out1) -> f266_out1 f287_in -> f287_out1 f287_in -> U3(f287_in) U3(f287_out1) -> f287_out1 f279_in -> U9(f266_in) U9(f266_out1) -> U10(f284_in) U10(f284_out1) -> f279_out1 f284_in -> U11(f266_in) U11(f266_out1) -> U12(f287_in) U12(f287_out1) -> f284_out1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (57) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 6 less nodes. ---------------------------------------- (58) Complex Obligation (AND) ---------------------------------------- (59) Obligation: Q DP problem: The TRS P consists of the following rules: F287_IN -> F287_IN The TRS R consists of the following rules: f266_in -> f266_out1 f266_in -> U2(f279_in) U2(f279_out1) -> f266_out1 f287_in -> f287_out1 f287_in -> U3(f287_in) U3(f287_out1) -> f287_out1 f279_in -> U9(f266_in) U9(f266_out1) -> U10(f284_in) U10(f284_out1) -> f279_out1 f284_in -> U11(f266_in) U11(f266_out1) -> U12(f287_in) U12(f287_out1) -> f284_out1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (60) Obligation: Q DP problem: The TRS P consists of the following rules: F266_IN -> F279_IN F279_IN -> U9^1(f266_in) U9^1(f266_out1) -> F284_IN F284_IN -> F266_IN F279_IN -> F266_IN The TRS R consists of the following rules: f266_in -> f266_out1 f266_in -> U2(f279_in) U2(f279_out1) -> f266_out1 f287_in -> f287_out1 f287_in -> U3(f287_in) U3(f287_out1) -> f287_out1 f279_in -> U9(f266_in) U9(f266_out1) -> U10(f284_in) U10(f284_out1) -> f279_out1 f284_in -> U11(f266_in) U11(f266_out1) -> U12(f287_in) U12(f287_out1) -> f284_out1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (61) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 25, "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": { "25": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "26": { "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": [] } }, "27": { "goal": [{ "clause": 0, "scope": 1, "term": "(in_order T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "29": { "goal": [{ "clause": 1, "scope": 1, "term": "(in_order T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "290": { "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": [] } }, "292": { "goal": [{ "clause": 2, "scope": 3, "term": "(app T37 (. T38 T36) X35)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X35"], "exprvars": [] } }, "type": "Nodes", "271": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "294": { "goal": [{ "clause": 3, "scope": 3, "term": "(app T37 (. T38 T36) X35)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X35"], "exprvars": [] } }, "296": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "133": { "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": [] } }, "298": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "134": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "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": [] } }, "310": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T19 X16)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X16"], "exprvars": [] } }, "278": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "311": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T73 (. T74 T72) T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": [], "exprvars": [] } }, "314": { "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": [] } }, "316": { "goal": [{ "clause": 2, "scope": 4, "term": "(app T73 (. T74 T72) T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": [], "exprvars": [] } }, "317": { "goal": [{ "clause": 3, "scope": 4, "term": "(app T73 (. T74 T72) T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": [], "exprvars": [] } }, "33": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "34": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "281": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T30 X33)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X33"], "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": [] } }, "261": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T15 X15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X15"], "exprvars": [] } }, "262": { "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": [] } }, "263": { "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": [] } }, "264": { "goal": [{ "clause": 0, "scope": 2, "term": "(in_order T15 X15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X15"], "exprvars": [] } }, "286": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T34 X34)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X34"], "exprvars": [] } }, "265": { "goal": [{ "clause": 1, "scope": 2, "term": "(in_order T15 X15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X15"], "exprvars": [] } }, "320": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "288": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T37 (. T38 T36) X35)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X35"], "exprvars": [] } }, "321": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "300": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "268": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "301": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T65 (. T66 T67) X57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X57"], "exprvars": [] } }, "323": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "269": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "302": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "128": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "328": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T104 (. T105 T106) T103)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T103"], "free": [], "exprvars": [] } }, "329": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 25, "to": 26, "label": "CASE" }, { "from": 26, "to": 27, "label": "PARALLEL" }, { "from": 26, "to": 29, "label": "PARALLEL" }, { "from": 27, "to": 33, "label": "EVAL with clause\nin_order(void, []).\nand substitutionT1 -> void,\nT2 -> []" }, { "from": 27, "to": 34, "label": "EVAL-BACKTRACK" }, { "from": 29, "to": 133, "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": 29, "to": 134, "label": "EVAL-BACKTRACK" }, { "from": 33, "to": 128, "label": "SUCCESS" }, { "from": 133, "to": 261, "label": "SPLIT 1" }, { "from": 133, "to": 262, "label": "SPLIT 2\nreplacements:X15 -> T18,\nT16 -> T19,\nT17 -> T20" }, { "from": 261, "to": 263, "label": "CASE" }, { "from": 262, "to": 310, "label": "SPLIT 1" }, { "from": 262, "to": 311, "label": "SPLIT 2\nreplacements:X16 -> T72,\nT18 -> T73,\nT20 -> T74" }, { "from": 263, "to": 264, "label": "PARALLEL" }, { "from": 263, "to": 265, "label": "PARALLEL" }, { "from": 264, "to": 268, "label": "EVAL with clause\nin_order(void, []).\nand substitutionT15 -> void,\nX15 -> []" }, { "from": 264, "to": 269, "label": "EVAL-BACKTRACK" }, { "from": 265, "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": 265, "to": 278, "label": "EVAL-BACKTRACK" }, { "from": 268, "to": 271, "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": 261, "label": "INSTANCE with matching:\nT15 -> T30\nX15 -> X33" }, { "from": 282, "to": 286, "label": "SPLIT 1" }, { "from": 282, "to": 288, "label": "SPLIT 2\nreplacements:X34 -> T36,\nT33 -> T37,\nT35 -> T38" }, { "from": 286, "to": 261, "label": "INSTANCE with matching:\nT15 -> T34\nX15 -> X34" }, { "from": 288, "to": 290, "label": "CASE" }, { "from": 290, "to": 292, "label": "PARALLEL" }, { "from": 290, "to": 294, "label": "PARALLEL" }, { "from": 292, "to": 296, "label": "EVAL with clause\napp([], X42, X42).\nand substitutionT37 -> [],\nT38 -> T51,\nT36 -> T52,\nX42 -> .(T51, T52),\nX35 -> .(T51, T52)" }, { "from": 292, "to": 298, "label": "EVAL-BACKTRACK" }, { "from": 294, "to": 301, "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": 294, "to": 302, "label": "EVAL-BACKTRACK" }, { "from": 296, "to": 300, "label": "SUCCESS" }, { "from": 301, "to": 288, "label": "INSTANCE with matching:\nT37 -> T65\nT38 -> T66\nT36 -> T67\nX35 -> X57" }, { "from": 310, "to": 261, "label": "INSTANCE with matching:\nT15 -> T19\nX15 -> X16" }, { "from": 311, "to": 314, "label": "CASE" }, { "from": 314, "to": 316, "label": "PARALLEL" }, { "from": 314, "to": 317, "label": "PARALLEL" }, { "from": 316, "to": 320, "label": "EVAL with clause\napp([], X66, X66).\nand substitutionT73 -> [],\nT74 -> T87,\nT72 -> T88,\nX66 -> .(T87, T88),\nT14 -> .(T87, T88)" }, { "from": 316, "to": 321, "label": "EVAL-BACKTRACK" }, { "from": 317, "to": 328, "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": 317, "to": 329, "label": "EVAL-BACKTRACK" }, { "from": 320, "to": 323, "label": "SUCCESS" }, { "from": 328, "to": 311, "label": "INSTANCE with matching:\nT73 -> T104\nT74 -> T105\nT72 -> T106\nT14 -> T103" } ], "type": "Graph" } } ---------------------------------------- (62) Complex Obligation (AND) ---------------------------------------- (63) Obligation: Rules: f328_in(T103) -> f311_in(T103) :|: TRUE f311_out(x) -> f328_out(x) :|: TRUE f329_out -> f317_out(T14) :|: TRUE f317_in(x1) -> f329_in :|: TRUE f328_out(x2) -> f317_out(.(x3, x2)) :|: TRUE f317_in(.(x4, x5)) -> f328_in(x5) :|: TRUE f314_in(x6) -> f317_in(x6) :|: TRUE f314_in(x7) -> f316_in(x7) :|: TRUE f316_out(x8) -> f314_out(x8) :|: TRUE f317_out(x9) -> f314_out(x9) :|: TRUE f314_out(x10) -> f311_out(x10) :|: TRUE f311_in(x11) -> f314_in(x11) :|: TRUE f25_in(T2) -> f26_in(T2) :|: TRUE f26_out(x12) -> f25_out(x12) :|: TRUE f27_out(x13) -> f26_out(x13) :|: TRUE f26_in(x14) -> f27_in(x14) :|: TRUE f29_out(x15) -> f26_out(x15) :|: TRUE f26_in(x16) -> f29_in(x16) :|: TRUE f29_in(x17) -> f133_in(x17) :|: TRUE f29_in(x18) -> f134_in :|: TRUE f133_out(x19) -> f29_out(x19) :|: TRUE f134_out -> f29_out(x20) :|: TRUE f262_out(x21) -> f133_out(x21) :|: TRUE f261_out -> f262_in(x22) :|: TRUE f133_in(x23) -> f261_in :|: TRUE f310_out -> f311_in(x24) :|: TRUE f311_out(x25) -> f262_out(x25) :|: TRUE f262_in(x26) -> f310_in :|: TRUE Start term: f25_in(T2) ---------------------------------------- (64) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (65) TRUE ---------------------------------------- (66) Obligation: Rules: f288_in -> f290_in :|: TRUE f290_out -> f288_out :|: TRUE f301_out -> f294_out :|: TRUE f302_out -> f294_out :|: TRUE f294_in -> f301_in :|: TRUE f294_in -> f302_in :|: TRUE f288_out -> f301_out :|: TRUE f301_in -> f288_in :|: TRUE f290_in -> f292_in :|: TRUE f290_in -> f294_in :|: TRUE f294_out -> f290_out :|: TRUE f292_out -> f290_out :|: TRUE f25_in(T2) -> f26_in(T2) :|: TRUE f26_out(x) -> f25_out(x) :|: TRUE f27_out(x1) -> f26_out(x1) :|: TRUE f26_in(x2) -> f27_in(x2) :|: TRUE f29_out(x3) -> f26_out(x3) :|: TRUE f26_in(x4) -> f29_in(x4) :|: TRUE f29_in(T14) -> f133_in(T14) :|: TRUE f29_in(x5) -> f134_in :|: TRUE f133_out(x6) -> f29_out(x6) :|: TRUE f134_out -> f29_out(x7) :|: TRUE f262_out(x8) -> f133_out(x8) :|: TRUE f261_out -> f262_in(x9) :|: TRUE f133_in(x10) -> f261_in :|: TRUE f310_out -> f311_in(x11) :|: TRUE f311_out(x12) -> f262_out(x12) :|: TRUE f262_in(x13) -> f310_in :|: TRUE f261_out -> f310_out :|: TRUE f310_in -> f261_in :|: TRUE f261_in -> f263_in :|: TRUE f263_out -> f261_out :|: TRUE f263_in -> f264_in :|: TRUE f263_in -> f265_in :|: TRUE f265_out -> f263_out :|: TRUE f264_out -> f263_out :|: TRUE f265_in -> f278_in :|: TRUE f278_out -> f265_out :|: TRUE f265_in -> f277_in :|: TRUE f277_out -> f265_out :|: TRUE f277_in -> f281_in :|: TRUE f281_out -> f282_in :|: TRUE f282_out -> f277_out :|: TRUE f282_in -> f286_in :|: TRUE f288_out -> f282_out :|: TRUE f286_out -> f288_in :|: TRUE Start term: f25_in(T2) ---------------------------------------- (67) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (68) TRUE ---------------------------------------- (69) Obligation: Rules: f288_in -> f290_in :|: TRUE f290_out -> f288_out :|: TRUE f261_in -> f263_in :|: TRUE f263_out -> f261_out :|: TRUE f296_in -> f296_out :|: TRUE f263_in -> f264_in :|: TRUE f263_in -> f265_in :|: TRUE f265_out -> f263_out :|: TRUE f264_out -> f263_out :|: TRUE f282_in -> f286_in :|: TRUE f288_out -> f282_out :|: TRUE f286_out -> f288_in :|: TRUE f265_in -> f278_in :|: TRUE f278_out -> f265_out :|: TRUE f265_in -> f277_in :|: TRUE f277_out -> f265_out :|: TRUE f301_out -> f294_out :|: TRUE f302_out -> f294_out :|: TRUE f294_in -> f301_in :|: TRUE f294_in -> f302_in :|: TRUE f288_out -> f301_out :|: TRUE f301_in -> f288_in :|: TRUE f286_in -> f261_in :|: TRUE f261_out -> f286_out :|: TRUE f290_in -> f292_in :|: TRUE f290_in -> f294_in :|: TRUE f294_out -> f290_out :|: TRUE f292_out -> f290_out :|: TRUE f277_in -> f281_in :|: TRUE f281_out -> f282_in :|: TRUE f282_out -> f277_out :|: TRUE f298_out -> f292_out :|: TRUE f292_in -> f296_in :|: TRUE f296_out -> f292_out :|: TRUE f292_in -> f298_in :|: TRUE f281_in -> f261_in :|: TRUE f261_out -> f281_out :|: TRUE f25_in(T2) -> f26_in(T2) :|: TRUE f26_out(x) -> f25_out(x) :|: TRUE f27_out(x1) -> f26_out(x1) :|: TRUE f26_in(x2) -> f27_in(x2) :|: TRUE f29_out(x3) -> f26_out(x3) :|: TRUE f26_in(x4) -> f29_in(x4) :|: TRUE f29_in(T14) -> f133_in(T14) :|: TRUE f29_in(x5) -> f134_in :|: TRUE f133_out(x6) -> f29_out(x6) :|: TRUE f134_out -> f29_out(x7) :|: TRUE f262_out(x8) -> f133_out(x8) :|: TRUE f261_out -> f262_in(x9) :|: TRUE f133_in(x10) -> f261_in :|: TRUE f310_out -> f311_in(x11) :|: TRUE f311_out(x12) -> f262_out(x12) :|: TRUE f262_in(x13) -> f310_in :|: TRUE f261_out -> f310_out :|: TRUE f310_in -> f261_in :|: TRUE Start term: f25_in(T2) ---------------------------------------- (70) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f261_in -> f263_in :|: TRUE f263_in -> f265_in :|: TRUE f265_in -> f277_in :|: TRUE f277_in -> f281_in :|: TRUE f281_in -> f261_in :|: TRUE ---------------------------------------- (71) Obligation: Rules: f261_in -> f263_in :|: TRUE f263_in -> f265_in :|: TRUE f265_in -> f277_in :|: TRUE f277_in -> f281_in :|: TRUE f281_in -> f261_in :|: TRUE ---------------------------------------- (72) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (73) Obligation: Rules: f261_in -> f261_in :|: TRUE ---------------------------------------- (74) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (75) Obligation: Rules: f261_in -> f261_in :|: TRUE ---------------------------------------- (76) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f261_in -> f261_in :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (77) Obligation: Termination digraph: Nodes: (1) f261_in -> f261_in :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (78) FilterProof (EQUIVALENT) Used the following sort dictionary for filtering: f261_in() Replaced non-predefined constructor symbols by 0. ---------------------------------------- (79) Obligation: Rules: f261_in -> f261_in :|: TRUE ---------------------------------------- (80) 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)) ---------------------------------------- (81) NO ---------------------------------------- (82) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 2, "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": { "44": { "goal": [{ "clause": 1, "scope": 1, "term": "(in_order T1 ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "390": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T132 X100)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X100"], "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", "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": [] } }, "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": [] } }, "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": [] } }, "395": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "110": { "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": [] } }, "396": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "397": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "430": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T182 X100)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X100"], "exprvars": [] } }, "398": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "431": { "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": [] } }, "234": { "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": [] } }, "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": [] } }, "432": { "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": [] } }, "312": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T29 X28)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X28"], "exprvars": [] } }, "433": { "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": [] } }, "236": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "313": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T32 (. T33 T31) X29)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X29"], "exprvars": [] } }, "434": { "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": [] } }, "435": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "315": { "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": [] } }, "436": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "437": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "92": { "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": [] } }, "438": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T222 (. T223 T224) T221)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T221"], "free": [], "exprvars": [] } }, "318": { "goal": [{ "clause": 2, "scope": 4, "term": "(app T32 (. T33 T31) X29)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X29"], "exprvars": [] } }, "439": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "319": { "goal": [{ "clause": 3, "scope": 4, "term": "(app T32 (. T33 T31) X29)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X29"], "exprvars": [] } }, "440": { "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": [] } }, "122": { "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": [] } }, "441": { "goal": [{ "clause": 2, "scope": 10, "term": "(app T222 (. T223 T224) T221)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T221"], "free": [], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "442": { "goal": [{ "clause": 3, "scope": 10, "term": "(app T222 (. T223 T224) T221)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T221"], "free": [], "exprvars": [] } }, "322": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "443": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "4": { "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": [] } }, "125": { "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": [] } }, "444": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "126": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (in_order T12 X10) (app ([]) (. T13 X10) ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X10"], "exprvars": [] } }, "247": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T25 X27)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X27"], "exprvars": [] } }, "324": { "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": [] } }, "445": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "127": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "248": { "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": [] } }, "325": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "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": [] } }, "446": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T254 (. T255 T256) T253)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T253"], "free": [], "exprvars": [] } }, "326": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T60 (. T61 T62) X51)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X51"], "exprvars": [] } }, "403": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T166 X129)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X129"], "exprvars": [] } }, "447": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "327": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "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": [] } }, "208": { "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": [] } }, "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": [] } }, "370": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T82 X77)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X77"], "exprvars": [] } }, "371": { "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": [] } }, "372": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T88 X78)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X78"], "exprvars": [] } }, "373": { "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": [] } }, "330": { "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": [] } }, "210": { "goal": [{ "clause": 0, "scope": 3, "term": "(in_order T12 X10)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X10"], "exprvars": [] } }, "331": { "goal": [{ "clause": 3, "scope": 5, "term": "(app ([]) (. T15 T14) ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "332": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "376": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T93 (. T94 T92) X79)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X79"], "exprvars": [] } }, "212": { "goal": [{ "clause": 1, "scope": 3, "term": "(in_order T12 X10)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X10"], "exprvars": [] } }, "333": { "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": [] } }, "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": [] } }, "136": { "goal": [{ "clause": -1, "scope": -1, "term": "(in_order T12 X10)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X10"], "exprvars": [] } }, "213": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "334": { "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": [] } }, "137": { "goal": [{ "clause": -1, "scope": -1, "term": "(app ([]) (. T15 T14) ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "214": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "379": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T109 (. T110 T108) ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "215": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "31": { "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": [] } }, "32": { "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": [] } }, "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": [] } }, "384": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "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": [] } }, "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": [] } }, "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": [] } }, "102": { "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": [] } }, "389": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 4, "label": "CASE" }, { "from": 4, "to": 31, "label": "EVAL with clause\nin_order(void, []).\nand substitutionT1 -> void,\nT2 -> []" }, { "from": 4, "to": 32, "label": "EVAL-BACKTRACK" }, { "from": 31, "to": 44, "label": "SUCCESS" }, { "from": 32, "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": 32, "to": 384, "label": "EVAL-BACKTRACK" }, { "from": 44, "to": 92, "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": 44, "to": 102, "label": "EVAL-BACKTRACK" }, { "from": 92, "to": 110, "label": "CASE" }, { "from": 110, "to": 122, "label": "PARALLEL" }, { "from": 110, "to": 125, "label": "PARALLEL" }, { "from": 122, "to": 126, "label": "EVAL with clause\nin_order(void, []).\nand substitutionT9 -> void,\nX9 -> [],\nT10 -> T12,\nT11 -> T13" }, { "from": 122, "to": 127, "label": "EVAL-BACKTRACK" }, { "from": 125, "to": 333, "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": 125, "to": 334, "label": "EVAL-BACKTRACK" }, { "from": 126, "to": 136, "label": "SPLIT 1" }, { "from": 126, "to": 137, "label": "SPLIT 2\nreplacements:X10 -> T14,\nT13 -> T15" }, { "from": 136, "to": 208, "label": "CASE" }, { "from": 137, "to": 330, "label": "CASE" }, { "from": 208, "to": 210, "label": "PARALLEL" }, { "from": 208, "to": 212, "label": "PARALLEL" }, { "from": 210, "to": 213, "label": "EVAL with clause\nin_order(void, []).\nand substitutionT12 -> void,\nX10 -> []" }, { "from": 210, "to": 214, "label": "EVAL-BACKTRACK" }, { "from": 212, "to": 234, "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": 212, "to": 236, "label": "EVAL-BACKTRACK" }, { "from": 213, "to": 215, "label": "SUCCESS" }, { "from": 234, "to": 247, "label": "SPLIT 1" }, { "from": 234, "to": 248, "label": "SPLIT 2\nreplacements:X27 -> T28,\nT26 -> T29,\nT27 -> T30" }, { "from": 247, "to": 136, "label": "INSTANCE with matching:\nT12 -> T25\nX10 -> X27" }, { "from": 248, "to": 312, "label": "SPLIT 1" }, { "from": 248, "to": 313, "label": "SPLIT 2\nreplacements:X28 -> T31,\nT28 -> T32,\nT30 -> T33" }, { "from": 312, "to": 136, "label": "INSTANCE with matching:\nT12 -> T29\nX10 -> X28" }, { "from": 313, "to": 315, "label": "CASE" }, { "from": 315, "to": 318, "label": "PARALLEL" }, { "from": 315, "to": 319, "label": "PARALLEL" }, { "from": 318, "to": 322, "label": "EVAL with clause\napp([], X36, X36).\nand substitutionT32 -> [],\nT33 -> T46,\nT31 -> T47,\nX36 -> .(T46, T47),\nX29 -> .(T46, T47)" }, { "from": 318, "to": 324, "label": "EVAL-BACKTRACK" }, { "from": 319, "to": 326, "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": 319, "to": 327, "label": "EVAL-BACKTRACK" }, { "from": 322, "to": 325, "label": "SUCCESS" }, { "from": 326, "to": 313, "label": "INSTANCE with matching:\nT32 -> T60\nT33 -> T61\nT31 -> T62\nX29 -> X51" }, { "from": 330, "to": 331, "label": "BACKTRACK\nfor clause: app([], X, X)because of non-unification" }, { "from": 331, "to": 332, "label": "BACKTRACK\nfor clause: app(.(X, Xs), Ys, .(X, Zs)) :- app(Xs, Ys, Zs)because of non-unification" }, { "from": 333, "to": 370, "label": "SPLIT 1" }, { "from": 333, "to": 371, "label": "SPLIT 2\nreplacements:X77 -> T87,\nT83 -> T88,\nT84 -> T89,\nT85 -> T90,\nT86 -> T91" }, { "from": 370, "to": 136, "label": "INSTANCE with matching:\nT12 -> T82\nX10 -> X77" }, { "from": 371, "to": 372, "label": "SPLIT 1" }, { "from": 371, "to": 373, "label": "SPLIT 2\nreplacements:X78 -> T92,\nT87 -> T93,\nT89 -> T94,\nT90 -> T95,\nT91 -> T96" }, { "from": 372, "to": 136, "label": "INSTANCE with matching:\nT12 -> T88\nX10 -> X78" }, { "from": 373, "to": 376, "label": "SPLIT 1" }, { "from": 373, "to": 377, "label": "SPLIT 2\nreplacements:X79 -> T101,\nT95 -> T102,\nT96 -> T103" }, { "from": 376, "to": 313, "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": 136, "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": 136, "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": 136, "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": 136, "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": 313, "label": "INSTANCE with matching:\nT32 -> T172\nT33 -> T173\nT31 -> T171\nX29 -> X130" }, { "from": 406, "to": 430, "label": "SPLIT 1" }, { "from": 406, "to": 431, "label": "SPLIT 2\nreplacements:X100 -> T189,\nT181 -> T190,\nT183 -> T191,\nT184 -> T192" }, { "from": 430, "to": 136, "label": "INSTANCE with matching:\nT12 -> T182\nX10 -> X100" }, { "from": 431, "to": 432, "label": "CASE" }, { "from": 432, "to": 433, "label": "PARALLEL" }, { "from": 432, "to": 434, "label": "PARALLEL" }, { "from": 433, "to": 435, "label": "EVAL with clause\napp([], X141, X141).\nand substitutionT190 -> [],\nT191 -> T205,\nT189 -> T206,\nX141 -> .(T205, T206),\nT128 -> .(T205, T206)" }, { "from": 433, "to": 436, "label": "EVAL-BACKTRACK" }, { "from": 434, "to": 438, "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": 434, "to": 439, "label": "EVAL-BACKTRACK" }, { "from": 435, "to": 437, "label": "SUCCESS" }, { "from": 438, "to": 440, "label": "CASE" }, { "from": 440, "to": 441, "label": "PARALLEL" }, { "from": 440, "to": 442, "label": "PARALLEL" }, { "from": 441, "to": 443, "label": "EVAL with clause\napp([], X160, X160).\nand substitutionT222 -> [],\nT223 -> T237,\nT224 -> T238,\nX160 -> .(T237, T238),\nT221 -> .(T237, T238)" }, { "from": 441, "to": 444, "label": "EVAL-BACKTRACK" }, { "from": 442, "to": 446, "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": 442, "to": 447, "label": "EVAL-BACKTRACK" }, { "from": 443, "to": 445, "label": "SUCCESS" }, { "from": 446, "to": 438, "label": "INSTANCE with matching:\nT222 -> T254\nT223 -> T255\nT224 -> T256\nT221 -> T253" } ], "type": "Graph" } } ---------------------------------------- (83) 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) ---------------------------------------- (84) 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 ---------------------------------------- (85) 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 ---------------------------------------- (86) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 39 less nodes. ---------------------------------------- (87) Complex Obligation (AND) ---------------------------------------- (88) 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 ---------------------------------------- (89) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (90) 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 ---------------------------------------- (91) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (92) 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. ---------------------------------------- (93) 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 ---------------------------------------- (94) YES ---------------------------------------- (95) 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 ---------------------------------------- (96) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (97) 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 ---------------------------------------- (98) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (99) 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. ---------------------------------------- (100) 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 ---------------------------------------- (101) YES ---------------------------------------- (102) 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 ---------------------------------------- (103) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (104) 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.