3.84/1.79 YES 4.17/1.89 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 4.17/1.89 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.17/1.89 4.17/1.89 4.17/1.89 Left Termination of the query pattern 4.17/1.89 4.17/1.89 int(g,g,a) 4.17/1.89 4.17/1.89 w.r.t. the given Prolog program could successfully be proven: 4.17/1.89 4.17/1.89 (0) Prolog 4.17/1.89 (1) PrologToPiTRSProof [SOUND, 0 ms] 4.17/1.89 (2) PiTRS 4.17/1.89 (3) DependencyPairsProof [EQUIVALENT, 14 ms] 4.17/1.89 (4) PiDP 4.17/1.89 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 4.17/1.89 (6) AND 4.17/1.89 (7) PiDP 4.17/1.89 (8) UsableRulesProof [EQUIVALENT, 0 ms] 4.17/1.89 (9) PiDP 4.17/1.89 (10) PiDPToQDPProof [SOUND, 14 ms] 4.17/1.89 (11) QDP 4.17/1.89 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.17/1.89 (13) YES 4.17/1.89 (14) PiDP 4.17/1.89 (15) UsableRulesProof [EQUIVALENT, 0 ms] 4.17/1.89 (16) PiDP 4.17/1.89 (17) PiDPToQDPProof [SOUND, 0 ms] 4.17/1.89 (18) QDP 4.17/1.89 (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.17/1.89 (20) YES 4.17/1.89 4.17/1.89 4.17/1.89 ---------------------------------------- 4.17/1.89 4.17/1.89 (0) 4.17/1.89 Obligation: 4.17/1.89 Clauses: 4.17/1.89 4.17/1.89 intlist([], []). 4.17/1.89 intlist(.(X, XS), .(s(X), YS)) :- intlist(XS, YS). 4.17/1.89 int(0, 0, .(0, [])). 4.17/1.89 int(0, s(Y), .(0, XS)) :- int(s(0), s(Y), XS). 4.17/1.89 int(s(X), 0, []). 4.17/1.89 int(s(X), s(Y), XS) :- ','(int(X, Y, ZS), intlist(ZS, XS)). 4.17/1.89 4.17/1.89 4.17/1.89 Query: int(g,g,a) 4.17/1.89 ---------------------------------------- 4.17/1.89 4.17/1.89 (1) PrologToPiTRSProof (SOUND) 4.17/1.89 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 4.17/1.89 4.17/1.89 int_in_3: (b,b,f) 4.17/1.89 4.17/1.89 intlist_in_2: (b,f) 4.17/1.89 4.17/1.89 Transforming Prolog into the following Term Rewriting System: 4.17/1.89 4.17/1.89 Pi-finite rewrite system: 4.17/1.89 The TRS R consists of the following rules: 4.17/1.89 4.17/1.89 int_in_gga(0, 0, .(0, [])) -> int_out_gga(0, 0, .(0, [])) 4.17/1.89 int_in_gga(0, s(Y), .(0, XS)) -> U2_gga(Y, XS, int_in_gga(s(0), s(Y), XS)) 4.17/1.89 int_in_gga(s(X), 0, []) -> int_out_gga(s(X), 0, []) 4.17/1.89 int_in_gga(s(X), s(Y), XS) -> U3_gga(X, Y, XS, int_in_gga(X, Y, ZS)) 4.17/1.89 U3_gga(X, Y, XS, int_out_gga(X, Y, ZS)) -> U4_gga(X, Y, XS, intlist_in_ga(ZS, XS)) 4.17/1.89 intlist_in_ga([], []) -> intlist_out_ga([], []) 4.17/1.89 intlist_in_ga(.(X, XS), .(s(X), YS)) -> U1_ga(X, XS, YS, intlist_in_ga(XS, YS)) 4.17/1.89 U1_ga(X, XS, YS, intlist_out_ga(XS, YS)) -> intlist_out_ga(.(X, XS), .(s(X), YS)) 4.17/1.89 U4_gga(X, Y, XS, intlist_out_ga(ZS, XS)) -> int_out_gga(s(X), s(Y), XS) 4.17/1.89 U2_gga(Y, XS, int_out_gga(s(0), s(Y), XS)) -> int_out_gga(0, s(Y), .(0, XS)) 4.17/1.89 4.17/1.89 The argument filtering Pi contains the following mapping: 4.17/1.89 int_in_gga(x1, x2, x3) = int_in_gga(x1, x2) 4.17/1.89 4.17/1.89 0 = 0 4.17/1.89 4.17/1.89 int_out_gga(x1, x2, x3) = int_out_gga(x3) 4.17/1.89 4.17/1.89 s(x1) = s(x1) 4.17/1.89 4.17/1.89 U2_gga(x1, x2, x3) = U2_gga(x3) 4.17/1.89 4.17/1.89 U3_gga(x1, x2, x3, x4) = U3_gga(x4) 4.17/1.89 4.17/1.89 U4_gga(x1, x2, x3, x4) = U4_gga(x4) 4.17/1.89 4.17/1.89 intlist_in_ga(x1, x2) = intlist_in_ga(x1) 4.17/1.89 4.17/1.89 [] = [] 4.17/1.89 4.17/1.89 intlist_out_ga(x1, x2) = intlist_out_ga(x2) 4.17/1.89 4.17/1.89 .(x1, x2) = .(x1, x2) 4.17/1.89 4.17/1.89 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) 4.17/1.89 4.17/1.89 4.17/1.89 4.17/1.89 4.17/1.89 4.17/1.89 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 4.17/1.89 4.17/1.89 4.17/1.89 4.17/1.89 ---------------------------------------- 4.17/1.89 4.17/1.89 (2) 4.17/1.89 Obligation: 4.17/1.89 Pi-finite rewrite system: 4.17/1.89 The TRS R consists of the following rules: 4.17/1.89 4.17/1.89 int_in_gga(0, 0, .(0, [])) -> int_out_gga(0, 0, .(0, [])) 4.17/1.89 int_in_gga(0, s(Y), .(0, XS)) -> U2_gga(Y, XS, int_in_gga(s(0), s(Y), XS)) 4.17/1.89 int_in_gga(s(X), 0, []) -> int_out_gga(s(X), 0, []) 4.17/1.89 int_in_gga(s(X), s(Y), XS) -> U3_gga(X, Y, XS, int_in_gga(X, Y, ZS)) 4.17/1.89 U3_gga(X, Y, XS, int_out_gga(X, Y, ZS)) -> U4_gga(X, Y, XS, intlist_in_ga(ZS, XS)) 4.17/1.89 intlist_in_ga([], []) -> intlist_out_ga([], []) 4.17/1.89 intlist_in_ga(.(X, XS), .(s(X), YS)) -> U1_ga(X, XS, YS, intlist_in_ga(XS, YS)) 4.17/1.89 U1_ga(X, XS, YS, intlist_out_ga(XS, YS)) -> intlist_out_ga(.(X, XS), .(s(X), YS)) 4.17/1.89 U4_gga(X, Y, XS, intlist_out_ga(ZS, XS)) -> int_out_gga(s(X), s(Y), XS) 4.17/1.89 U2_gga(Y, XS, int_out_gga(s(0), s(Y), XS)) -> int_out_gga(0, s(Y), .(0, XS)) 4.17/1.89 4.17/1.89 The argument filtering Pi contains the following mapping: 4.17/1.89 int_in_gga(x1, x2, x3) = int_in_gga(x1, x2) 4.17/1.89 4.17/1.89 0 = 0 4.17/1.89 4.17/1.89 int_out_gga(x1, x2, x3) = int_out_gga(x3) 4.17/1.89 4.17/1.89 s(x1) = s(x1) 4.17/1.89 4.17/1.89 U2_gga(x1, x2, x3) = U2_gga(x3) 4.17/1.89 4.17/1.89 U3_gga(x1, x2, x3, x4) = U3_gga(x4) 4.17/1.89 4.17/1.89 U4_gga(x1, x2, x3, x4) = U4_gga(x4) 4.17/1.89 4.17/1.89 intlist_in_ga(x1, x2) = intlist_in_ga(x1) 4.17/1.89 4.17/1.89 [] = [] 4.17/1.89 4.17/1.89 intlist_out_ga(x1, x2) = intlist_out_ga(x2) 4.17/1.89 4.17/1.89 .(x1, x2) = .(x1, x2) 4.17/1.89 4.17/1.89 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) 4.17/1.89 4.17/1.89 4.17/1.89 4.17/1.89 ---------------------------------------- 4.17/1.89 4.17/1.89 (3) DependencyPairsProof (EQUIVALENT) 4.17/1.89 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 4.17/1.89 Pi DP problem: 4.17/1.89 The TRS P consists of the following rules: 4.17/1.89 4.17/1.89 INT_IN_GGA(0, s(Y), .(0, XS)) -> U2_GGA(Y, XS, int_in_gga(s(0), s(Y), XS)) 4.17/1.89 INT_IN_GGA(0, s(Y), .(0, XS)) -> INT_IN_GGA(s(0), s(Y), XS) 4.17/1.89 INT_IN_GGA(s(X), s(Y), XS) -> U3_GGA(X, Y, XS, int_in_gga(X, Y, ZS)) 4.17/1.89 INT_IN_GGA(s(X), s(Y), XS) -> INT_IN_GGA(X, Y, ZS) 4.17/1.89 U3_GGA(X, Y, XS, int_out_gga(X, Y, ZS)) -> U4_GGA(X, Y, XS, intlist_in_ga(ZS, XS)) 4.17/1.89 U3_GGA(X, Y, XS, int_out_gga(X, Y, ZS)) -> INTLIST_IN_GA(ZS, XS) 4.17/1.89 INTLIST_IN_GA(.(X, XS), .(s(X), YS)) -> U1_GA(X, XS, YS, intlist_in_ga(XS, YS)) 4.17/1.89 INTLIST_IN_GA(.(X, XS), .(s(X), YS)) -> INTLIST_IN_GA(XS, YS) 4.17/1.89 4.17/1.89 The TRS R consists of the following rules: 4.17/1.89 4.17/1.89 int_in_gga(0, 0, .(0, [])) -> int_out_gga(0, 0, .(0, [])) 4.17/1.89 int_in_gga(0, s(Y), .(0, XS)) -> U2_gga(Y, XS, int_in_gga(s(0), s(Y), XS)) 4.17/1.89 int_in_gga(s(X), 0, []) -> int_out_gga(s(X), 0, []) 4.17/1.89 int_in_gga(s(X), s(Y), XS) -> U3_gga(X, Y, XS, int_in_gga(X, Y, ZS)) 4.17/1.89 U3_gga(X, Y, XS, int_out_gga(X, Y, ZS)) -> U4_gga(X, Y, XS, intlist_in_ga(ZS, XS)) 4.17/1.89 intlist_in_ga([], []) -> intlist_out_ga([], []) 4.17/1.89 intlist_in_ga(.(X, XS), .(s(X), YS)) -> U1_ga(X, XS, YS, intlist_in_ga(XS, YS)) 4.17/1.89 U1_ga(X, XS, YS, intlist_out_ga(XS, YS)) -> intlist_out_ga(.(X, XS), .(s(X), YS)) 4.17/1.89 U4_gga(X, Y, XS, intlist_out_ga(ZS, XS)) -> int_out_gga(s(X), s(Y), XS) 4.17/1.89 U2_gga(Y, XS, int_out_gga(s(0), s(Y), XS)) -> int_out_gga(0, s(Y), .(0, XS)) 4.17/1.89 4.17/1.89 The argument filtering Pi contains the following mapping: 4.17/1.89 int_in_gga(x1, x2, x3) = int_in_gga(x1, x2) 4.17/1.89 4.17/1.89 0 = 0 4.17/1.89 4.17/1.89 int_out_gga(x1, x2, x3) = int_out_gga(x3) 4.17/1.89 4.17/1.89 s(x1) = s(x1) 4.17/1.89 4.17/1.89 U2_gga(x1, x2, x3) = U2_gga(x3) 4.17/1.89 4.17/1.89 U3_gga(x1, x2, x3, x4) = U3_gga(x4) 4.17/1.89 4.17/1.89 U4_gga(x1, x2, x3, x4) = U4_gga(x4) 4.17/1.89 4.17/1.89 intlist_in_ga(x1, x2) = intlist_in_ga(x1) 4.17/1.89 4.17/1.89 [] = [] 4.17/1.89 4.17/1.89 intlist_out_ga(x1, x2) = intlist_out_ga(x2) 4.17/1.89 4.17/1.89 .(x1, x2) = .(x1, x2) 4.17/1.89 4.17/1.89 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) 4.17/1.89 4.17/1.89 INT_IN_GGA(x1, x2, x3) = INT_IN_GGA(x1, x2) 4.17/1.89 4.17/1.89 U2_GGA(x1, x2, x3) = U2_GGA(x3) 4.17/1.89 4.17/1.89 U3_GGA(x1, x2, x3, x4) = U3_GGA(x4) 4.17/1.89 4.17/1.89 U4_GGA(x1, x2, x3, x4) = U4_GGA(x4) 4.17/1.89 4.17/1.89 INTLIST_IN_GA(x1, x2) = INTLIST_IN_GA(x1) 4.17/1.89 4.17/1.89 U1_GA(x1, x2, x3, x4) = U1_GA(x1, x4) 4.17/1.89 4.17/1.89 4.17/1.89 We have to consider all (P,R,Pi)-chains 4.17/1.89 ---------------------------------------- 4.17/1.89 4.17/1.89 (4) 4.17/1.89 Obligation: 4.17/1.89 Pi DP problem: 4.17/1.89 The TRS P consists of the following rules: 4.17/1.89 4.17/1.89 INT_IN_GGA(0, s(Y), .(0, XS)) -> U2_GGA(Y, XS, int_in_gga(s(0), s(Y), XS)) 4.17/1.89 INT_IN_GGA(0, s(Y), .(0, XS)) -> INT_IN_GGA(s(0), s(Y), XS) 4.17/1.89 INT_IN_GGA(s(X), s(Y), XS) -> U3_GGA(X, Y, XS, int_in_gga(X, Y, ZS)) 4.17/1.89 INT_IN_GGA(s(X), s(Y), XS) -> INT_IN_GGA(X, Y, ZS) 4.17/1.89 U3_GGA(X, Y, XS, int_out_gga(X, Y, ZS)) -> U4_GGA(X, Y, XS, intlist_in_ga(ZS, XS)) 4.17/1.89 U3_GGA(X, Y, XS, int_out_gga(X, Y, ZS)) -> INTLIST_IN_GA(ZS, XS) 4.17/1.89 INTLIST_IN_GA(.(X, XS), .(s(X), YS)) -> U1_GA(X, XS, YS, intlist_in_ga(XS, YS)) 4.17/1.89 INTLIST_IN_GA(.(X, XS), .(s(X), YS)) -> INTLIST_IN_GA(XS, YS) 4.17/1.89 4.17/1.89 The TRS R consists of the following rules: 4.17/1.89 4.17/1.89 int_in_gga(0, 0, .(0, [])) -> int_out_gga(0, 0, .(0, [])) 4.17/1.89 int_in_gga(0, s(Y), .(0, XS)) -> U2_gga(Y, XS, int_in_gga(s(0), s(Y), XS)) 4.17/1.89 int_in_gga(s(X), 0, []) -> int_out_gga(s(X), 0, []) 4.17/1.89 int_in_gga(s(X), s(Y), XS) -> U3_gga(X, Y, XS, int_in_gga(X, Y, ZS)) 4.17/1.89 U3_gga(X, Y, XS, int_out_gga(X, Y, ZS)) -> U4_gga(X, Y, XS, intlist_in_ga(ZS, XS)) 4.17/1.89 intlist_in_ga([], []) -> intlist_out_ga([], []) 4.17/1.89 intlist_in_ga(.(X, XS), .(s(X), YS)) -> U1_ga(X, XS, YS, intlist_in_ga(XS, YS)) 4.17/1.89 U1_ga(X, XS, YS, intlist_out_ga(XS, YS)) -> intlist_out_ga(.(X, XS), .(s(X), YS)) 4.17/1.89 U4_gga(X, Y, XS, intlist_out_ga(ZS, XS)) -> int_out_gga(s(X), s(Y), XS) 4.17/1.89 U2_gga(Y, XS, int_out_gga(s(0), s(Y), XS)) -> int_out_gga(0, s(Y), .(0, XS)) 4.17/1.89 4.17/1.89 The argument filtering Pi contains the following mapping: 4.17/1.89 int_in_gga(x1, x2, x3) = int_in_gga(x1, x2) 4.17/1.89 4.17/1.89 0 = 0 4.17/1.89 4.17/1.89 int_out_gga(x1, x2, x3) = int_out_gga(x3) 4.17/1.89 4.17/1.89 s(x1) = s(x1) 4.17/1.89 4.17/1.89 U2_gga(x1, x2, x3) = U2_gga(x3) 4.17/1.89 4.17/1.89 U3_gga(x1, x2, x3, x4) = U3_gga(x4) 4.17/1.89 4.17/1.89 U4_gga(x1, x2, x3, x4) = U4_gga(x4) 4.17/1.89 4.17/1.89 intlist_in_ga(x1, x2) = intlist_in_ga(x1) 4.17/1.89 4.17/1.89 [] = [] 4.17/1.89 4.17/1.89 intlist_out_ga(x1, x2) = intlist_out_ga(x2) 4.17/1.89 4.17/1.89 .(x1, x2) = .(x1, x2) 4.17/1.89 4.17/1.89 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) 4.17/1.89 4.17/1.89 INT_IN_GGA(x1, x2, x3) = INT_IN_GGA(x1, x2) 4.17/1.89 4.17/1.89 U2_GGA(x1, x2, x3) = U2_GGA(x3) 4.17/1.89 4.17/1.89 U3_GGA(x1, x2, x3, x4) = U3_GGA(x4) 4.17/1.89 4.17/1.89 U4_GGA(x1, x2, x3, x4) = U4_GGA(x4) 4.17/1.89 4.17/1.89 INTLIST_IN_GA(x1, x2) = INTLIST_IN_GA(x1) 4.17/1.89 4.17/1.89 U1_GA(x1, x2, x3, x4) = U1_GA(x1, x4) 4.17/1.89 4.17/1.89 4.17/1.89 We have to consider all (P,R,Pi)-chains 4.17/1.89 ---------------------------------------- 4.17/1.89 4.17/1.89 (5) DependencyGraphProof (EQUIVALENT) 4.17/1.89 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 5 less nodes. 4.17/1.89 ---------------------------------------- 4.17/1.89 4.17/1.89 (6) 4.17/1.89 Complex Obligation (AND) 4.17/1.89 4.17/1.89 ---------------------------------------- 4.17/1.89 4.17/1.89 (7) 4.17/1.89 Obligation: 4.17/1.89 Pi DP problem: 4.17/1.89 The TRS P consists of the following rules: 4.17/1.89 4.17/1.89 INTLIST_IN_GA(.(X, XS), .(s(X), YS)) -> INTLIST_IN_GA(XS, YS) 4.17/1.89 4.17/1.89 The TRS R consists of the following rules: 4.17/1.89 4.17/1.89 int_in_gga(0, 0, .(0, [])) -> int_out_gga(0, 0, .(0, [])) 4.17/1.89 int_in_gga(0, s(Y), .(0, XS)) -> U2_gga(Y, XS, int_in_gga(s(0), s(Y), XS)) 4.17/1.89 int_in_gga(s(X), 0, []) -> int_out_gga(s(X), 0, []) 4.17/1.89 int_in_gga(s(X), s(Y), XS) -> U3_gga(X, Y, XS, int_in_gga(X, Y, ZS)) 4.17/1.89 U3_gga(X, Y, XS, int_out_gga(X, Y, ZS)) -> U4_gga(X, Y, XS, intlist_in_ga(ZS, XS)) 4.17/1.89 intlist_in_ga([], []) -> intlist_out_ga([], []) 4.17/1.89 intlist_in_ga(.(X, XS), .(s(X), YS)) -> U1_ga(X, XS, YS, intlist_in_ga(XS, YS)) 4.17/1.89 U1_ga(X, XS, YS, intlist_out_ga(XS, YS)) -> intlist_out_ga(.(X, XS), .(s(X), YS)) 4.17/1.89 U4_gga(X, Y, XS, intlist_out_ga(ZS, XS)) -> int_out_gga(s(X), s(Y), XS) 4.17/1.89 U2_gga(Y, XS, int_out_gga(s(0), s(Y), XS)) -> int_out_gga(0, s(Y), .(0, XS)) 4.17/1.89 4.17/1.89 The argument filtering Pi contains the following mapping: 4.17/1.89 int_in_gga(x1, x2, x3) = int_in_gga(x1, x2) 4.17/1.89 4.17/1.89 0 = 0 4.17/1.89 4.17/1.89 int_out_gga(x1, x2, x3) = int_out_gga(x3) 4.17/1.89 4.17/1.89 s(x1) = s(x1) 4.17/1.89 4.17/1.89 U2_gga(x1, x2, x3) = U2_gga(x3) 4.17/1.89 4.17/1.89 U3_gga(x1, x2, x3, x4) = U3_gga(x4) 4.17/1.89 4.17/1.89 U4_gga(x1, x2, x3, x4) = U4_gga(x4) 4.17/1.89 4.17/1.89 intlist_in_ga(x1, x2) = intlist_in_ga(x1) 4.17/1.89 4.17/1.89 [] = [] 4.17/1.89 4.17/1.89 intlist_out_ga(x1, x2) = intlist_out_ga(x2) 4.17/1.89 4.17/1.89 .(x1, x2) = .(x1, x2) 4.17/1.89 4.17/1.89 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) 4.17/1.89 4.17/1.89 INTLIST_IN_GA(x1, x2) = INTLIST_IN_GA(x1) 4.17/1.89 4.17/1.89 4.17/1.89 We have to consider all (P,R,Pi)-chains 4.17/1.89 ---------------------------------------- 4.17/1.89 4.17/1.89 (8) UsableRulesProof (EQUIVALENT) 4.17/1.89 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.17/1.89 ---------------------------------------- 4.17/1.89 4.17/1.89 (9) 4.17/1.89 Obligation: 4.17/1.89 Pi DP problem: 4.17/1.89 The TRS P consists of the following rules: 4.17/1.89 4.17/1.89 INTLIST_IN_GA(.(X, XS), .(s(X), YS)) -> INTLIST_IN_GA(XS, YS) 4.17/1.89 4.17/1.89 R is empty. 4.17/1.89 The argument filtering Pi contains the following mapping: 4.17/1.89 s(x1) = s(x1) 4.17/1.89 4.17/1.89 .(x1, x2) = .(x1, x2) 4.17/1.89 4.17/1.89 INTLIST_IN_GA(x1, x2) = INTLIST_IN_GA(x1) 4.17/1.89 4.17/1.89 4.17/1.89 We have to consider all (P,R,Pi)-chains 4.17/1.89 ---------------------------------------- 4.17/1.89 4.17/1.89 (10) PiDPToQDPProof (SOUND) 4.17/1.89 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.17/1.89 ---------------------------------------- 4.17/1.89 4.17/1.89 (11) 4.17/1.89 Obligation: 4.17/1.89 Q DP problem: 4.17/1.89 The TRS P consists of the following rules: 4.17/1.89 4.17/1.89 INTLIST_IN_GA(.(X, XS)) -> INTLIST_IN_GA(XS) 4.17/1.89 4.17/1.89 R is empty. 4.17/1.89 Q is empty. 4.17/1.89 We have to consider all (P,Q,R)-chains. 4.17/1.89 ---------------------------------------- 4.17/1.89 4.17/1.89 (12) QDPSizeChangeProof (EQUIVALENT) 4.17/1.89 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 4.17/1.89 4.17/1.89 From the DPs we obtained the following set of size-change graphs: 4.17/1.89 *INTLIST_IN_GA(.(X, XS)) -> INTLIST_IN_GA(XS) 4.17/1.89 The graph contains the following edges 1 > 1 4.17/1.89 4.17/1.89 4.17/1.89 ---------------------------------------- 4.17/1.89 4.17/1.89 (13) 4.17/1.89 YES 4.17/1.89 4.17/1.89 ---------------------------------------- 4.17/1.89 4.17/1.89 (14) 4.17/1.89 Obligation: 4.17/1.89 Pi DP problem: 4.17/1.89 The TRS P consists of the following rules: 4.17/1.89 4.17/1.89 INT_IN_GGA(0, s(Y), .(0, XS)) -> INT_IN_GGA(s(0), s(Y), XS) 4.17/1.89 INT_IN_GGA(s(X), s(Y), XS) -> INT_IN_GGA(X, Y, ZS) 4.17/1.89 4.17/1.89 The TRS R consists of the following rules: 4.17/1.89 4.17/1.89 int_in_gga(0, 0, .(0, [])) -> int_out_gga(0, 0, .(0, [])) 4.17/1.89 int_in_gga(0, s(Y), .(0, XS)) -> U2_gga(Y, XS, int_in_gga(s(0), s(Y), XS)) 4.17/1.89 int_in_gga(s(X), 0, []) -> int_out_gga(s(X), 0, []) 4.17/1.89 int_in_gga(s(X), s(Y), XS) -> U3_gga(X, Y, XS, int_in_gga(X, Y, ZS)) 4.17/1.89 U3_gga(X, Y, XS, int_out_gga(X, Y, ZS)) -> U4_gga(X, Y, XS, intlist_in_ga(ZS, XS)) 4.17/1.89 intlist_in_ga([], []) -> intlist_out_ga([], []) 4.17/1.89 intlist_in_ga(.(X, XS), .(s(X), YS)) -> U1_ga(X, XS, YS, intlist_in_ga(XS, YS)) 4.17/1.89 U1_ga(X, XS, YS, intlist_out_ga(XS, YS)) -> intlist_out_ga(.(X, XS), .(s(X), YS)) 4.17/1.89 U4_gga(X, Y, XS, intlist_out_ga(ZS, XS)) -> int_out_gga(s(X), s(Y), XS) 4.17/1.89 U2_gga(Y, XS, int_out_gga(s(0), s(Y), XS)) -> int_out_gga(0, s(Y), .(0, XS)) 4.17/1.89 4.17/1.89 The argument filtering Pi contains the following mapping: 4.17/1.89 int_in_gga(x1, x2, x3) = int_in_gga(x1, x2) 4.17/1.89 4.17/1.89 0 = 0 4.17/1.89 4.17/1.89 int_out_gga(x1, x2, x3) = int_out_gga(x3) 4.17/1.89 4.17/1.89 s(x1) = s(x1) 4.17/1.89 4.17/1.89 U2_gga(x1, x2, x3) = U2_gga(x3) 4.17/1.89 4.17/1.89 U3_gga(x1, x2, x3, x4) = U3_gga(x4) 4.17/1.89 4.17/1.89 U4_gga(x1, x2, x3, x4) = U4_gga(x4) 4.17/1.89 4.17/1.89 intlist_in_ga(x1, x2) = intlist_in_ga(x1) 4.17/1.89 4.17/1.89 [] = [] 4.17/1.89 4.17/1.89 intlist_out_ga(x1, x2) = intlist_out_ga(x2) 4.17/1.89 4.17/1.89 .(x1, x2) = .(x1, x2) 4.17/1.89 4.17/1.89 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) 4.17/1.89 4.17/1.89 INT_IN_GGA(x1, x2, x3) = INT_IN_GGA(x1, x2) 4.17/1.89 4.17/1.89 4.17/1.89 We have to consider all (P,R,Pi)-chains 4.17/1.89 ---------------------------------------- 4.17/1.89 4.17/1.89 (15) UsableRulesProof (EQUIVALENT) 4.17/1.89 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.17/1.89 ---------------------------------------- 4.17/1.89 4.17/1.89 (16) 4.17/1.89 Obligation: 4.17/1.89 Pi DP problem: 4.17/1.89 The TRS P consists of the following rules: 4.17/1.89 4.17/1.89 INT_IN_GGA(0, s(Y), .(0, XS)) -> INT_IN_GGA(s(0), s(Y), XS) 4.17/1.89 INT_IN_GGA(s(X), s(Y), XS) -> INT_IN_GGA(X, Y, ZS) 4.17/1.89 4.17/1.89 R is empty. 4.17/1.89 The argument filtering Pi contains the following mapping: 4.17/1.89 0 = 0 4.17/1.89 4.17/1.89 s(x1) = s(x1) 4.17/1.89 4.17/1.89 .(x1, x2) = .(x1, x2) 4.17/1.89 4.17/1.89 INT_IN_GGA(x1, x2, x3) = INT_IN_GGA(x1, x2) 4.17/1.89 4.17/1.89 4.17/1.89 We have to consider all (P,R,Pi)-chains 4.17/1.89 ---------------------------------------- 4.17/1.89 4.17/1.89 (17) PiDPToQDPProof (SOUND) 4.17/1.89 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.17/1.89 ---------------------------------------- 4.17/1.89 4.17/1.89 (18) 4.17/1.89 Obligation: 4.17/1.89 Q DP problem: 4.17/1.89 The TRS P consists of the following rules: 4.17/1.89 4.17/1.89 INT_IN_GGA(0, s(Y)) -> INT_IN_GGA(s(0), s(Y)) 4.17/1.90 INT_IN_GGA(s(X), s(Y)) -> INT_IN_GGA(X, Y) 4.17/1.90 4.17/1.90 R is empty. 4.17/1.90 Q is empty. 4.17/1.90 We have to consider all (P,Q,R)-chains. 4.17/1.90 ---------------------------------------- 4.17/1.90 4.17/1.90 (19) QDPSizeChangeProof (EQUIVALENT) 4.17/1.90 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 4.17/1.90 4.17/1.90 From the DPs we obtained the following set of size-change graphs: 4.17/1.90 *INT_IN_GGA(s(X), s(Y)) -> INT_IN_GGA(X, Y) 4.17/1.90 The graph contains the following edges 1 > 1, 2 > 2 4.17/1.90 4.17/1.90 4.17/1.90 *INT_IN_GGA(0, s(Y)) -> INT_IN_GGA(s(0), s(Y)) 4.17/1.90 The graph contains the following edges 2 >= 2 4.17/1.90 4.17/1.90 4.17/1.90 ---------------------------------------- 4.17/1.90 4.17/1.90 (20) 4.17/1.90 YES 4.47/1.91 EOF