/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.pl /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern ways(g,g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) UnifyTransformerProof [EQUIVALENT, 0 ms] (2) Prolog (3) PrologToPiTRSProof [SOUND, 0 ms] (4) PiTRS (5) DependencyPairsProof [EQUIVALENT, 1 ms] (6) PiDP (7) DependencyGraphProof [EQUIVALENT, 0 ms] (8) AND (9) PiDP (10) UsableRulesProof [EQUIVALENT, 0 ms] (11) PiDP (12) PiDPToQDPProof [EQUIVALENT, 3 ms] (13) QDP (14) QDPSizeChangeProof [EQUIVALENT, 0 ms] (15) YES (16) PiDP (17) UsableRulesProof [EQUIVALENT, 0 ms] (18) PiDP (19) PiDPToQDPProof [SOUND, 0 ms] (20) QDP (21) QDPSizeChangeProof [EQUIVALENT, 0 ms] (22) YES (23) PiDP (24) UsableRulesProof [EQUIVALENT, 0 ms] (25) PiDP (26) PiDPToQDPProof [SOUND, 0 ms] (27) QDP (28) QDPSizeChangeProof [EQUIVALENT, 0 ms] (29) YES (30) PiDP (31) PiDPToQDPProof [SOUND, 4 ms] (32) QDP (33) TransformationProof [EQUIVALENT, 0 ms] (34) QDP (35) TransformationProof [EQUIVALENT, 0 ms] (36) QDP (37) TransformationProof [EQUIVALENT, 0 ms] (38) QDP (39) TransformationProof [EQUIVALENT, 0 ms] (40) QDP (41) TransformationProof [EQUIVALENT, 0 ms] (42) QDP (43) TransformationProof [EQUIVALENT, 0 ms] (44) QDP (45) QDPQMonotonicMRRProof [EQUIVALENT, 121 ms] (46) QDP (47) DependencyGraphProof [EQUIVALENT, 0 ms] (48) QDP (49) QDPOrderProof [EQUIVALENT, 395 ms] (50) QDP (51) DependencyGraphProof [EQUIVALENT, 0 ms] (52) TRUE ---------------------------------------- (0) Obligation: Clauses: nat(0). nat(s(X)) :- nat(X). plus(0, X, X) :- nat(X). plus(s(X), Y, s(Z)) :- plus(X, Y, Z). ways(0, X1, s(0)). ways(X2, [], 0). ways(Amount, .(s(C), Coins), N) :- ','(=(Amount, s(X3)), ','(plus(s(C), NewAmount, Amount), ','(ways(Amount, Coins, N1), ','(ways(NewAmount, .(s(C), Coins), N2), plus(N1, N2, N))))). ways(Amount, .(s(C), Coins), N) :- ','(=(Amount, s(X4)), ','(plus(Amount, s(X5), s(C)), ways(Amount, Coins, N))). Query: ways(g,g,a) ---------------------------------------- (1) UnifyTransformerProof (EQUIVALENT) Added a fact for the built-in = predicate [PROLOG]. ---------------------------------------- (2) Obligation: Clauses: nat(0). nat(s(X)) :- nat(X). plus(0, X, X) :- nat(X). plus(s(X), Y, s(Z)) :- plus(X, Y, Z). ways(0, X1, s(0)). ways(X2, [], 0). ways(Amount, .(s(C), Coins), N) :- ','(=(Amount, s(X3)), ','(plus(s(C), NewAmount, Amount), ','(ways(Amount, Coins, N1), ','(ways(NewAmount, .(s(C), Coins), N2), plus(N1, N2, N))))). ways(Amount, .(s(C), Coins), N) :- ','(=(Amount, s(X4)), ','(plus(Amount, s(X5), s(C)), ways(Amount, Coins, N))). =(X, X). Query: ways(g,g,a) ---------------------------------------- (3) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: ways_in_3: (b,b,f) plus_in_3: (b,f,b) (b,b,f) nat_in_1: (b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: ways_in_gga(0, X1, s(0)) -> ways_out_gga(0, X1, s(0)) ways_in_gga(X2, [], 0) -> ways_out_gga(X2, [], 0) ways_in_gga(Amount, .(s(C), Coins), N) -> U4_gga(Amount, C, Coins, N, =_in_ga(Amount, s(X3))) =_in_ga(X, X) -> =_out_ga(X, X) U4_gga(Amount, C, Coins, N, =_out_ga(Amount, s(X3))) -> U5_gga(Amount, C, Coins, N, X3, plus_in_gag(s(C), NewAmount, Amount)) plus_in_gag(0, X, X) -> U2_gag(X, nat_in_g(X)) nat_in_g(0) -> nat_out_g(0) nat_in_g(s(X)) -> U1_g(X, nat_in_g(X)) U1_g(X, nat_out_g(X)) -> nat_out_g(s(X)) U2_gag(X, nat_out_g(X)) -> plus_out_gag(0, X, X) plus_in_gag(s(X), Y, s(Z)) -> U3_gag(X, Y, Z, plus_in_gag(X, Y, Z)) U3_gag(X, Y, Z, plus_out_gag(X, Y, Z)) -> plus_out_gag(s(X), Y, s(Z)) U5_gga(Amount, C, Coins, N, X3, plus_out_gag(s(C), NewAmount, Amount)) -> U6_gga(Amount, C, Coins, N, X3, NewAmount, ways_in_gga(Amount, Coins, N1)) ways_in_gga(Amount, .(s(C), Coins), N) -> U9_gga(Amount, C, Coins, N, =_in_ga(Amount, s(X4))) U9_gga(Amount, C, Coins, N, =_out_ga(Amount, s(X4))) -> U10_gga(Amount, C, Coins, N, X4, plus_in_gag(Amount, s(X5), s(C))) U10_gga(Amount, C, Coins, N, X4, plus_out_gag(Amount, s(X5), s(C))) -> U11_gga(Amount, C, Coins, N, ways_in_gga(Amount, Coins, N)) U11_gga(Amount, C, Coins, N, ways_out_gga(Amount, Coins, N)) -> ways_out_gga(Amount, .(s(C), Coins), N) U6_gga(Amount, C, Coins, N, X3, NewAmount, ways_out_gga(Amount, Coins, N1)) -> U7_gga(Amount, C, Coins, N, X3, NewAmount, N1, ways_in_gga(NewAmount, .(s(C), Coins), N2)) U7_gga(Amount, C, Coins, N, X3, NewAmount, N1, ways_out_gga(NewAmount, .(s(C), Coins), N2)) -> U8_gga(Amount, C, Coins, N, plus_in_gga(N1, N2, N)) plus_in_gga(0, X, X) -> U2_gga(X, nat_in_g(X)) U2_gga(X, nat_out_g(X)) -> plus_out_gga(0, X, X) plus_in_gga(s(X), Y, s(Z)) -> U3_gga(X, Y, Z, plus_in_gga(X, Y, Z)) U3_gga(X, Y, Z, plus_out_gga(X, Y, Z)) -> plus_out_gga(s(X), Y, s(Z)) U8_gga(Amount, C, Coins, N, plus_out_gga(N1, N2, N)) -> ways_out_gga(Amount, .(s(C), Coins), N) The argument filtering Pi contains the following mapping: ways_in_gga(x1, x2, x3) = ways_in_gga(x1, x2) 0 = 0 ways_out_gga(x1, x2, x3) = ways_out_gga(x3) [] = [] .(x1, x2) = .(x1, x2) s(x1) = s(x1) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x1, x2, x3, x5) =_in_ga(x1, x2) = =_in_ga(x1) =_out_ga(x1, x2) = =_out_ga(x2) U5_gga(x1, x2, x3, x4, x5, x6) = U5_gga(x1, x2, x3, x6) plus_in_gag(x1, x2, x3) = plus_in_gag(x1, x3) U2_gag(x1, x2) = U2_gag(x1, x2) nat_in_g(x1) = nat_in_g(x1) nat_out_g(x1) = nat_out_g U1_g(x1, x2) = U1_g(x2) plus_out_gag(x1, x2, x3) = plus_out_gag(x2) U3_gag(x1, x2, x3, x4) = U3_gag(x4) U6_gga(x1, x2, x3, x4, x5, x6, x7) = U6_gga(x2, x3, x6, x7) U9_gga(x1, x2, x3, x4, x5) = U9_gga(x1, x2, x3, x5) U10_gga(x1, x2, x3, x4, x5, x6) = U10_gga(x1, x3, x6) U11_gga(x1, x2, x3, x4, x5) = U11_gga(x5) U7_gga(x1, x2, x3, x4, x5, x6, x7, x8) = U7_gga(x7, x8) U8_gga(x1, x2, x3, x4, x5) = U8_gga(x5) plus_in_gga(x1, x2, x3) = plus_in_gga(x1, x2) U2_gga(x1, x2) = U2_gga(x1, x2) plus_out_gga(x1, x2, x3) = plus_out_gga(x3) U3_gga(x1, x2, x3, x4) = U3_gga(x4) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (4) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: ways_in_gga(0, X1, s(0)) -> ways_out_gga(0, X1, s(0)) ways_in_gga(X2, [], 0) -> ways_out_gga(X2, [], 0) ways_in_gga(Amount, .(s(C), Coins), N) -> U4_gga(Amount, C, Coins, N, =_in_ga(Amount, s(X3))) =_in_ga(X, X) -> =_out_ga(X, X) U4_gga(Amount, C, Coins, N, =_out_ga(Amount, s(X3))) -> U5_gga(Amount, C, Coins, N, X3, plus_in_gag(s(C), NewAmount, Amount)) plus_in_gag(0, X, X) -> U2_gag(X, nat_in_g(X)) nat_in_g(0) -> nat_out_g(0) nat_in_g(s(X)) -> U1_g(X, nat_in_g(X)) U1_g(X, nat_out_g(X)) -> nat_out_g(s(X)) U2_gag(X, nat_out_g(X)) -> plus_out_gag(0, X, X) plus_in_gag(s(X), Y, s(Z)) -> U3_gag(X, Y, Z, plus_in_gag(X, Y, Z)) U3_gag(X, Y, Z, plus_out_gag(X, Y, Z)) -> plus_out_gag(s(X), Y, s(Z)) U5_gga(Amount, C, Coins, N, X3, plus_out_gag(s(C), NewAmount, Amount)) -> U6_gga(Amount, C, Coins, N, X3, NewAmount, ways_in_gga(Amount, Coins, N1)) ways_in_gga(Amount, .(s(C), Coins), N) -> U9_gga(Amount, C, Coins, N, =_in_ga(Amount, s(X4))) U9_gga(Amount, C, Coins, N, =_out_ga(Amount, s(X4))) -> U10_gga(Amount, C, Coins, N, X4, plus_in_gag(Amount, s(X5), s(C))) U10_gga(Amount, C, Coins, N, X4, plus_out_gag(Amount, s(X5), s(C))) -> U11_gga(Amount, C, Coins, N, ways_in_gga(Amount, Coins, N)) U11_gga(Amount, C, Coins, N, ways_out_gga(Amount, Coins, N)) -> ways_out_gga(Amount, .(s(C), Coins), N) U6_gga(Amount, C, Coins, N, X3, NewAmount, ways_out_gga(Amount, Coins, N1)) -> U7_gga(Amount, C, Coins, N, X3, NewAmount, N1, ways_in_gga(NewAmount, .(s(C), Coins), N2)) U7_gga(Amount, C, Coins, N, X3, NewAmount, N1, ways_out_gga(NewAmount, .(s(C), Coins), N2)) -> U8_gga(Amount, C, Coins, N, plus_in_gga(N1, N2, N)) plus_in_gga(0, X, X) -> U2_gga(X, nat_in_g(X)) U2_gga(X, nat_out_g(X)) -> plus_out_gga(0, X, X) plus_in_gga(s(X), Y, s(Z)) -> U3_gga(X, Y, Z, plus_in_gga(X, Y, Z)) U3_gga(X, Y, Z, plus_out_gga(X, Y, Z)) -> plus_out_gga(s(X), Y, s(Z)) U8_gga(Amount, C, Coins, N, plus_out_gga(N1, N2, N)) -> ways_out_gga(Amount, .(s(C), Coins), N) The argument filtering Pi contains the following mapping: ways_in_gga(x1, x2, x3) = ways_in_gga(x1, x2) 0 = 0 ways_out_gga(x1, x2, x3) = ways_out_gga(x3) [] = [] .(x1, x2) = .(x1, x2) s(x1) = s(x1) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x1, x2, x3, x5) =_in_ga(x1, x2) = =_in_ga(x1) =_out_ga(x1, x2) = =_out_ga(x2) U5_gga(x1, x2, x3, x4, x5, x6) = U5_gga(x1, x2, x3, x6) plus_in_gag(x1, x2, x3) = plus_in_gag(x1, x3) U2_gag(x1, x2) = U2_gag(x1, x2) nat_in_g(x1) = nat_in_g(x1) nat_out_g(x1) = nat_out_g U1_g(x1, x2) = U1_g(x2) plus_out_gag(x1, x2, x3) = plus_out_gag(x2) U3_gag(x1, x2, x3, x4) = U3_gag(x4) U6_gga(x1, x2, x3, x4, x5, x6, x7) = U6_gga(x2, x3, x6, x7) U9_gga(x1, x2, x3, x4, x5) = U9_gga(x1, x2, x3, x5) U10_gga(x1, x2, x3, x4, x5, x6) = U10_gga(x1, x3, x6) U11_gga(x1, x2, x3, x4, x5) = U11_gga(x5) U7_gga(x1, x2, x3, x4, x5, x6, x7, x8) = U7_gga(x7, x8) U8_gga(x1, x2, x3, x4, x5) = U8_gga(x5) plus_in_gga(x1, x2, x3) = plus_in_gga(x1, x2) U2_gga(x1, x2) = U2_gga(x1, x2) plus_out_gga(x1, x2, x3) = plus_out_gga(x3) U3_gga(x1, x2, x3, x4) = U3_gga(x4) ---------------------------------------- (5) 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: WAYS_IN_GGA(Amount, .(s(C), Coins), N) -> U4_GGA(Amount, C, Coins, N, =_in_ga(Amount, s(X3))) WAYS_IN_GGA(Amount, .(s(C), Coins), N) -> =_IN_GA(Amount, s(X3)) U4_GGA(Amount, C, Coins, N, =_out_ga(Amount, s(X3))) -> U5_GGA(Amount, C, Coins, N, X3, plus_in_gag(s(C), NewAmount, Amount)) U4_GGA(Amount, C, Coins, N, =_out_ga(Amount, s(X3))) -> PLUS_IN_GAG(s(C), NewAmount, Amount) PLUS_IN_GAG(0, X, X) -> U2_GAG(X, nat_in_g(X)) PLUS_IN_GAG(0, X, X) -> NAT_IN_G(X) NAT_IN_G(s(X)) -> U1_G(X, nat_in_g(X)) NAT_IN_G(s(X)) -> NAT_IN_G(X) PLUS_IN_GAG(s(X), Y, s(Z)) -> U3_GAG(X, Y, Z, plus_in_gag(X, Y, Z)) PLUS_IN_GAG(s(X), Y, s(Z)) -> PLUS_IN_GAG(X, Y, Z) U5_GGA(Amount, C, Coins, N, X3, plus_out_gag(s(C), NewAmount, Amount)) -> U6_GGA(Amount, C, Coins, N, X3, NewAmount, ways_in_gga(Amount, Coins, N1)) U5_GGA(Amount, C, Coins, N, X3, plus_out_gag(s(C), NewAmount, Amount)) -> WAYS_IN_GGA(Amount, Coins, N1) WAYS_IN_GGA(Amount, .(s(C), Coins), N) -> U9_GGA(Amount, C, Coins, N, =_in_ga(Amount, s(X4))) U9_GGA(Amount, C, Coins, N, =_out_ga(Amount, s(X4))) -> U10_GGA(Amount, C, Coins, N, X4, plus_in_gag(Amount, s(X5), s(C))) U9_GGA(Amount, C, Coins, N, =_out_ga(Amount, s(X4))) -> PLUS_IN_GAG(Amount, s(X5), s(C)) U10_GGA(Amount, C, Coins, N, X4, plus_out_gag(Amount, s(X5), s(C))) -> U11_GGA(Amount, C, Coins, N, ways_in_gga(Amount, Coins, N)) U10_GGA(Amount, C, Coins, N, X4, plus_out_gag(Amount, s(X5), s(C))) -> WAYS_IN_GGA(Amount, Coins, N) U6_GGA(Amount, C, Coins, N, X3, NewAmount, ways_out_gga(Amount, Coins, N1)) -> U7_GGA(Amount, C, Coins, N, X3, NewAmount, N1, ways_in_gga(NewAmount, .(s(C), Coins), N2)) U6_GGA(Amount, C, Coins, N, X3, NewAmount, ways_out_gga(Amount, Coins, N1)) -> WAYS_IN_GGA(NewAmount, .(s(C), Coins), N2) U7_GGA(Amount, C, Coins, N, X3, NewAmount, N1, ways_out_gga(NewAmount, .(s(C), Coins), N2)) -> U8_GGA(Amount, C, Coins, N, plus_in_gga(N1, N2, N)) U7_GGA(Amount, C, Coins, N, X3, NewAmount, N1, ways_out_gga(NewAmount, .(s(C), Coins), N2)) -> PLUS_IN_GGA(N1, N2, N) PLUS_IN_GGA(0, X, X) -> U2_GGA(X, nat_in_g(X)) PLUS_IN_GGA(0, X, X) -> NAT_IN_G(X) PLUS_IN_GGA(s(X), Y, s(Z)) -> U3_GGA(X, Y, Z, plus_in_gga(X, Y, Z)) PLUS_IN_GGA(s(X), Y, s(Z)) -> PLUS_IN_GGA(X, Y, Z) The TRS R consists of the following rules: ways_in_gga(0, X1, s(0)) -> ways_out_gga(0, X1, s(0)) ways_in_gga(X2, [], 0) -> ways_out_gga(X2, [], 0) ways_in_gga(Amount, .(s(C), Coins), N) -> U4_gga(Amount, C, Coins, N, =_in_ga(Amount, s(X3))) =_in_ga(X, X) -> =_out_ga(X, X) U4_gga(Amount, C, Coins, N, =_out_ga(Amount, s(X3))) -> U5_gga(Amount, C, Coins, N, X3, plus_in_gag(s(C), NewAmount, Amount)) plus_in_gag(0, X, X) -> U2_gag(X, nat_in_g(X)) nat_in_g(0) -> nat_out_g(0) nat_in_g(s(X)) -> U1_g(X, nat_in_g(X)) U1_g(X, nat_out_g(X)) -> nat_out_g(s(X)) U2_gag(X, nat_out_g(X)) -> plus_out_gag(0, X, X) plus_in_gag(s(X), Y, s(Z)) -> U3_gag(X, Y, Z, plus_in_gag(X, Y, Z)) U3_gag(X, Y, Z, plus_out_gag(X, Y, Z)) -> plus_out_gag(s(X), Y, s(Z)) U5_gga(Amount, C, Coins, N, X3, plus_out_gag(s(C), NewAmount, Amount)) -> U6_gga(Amount, C, Coins, N, X3, NewAmount, ways_in_gga(Amount, Coins, N1)) ways_in_gga(Amount, .(s(C), Coins), N) -> U9_gga(Amount, C, Coins, N, =_in_ga(Amount, s(X4))) U9_gga(Amount, C, Coins, N, =_out_ga(Amount, s(X4))) -> U10_gga(Amount, C, Coins, N, X4, plus_in_gag(Amount, s(X5), s(C))) U10_gga(Amount, C, Coins, N, X4, plus_out_gag(Amount, s(X5), s(C))) -> U11_gga(Amount, C, Coins, N, ways_in_gga(Amount, Coins, N)) U11_gga(Amount, C, Coins, N, ways_out_gga(Amount, Coins, N)) -> ways_out_gga(Amount, .(s(C), Coins), N) U6_gga(Amount, C, Coins, N, X3, NewAmount, ways_out_gga(Amount, Coins, N1)) -> U7_gga(Amount, C, Coins, N, X3, NewAmount, N1, ways_in_gga(NewAmount, .(s(C), Coins), N2)) U7_gga(Amount, C, Coins, N, X3, NewAmount, N1, ways_out_gga(NewAmount, .(s(C), Coins), N2)) -> U8_gga(Amount, C, Coins, N, plus_in_gga(N1, N2, N)) plus_in_gga(0, X, X) -> U2_gga(X, nat_in_g(X)) U2_gga(X, nat_out_g(X)) -> plus_out_gga(0, X, X) plus_in_gga(s(X), Y, s(Z)) -> U3_gga(X, Y, Z, plus_in_gga(X, Y, Z)) U3_gga(X, Y, Z, plus_out_gga(X, Y, Z)) -> plus_out_gga(s(X), Y, s(Z)) U8_gga(Amount, C, Coins, N, plus_out_gga(N1, N2, N)) -> ways_out_gga(Amount, .(s(C), Coins), N) The argument filtering Pi contains the following mapping: ways_in_gga(x1, x2, x3) = ways_in_gga(x1, x2) 0 = 0 ways_out_gga(x1, x2, x3) = ways_out_gga(x3) [] = [] .(x1, x2) = .(x1, x2) s(x1) = s(x1) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x1, x2, x3, x5) =_in_ga(x1, x2) = =_in_ga(x1) =_out_ga(x1, x2) = =_out_ga(x2) U5_gga(x1, x2, x3, x4, x5, x6) = U5_gga(x1, x2, x3, x6) plus_in_gag(x1, x2, x3) = plus_in_gag(x1, x3) U2_gag(x1, x2) = U2_gag(x1, x2) nat_in_g(x1) = nat_in_g(x1) nat_out_g(x1) = nat_out_g U1_g(x1, x2) = U1_g(x2) plus_out_gag(x1, x2, x3) = plus_out_gag(x2) U3_gag(x1, x2, x3, x4) = U3_gag(x4) U6_gga(x1, x2, x3, x4, x5, x6, x7) = U6_gga(x2, x3, x6, x7) U9_gga(x1, x2, x3, x4, x5) = U9_gga(x1, x2, x3, x5) U10_gga(x1, x2, x3, x4, x5, x6) = U10_gga(x1, x3, x6) U11_gga(x1, x2, x3, x4, x5) = U11_gga(x5) U7_gga(x1, x2, x3, x4, x5, x6, x7, x8) = U7_gga(x7, x8) U8_gga(x1, x2, x3, x4, x5) = U8_gga(x5) plus_in_gga(x1, x2, x3) = plus_in_gga(x1, x2) U2_gga(x1, x2) = U2_gga(x1, x2) plus_out_gga(x1, x2, x3) = plus_out_gga(x3) U3_gga(x1, x2, x3, x4) = U3_gga(x4) WAYS_IN_GGA(x1, x2, x3) = WAYS_IN_GGA(x1, x2) U4_GGA(x1, x2, x3, x4, x5) = U4_GGA(x1, x2, x3, x5) =_IN_GA(x1, x2) = =_IN_GA(x1) U5_GGA(x1, x2, x3, x4, x5, x6) = U5_GGA(x1, x2, x3, x6) PLUS_IN_GAG(x1, x2, x3) = PLUS_IN_GAG(x1, x3) U2_GAG(x1, x2) = U2_GAG(x1, x2) NAT_IN_G(x1) = NAT_IN_G(x1) U1_G(x1, x2) = U1_G(x2) U3_GAG(x1, x2, x3, x4) = U3_GAG(x4) U6_GGA(x1, x2, x3, x4, x5, x6, x7) = U6_GGA(x2, x3, x6, x7) U9_GGA(x1, x2, x3, x4, x5) = U9_GGA(x1, x2, x3, x5) U10_GGA(x1, x2, x3, x4, x5, x6) = U10_GGA(x1, x3, x6) U11_GGA(x1, x2, x3, x4, x5) = U11_GGA(x5) U7_GGA(x1, x2, x3, x4, x5, x6, x7, x8) = U7_GGA(x7, x8) U8_GGA(x1, x2, x3, x4, x5) = U8_GGA(x5) PLUS_IN_GGA(x1, x2, x3) = PLUS_IN_GGA(x1, x2) U2_GGA(x1, x2) = U2_GGA(x1, x2) U3_GGA(x1, x2, x3, x4) = U3_GGA(x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (6) Obligation: Pi DP problem: The TRS P consists of the following rules: WAYS_IN_GGA(Amount, .(s(C), Coins), N) -> U4_GGA(Amount, C, Coins, N, =_in_ga(Amount, s(X3))) WAYS_IN_GGA(Amount, .(s(C), Coins), N) -> =_IN_GA(Amount, s(X3)) U4_GGA(Amount, C, Coins, N, =_out_ga(Amount, s(X3))) -> U5_GGA(Amount, C, Coins, N, X3, plus_in_gag(s(C), NewAmount, Amount)) U4_GGA(Amount, C, Coins, N, =_out_ga(Amount, s(X3))) -> PLUS_IN_GAG(s(C), NewAmount, Amount) PLUS_IN_GAG(0, X, X) -> U2_GAG(X, nat_in_g(X)) PLUS_IN_GAG(0, X, X) -> NAT_IN_G(X) NAT_IN_G(s(X)) -> U1_G(X, nat_in_g(X)) NAT_IN_G(s(X)) -> NAT_IN_G(X) PLUS_IN_GAG(s(X), Y, s(Z)) -> U3_GAG(X, Y, Z, plus_in_gag(X, Y, Z)) PLUS_IN_GAG(s(X), Y, s(Z)) -> PLUS_IN_GAG(X, Y, Z) U5_GGA(Amount, C, Coins, N, X3, plus_out_gag(s(C), NewAmount, Amount)) -> U6_GGA(Amount, C, Coins, N, X3, NewAmount, ways_in_gga(Amount, Coins, N1)) U5_GGA(Amount, C, Coins, N, X3, plus_out_gag(s(C), NewAmount, Amount)) -> WAYS_IN_GGA(Amount, Coins, N1) WAYS_IN_GGA(Amount, .(s(C), Coins), N) -> U9_GGA(Amount, C, Coins, N, =_in_ga(Amount, s(X4))) U9_GGA(Amount, C, Coins, N, =_out_ga(Amount, s(X4))) -> U10_GGA(Amount, C, Coins, N, X4, plus_in_gag(Amount, s(X5), s(C))) U9_GGA(Amount, C, Coins, N, =_out_ga(Amount, s(X4))) -> PLUS_IN_GAG(Amount, s(X5), s(C)) U10_GGA(Amount, C, Coins, N, X4, plus_out_gag(Amount, s(X5), s(C))) -> U11_GGA(Amount, C, Coins, N, ways_in_gga(Amount, Coins, N)) U10_GGA(Amount, C, Coins, N, X4, plus_out_gag(Amount, s(X5), s(C))) -> WAYS_IN_GGA(Amount, Coins, N) U6_GGA(Amount, C, Coins, N, X3, NewAmount, ways_out_gga(Amount, Coins, N1)) -> U7_GGA(Amount, C, Coins, N, X3, NewAmount, N1, ways_in_gga(NewAmount, .(s(C), Coins), N2)) U6_GGA(Amount, C, Coins, N, X3, NewAmount, ways_out_gga(Amount, Coins, N1)) -> WAYS_IN_GGA(NewAmount, .(s(C), Coins), N2) U7_GGA(Amount, C, Coins, N, X3, NewAmount, N1, ways_out_gga(NewAmount, .(s(C), Coins), N2)) -> U8_GGA(Amount, C, Coins, N, plus_in_gga(N1, N2, N)) U7_GGA(Amount, C, Coins, N, X3, NewAmount, N1, ways_out_gga(NewAmount, .(s(C), Coins), N2)) -> PLUS_IN_GGA(N1, N2, N) PLUS_IN_GGA(0, X, X) -> U2_GGA(X, nat_in_g(X)) PLUS_IN_GGA(0, X, X) -> NAT_IN_G(X) PLUS_IN_GGA(s(X), Y, s(Z)) -> U3_GGA(X, Y, Z, plus_in_gga(X, Y, Z)) PLUS_IN_GGA(s(X), Y, s(Z)) -> PLUS_IN_GGA(X, Y, Z) The TRS R consists of the following rules: ways_in_gga(0, X1, s(0)) -> ways_out_gga(0, X1, s(0)) ways_in_gga(X2, [], 0) -> ways_out_gga(X2, [], 0) ways_in_gga(Amount, .(s(C), Coins), N) -> U4_gga(Amount, C, Coins, N, =_in_ga(Amount, s(X3))) =_in_ga(X, X) -> =_out_ga(X, X) U4_gga(Amount, C, Coins, N, =_out_ga(Amount, s(X3))) -> U5_gga(Amount, C, Coins, N, X3, plus_in_gag(s(C), NewAmount, Amount)) plus_in_gag(0, X, X) -> U2_gag(X, nat_in_g(X)) nat_in_g(0) -> nat_out_g(0) nat_in_g(s(X)) -> U1_g(X, nat_in_g(X)) U1_g(X, nat_out_g(X)) -> nat_out_g(s(X)) U2_gag(X, nat_out_g(X)) -> plus_out_gag(0, X, X) plus_in_gag(s(X), Y, s(Z)) -> U3_gag(X, Y, Z, plus_in_gag(X, Y, Z)) U3_gag(X, Y, Z, plus_out_gag(X, Y, Z)) -> plus_out_gag(s(X), Y, s(Z)) U5_gga(Amount, C, Coins, N, X3, plus_out_gag(s(C), NewAmount, Amount)) -> U6_gga(Amount, C, Coins, N, X3, NewAmount, ways_in_gga(Amount, Coins, N1)) ways_in_gga(Amount, .(s(C), Coins), N) -> U9_gga(Amount, C, Coins, N, =_in_ga(Amount, s(X4))) U9_gga(Amount, C, Coins, N, =_out_ga(Amount, s(X4))) -> U10_gga(Amount, C, Coins, N, X4, plus_in_gag(Amount, s(X5), s(C))) U10_gga(Amount, C, Coins, N, X4, plus_out_gag(Amount, s(X5), s(C))) -> U11_gga(Amount, C, Coins, N, ways_in_gga(Amount, Coins, N)) U11_gga(Amount, C, Coins, N, ways_out_gga(Amount, Coins, N)) -> ways_out_gga(Amount, .(s(C), Coins), N) U6_gga(Amount, C, Coins, N, X3, NewAmount, ways_out_gga(Amount, Coins, N1)) -> U7_gga(Amount, C, Coins, N, X3, NewAmount, N1, ways_in_gga(NewAmount, .(s(C), Coins), N2)) U7_gga(Amount, C, Coins, N, X3, NewAmount, N1, ways_out_gga(NewAmount, .(s(C), Coins), N2)) -> U8_gga(Amount, C, Coins, N, plus_in_gga(N1, N2, N)) plus_in_gga(0, X, X) -> U2_gga(X, nat_in_g(X)) U2_gga(X, nat_out_g(X)) -> plus_out_gga(0, X, X) plus_in_gga(s(X), Y, s(Z)) -> U3_gga(X, Y, Z, plus_in_gga(X, Y, Z)) U3_gga(X, Y, Z, plus_out_gga(X, Y, Z)) -> plus_out_gga(s(X), Y, s(Z)) U8_gga(Amount, C, Coins, N, plus_out_gga(N1, N2, N)) -> ways_out_gga(Amount, .(s(C), Coins), N) The argument filtering Pi contains the following mapping: ways_in_gga(x1, x2, x3) = ways_in_gga(x1, x2) 0 = 0 ways_out_gga(x1, x2, x3) = ways_out_gga(x3) [] = [] .(x1, x2) = .(x1, x2) s(x1) = s(x1) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x1, x2, x3, x5) =_in_ga(x1, x2) = =_in_ga(x1) =_out_ga(x1, x2) = =_out_ga(x2) U5_gga(x1, x2, x3, x4, x5, x6) = U5_gga(x1, x2, x3, x6) plus_in_gag(x1, x2, x3) = plus_in_gag(x1, x3) U2_gag(x1, x2) = U2_gag(x1, x2) nat_in_g(x1) = nat_in_g(x1) nat_out_g(x1) = nat_out_g U1_g(x1, x2) = U1_g(x2) plus_out_gag(x1, x2, x3) = plus_out_gag(x2) U3_gag(x1, x2, x3, x4) = U3_gag(x4) U6_gga(x1, x2, x3, x4, x5, x6, x7) = U6_gga(x2, x3, x6, x7) U9_gga(x1, x2, x3, x4, x5) = U9_gga(x1, x2, x3, x5) U10_gga(x1, x2, x3, x4, x5, x6) = U10_gga(x1, x3, x6) U11_gga(x1, x2, x3, x4, x5) = U11_gga(x5) U7_gga(x1, x2, x3, x4, x5, x6, x7, x8) = U7_gga(x7, x8) U8_gga(x1, x2, x3, x4, x5) = U8_gga(x5) plus_in_gga(x1, x2, x3) = plus_in_gga(x1, x2) U2_gga(x1, x2) = U2_gga(x1, x2) plus_out_gga(x1, x2, x3) = plus_out_gga(x3) U3_gga(x1, x2, x3, x4) = U3_gga(x4) WAYS_IN_GGA(x1, x2, x3) = WAYS_IN_GGA(x1, x2) U4_GGA(x1, x2, x3, x4, x5) = U4_GGA(x1, x2, x3, x5) =_IN_GA(x1, x2) = =_IN_GA(x1) U5_GGA(x1, x2, x3, x4, x5, x6) = U5_GGA(x1, x2, x3, x6) PLUS_IN_GAG(x1, x2, x3) = PLUS_IN_GAG(x1, x3) U2_GAG(x1, x2) = U2_GAG(x1, x2) NAT_IN_G(x1) = NAT_IN_G(x1) U1_G(x1, x2) = U1_G(x2) U3_GAG(x1, x2, x3, x4) = U3_GAG(x4) U6_GGA(x1, x2, x3, x4, x5, x6, x7) = U6_GGA(x2, x3, x6, x7) U9_GGA(x1, x2, x3, x4, x5) = U9_GGA(x1, x2, x3, x5) U10_GGA(x1, x2, x3, x4, x5, x6) = U10_GGA(x1, x3, x6) U11_GGA(x1, x2, x3, x4, x5) = U11_GGA(x5) U7_GGA(x1, x2, x3, x4, x5, x6, x7, x8) = U7_GGA(x7, x8) U8_GGA(x1, x2, x3, x4, x5) = U8_GGA(x5) PLUS_IN_GGA(x1, x2, x3) = PLUS_IN_GGA(x1, x2) U2_GGA(x1, x2) = U2_GGA(x1, x2) U3_GGA(x1, x2, x3, x4) = U3_GGA(x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (7) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 4 SCCs with 14 less nodes. ---------------------------------------- (8) Complex Obligation (AND) ---------------------------------------- (9) Obligation: Pi DP problem: The TRS P consists of the following rules: NAT_IN_G(s(X)) -> NAT_IN_G(X) The TRS R consists of the following rules: ways_in_gga(0, X1, s(0)) -> ways_out_gga(0, X1, s(0)) ways_in_gga(X2, [], 0) -> ways_out_gga(X2, [], 0) ways_in_gga(Amount, .(s(C), Coins), N) -> U4_gga(Amount, C, Coins, N, =_in_ga(Amount, s(X3))) =_in_ga(X, X) -> =_out_ga(X, X) U4_gga(Amount, C, Coins, N, =_out_ga(Amount, s(X3))) -> U5_gga(Amount, C, Coins, N, X3, plus_in_gag(s(C), NewAmount, Amount)) plus_in_gag(0, X, X) -> U2_gag(X, nat_in_g(X)) nat_in_g(0) -> nat_out_g(0) nat_in_g(s(X)) -> U1_g(X, nat_in_g(X)) U1_g(X, nat_out_g(X)) -> nat_out_g(s(X)) U2_gag(X, nat_out_g(X)) -> plus_out_gag(0, X, X) plus_in_gag(s(X), Y, s(Z)) -> U3_gag(X, Y, Z, plus_in_gag(X, Y, Z)) U3_gag(X, Y, Z, plus_out_gag(X, Y, Z)) -> plus_out_gag(s(X), Y, s(Z)) U5_gga(Amount, C, Coins, N, X3, plus_out_gag(s(C), NewAmount, Amount)) -> U6_gga(Amount, C, Coins, N, X3, NewAmount, ways_in_gga(Amount, Coins, N1)) ways_in_gga(Amount, .(s(C), Coins), N) -> U9_gga(Amount, C, Coins, N, =_in_ga(Amount, s(X4))) U9_gga(Amount, C, Coins, N, =_out_ga(Amount, s(X4))) -> U10_gga(Amount, C, Coins, N, X4, plus_in_gag(Amount, s(X5), s(C))) U10_gga(Amount, C, Coins, N, X4, plus_out_gag(Amount, s(X5), s(C))) -> U11_gga(Amount, C, Coins, N, ways_in_gga(Amount, Coins, N)) U11_gga(Amount, C, Coins, N, ways_out_gga(Amount, Coins, N)) -> ways_out_gga(Amount, .(s(C), Coins), N) U6_gga(Amount, C, Coins, N, X3, NewAmount, ways_out_gga(Amount, Coins, N1)) -> U7_gga(Amount, C, Coins, N, X3, NewAmount, N1, ways_in_gga(NewAmount, .(s(C), Coins), N2)) U7_gga(Amount, C, Coins, N, X3, NewAmount, N1, ways_out_gga(NewAmount, .(s(C), Coins), N2)) -> U8_gga(Amount, C, Coins, N, plus_in_gga(N1, N2, N)) plus_in_gga(0, X, X) -> U2_gga(X, nat_in_g(X)) U2_gga(X, nat_out_g(X)) -> plus_out_gga(0, X, X) plus_in_gga(s(X), Y, s(Z)) -> U3_gga(X, Y, Z, plus_in_gga(X, Y, Z)) U3_gga(X, Y, Z, plus_out_gga(X, Y, Z)) -> plus_out_gga(s(X), Y, s(Z)) U8_gga(Amount, C, Coins, N, plus_out_gga(N1, N2, N)) -> ways_out_gga(Amount, .(s(C), Coins), N) The argument filtering Pi contains the following mapping: ways_in_gga(x1, x2, x3) = ways_in_gga(x1, x2) 0 = 0 ways_out_gga(x1, x2, x3) = ways_out_gga(x3) [] = [] .(x1, x2) = .(x1, x2) s(x1) = s(x1) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x1, x2, x3, x5) =_in_ga(x1, x2) = =_in_ga(x1) =_out_ga(x1, x2) = =_out_ga(x2) U5_gga(x1, x2, x3, x4, x5, x6) = U5_gga(x1, x2, x3, x6) plus_in_gag(x1, x2, x3) = plus_in_gag(x1, x3) U2_gag(x1, x2) = U2_gag(x1, x2) nat_in_g(x1) = nat_in_g(x1) nat_out_g(x1) = nat_out_g U1_g(x1, x2) = U1_g(x2) plus_out_gag(x1, x2, x3) = plus_out_gag(x2) U3_gag(x1, x2, x3, x4) = U3_gag(x4) U6_gga(x1, x2, x3, x4, x5, x6, x7) = U6_gga(x2, x3, x6, x7) U9_gga(x1, x2, x3, x4, x5) = U9_gga(x1, x2, x3, x5) U10_gga(x1, x2, x3, x4, x5, x6) = U10_gga(x1, x3, x6) U11_gga(x1, x2, x3, x4, x5) = U11_gga(x5) U7_gga(x1, x2, x3, x4, x5, x6, x7, x8) = U7_gga(x7, x8) U8_gga(x1, x2, x3, x4, x5) = U8_gga(x5) plus_in_gga(x1, x2, x3) = plus_in_gga(x1, x2) U2_gga(x1, x2) = U2_gga(x1, x2) plus_out_gga(x1, x2, x3) = plus_out_gga(x3) U3_gga(x1, x2, x3, x4) = U3_gga(x4) NAT_IN_G(x1) = NAT_IN_G(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (11) Obligation: Pi DP problem: The TRS P consists of the following rules: NAT_IN_G(s(X)) -> NAT_IN_G(X) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (12) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (13) Obligation: Q DP problem: The TRS P consists of the following rules: NAT_IN_G(s(X)) -> NAT_IN_G(X) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (14) 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: *NAT_IN_G(s(X)) -> NAT_IN_G(X) The graph contains the following edges 1 > 1 ---------------------------------------- (15) YES ---------------------------------------- (16) Obligation: Pi DP problem: The TRS P consists of the following rules: PLUS_IN_GGA(s(X), Y, s(Z)) -> PLUS_IN_GGA(X, Y, Z) The TRS R consists of the following rules: ways_in_gga(0, X1, s(0)) -> ways_out_gga(0, X1, s(0)) ways_in_gga(X2, [], 0) -> ways_out_gga(X2, [], 0) ways_in_gga(Amount, .(s(C), Coins), N) -> U4_gga(Amount, C, Coins, N, =_in_ga(Amount, s(X3))) =_in_ga(X, X) -> =_out_ga(X, X) U4_gga(Amount, C, Coins, N, =_out_ga(Amount, s(X3))) -> U5_gga(Amount, C, Coins, N, X3, plus_in_gag(s(C), NewAmount, Amount)) plus_in_gag(0, X, X) -> U2_gag(X, nat_in_g(X)) nat_in_g(0) -> nat_out_g(0) nat_in_g(s(X)) -> U1_g(X, nat_in_g(X)) U1_g(X, nat_out_g(X)) -> nat_out_g(s(X)) U2_gag(X, nat_out_g(X)) -> plus_out_gag(0, X, X) plus_in_gag(s(X), Y, s(Z)) -> U3_gag(X, Y, Z, plus_in_gag(X, Y, Z)) U3_gag(X, Y, Z, plus_out_gag(X, Y, Z)) -> plus_out_gag(s(X), Y, s(Z)) U5_gga(Amount, C, Coins, N, X3, plus_out_gag(s(C), NewAmount, Amount)) -> U6_gga(Amount, C, Coins, N, X3, NewAmount, ways_in_gga(Amount, Coins, N1)) ways_in_gga(Amount, .(s(C), Coins), N) -> U9_gga(Amount, C, Coins, N, =_in_ga(Amount, s(X4))) U9_gga(Amount, C, Coins, N, =_out_ga(Amount, s(X4))) -> U10_gga(Amount, C, Coins, N, X4, plus_in_gag(Amount, s(X5), s(C))) U10_gga(Amount, C, Coins, N, X4, plus_out_gag(Amount, s(X5), s(C))) -> U11_gga(Amount, C, Coins, N, ways_in_gga(Amount, Coins, N)) U11_gga(Amount, C, Coins, N, ways_out_gga(Amount, Coins, N)) -> ways_out_gga(Amount, .(s(C), Coins), N) U6_gga(Amount, C, Coins, N, X3, NewAmount, ways_out_gga(Amount, Coins, N1)) -> U7_gga(Amount, C, Coins, N, X3, NewAmount, N1, ways_in_gga(NewAmount, .(s(C), Coins), N2)) U7_gga(Amount, C, Coins, N, X3, NewAmount, N1, ways_out_gga(NewAmount, .(s(C), Coins), N2)) -> U8_gga(Amount, C, Coins, N, plus_in_gga(N1, N2, N)) plus_in_gga(0, X, X) -> U2_gga(X, nat_in_g(X)) U2_gga(X, nat_out_g(X)) -> plus_out_gga(0, X, X) plus_in_gga(s(X), Y, s(Z)) -> U3_gga(X, Y, Z, plus_in_gga(X, Y, Z)) U3_gga(X, Y, Z, plus_out_gga(X, Y, Z)) -> plus_out_gga(s(X), Y, s(Z)) U8_gga(Amount, C, Coins, N, plus_out_gga(N1, N2, N)) -> ways_out_gga(Amount, .(s(C), Coins), N) The argument filtering Pi contains the following mapping: ways_in_gga(x1, x2, x3) = ways_in_gga(x1, x2) 0 = 0 ways_out_gga(x1, x2, x3) = ways_out_gga(x3) [] = [] .(x1, x2) = .(x1, x2) s(x1) = s(x1) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x1, x2, x3, x5) =_in_ga(x1, x2) = =_in_ga(x1) =_out_ga(x1, x2) = =_out_ga(x2) U5_gga(x1, x2, x3, x4, x5, x6) = U5_gga(x1, x2, x3, x6) plus_in_gag(x1, x2, x3) = plus_in_gag(x1, x3) U2_gag(x1, x2) = U2_gag(x1, x2) nat_in_g(x1) = nat_in_g(x1) nat_out_g(x1) = nat_out_g U1_g(x1, x2) = U1_g(x2) plus_out_gag(x1, x2, x3) = plus_out_gag(x2) U3_gag(x1, x2, x3, x4) = U3_gag(x4) U6_gga(x1, x2, x3, x4, x5, x6, x7) = U6_gga(x2, x3, x6, x7) U9_gga(x1, x2, x3, x4, x5) = U9_gga(x1, x2, x3, x5) U10_gga(x1, x2, x3, x4, x5, x6) = U10_gga(x1, x3, x6) U11_gga(x1, x2, x3, x4, x5) = U11_gga(x5) U7_gga(x1, x2, x3, x4, x5, x6, x7, x8) = U7_gga(x7, x8) U8_gga(x1, x2, x3, x4, x5) = U8_gga(x5) plus_in_gga(x1, x2, x3) = plus_in_gga(x1, x2) U2_gga(x1, x2) = U2_gga(x1, x2) plus_out_gga(x1, x2, x3) = plus_out_gga(x3) U3_gga(x1, x2, x3, x4) = U3_gga(x4) PLUS_IN_GGA(x1, x2, x3) = PLUS_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (18) Obligation: Pi DP problem: The TRS P consists of the following rules: PLUS_IN_GGA(s(X), Y, s(Z)) -> PLUS_IN_GGA(X, Y, Z) R is empty. The argument filtering Pi contains the following mapping: s(x1) = s(x1) PLUS_IN_GGA(x1, x2, x3) = PLUS_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (19) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: PLUS_IN_GGA(s(X), Y) -> PLUS_IN_GGA(X, Y) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (21) 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: *PLUS_IN_GGA(s(X), Y) -> PLUS_IN_GGA(X, Y) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (22) YES ---------------------------------------- (23) Obligation: Pi DP problem: The TRS P consists of the following rules: PLUS_IN_GAG(s(X), Y, s(Z)) -> PLUS_IN_GAG(X, Y, Z) The TRS R consists of the following rules: ways_in_gga(0, X1, s(0)) -> ways_out_gga(0, X1, s(0)) ways_in_gga(X2, [], 0) -> ways_out_gga(X2, [], 0) ways_in_gga(Amount, .(s(C), Coins), N) -> U4_gga(Amount, C, Coins, N, =_in_ga(Amount, s(X3))) =_in_ga(X, X) -> =_out_ga(X, X) U4_gga(Amount, C, Coins, N, =_out_ga(Amount, s(X3))) -> U5_gga(Amount, C, Coins, N, X3, plus_in_gag(s(C), NewAmount, Amount)) plus_in_gag(0, X, X) -> U2_gag(X, nat_in_g(X)) nat_in_g(0) -> nat_out_g(0) nat_in_g(s(X)) -> U1_g(X, nat_in_g(X)) U1_g(X, nat_out_g(X)) -> nat_out_g(s(X)) U2_gag(X, nat_out_g(X)) -> plus_out_gag(0, X, X) plus_in_gag(s(X), Y, s(Z)) -> U3_gag(X, Y, Z, plus_in_gag(X, Y, Z)) U3_gag(X, Y, Z, plus_out_gag(X, Y, Z)) -> plus_out_gag(s(X), Y, s(Z)) U5_gga(Amount, C, Coins, N, X3, plus_out_gag(s(C), NewAmount, Amount)) -> U6_gga(Amount, C, Coins, N, X3, NewAmount, ways_in_gga(Amount, Coins, N1)) ways_in_gga(Amount, .(s(C), Coins), N) -> U9_gga(Amount, C, Coins, N, =_in_ga(Amount, s(X4))) U9_gga(Amount, C, Coins, N, =_out_ga(Amount, s(X4))) -> U10_gga(Amount, C, Coins, N, X4, plus_in_gag(Amount, s(X5), s(C))) U10_gga(Amount, C, Coins, N, X4, plus_out_gag(Amount, s(X5), s(C))) -> U11_gga(Amount, C, Coins, N, ways_in_gga(Amount, Coins, N)) U11_gga(Amount, C, Coins, N, ways_out_gga(Amount, Coins, N)) -> ways_out_gga(Amount, .(s(C), Coins), N) U6_gga(Amount, C, Coins, N, X3, NewAmount, ways_out_gga(Amount, Coins, N1)) -> U7_gga(Amount, C, Coins, N, X3, NewAmount, N1, ways_in_gga(NewAmount, .(s(C), Coins), N2)) U7_gga(Amount, C, Coins, N, X3, NewAmount, N1, ways_out_gga(NewAmount, .(s(C), Coins), N2)) -> U8_gga(Amount, C, Coins, N, plus_in_gga(N1, N2, N)) plus_in_gga(0, X, X) -> U2_gga(X, nat_in_g(X)) U2_gga(X, nat_out_g(X)) -> plus_out_gga(0, X, X) plus_in_gga(s(X), Y, s(Z)) -> U3_gga(X, Y, Z, plus_in_gga(X, Y, Z)) U3_gga(X, Y, Z, plus_out_gga(X, Y, Z)) -> plus_out_gga(s(X), Y, s(Z)) U8_gga(Amount, C, Coins, N, plus_out_gga(N1, N2, N)) -> ways_out_gga(Amount, .(s(C), Coins), N) The argument filtering Pi contains the following mapping: ways_in_gga(x1, x2, x3) = ways_in_gga(x1, x2) 0 = 0 ways_out_gga(x1, x2, x3) = ways_out_gga(x3) [] = [] .(x1, x2) = .(x1, x2) s(x1) = s(x1) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x1, x2, x3, x5) =_in_ga(x1, x2) = =_in_ga(x1) =_out_ga(x1, x2) = =_out_ga(x2) U5_gga(x1, x2, x3, x4, x5, x6) = U5_gga(x1, x2, x3, x6) plus_in_gag(x1, x2, x3) = plus_in_gag(x1, x3) U2_gag(x1, x2) = U2_gag(x1, x2) nat_in_g(x1) = nat_in_g(x1) nat_out_g(x1) = nat_out_g U1_g(x1, x2) = U1_g(x2) plus_out_gag(x1, x2, x3) = plus_out_gag(x2) U3_gag(x1, x2, x3, x4) = U3_gag(x4) U6_gga(x1, x2, x3, x4, x5, x6, x7) = U6_gga(x2, x3, x6, x7) U9_gga(x1, x2, x3, x4, x5) = U9_gga(x1, x2, x3, x5) U10_gga(x1, x2, x3, x4, x5, x6) = U10_gga(x1, x3, x6) U11_gga(x1, x2, x3, x4, x5) = U11_gga(x5) U7_gga(x1, x2, x3, x4, x5, x6, x7, x8) = U7_gga(x7, x8) U8_gga(x1, x2, x3, x4, x5) = U8_gga(x5) plus_in_gga(x1, x2, x3) = plus_in_gga(x1, x2) U2_gga(x1, x2) = U2_gga(x1, x2) plus_out_gga(x1, x2, x3) = plus_out_gga(x3) U3_gga(x1, x2, x3, x4) = U3_gga(x4) PLUS_IN_GAG(x1, x2, x3) = PLUS_IN_GAG(x1, x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (24) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (25) Obligation: Pi DP problem: The TRS P consists of the following rules: PLUS_IN_GAG(s(X), Y, s(Z)) -> PLUS_IN_GAG(X, Y, Z) R is empty. The argument filtering Pi contains the following mapping: s(x1) = s(x1) PLUS_IN_GAG(x1, x2, x3) = PLUS_IN_GAG(x1, x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (26) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: PLUS_IN_GAG(s(X), s(Z)) -> PLUS_IN_GAG(X, Z) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (28) 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: *PLUS_IN_GAG(s(X), s(Z)) -> PLUS_IN_GAG(X, Z) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (29) YES ---------------------------------------- (30) Obligation: Pi DP problem: The TRS P consists of the following rules: U4_GGA(Amount, C, Coins, N, =_out_ga(Amount, s(X3))) -> U5_GGA(Amount, C, Coins, N, X3, plus_in_gag(s(C), NewAmount, Amount)) U5_GGA(Amount, C, Coins, N, X3, plus_out_gag(s(C), NewAmount, Amount)) -> U6_GGA(Amount, C, Coins, N, X3, NewAmount, ways_in_gga(Amount, Coins, N1)) U6_GGA(Amount, C, Coins, N, X3, NewAmount, ways_out_gga(Amount, Coins, N1)) -> WAYS_IN_GGA(NewAmount, .(s(C), Coins), N2) WAYS_IN_GGA(Amount, .(s(C), Coins), N) -> U4_GGA(Amount, C, Coins, N, =_in_ga(Amount, s(X3))) WAYS_IN_GGA(Amount, .(s(C), Coins), N) -> U9_GGA(Amount, C, Coins, N, =_in_ga(Amount, s(X4))) U9_GGA(Amount, C, Coins, N, =_out_ga(Amount, s(X4))) -> U10_GGA(Amount, C, Coins, N, X4, plus_in_gag(Amount, s(X5), s(C))) U10_GGA(Amount, C, Coins, N, X4, plus_out_gag(Amount, s(X5), s(C))) -> WAYS_IN_GGA(Amount, Coins, N) U5_GGA(Amount, C, Coins, N, X3, plus_out_gag(s(C), NewAmount, Amount)) -> WAYS_IN_GGA(Amount, Coins, N1) The TRS R consists of the following rules: ways_in_gga(0, X1, s(0)) -> ways_out_gga(0, X1, s(0)) ways_in_gga(X2, [], 0) -> ways_out_gga(X2, [], 0) ways_in_gga(Amount, .(s(C), Coins), N) -> U4_gga(Amount, C, Coins, N, =_in_ga(Amount, s(X3))) =_in_ga(X, X) -> =_out_ga(X, X) U4_gga(Amount, C, Coins, N, =_out_ga(Amount, s(X3))) -> U5_gga(Amount, C, Coins, N, X3, plus_in_gag(s(C), NewAmount, Amount)) plus_in_gag(0, X, X) -> U2_gag(X, nat_in_g(X)) nat_in_g(0) -> nat_out_g(0) nat_in_g(s(X)) -> U1_g(X, nat_in_g(X)) U1_g(X, nat_out_g(X)) -> nat_out_g(s(X)) U2_gag(X, nat_out_g(X)) -> plus_out_gag(0, X, X) plus_in_gag(s(X), Y, s(Z)) -> U3_gag(X, Y, Z, plus_in_gag(X, Y, Z)) U3_gag(X, Y, Z, plus_out_gag(X, Y, Z)) -> plus_out_gag(s(X), Y, s(Z)) U5_gga(Amount, C, Coins, N, X3, plus_out_gag(s(C), NewAmount, Amount)) -> U6_gga(Amount, C, Coins, N, X3, NewAmount, ways_in_gga(Amount, Coins, N1)) ways_in_gga(Amount, .(s(C), Coins), N) -> U9_gga(Amount, C, Coins, N, =_in_ga(Amount, s(X4))) U9_gga(Amount, C, Coins, N, =_out_ga(Amount, s(X4))) -> U10_gga(Amount, C, Coins, N, X4, plus_in_gag(Amount, s(X5), s(C))) U10_gga(Amount, C, Coins, N, X4, plus_out_gag(Amount, s(X5), s(C))) -> U11_gga(Amount, C, Coins, N, ways_in_gga(Amount, Coins, N)) U11_gga(Amount, C, Coins, N, ways_out_gga(Amount, Coins, N)) -> ways_out_gga(Amount, .(s(C), Coins), N) U6_gga(Amount, C, Coins, N, X3, NewAmount, ways_out_gga(Amount, Coins, N1)) -> U7_gga(Amount, C, Coins, N, X3, NewAmount, N1, ways_in_gga(NewAmount, .(s(C), Coins), N2)) U7_gga(Amount, C, Coins, N, X3, NewAmount, N1, ways_out_gga(NewAmount, .(s(C), Coins), N2)) -> U8_gga(Amount, C, Coins, N, plus_in_gga(N1, N2, N)) plus_in_gga(0, X, X) -> U2_gga(X, nat_in_g(X)) U2_gga(X, nat_out_g(X)) -> plus_out_gga(0, X, X) plus_in_gga(s(X), Y, s(Z)) -> U3_gga(X, Y, Z, plus_in_gga(X, Y, Z)) U3_gga(X, Y, Z, plus_out_gga(X, Y, Z)) -> plus_out_gga(s(X), Y, s(Z)) U8_gga(Amount, C, Coins, N, plus_out_gga(N1, N2, N)) -> ways_out_gga(Amount, .(s(C), Coins), N) The argument filtering Pi contains the following mapping: ways_in_gga(x1, x2, x3) = ways_in_gga(x1, x2) 0 = 0 ways_out_gga(x1, x2, x3) = ways_out_gga(x3) [] = [] .(x1, x2) = .(x1, x2) s(x1) = s(x1) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x1, x2, x3, x5) =_in_ga(x1, x2) = =_in_ga(x1) =_out_ga(x1, x2) = =_out_ga(x2) U5_gga(x1, x2, x3, x4, x5, x6) = U5_gga(x1, x2, x3, x6) plus_in_gag(x1, x2, x3) = plus_in_gag(x1, x3) U2_gag(x1, x2) = U2_gag(x1, x2) nat_in_g(x1) = nat_in_g(x1) nat_out_g(x1) = nat_out_g U1_g(x1, x2) = U1_g(x2) plus_out_gag(x1, x2, x3) = plus_out_gag(x2) U3_gag(x1, x2, x3, x4) = U3_gag(x4) U6_gga(x1, x2, x3, x4, x5, x6, x7) = U6_gga(x2, x3, x6, x7) U9_gga(x1, x2, x3, x4, x5) = U9_gga(x1, x2, x3, x5) U10_gga(x1, x2, x3, x4, x5, x6) = U10_gga(x1, x3, x6) U11_gga(x1, x2, x3, x4, x5) = U11_gga(x5) U7_gga(x1, x2, x3, x4, x5, x6, x7, x8) = U7_gga(x7, x8) U8_gga(x1, x2, x3, x4, x5) = U8_gga(x5) plus_in_gga(x1, x2, x3) = plus_in_gga(x1, x2) U2_gga(x1, x2) = U2_gga(x1, x2) plus_out_gga(x1, x2, x3) = plus_out_gga(x3) U3_gga(x1, x2, x3, x4) = U3_gga(x4) WAYS_IN_GGA(x1, x2, x3) = WAYS_IN_GGA(x1, x2) U4_GGA(x1, x2, x3, x4, x5) = U4_GGA(x1, x2, x3, x5) U5_GGA(x1, x2, x3, x4, x5, x6) = U5_GGA(x1, x2, x3, x6) U6_GGA(x1, x2, x3, x4, x5, x6, x7) = U6_GGA(x2, x3, x6, x7) U9_GGA(x1, x2, x3, x4, x5) = U9_GGA(x1, x2, x3, x5) U10_GGA(x1, x2, x3, x4, x5, x6) = U10_GGA(x1, x3, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (31) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: U4_GGA(Amount, C, Coins, =_out_ga(s(X3))) -> U5_GGA(Amount, C, Coins, plus_in_gag(s(C), Amount)) U5_GGA(Amount, C, Coins, plus_out_gag(NewAmount)) -> U6_GGA(C, Coins, NewAmount, ways_in_gga(Amount, Coins)) U6_GGA(C, Coins, NewAmount, ways_out_gga(N1)) -> WAYS_IN_GGA(NewAmount, .(s(C), Coins)) WAYS_IN_GGA(Amount, .(s(C), Coins)) -> U4_GGA(Amount, C, Coins, =_in_ga(Amount)) WAYS_IN_GGA(Amount, .(s(C), Coins)) -> U9_GGA(Amount, C, Coins, =_in_ga(Amount)) U9_GGA(Amount, C, Coins, =_out_ga(s(X4))) -> U10_GGA(Amount, Coins, plus_in_gag(Amount, s(C))) U10_GGA(Amount, Coins, plus_out_gag(s(X5))) -> WAYS_IN_GGA(Amount, Coins) U5_GGA(Amount, C, Coins, plus_out_gag(NewAmount)) -> WAYS_IN_GGA(Amount, Coins) The TRS R consists of the following rules: ways_in_gga(0, X1) -> ways_out_gga(s(0)) ways_in_gga(X2, []) -> ways_out_gga(0) ways_in_gga(Amount, .(s(C), Coins)) -> U4_gga(Amount, C, Coins, =_in_ga(Amount)) =_in_ga(X) -> =_out_ga(X) U4_gga(Amount, C, Coins, =_out_ga(s(X3))) -> U5_gga(Amount, C, Coins, plus_in_gag(s(C), Amount)) plus_in_gag(0, X) -> U2_gag(X, nat_in_g(X)) nat_in_g(0) -> nat_out_g nat_in_g(s(X)) -> U1_g(nat_in_g(X)) U1_g(nat_out_g) -> nat_out_g U2_gag(X, nat_out_g) -> plus_out_gag(X) plus_in_gag(s(X), s(Z)) -> U3_gag(plus_in_gag(X, Z)) U3_gag(plus_out_gag(Y)) -> plus_out_gag(Y) U5_gga(Amount, C, Coins, plus_out_gag(NewAmount)) -> U6_gga(C, Coins, NewAmount, ways_in_gga(Amount, Coins)) ways_in_gga(Amount, .(s(C), Coins)) -> U9_gga(Amount, C, Coins, =_in_ga(Amount)) U9_gga(Amount, C, Coins, =_out_ga(s(X4))) -> U10_gga(Amount, Coins, plus_in_gag(Amount, s(C))) U10_gga(Amount, Coins, plus_out_gag(s(X5))) -> U11_gga(ways_in_gga(Amount, Coins)) U11_gga(ways_out_gga(N)) -> ways_out_gga(N) U6_gga(C, Coins, NewAmount, ways_out_gga(N1)) -> U7_gga(N1, ways_in_gga(NewAmount, .(s(C), Coins))) U7_gga(N1, ways_out_gga(N2)) -> U8_gga(plus_in_gga(N1, N2)) plus_in_gga(0, X) -> U2_gga(X, nat_in_g(X)) U2_gga(X, nat_out_g) -> plus_out_gga(X) plus_in_gga(s(X), Y) -> U3_gga(plus_in_gga(X, Y)) U3_gga(plus_out_gga(Z)) -> plus_out_gga(s(Z)) U8_gga(plus_out_gga(N)) -> ways_out_gga(N) The set Q consists of the following terms: ways_in_gga(x0, x1) =_in_ga(x0) U4_gga(x0, x1, x2, x3) plus_in_gag(x0, x1) nat_in_g(x0) U1_g(x0) U2_gag(x0, x1) U3_gag(x0) U5_gga(x0, x1, x2, x3) U9_gga(x0, x1, x2, x3) U10_gga(x0, x1, x2) U11_gga(x0) U6_gga(x0, x1, x2, x3) U7_gga(x0, x1) plus_in_gga(x0, x1) U2_gga(x0, x1) U3_gga(x0) U8_gga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (33) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule WAYS_IN_GGA(Amount, .(s(C), Coins)) -> U4_GGA(Amount, C, Coins, =_in_ga(Amount)) at position [3] we obtained the following new rules [LPAR04]: (WAYS_IN_GGA(Amount, .(s(C), Coins)) -> U4_GGA(Amount, C, Coins, =_out_ga(Amount)),WAYS_IN_GGA(Amount, .(s(C), Coins)) -> U4_GGA(Amount, C, Coins, =_out_ga(Amount))) ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: U4_GGA(Amount, C, Coins, =_out_ga(s(X3))) -> U5_GGA(Amount, C, Coins, plus_in_gag(s(C), Amount)) U5_GGA(Amount, C, Coins, plus_out_gag(NewAmount)) -> U6_GGA(C, Coins, NewAmount, ways_in_gga(Amount, Coins)) U6_GGA(C, Coins, NewAmount, ways_out_gga(N1)) -> WAYS_IN_GGA(NewAmount, .(s(C), Coins)) WAYS_IN_GGA(Amount, .(s(C), Coins)) -> U9_GGA(Amount, C, Coins, =_in_ga(Amount)) U9_GGA(Amount, C, Coins, =_out_ga(s(X4))) -> U10_GGA(Amount, Coins, plus_in_gag(Amount, s(C))) U10_GGA(Amount, Coins, plus_out_gag(s(X5))) -> WAYS_IN_GGA(Amount, Coins) U5_GGA(Amount, C, Coins, plus_out_gag(NewAmount)) -> WAYS_IN_GGA(Amount, Coins) WAYS_IN_GGA(Amount, .(s(C), Coins)) -> U4_GGA(Amount, C, Coins, =_out_ga(Amount)) The TRS R consists of the following rules: ways_in_gga(0, X1) -> ways_out_gga(s(0)) ways_in_gga(X2, []) -> ways_out_gga(0) ways_in_gga(Amount, .(s(C), Coins)) -> U4_gga(Amount, C, Coins, =_in_ga(Amount)) =_in_ga(X) -> =_out_ga(X) U4_gga(Amount, C, Coins, =_out_ga(s(X3))) -> U5_gga(Amount, C, Coins, plus_in_gag(s(C), Amount)) plus_in_gag(0, X) -> U2_gag(X, nat_in_g(X)) nat_in_g(0) -> nat_out_g nat_in_g(s(X)) -> U1_g(nat_in_g(X)) U1_g(nat_out_g) -> nat_out_g U2_gag(X, nat_out_g) -> plus_out_gag(X) plus_in_gag(s(X), s(Z)) -> U3_gag(plus_in_gag(X, Z)) U3_gag(plus_out_gag(Y)) -> plus_out_gag(Y) U5_gga(Amount, C, Coins, plus_out_gag(NewAmount)) -> U6_gga(C, Coins, NewAmount, ways_in_gga(Amount, Coins)) ways_in_gga(Amount, .(s(C), Coins)) -> U9_gga(Amount, C, Coins, =_in_ga(Amount)) U9_gga(Amount, C, Coins, =_out_ga(s(X4))) -> U10_gga(Amount, Coins, plus_in_gag(Amount, s(C))) U10_gga(Amount, Coins, plus_out_gag(s(X5))) -> U11_gga(ways_in_gga(Amount, Coins)) U11_gga(ways_out_gga(N)) -> ways_out_gga(N) U6_gga(C, Coins, NewAmount, ways_out_gga(N1)) -> U7_gga(N1, ways_in_gga(NewAmount, .(s(C), Coins))) U7_gga(N1, ways_out_gga(N2)) -> U8_gga(plus_in_gga(N1, N2)) plus_in_gga(0, X) -> U2_gga(X, nat_in_g(X)) U2_gga(X, nat_out_g) -> plus_out_gga(X) plus_in_gga(s(X), Y) -> U3_gga(plus_in_gga(X, Y)) U3_gga(plus_out_gga(Z)) -> plus_out_gga(s(Z)) U8_gga(plus_out_gga(N)) -> ways_out_gga(N) The set Q consists of the following terms: ways_in_gga(x0, x1) =_in_ga(x0) U4_gga(x0, x1, x2, x3) plus_in_gag(x0, x1) nat_in_g(x0) U1_g(x0) U2_gag(x0, x1) U3_gag(x0) U5_gga(x0, x1, x2, x3) U9_gga(x0, x1, x2, x3) U10_gga(x0, x1, x2) U11_gga(x0) U6_gga(x0, x1, x2, x3) U7_gga(x0, x1) plus_in_gga(x0, x1) U2_gga(x0, x1) U3_gga(x0) U8_gga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (35) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule WAYS_IN_GGA(Amount, .(s(C), Coins)) -> U9_GGA(Amount, C, Coins, =_in_ga(Amount)) at position [3] we obtained the following new rules [LPAR04]: (WAYS_IN_GGA(Amount, .(s(C), Coins)) -> U9_GGA(Amount, C, Coins, =_out_ga(Amount)),WAYS_IN_GGA(Amount, .(s(C), Coins)) -> U9_GGA(Amount, C, Coins, =_out_ga(Amount))) ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: U4_GGA(Amount, C, Coins, =_out_ga(s(X3))) -> U5_GGA(Amount, C, Coins, plus_in_gag(s(C), Amount)) U5_GGA(Amount, C, Coins, plus_out_gag(NewAmount)) -> U6_GGA(C, Coins, NewAmount, ways_in_gga(Amount, Coins)) U6_GGA(C, Coins, NewAmount, ways_out_gga(N1)) -> WAYS_IN_GGA(NewAmount, .(s(C), Coins)) U9_GGA(Amount, C, Coins, =_out_ga(s(X4))) -> U10_GGA(Amount, Coins, plus_in_gag(Amount, s(C))) U10_GGA(Amount, Coins, plus_out_gag(s(X5))) -> WAYS_IN_GGA(Amount, Coins) U5_GGA(Amount, C, Coins, plus_out_gag(NewAmount)) -> WAYS_IN_GGA(Amount, Coins) WAYS_IN_GGA(Amount, .(s(C), Coins)) -> U4_GGA(Amount, C, Coins, =_out_ga(Amount)) WAYS_IN_GGA(Amount, .(s(C), Coins)) -> U9_GGA(Amount, C, Coins, =_out_ga(Amount)) The TRS R consists of the following rules: ways_in_gga(0, X1) -> ways_out_gga(s(0)) ways_in_gga(X2, []) -> ways_out_gga(0) ways_in_gga(Amount, .(s(C), Coins)) -> U4_gga(Amount, C, Coins, =_in_ga(Amount)) =_in_ga(X) -> =_out_ga(X) U4_gga(Amount, C, Coins, =_out_ga(s(X3))) -> U5_gga(Amount, C, Coins, plus_in_gag(s(C), Amount)) plus_in_gag(0, X) -> U2_gag(X, nat_in_g(X)) nat_in_g(0) -> nat_out_g nat_in_g(s(X)) -> U1_g(nat_in_g(X)) U1_g(nat_out_g) -> nat_out_g U2_gag(X, nat_out_g) -> plus_out_gag(X) plus_in_gag(s(X), s(Z)) -> U3_gag(plus_in_gag(X, Z)) U3_gag(plus_out_gag(Y)) -> plus_out_gag(Y) U5_gga(Amount, C, Coins, plus_out_gag(NewAmount)) -> U6_gga(C, Coins, NewAmount, ways_in_gga(Amount, Coins)) ways_in_gga(Amount, .(s(C), Coins)) -> U9_gga(Amount, C, Coins, =_in_ga(Amount)) U9_gga(Amount, C, Coins, =_out_ga(s(X4))) -> U10_gga(Amount, Coins, plus_in_gag(Amount, s(C))) U10_gga(Amount, Coins, plus_out_gag(s(X5))) -> U11_gga(ways_in_gga(Amount, Coins)) U11_gga(ways_out_gga(N)) -> ways_out_gga(N) U6_gga(C, Coins, NewAmount, ways_out_gga(N1)) -> U7_gga(N1, ways_in_gga(NewAmount, .(s(C), Coins))) U7_gga(N1, ways_out_gga(N2)) -> U8_gga(plus_in_gga(N1, N2)) plus_in_gga(0, X) -> U2_gga(X, nat_in_g(X)) U2_gga(X, nat_out_g) -> plus_out_gga(X) plus_in_gga(s(X), Y) -> U3_gga(plus_in_gga(X, Y)) U3_gga(plus_out_gga(Z)) -> plus_out_gga(s(Z)) U8_gga(plus_out_gga(N)) -> ways_out_gga(N) The set Q consists of the following terms: ways_in_gga(x0, x1) =_in_ga(x0) U4_gga(x0, x1, x2, x3) plus_in_gag(x0, x1) nat_in_g(x0) U1_g(x0) U2_gag(x0, x1) U3_gag(x0) U5_gga(x0, x1, x2, x3) U9_gga(x0, x1, x2, x3) U10_gga(x0, x1, x2) U11_gga(x0) U6_gga(x0, x1, x2, x3) U7_gga(x0, x1) plus_in_gga(x0, x1) U2_gga(x0, x1) U3_gga(x0) U8_gga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (37) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U4_GGA(Amount, C, Coins, =_out_ga(s(X3))) -> U5_GGA(Amount, C, Coins, plus_in_gag(s(C), Amount)) we obtained the following new rules [LPAR04]: (U4_GGA(s(x3), z1, z2, =_out_ga(s(x3))) -> U5_GGA(s(x3), z1, z2, plus_in_gag(s(z1), s(x3))),U4_GGA(s(x3), z1, z2, =_out_ga(s(x3))) -> U5_GGA(s(x3), z1, z2, plus_in_gag(s(z1), s(x3)))) ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: U5_GGA(Amount, C, Coins, plus_out_gag(NewAmount)) -> U6_GGA(C, Coins, NewAmount, ways_in_gga(Amount, Coins)) U6_GGA(C, Coins, NewAmount, ways_out_gga(N1)) -> WAYS_IN_GGA(NewAmount, .(s(C), Coins)) U9_GGA(Amount, C, Coins, =_out_ga(s(X4))) -> U10_GGA(Amount, Coins, plus_in_gag(Amount, s(C))) U10_GGA(Amount, Coins, plus_out_gag(s(X5))) -> WAYS_IN_GGA(Amount, Coins) U5_GGA(Amount, C, Coins, plus_out_gag(NewAmount)) -> WAYS_IN_GGA(Amount, Coins) WAYS_IN_GGA(Amount, .(s(C), Coins)) -> U4_GGA(Amount, C, Coins, =_out_ga(Amount)) WAYS_IN_GGA(Amount, .(s(C), Coins)) -> U9_GGA(Amount, C, Coins, =_out_ga(Amount)) U4_GGA(s(x3), z1, z2, =_out_ga(s(x3))) -> U5_GGA(s(x3), z1, z2, plus_in_gag(s(z1), s(x3))) The TRS R consists of the following rules: ways_in_gga(0, X1) -> ways_out_gga(s(0)) ways_in_gga(X2, []) -> ways_out_gga(0) ways_in_gga(Amount, .(s(C), Coins)) -> U4_gga(Amount, C, Coins, =_in_ga(Amount)) =_in_ga(X) -> =_out_ga(X) U4_gga(Amount, C, Coins, =_out_ga(s(X3))) -> U5_gga(Amount, C, Coins, plus_in_gag(s(C), Amount)) plus_in_gag(0, X) -> U2_gag(X, nat_in_g(X)) nat_in_g(0) -> nat_out_g nat_in_g(s(X)) -> U1_g(nat_in_g(X)) U1_g(nat_out_g) -> nat_out_g U2_gag(X, nat_out_g) -> plus_out_gag(X) plus_in_gag(s(X), s(Z)) -> U3_gag(plus_in_gag(X, Z)) U3_gag(plus_out_gag(Y)) -> plus_out_gag(Y) U5_gga(Amount, C, Coins, plus_out_gag(NewAmount)) -> U6_gga(C, Coins, NewAmount, ways_in_gga(Amount, Coins)) ways_in_gga(Amount, .(s(C), Coins)) -> U9_gga(Amount, C, Coins, =_in_ga(Amount)) U9_gga(Amount, C, Coins, =_out_ga(s(X4))) -> U10_gga(Amount, Coins, plus_in_gag(Amount, s(C))) U10_gga(Amount, Coins, plus_out_gag(s(X5))) -> U11_gga(ways_in_gga(Amount, Coins)) U11_gga(ways_out_gga(N)) -> ways_out_gga(N) U6_gga(C, Coins, NewAmount, ways_out_gga(N1)) -> U7_gga(N1, ways_in_gga(NewAmount, .(s(C), Coins))) U7_gga(N1, ways_out_gga(N2)) -> U8_gga(plus_in_gga(N1, N2)) plus_in_gga(0, X) -> U2_gga(X, nat_in_g(X)) U2_gga(X, nat_out_g) -> plus_out_gga(X) plus_in_gga(s(X), Y) -> U3_gga(plus_in_gga(X, Y)) U3_gga(plus_out_gga(Z)) -> plus_out_gga(s(Z)) U8_gga(plus_out_gga(N)) -> ways_out_gga(N) The set Q consists of the following terms: ways_in_gga(x0, x1) =_in_ga(x0) U4_gga(x0, x1, x2, x3) plus_in_gag(x0, x1) nat_in_g(x0) U1_g(x0) U2_gag(x0, x1) U3_gag(x0) U5_gga(x0, x1, x2, x3) U9_gga(x0, x1, x2, x3) U10_gga(x0, x1, x2) U11_gga(x0) U6_gga(x0, x1, x2, x3) U7_gga(x0, x1) plus_in_gga(x0, x1) U2_gga(x0, x1) U3_gga(x0) U8_gga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (39) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule U4_GGA(s(x3), z1, z2, =_out_ga(s(x3))) -> U5_GGA(s(x3), z1, z2, plus_in_gag(s(z1), s(x3))) at position [3] we obtained the following new rules [LPAR04]: (U4_GGA(s(x3), z1, z2, =_out_ga(s(x3))) -> U5_GGA(s(x3), z1, z2, U3_gag(plus_in_gag(z1, x3))),U4_GGA(s(x3), z1, z2, =_out_ga(s(x3))) -> U5_GGA(s(x3), z1, z2, U3_gag(plus_in_gag(z1, x3)))) ---------------------------------------- (40) Obligation: Q DP problem: The TRS P consists of the following rules: U5_GGA(Amount, C, Coins, plus_out_gag(NewAmount)) -> U6_GGA(C, Coins, NewAmount, ways_in_gga(Amount, Coins)) U6_GGA(C, Coins, NewAmount, ways_out_gga(N1)) -> WAYS_IN_GGA(NewAmount, .(s(C), Coins)) U9_GGA(Amount, C, Coins, =_out_ga(s(X4))) -> U10_GGA(Amount, Coins, plus_in_gag(Amount, s(C))) U10_GGA(Amount, Coins, plus_out_gag(s(X5))) -> WAYS_IN_GGA(Amount, Coins) U5_GGA(Amount, C, Coins, plus_out_gag(NewAmount)) -> WAYS_IN_GGA(Amount, Coins) WAYS_IN_GGA(Amount, .(s(C), Coins)) -> U4_GGA(Amount, C, Coins, =_out_ga(Amount)) WAYS_IN_GGA(Amount, .(s(C), Coins)) -> U9_GGA(Amount, C, Coins, =_out_ga(Amount)) U4_GGA(s(x3), z1, z2, =_out_ga(s(x3))) -> U5_GGA(s(x3), z1, z2, U3_gag(plus_in_gag(z1, x3))) The TRS R consists of the following rules: ways_in_gga(0, X1) -> ways_out_gga(s(0)) ways_in_gga(X2, []) -> ways_out_gga(0) ways_in_gga(Amount, .(s(C), Coins)) -> U4_gga(Amount, C, Coins, =_in_ga(Amount)) =_in_ga(X) -> =_out_ga(X) U4_gga(Amount, C, Coins, =_out_ga(s(X3))) -> U5_gga(Amount, C, Coins, plus_in_gag(s(C), Amount)) plus_in_gag(0, X) -> U2_gag(X, nat_in_g(X)) nat_in_g(0) -> nat_out_g nat_in_g(s(X)) -> U1_g(nat_in_g(X)) U1_g(nat_out_g) -> nat_out_g U2_gag(X, nat_out_g) -> plus_out_gag(X) plus_in_gag(s(X), s(Z)) -> U3_gag(plus_in_gag(X, Z)) U3_gag(plus_out_gag(Y)) -> plus_out_gag(Y) U5_gga(Amount, C, Coins, plus_out_gag(NewAmount)) -> U6_gga(C, Coins, NewAmount, ways_in_gga(Amount, Coins)) ways_in_gga(Amount, .(s(C), Coins)) -> U9_gga(Amount, C, Coins, =_in_ga(Amount)) U9_gga(Amount, C, Coins, =_out_ga(s(X4))) -> U10_gga(Amount, Coins, plus_in_gag(Amount, s(C))) U10_gga(Amount, Coins, plus_out_gag(s(X5))) -> U11_gga(ways_in_gga(Amount, Coins)) U11_gga(ways_out_gga(N)) -> ways_out_gga(N) U6_gga(C, Coins, NewAmount, ways_out_gga(N1)) -> U7_gga(N1, ways_in_gga(NewAmount, .(s(C), Coins))) U7_gga(N1, ways_out_gga(N2)) -> U8_gga(plus_in_gga(N1, N2)) plus_in_gga(0, X) -> U2_gga(X, nat_in_g(X)) U2_gga(X, nat_out_g) -> plus_out_gga(X) plus_in_gga(s(X), Y) -> U3_gga(plus_in_gga(X, Y)) U3_gga(plus_out_gga(Z)) -> plus_out_gga(s(Z)) U8_gga(plus_out_gga(N)) -> ways_out_gga(N) The set Q consists of the following terms: ways_in_gga(x0, x1) =_in_ga(x0) U4_gga(x0, x1, x2, x3) plus_in_gag(x0, x1) nat_in_g(x0) U1_g(x0) U2_gag(x0, x1) U3_gag(x0) U5_gga(x0, x1, x2, x3) U9_gga(x0, x1, x2, x3) U10_gga(x0, x1, x2) U11_gga(x0) U6_gga(x0, x1, x2, x3) U7_gga(x0, x1) plus_in_gga(x0, x1) U2_gga(x0, x1) U3_gga(x0) U8_gga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (41) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U9_GGA(Amount, C, Coins, =_out_ga(s(X4))) -> U10_GGA(Amount, Coins, plus_in_gag(Amount, s(C))) we obtained the following new rules [LPAR04]: (U9_GGA(s(x3), z1, z2, =_out_ga(s(x3))) -> U10_GGA(s(x3), z2, plus_in_gag(s(x3), s(z1))),U9_GGA(s(x3), z1, z2, =_out_ga(s(x3))) -> U10_GGA(s(x3), z2, plus_in_gag(s(x3), s(z1)))) ---------------------------------------- (42) Obligation: Q DP problem: The TRS P consists of the following rules: U5_GGA(Amount, C, Coins, plus_out_gag(NewAmount)) -> U6_GGA(C, Coins, NewAmount, ways_in_gga(Amount, Coins)) U6_GGA(C, Coins, NewAmount, ways_out_gga(N1)) -> WAYS_IN_GGA(NewAmount, .(s(C), Coins)) U10_GGA(Amount, Coins, plus_out_gag(s(X5))) -> WAYS_IN_GGA(Amount, Coins) U5_GGA(Amount, C, Coins, plus_out_gag(NewAmount)) -> WAYS_IN_GGA(Amount, Coins) WAYS_IN_GGA(Amount, .(s(C), Coins)) -> U4_GGA(Amount, C, Coins, =_out_ga(Amount)) WAYS_IN_GGA(Amount, .(s(C), Coins)) -> U9_GGA(Amount, C, Coins, =_out_ga(Amount)) U4_GGA(s(x3), z1, z2, =_out_ga(s(x3))) -> U5_GGA(s(x3), z1, z2, U3_gag(plus_in_gag(z1, x3))) U9_GGA(s(x3), z1, z2, =_out_ga(s(x3))) -> U10_GGA(s(x3), z2, plus_in_gag(s(x3), s(z1))) The TRS R consists of the following rules: ways_in_gga(0, X1) -> ways_out_gga(s(0)) ways_in_gga(X2, []) -> ways_out_gga(0) ways_in_gga(Amount, .(s(C), Coins)) -> U4_gga(Amount, C, Coins, =_in_ga(Amount)) =_in_ga(X) -> =_out_ga(X) U4_gga(Amount, C, Coins, =_out_ga(s(X3))) -> U5_gga(Amount, C, Coins, plus_in_gag(s(C), Amount)) plus_in_gag(0, X) -> U2_gag(X, nat_in_g(X)) nat_in_g(0) -> nat_out_g nat_in_g(s(X)) -> U1_g(nat_in_g(X)) U1_g(nat_out_g) -> nat_out_g U2_gag(X, nat_out_g) -> plus_out_gag(X) plus_in_gag(s(X), s(Z)) -> U3_gag(plus_in_gag(X, Z)) U3_gag(plus_out_gag(Y)) -> plus_out_gag(Y) U5_gga(Amount, C, Coins, plus_out_gag(NewAmount)) -> U6_gga(C, Coins, NewAmount, ways_in_gga(Amount, Coins)) ways_in_gga(Amount, .(s(C), Coins)) -> U9_gga(Amount, C, Coins, =_in_ga(Amount)) U9_gga(Amount, C, Coins, =_out_ga(s(X4))) -> U10_gga(Amount, Coins, plus_in_gag(Amount, s(C))) U10_gga(Amount, Coins, plus_out_gag(s(X5))) -> U11_gga(ways_in_gga(Amount, Coins)) U11_gga(ways_out_gga(N)) -> ways_out_gga(N) U6_gga(C, Coins, NewAmount, ways_out_gga(N1)) -> U7_gga(N1, ways_in_gga(NewAmount, .(s(C), Coins))) U7_gga(N1, ways_out_gga(N2)) -> U8_gga(plus_in_gga(N1, N2)) plus_in_gga(0, X) -> U2_gga(X, nat_in_g(X)) U2_gga(X, nat_out_g) -> plus_out_gga(X) plus_in_gga(s(X), Y) -> U3_gga(plus_in_gga(X, Y)) U3_gga(plus_out_gga(Z)) -> plus_out_gga(s(Z)) U8_gga(plus_out_gga(N)) -> ways_out_gga(N) The set Q consists of the following terms: ways_in_gga(x0, x1) =_in_ga(x0) U4_gga(x0, x1, x2, x3) plus_in_gag(x0, x1) nat_in_g(x0) U1_g(x0) U2_gag(x0, x1) U3_gag(x0) U5_gga(x0, x1, x2, x3) U9_gga(x0, x1, x2, x3) U10_gga(x0, x1, x2) U11_gga(x0) U6_gga(x0, x1, x2, x3) U7_gga(x0, x1) plus_in_gga(x0, x1) U2_gga(x0, x1) U3_gga(x0) U8_gga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (43) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule U9_GGA(s(x3), z1, z2, =_out_ga(s(x3))) -> U10_GGA(s(x3), z2, plus_in_gag(s(x3), s(z1))) at position [2] we obtained the following new rules [LPAR04]: (U9_GGA(s(x3), z1, z2, =_out_ga(s(x3))) -> U10_GGA(s(x3), z2, U3_gag(plus_in_gag(x3, z1))),U9_GGA(s(x3), z1, z2, =_out_ga(s(x3))) -> U10_GGA(s(x3), z2, U3_gag(plus_in_gag(x3, z1)))) ---------------------------------------- (44) Obligation: Q DP problem: The TRS P consists of the following rules: U5_GGA(Amount, C, Coins, plus_out_gag(NewAmount)) -> U6_GGA(C, Coins, NewAmount, ways_in_gga(Amount, Coins)) U6_GGA(C, Coins, NewAmount, ways_out_gga(N1)) -> WAYS_IN_GGA(NewAmount, .(s(C), Coins)) U10_GGA(Amount, Coins, plus_out_gag(s(X5))) -> WAYS_IN_GGA(Amount, Coins) U5_GGA(Amount, C, Coins, plus_out_gag(NewAmount)) -> WAYS_IN_GGA(Amount, Coins) WAYS_IN_GGA(Amount, .(s(C), Coins)) -> U4_GGA(Amount, C, Coins, =_out_ga(Amount)) WAYS_IN_GGA(Amount, .(s(C), Coins)) -> U9_GGA(Amount, C, Coins, =_out_ga(Amount)) U4_GGA(s(x3), z1, z2, =_out_ga(s(x3))) -> U5_GGA(s(x3), z1, z2, U3_gag(plus_in_gag(z1, x3))) U9_GGA(s(x3), z1, z2, =_out_ga(s(x3))) -> U10_GGA(s(x3), z2, U3_gag(plus_in_gag(x3, z1))) The TRS R consists of the following rules: ways_in_gga(0, X1) -> ways_out_gga(s(0)) ways_in_gga(X2, []) -> ways_out_gga(0) ways_in_gga(Amount, .(s(C), Coins)) -> U4_gga(Amount, C, Coins, =_in_ga(Amount)) =_in_ga(X) -> =_out_ga(X) U4_gga(Amount, C, Coins, =_out_ga(s(X3))) -> U5_gga(Amount, C, Coins, plus_in_gag(s(C), Amount)) plus_in_gag(0, X) -> U2_gag(X, nat_in_g(X)) nat_in_g(0) -> nat_out_g nat_in_g(s(X)) -> U1_g(nat_in_g(X)) U1_g(nat_out_g) -> nat_out_g U2_gag(X, nat_out_g) -> plus_out_gag(X) plus_in_gag(s(X), s(Z)) -> U3_gag(plus_in_gag(X, Z)) U3_gag(plus_out_gag(Y)) -> plus_out_gag(Y) U5_gga(Amount, C, Coins, plus_out_gag(NewAmount)) -> U6_gga(C, Coins, NewAmount, ways_in_gga(Amount, Coins)) ways_in_gga(Amount, .(s(C), Coins)) -> U9_gga(Amount, C, Coins, =_in_ga(Amount)) U9_gga(Amount, C, Coins, =_out_ga(s(X4))) -> U10_gga(Amount, Coins, plus_in_gag(Amount, s(C))) U10_gga(Amount, Coins, plus_out_gag(s(X5))) -> U11_gga(ways_in_gga(Amount, Coins)) U11_gga(ways_out_gga(N)) -> ways_out_gga(N) U6_gga(C, Coins, NewAmount, ways_out_gga(N1)) -> U7_gga(N1, ways_in_gga(NewAmount, .(s(C), Coins))) U7_gga(N1, ways_out_gga(N2)) -> U8_gga(plus_in_gga(N1, N2)) plus_in_gga(0, X) -> U2_gga(X, nat_in_g(X)) U2_gga(X, nat_out_g) -> plus_out_gga(X) plus_in_gga(s(X), Y) -> U3_gga(plus_in_gga(X, Y)) U3_gga(plus_out_gga(Z)) -> plus_out_gga(s(Z)) U8_gga(plus_out_gga(N)) -> ways_out_gga(N) The set Q consists of the following terms: ways_in_gga(x0, x1) =_in_ga(x0) U4_gga(x0, x1, x2, x3) plus_in_gag(x0, x1) nat_in_g(x0) U1_g(x0) U2_gag(x0, x1) U3_gag(x0) U5_gga(x0, x1, x2, x3) U9_gga(x0, x1, x2, x3) U10_gga(x0, x1, x2) U11_gga(x0) U6_gga(x0, x1, x2, x3) U7_gga(x0, x1) plus_in_gga(x0, x1) U2_gga(x0, x1) U3_gga(x0) U8_gga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (45) QDPQMonotonicMRRProof (EQUIVALENT) By using the Q-monotonic rule removal processor with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented such that it always occurs at a strongly monotonic position in a (P,Q,R)-chain. Strictly oriented dependency pairs: U10_GGA(Amount, Coins, plus_out_gag(s(X5))) -> WAYS_IN_GGA(Amount, Coins) U5_GGA(Amount, C, Coins, plus_out_gag(NewAmount)) -> WAYS_IN_GGA(Amount, Coins) Used ordering: Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = 1 + x_2 POL(0) = 2 POL(=_in_ga(x_1)) = 1 POL(=_out_ga(x_1)) = 1 POL(U10_GGA(x_1, x_2, x_3)) = 1 + x_2 POL(U10_gga(x_1, x_2, x_3)) = 1 + 2*x_2 POL(U11_gga(x_1)) = 1 POL(U1_g(x_1)) = 0 POL(U2_gag(x_1, x_2)) = 0 POL(U2_gga(x_1, x_2)) = 2 POL(U3_gag(x_1)) = 0 POL(U3_gga(x_1)) = 0 POL(U4_GGA(x_1, x_2, x_3, x_4)) = 1 + x_3 POL(U4_gga(x_1, x_2, x_3, x_4)) = 2*x_3 POL(U5_GGA(x_1, x_2, x_3, x_4)) = 1 + x_3 POL(U5_gga(x_1, x_2, x_3, x_4)) = x_3 POL(U6_GGA(x_1, x_2, x_3, x_4)) = 1 + x_2 POL(U6_gga(x_1, x_2, x_3, x_4)) = 0 POL(U7_gga(x_1, x_2)) = 0 POL(U8_gga(x_1)) = 0 POL(U9_GGA(x_1, x_2, x_3, x_4)) = 1 + x_3 POL(U9_gga(x_1, x_2, x_3, x_4)) = 2*x_3 + 2*x_4 POL(WAYS_IN_GGA(x_1, x_2)) = x_2 POL([]) = 0 POL(nat_in_g(x_1)) = 0 POL(nat_out_g) = 0 POL(plus_in_gag(x_1, x_2)) = 0 POL(plus_in_gga(x_1, x_2)) = 1 + 2*x_1 POL(plus_out_gag(x_1)) = 0 POL(plus_out_gga(x_1)) = 0 POL(s(x_1)) = 0 POL(ways_in_gga(x_1, x_2)) = 2*x_2 POL(ways_out_gga(x_1)) = 0 ---------------------------------------- (46) Obligation: Q DP problem: The TRS P consists of the following rules: U5_GGA(Amount, C, Coins, plus_out_gag(NewAmount)) -> U6_GGA(C, Coins, NewAmount, ways_in_gga(Amount, Coins)) U6_GGA(C, Coins, NewAmount, ways_out_gga(N1)) -> WAYS_IN_GGA(NewAmount, .(s(C), Coins)) WAYS_IN_GGA(Amount, .(s(C), Coins)) -> U4_GGA(Amount, C, Coins, =_out_ga(Amount)) WAYS_IN_GGA(Amount, .(s(C), Coins)) -> U9_GGA(Amount, C, Coins, =_out_ga(Amount)) U4_GGA(s(x3), z1, z2, =_out_ga(s(x3))) -> U5_GGA(s(x3), z1, z2, U3_gag(plus_in_gag(z1, x3))) U9_GGA(s(x3), z1, z2, =_out_ga(s(x3))) -> U10_GGA(s(x3), z2, U3_gag(plus_in_gag(x3, z1))) The TRS R consists of the following rules: ways_in_gga(0, X1) -> ways_out_gga(s(0)) ways_in_gga(X2, []) -> ways_out_gga(0) ways_in_gga(Amount, .(s(C), Coins)) -> U4_gga(Amount, C, Coins, =_in_ga(Amount)) =_in_ga(X) -> =_out_ga(X) U4_gga(Amount, C, Coins, =_out_ga(s(X3))) -> U5_gga(Amount, C, Coins, plus_in_gag(s(C), Amount)) plus_in_gag(0, X) -> U2_gag(X, nat_in_g(X)) nat_in_g(0) -> nat_out_g nat_in_g(s(X)) -> U1_g(nat_in_g(X)) U1_g(nat_out_g) -> nat_out_g U2_gag(X, nat_out_g) -> plus_out_gag(X) plus_in_gag(s(X), s(Z)) -> U3_gag(plus_in_gag(X, Z)) U3_gag(plus_out_gag(Y)) -> plus_out_gag(Y) U5_gga(Amount, C, Coins, plus_out_gag(NewAmount)) -> U6_gga(C, Coins, NewAmount, ways_in_gga(Amount, Coins)) ways_in_gga(Amount, .(s(C), Coins)) -> U9_gga(Amount, C, Coins, =_in_ga(Amount)) U9_gga(Amount, C, Coins, =_out_ga(s(X4))) -> U10_gga(Amount, Coins, plus_in_gag(Amount, s(C))) U10_gga(Amount, Coins, plus_out_gag(s(X5))) -> U11_gga(ways_in_gga(Amount, Coins)) U11_gga(ways_out_gga(N)) -> ways_out_gga(N) U6_gga(C, Coins, NewAmount, ways_out_gga(N1)) -> U7_gga(N1, ways_in_gga(NewAmount, .(s(C), Coins))) U7_gga(N1, ways_out_gga(N2)) -> U8_gga(plus_in_gga(N1, N2)) plus_in_gga(0, X) -> U2_gga(X, nat_in_g(X)) U2_gga(X, nat_out_g) -> plus_out_gga(X) plus_in_gga(s(X), Y) -> U3_gga(plus_in_gga(X, Y)) U3_gga(plus_out_gga(Z)) -> plus_out_gga(s(Z)) U8_gga(plus_out_gga(N)) -> ways_out_gga(N) The set Q consists of the following terms: ways_in_gga(x0, x1) =_in_ga(x0) U4_gga(x0, x1, x2, x3) plus_in_gag(x0, x1) nat_in_g(x0) U1_g(x0) U2_gag(x0, x1) U3_gag(x0) U5_gga(x0, x1, x2, x3) U9_gga(x0, x1, x2, x3) U10_gga(x0, x1, x2) U11_gga(x0) U6_gga(x0, x1, x2, x3) U7_gga(x0, x1) plus_in_gga(x0, x1) U2_gga(x0, x1) U3_gga(x0) U8_gga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (47) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (48) Obligation: Q DP problem: The TRS P consists of the following rules: U6_GGA(C, Coins, NewAmount, ways_out_gga(N1)) -> WAYS_IN_GGA(NewAmount, .(s(C), Coins)) WAYS_IN_GGA(Amount, .(s(C), Coins)) -> U4_GGA(Amount, C, Coins, =_out_ga(Amount)) U4_GGA(s(x3), z1, z2, =_out_ga(s(x3))) -> U5_GGA(s(x3), z1, z2, U3_gag(plus_in_gag(z1, x3))) U5_GGA(Amount, C, Coins, plus_out_gag(NewAmount)) -> U6_GGA(C, Coins, NewAmount, ways_in_gga(Amount, Coins)) The TRS R consists of the following rules: ways_in_gga(0, X1) -> ways_out_gga(s(0)) ways_in_gga(X2, []) -> ways_out_gga(0) ways_in_gga(Amount, .(s(C), Coins)) -> U4_gga(Amount, C, Coins, =_in_ga(Amount)) =_in_ga(X) -> =_out_ga(X) U4_gga(Amount, C, Coins, =_out_ga(s(X3))) -> U5_gga(Amount, C, Coins, plus_in_gag(s(C), Amount)) plus_in_gag(0, X) -> U2_gag(X, nat_in_g(X)) nat_in_g(0) -> nat_out_g nat_in_g(s(X)) -> U1_g(nat_in_g(X)) U1_g(nat_out_g) -> nat_out_g U2_gag(X, nat_out_g) -> plus_out_gag(X) plus_in_gag(s(X), s(Z)) -> U3_gag(plus_in_gag(X, Z)) U3_gag(plus_out_gag(Y)) -> plus_out_gag(Y) U5_gga(Amount, C, Coins, plus_out_gag(NewAmount)) -> U6_gga(C, Coins, NewAmount, ways_in_gga(Amount, Coins)) ways_in_gga(Amount, .(s(C), Coins)) -> U9_gga(Amount, C, Coins, =_in_ga(Amount)) U9_gga(Amount, C, Coins, =_out_ga(s(X4))) -> U10_gga(Amount, Coins, plus_in_gag(Amount, s(C))) U10_gga(Amount, Coins, plus_out_gag(s(X5))) -> U11_gga(ways_in_gga(Amount, Coins)) U11_gga(ways_out_gga(N)) -> ways_out_gga(N) U6_gga(C, Coins, NewAmount, ways_out_gga(N1)) -> U7_gga(N1, ways_in_gga(NewAmount, .(s(C), Coins))) U7_gga(N1, ways_out_gga(N2)) -> U8_gga(plus_in_gga(N1, N2)) plus_in_gga(0, X) -> U2_gga(X, nat_in_g(X)) U2_gga(X, nat_out_g) -> plus_out_gga(X) plus_in_gga(s(X), Y) -> U3_gga(plus_in_gga(X, Y)) U3_gga(plus_out_gga(Z)) -> plus_out_gga(s(Z)) U8_gga(plus_out_gga(N)) -> ways_out_gga(N) The set Q consists of the following terms: ways_in_gga(x0, x1) =_in_ga(x0) U4_gga(x0, x1, x2, x3) plus_in_gag(x0, x1) nat_in_g(x0) U1_g(x0) U2_gag(x0, x1) U3_gag(x0) U5_gga(x0, x1, x2, x3) U9_gga(x0, x1, x2, x3) U10_gga(x0, x1, x2) U11_gga(x0) U6_gga(x0, x1, x2, x3) U7_gga(x0, x1) plus_in_gga(x0, x1) U2_gga(x0, x1) U3_gga(x0) U8_gga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (49) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. U6_GGA(C, Coins, NewAmount, ways_out_gga(N1)) -> WAYS_IN_GGA(NewAmount, .(s(C), Coins)) U4_GGA(s(x3), z1, z2, =_out_ga(s(x3))) -> U5_GGA(s(x3), z1, z2, U3_gag(plus_in_gag(z1, x3))) U5_GGA(Amount, C, Coins, plus_out_gag(NewAmount)) -> U6_GGA(C, Coins, NewAmount, ways_in_gga(Amount, Coins)) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. U6_GGA(x1, x2, x3, x4) = U6_GGA(x3, x4) ways_out_gga(x1) = ways_out_gga WAYS_IN_GGA(x1, x2) = WAYS_IN_GGA(x1) .(x1, x2) = .(x1) s(x1) = s(x1) U4_GGA(x1, x2, x3, x4) = x4 =_out_ga(x1) = =_out_ga(x1) U5_GGA(x1, x2, x3, x4) = U5_GGA(x4) U3_gag(x1) = x1 plus_in_gag(x1, x2) = x2 plus_out_gag(x1) = x1 ways_in_gga(x1, x2) = ways_in_gga 0 = 0 U2_gag(x1, x2) = x1 nat_in_g(x1) = nat_in_g [] = [] U4_gga(x1, x2, x3, x4) = U4_gga =_in_ga(x1) = =_in_ga U9_gga(x1, x2, x3, x4) = U9_gga U5_gga(x1, x2, x3, x4) = U5_gga U6_gga(x1, x2, x3, x4) = U6_gga U10_gga(x1, x2, x3) = U10_gga U11_gga(x1) = U11_gga U7_gga(x1, x2) = U7_gga U8_gga(x1) = U8_gga plus_in_gga(x1, x2) = plus_in_gga nat_out_g = nat_out_g U1_g(x1) = U1_g U2_gga(x1, x2) = U2_gga(x1) U3_gga(x1) = U3_gga(x1) plus_out_gga(x1) = plus_out_gga Recursive path order with status [RPO]. Quasi-Precedence: [s_1, U5_GGA_1, =_in_ga, plus_in_gga] > U6_GGA_2 > [WAYS_IN_GGA_1, =_out_ga_1] > [U4_gga, U5_gga] > U6_gga > U7_gga > [ways_out_gga, U8_gga] [s_1, U5_GGA_1, =_in_ga, plus_in_gga] > U6_GGA_2 > ._1 > [U4_gga, U5_gga] > U6_gga > U7_gga > [ways_out_gga, U8_gga] [s_1, U5_GGA_1, =_in_ga, plus_in_gga] > [ways_in_gga, U9_gga] > [U4_gga, U5_gga] > U6_gga > U7_gga > [ways_out_gga, U8_gga] [s_1, U5_GGA_1, =_in_ga, plus_in_gga] > [ways_in_gga, U9_gga] > [U10_gga, U11_gga] > [ways_out_gga, U8_gga] [s_1, U5_GGA_1, =_in_ga, plus_in_gga] > nat_in_g > U1_g [s_1, U5_GGA_1, =_in_ga, plus_in_gga] > [nat_out_g, U3_gga_1, plus_out_gga] > [ways_out_gga, U8_gga] [s_1, U5_GGA_1, =_in_ga, plus_in_gga] > U2_gga_1 0 > [ways_out_gga, U8_gga] 0 > nat_in_g > U1_g 0 > U2_gga_1 Status: U6_GGA_2: multiset status ways_out_gga: multiset status WAYS_IN_GGA_1: multiset status ._1: multiset status s_1: [1] =_out_ga_1: multiset status U5_GGA_1: [1] ways_in_gga: multiset status 0: multiset status nat_in_g: [] []: multiset status U4_gga: [] =_in_ga: multiset status U9_gga: multiset status U5_gga: [] U6_gga: multiset status U10_gga: [] U11_gga: [] U7_gga: [] U8_gga: multiset status plus_in_gga: multiset status nat_out_g: multiset status U1_g: [] U2_gga_1: multiset status U3_gga_1: multiset status plus_out_gga: [] The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: plus_in_gag(0, X) -> U2_gag(X, nat_in_g(X)) plus_in_gag(s(X), s(Z)) -> U3_gag(plus_in_gag(X, Z)) U3_gag(plus_out_gag(Y)) -> plus_out_gag(Y) ways_in_gga(0, X1) -> ways_out_gga(s(0)) ways_in_gga(X2, []) -> ways_out_gga(0) ways_in_gga(Amount, .(s(C), Coins)) -> U4_gga(Amount, C, Coins, =_in_ga(Amount)) ways_in_gga(Amount, .(s(C), Coins)) -> U9_gga(Amount, C, Coins, =_in_ga(Amount)) U4_gga(Amount, C, Coins, =_out_ga(s(X3))) -> U5_gga(Amount, C, Coins, plus_in_gag(s(C), Amount)) U5_gga(Amount, C, Coins, plus_out_gag(NewAmount)) -> U6_gga(C, Coins, NewAmount, ways_in_gga(Amount, Coins)) U9_gga(Amount, C, Coins, =_out_ga(s(X4))) -> U10_gga(Amount, Coins, plus_in_gag(Amount, s(C))) U10_gga(Amount, Coins, plus_out_gag(s(X5))) -> U11_gga(ways_in_gga(Amount, Coins)) U11_gga(ways_out_gga(N)) -> ways_out_gga(N) U6_gga(C, Coins, NewAmount, ways_out_gga(N1)) -> U7_gga(N1, ways_in_gga(NewAmount, .(s(C), Coins))) U7_gga(N1, ways_out_gga(N2)) -> U8_gga(plus_in_gga(N1, N2)) U2_gag(X, nat_out_g) -> plus_out_gag(X) U8_gga(plus_out_gga(N)) -> ways_out_gga(N) ---------------------------------------- (50) Obligation: Q DP problem: The TRS P consists of the following rules: WAYS_IN_GGA(Amount, .(s(C), Coins)) -> U4_GGA(Amount, C, Coins, =_out_ga(Amount)) The TRS R consists of the following rules: ways_in_gga(0, X1) -> ways_out_gga(s(0)) ways_in_gga(X2, []) -> ways_out_gga(0) ways_in_gga(Amount, .(s(C), Coins)) -> U4_gga(Amount, C, Coins, =_in_ga(Amount)) =_in_ga(X) -> =_out_ga(X) U4_gga(Amount, C, Coins, =_out_ga(s(X3))) -> U5_gga(Amount, C, Coins, plus_in_gag(s(C), Amount)) plus_in_gag(0, X) -> U2_gag(X, nat_in_g(X)) nat_in_g(0) -> nat_out_g nat_in_g(s(X)) -> U1_g(nat_in_g(X)) U1_g(nat_out_g) -> nat_out_g U2_gag(X, nat_out_g) -> plus_out_gag(X) plus_in_gag(s(X), s(Z)) -> U3_gag(plus_in_gag(X, Z)) U3_gag(plus_out_gag(Y)) -> plus_out_gag(Y) U5_gga(Amount, C, Coins, plus_out_gag(NewAmount)) -> U6_gga(C, Coins, NewAmount, ways_in_gga(Amount, Coins)) ways_in_gga(Amount, .(s(C), Coins)) -> U9_gga(Amount, C, Coins, =_in_ga(Amount)) U9_gga(Amount, C, Coins, =_out_ga(s(X4))) -> U10_gga(Amount, Coins, plus_in_gag(Amount, s(C))) U10_gga(Amount, Coins, plus_out_gag(s(X5))) -> U11_gga(ways_in_gga(Amount, Coins)) U11_gga(ways_out_gga(N)) -> ways_out_gga(N) U6_gga(C, Coins, NewAmount, ways_out_gga(N1)) -> U7_gga(N1, ways_in_gga(NewAmount, .(s(C), Coins))) U7_gga(N1, ways_out_gga(N2)) -> U8_gga(plus_in_gga(N1, N2)) plus_in_gga(0, X) -> U2_gga(X, nat_in_g(X)) U2_gga(X, nat_out_g) -> plus_out_gga(X) plus_in_gga(s(X), Y) -> U3_gga(plus_in_gga(X, Y)) U3_gga(plus_out_gga(Z)) -> plus_out_gga(s(Z)) U8_gga(plus_out_gga(N)) -> ways_out_gga(N) The set Q consists of the following terms: ways_in_gga(x0, x1) =_in_ga(x0) U4_gga(x0, x1, x2, x3) plus_in_gag(x0, x1) nat_in_g(x0) U1_g(x0) U2_gag(x0, x1) U3_gag(x0) U5_gga(x0, x1, x2, x3) U9_gga(x0, x1, x2, x3) U10_gga(x0, x1, x2) U11_gga(x0) U6_gga(x0, x1, x2, x3) U7_gga(x0, x1) plus_in_gga(x0, x1) U2_gga(x0, x1) U3_gga(x0) U8_gga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (51) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (52) TRUE