/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern get(a,a,a) w.r.t. the given Prolog program could not be shown: (0) Prolog (1) IntegerArithmeticTransformerProof [SOUND, 0 ms] (2) Prolog (3) CutEliminatorProof [SOUND, 0 ms] (4) Prolog (5) UnifyTransformerProof [EQUIVALENT, 0 ms] (6) Prolog (7) PrologToPiTRSProof [SOUND, 26 ms] (8) PiTRS (9) DependencyPairsProof [EQUIVALENT, 49 ms] (10) PiDP (11) DependencyGraphProof [EQUIVALENT, 0 ms] (12) AND (13) PiDP (14) UsableRulesProof [EQUIVALENT, 0 ms] (15) PiDP (16) PiDPToQDPProof [SOUND, 0 ms] (17) QDP (18) QDPSizeChangeProof [EQUIVALENT, 0 ms] (19) YES (20) PiDP (21) UsableRulesProof [EQUIVALENT, 0 ms] (22) PiDP (23) PiDPToQDPProof [SOUND, 0 ms] (24) QDP (25) QDPSizeChangeProof [EQUIVALENT, 0 ms] (26) YES (27) PiDP (28) UsableRulesProof [EQUIVALENT, 0 ms] (29) PiDP (30) PiDPToQDPProof [SOUND, 0 ms] (31) QDP (32) QDPSizeChangeProof [EQUIVALENT, 0 ms] (33) YES (34) PiDP (35) UsableRulesProof [EQUIVALENT, 0 ms] (36) PiDP (37) PiDPToQDPProof [SOUND, 0 ms] (38) QDP (39) PrologToPiTRSProof [SOUND, 14 ms] (40) PiTRS (41) DependencyPairsProof [EQUIVALENT, 51 ms] (42) PiDP (43) DependencyGraphProof [EQUIVALENT, 0 ms] (44) AND (45) PiDP (46) UsableRulesProof [EQUIVALENT, 0 ms] (47) PiDP (48) PiDPToQDPProof [SOUND, 0 ms] (49) QDP (50) QDPSizeChangeProof [EQUIVALENT, 0 ms] (51) YES (52) PiDP (53) UsableRulesProof [EQUIVALENT, 0 ms] (54) PiDP (55) PiDPToQDPProof [SOUND, 0 ms] (56) QDP (57) QDPSizeChangeProof [EQUIVALENT, 0 ms] (58) YES (59) PiDP (60) UsableRulesProof [EQUIVALENT, 0 ms] (61) PiDP (62) PiDPToQDPProof [SOUND, 0 ms] (63) QDP (64) QDPSizeChangeProof [EQUIVALENT, 0 ms] (65) YES (66) PiDP (67) UsableRulesProof [EQUIVALENT, 0 ms] (68) PiDP (69) PiDPToQDPProof [SOUND, 0 ms] (70) QDP (71) TransformationProof [EQUIVALENT, 3 ms] (72) QDP (73) UsableRulesProof [EQUIVALENT, 0 ms] (74) QDP (75) QReductionProof [EQUIVALENT, 0 ms] (76) QDP (77) QDPQMonotonicMRRProof [EQUIVALENT, 42 ms] (78) QDP (79) UsableRulesProof [EQUIVALENT, 0 ms] (80) QDP (81) QReductionProof [EQUIVALENT, 1 ms] (82) QDP (83) QDPQMonotonicMRRProof [EQUIVALENT, 19 ms] (84) QDP (85) UsableRulesProof [EQUIVALENT, 0 ms] (86) QDP (87) QReductionProof [EQUIVALENT, 0 ms] (88) QDP (89) CutEliminatorProof [SOUND, 0 ms] (90) Prolog (91) UnifyTransformerProof [EQUIVALENT, 0 ms] (92) Prolog (93) UndefinedPredicateHandlerProof [SOUND, 0 ms] (94) Prolog (95) PrologToPiTRSProof [SOUND, 0 ms] (96) PiTRS (97) DependencyPairsProof [EQUIVALENT, 0 ms] (98) PiDP (99) DependencyGraphProof [EQUIVALENT, 0 ms] (100) PiDP (101) UsableRulesProof [EQUIVALENT, 0 ms] (102) PiDP (103) PiDPToQDPProof [SOUND, 0 ms] (104) QDP (105) TransformationProof [EQUIVALENT, 0 ms] (106) QDP (107) UsableRulesProof [EQUIVALENT, 0 ms] (108) QDP (109) QReductionProof [EQUIVALENT, 0 ms] (110) QDP (111) PrologToPiTRSProof [SOUND, 0 ms] (112) PiTRS (113) DependencyPairsProof [EQUIVALENT, 0 ms] (114) PiDP (115) DependencyGraphProof [EQUIVALENT, 0 ms] (116) PiDP (117) UsableRulesProof [EQUIVALENT, 0 ms] (118) PiDP (119) PiDPToQDPProof [SOUND, 0 ms] (120) QDP (121) TransformationProof [EQUIVALENT, 0 ms] (122) QDP (123) UsableRulesProof [EQUIVALENT, 0 ms] (124) QDP (125) QReductionProof [EQUIVALENT, 0 ms] (126) QDP (127) PrologToDTProblemTransformerProof [SOUND, 0 ms] (128) TRIPLES (129) TriplesToPiDPProof [SOUND, 2 ms] (130) PiDP (131) DependencyGraphProof [EQUIVALENT, 0 ms] (132) PiDP (133) PiDPToQDPProof [SOUND, 0 ms] (134) QDP (135) NonTerminationLoopProof [COMPLETE, 2 ms] (136) NO (137) PrologToIRSwTTransformerProof [SOUND, 72 ms] (138) IRSwT (139) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (140) IRSwT (141) IntTRSCompressionProof [EQUIVALENT, 54 ms] (142) IRSwT (143) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (144) IRSwT (145) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (146) IRSwT (147) IntTRSCompressionProof [EQUIVALENT, 0 ms] (148) IRSwT (149) IRSwTToIntTRSProof [SOUND, 0 ms] (150) IRSwT (151) IntTRSNonPeriodicNontermProof [COMPLETE, 6 ms] (152) NO ---------------------------------------- (0) Obligation: Clauses: get(.(X, XS), 0, Res) :- ','(!, =(Res, X)). get(.(X, XS), Y, Res) :- ','(!, ','(is(YP, -(Y, 1)), get(XS, YP, Res))). Query: get(a,a,a) ---------------------------------------- (1) IntegerArithmeticTransformerProof (SOUND) Added definitions of predefined predicates [PROLOG]. ---------------------------------------- (2) Obligation: Clauses: get(.(X, XS), zero, Res) :- ','(!, =(Res, X)). get(.(X, XS), Y, Res) :- ','(!, ','(isMinus(Y, succ(zero), U), ','(=(YP, U), get(XS, YP, Res)))). isPlus(zero, X, X). isPlus(succ(X), zero, succ(X)). isPlus(succ(X), succ(Y), succ(succ(Z))) :- isPlus(X, Y, Z). isPlus(succ(X), pred(Y), Z) :- isPlus(X, Y, Z). isPlus(pred(X), zero, pred(X)). isPlus(pred(X), succ(Y), Z) :- isPlus(X, Y, Z). isPlus(pred(X), pred(Y), pred(pred(Z))) :- isPlus(X, Y, Z). isMinus(X, zero, X). isMinus(zero, succ(Y), pred(Z)) :- isMinus(zero, Y, Z). isMinus(zero, pred(Y), succ(Z)) :- isMinus(zero, Y, Z). isMinus(succ(X), succ(Y), Z) :- isMinus(X, Y, Z). isMinus(succ(X), pred(Y), succ(succ(Z))) :- isMinus(X, Y, Z). isMinus(pred(X), succ(Y), pred(pred(Z))) :- isMinus(X, Y, Z). isMinus(pred(X), pred(Y), Z) :- isMinus(X, Y, Z). isTimes(X, zero, zero). isTimes(zero, succ(Y), zero). isTimes(zero, pred(Y), zero). isTimes(succ(X), succ(Y), Z) :- ','(isTimes(succ(X), Y, A), isPlus(A, succ(X), Z)). isTimes(succ(X), pred(Y), Z) :- ','(isTimes(succ(X), Y, A), isMinus(A, succ(X), Z)). isTimes(pred(X), succ(Y), Z) :- ','(isTimes(pred(X), Y, A), isPlus(A, pred(X), Z)). isTimes(pred(X), pred(Y), Z) :- ','(isTimes(pred(X), Y, A), isMinus(A, pred(X), Z)). isDiv(zero, succ(Y), zero). isDiv(zero, pred(Y), zero). isDiv(succ(X), succ(Y), zero) :- isMinus(succ(X), succ(Y), pred(Z)). isDiv(succ(X), succ(Y), succ(Z)) :- ','(isMinus(succ(X), succ(Y), A), isDiv(A, succ(Y), Z)). isDiv(succ(X), pred(Y), Z) :- ','(isMinus(zero, pred(Y), A), ','(isDiv(succ(X), A, B), isMinus(zero, B, Z))). isDiv(pred(X), pred(Y), zero) :- isMinus(pred(X), pred(Y), succ(Z)). isDiv(pred(X), pred(Y), succ(Z)) :- ','(isMinus(pred(X), pred(Y), A), isDiv(A, pred(Y), Z)). isDiv(pred(X), succ(Y), Z) :- ','(isMinus(zero, pred(X), A), ','(isDiv(A, succ(Y), B), isMinus(zero, B, Z))). isModulo(X, Y, Z) :- ','(isDiv(X, Y, A), ','(isTimes(A, Y, B), isMinus(X, B, Z))). Query: get(a,a,a) ---------------------------------------- (3) CutEliminatorProof (SOUND) Eliminated all cuts by simply ignoring them[PROLOG]. ---------------------------------------- (4) Obligation: Clauses: get(.(X, XS), zero, Res) :- =(Res, X). get(.(X, XS), Y, Res) :- ','(isMinus(Y, succ(zero), U), ','(=(YP, U), get(XS, YP, Res))). isPlus(zero, X, X). isPlus(succ(X), zero, succ(X)). isPlus(succ(X), succ(Y), succ(succ(Z))) :- isPlus(X, Y, Z). isPlus(succ(X), pred(Y), Z) :- isPlus(X, Y, Z). isPlus(pred(X), zero, pred(X)). isPlus(pred(X), succ(Y), Z) :- isPlus(X, Y, Z). isPlus(pred(X), pred(Y), pred(pred(Z))) :- isPlus(X, Y, Z). isMinus(X, zero, X). isMinus(zero, succ(Y), pred(Z)) :- isMinus(zero, Y, Z). isMinus(zero, pred(Y), succ(Z)) :- isMinus(zero, Y, Z). isMinus(succ(X), succ(Y), Z) :- isMinus(X, Y, Z). isMinus(succ(X), pred(Y), succ(succ(Z))) :- isMinus(X, Y, Z). isMinus(pred(X), succ(Y), pred(pred(Z))) :- isMinus(X, Y, Z). isMinus(pred(X), pred(Y), Z) :- isMinus(X, Y, Z). isTimes(X, zero, zero). isTimes(zero, succ(Y), zero). isTimes(zero, pred(Y), zero). isTimes(succ(X), succ(Y), Z) :- ','(isTimes(succ(X), Y, A), isPlus(A, succ(X), Z)). isTimes(succ(X), pred(Y), Z) :- ','(isTimes(succ(X), Y, A), isMinus(A, succ(X), Z)). isTimes(pred(X), succ(Y), Z) :- ','(isTimes(pred(X), Y, A), isPlus(A, pred(X), Z)). isTimes(pred(X), pred(Y), Z) :- ','(isTimes(pred(X), Y, A), isMinus(A, pred(X), Z)). isDiv(zero, succ(Y), zero). isDiv(zero, pred(Y), zero). isDiv(succ(X), succ(Y), zero) :- isMinus(succ(X), succ(Y), pred(Z)). isDiv(succ(X), succ(Y), succ(Z)) :- ','(isMinus(succ(X), succ(Y), A), isDiv(A, succ(Y), Z)). isDiv(succ(X), pred(Y), Z) :- ','(isMinus(zero, pred(Y), A), ','(isDiv(succ(X), A, B), isMinus(zero, B, Z))). isDiv(pred(X), pred(Y), zero) :- isMinus(pred(X), pred(Y), succ(Z)). isDiv(pred(X), pred(Y), succ(Z)) :- ','(isMinus(pred(X), pred(Y), A), isDiv(A, pred(Y), Z)). isDiv(pred(X), succ(Y), Z) :- ','(isMinus(zero, pred(X), A), ','(isDiv(A, succ(Y), B), isMinus(zero, B, Z))). isModulo(X, Y, Z) :- ','(isDiv(X, Y, A), ','(isTimes(A, Y, B), isMinus(X, B, Z))). Query: get(a,a,a) ---------------------------------------- (5) UnifyTransformerProof (EQUIVALENT) Added a fact for the built-in = predicate [PROLOG]. ---------------------------------------- (6) Obligation: Clauses: get(.(X, XS), zero, Res) :- =(Res, X). get(.(X, XS), Y, Res) :- ','(isMinus(Y, succ(zero), U), ','(=(YP, U), get(XS, YP, Res))). isPlus(zero, X, X). isPlus(succ(X), zero, succ(X)). isPlus(succ(X), succ(Y), succ(succ(Z))) :- isPlus(X, Y, Z). isPlus(succ(X), pred(Y), Z) :- isPlus(X, Y, Z). isPlus(pred(X), zero, pred(X)). isPlus(pred(X), succ(Y), Z) :- isPlus(X, Y, Z). isPlus(pred(X), pred(Y), pred(pred(Z))) :- isPlus(X, Y, Z). isMinus(X, zero, X). isMinus(zero, succ(Y), pred(Z)) :- isMinus(zero, Y, Z). isMinus(zero, pred(Y), succ(Z)) :- isMinus(zero, Y, Z). isMinus(succ(X), succ(Y), Z) :- isMinus(X, Y, Z). isMinus(succ(X), pred(Y), succ(succ(Z))) :- isMinus(X, Y, Z). isMinus(pred(X), succ(Y), pred(pred(Z))) :- isMinus(X, Y, Z). isMinus(pred(X), pred(Y), Z) :- isMinus(X, Y, Z). isTimes(X, zero, zero). isTimes(zero, succ(Y), zero). isTimes(zero, pred(Y), zero). isTimes(succ(X), succ(Y), Z) :- ','(isTimes(succ(X), Y, A), isPlus(A, succ(X), Z)). isTimes(succ(X), pred(Y), Z) :- ','(isTimes(succ(X), Y, A), isMinus(A, succ(X), Z)). isTimes(pred(X), succ(Y), Z) :- ','(isTimes(pred(X), Y, A), isPlus(A, pred(X), Z)). isTimes(pred(X), pred(Y), Z) :- ','(isTimes(pred(X), Y, A), isMinus(A, pred(X), Z)). isDiv(zero, succ(Y), zero). isDiv(zero, pred(Y), zero). isDiv(succ(X), succ(Y), zero) :- isMinus(succ(X), succ(Y), pred(Z)). isDiv(succ(X), succ(Y), succ(Z)) :- ','(isMinus(succ(X), succ(Y), A), isDiv(A, succ(Y), Z)). isDiv(succ(X), pred(Y), Z) :- ','(isMinus(zero, pred(Y), A), ','(isDiv(succ(X), A, B), isMinus(zero, B, Z))). isDiv(pred(X), pred(Y), zero) :- isMinus(pred(X), pred(Y), succ(Z)). isDiv(pred(X), pred(Y), succ(Z)) :- ','(isMinus(pred(X), pred(Y), A), isDiv(A, pred(Y), Z)). isDiv(pred(X), succ(Y), Z) :- ','(isMinus(zero, pred(X), A), ','(isDiv(A, succ(Y), B), isMinus(zero, B, Z))). isModulo(X, Y, Z) :- ','(isDiv(X, Y, A), ','(isTimes(A, Y, B), isMinus(X, B, Z))). =(X, X). Query: get(a,a,a) ---------------------------------------- (7) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: get_in_3: (f,f,f) isMinus_in_3: (f,b,f) (b,b,f) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: get_in_aaa(.(X, XS), zero, Res) -> U1_aaa(X, XS, Res, =_in_aa(Res, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_aaa(X, XS, Res, =_out_aa(Res, X)) -> get_out_aaa(.(X, XS), zero, Res) get_in_aaa(.(X, XS), Y, Res) -> U2_aaa(X, XS, Y, Res, isMinus_in_aga(Y, succ(zero), U)) isMinus_in_aga(X, zero, X) -> isMinus_out_aga(X, zero, X) isMinus_in_aga(zero, succ(Y), pred(Z)) -> U9_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(X, zero, X) -> isMinus_out_gga(X, zero, X) isMinus_in_gga(zero, succ(Y), pred(Z)) -> U9_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(zero, pred(Y), succ(Z)) -> U10_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(succ(X), succ(Y), Z) -> U11_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(succ(X), pred(Y), succ(succ(Z))) -> U12_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), succ(Y), pred(pred(Z))) -> U13_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), pred(Y), Z) -> U14_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) U14_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), pred(Y), Z) U13_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), succ(Y), pred(pred(Z))) U12_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), pred(Y), succ(succ(Z))) U11_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), succ(Y), Z) U10_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, pred(Y), succ(Z)) U9_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, succ(Y), pred(Z)) U9_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, succ(Y), pred(Z)) isMinus_in_aga(zero, pred(Y), succ(Z)) -> U10_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) U10_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, pred(Y), succ(Z)) isMinus_in_aga(succ(X), succ(Y), Z) -> U11_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(succ(X), pred(Y), succ(succ(Z))) -> U12_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), succ(Y), pred(pred(Z))) -> U13_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), pred(Y), Z) -> U14_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) U14_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), pred(Y), Z) U13_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), succ(Y), pred(pred(Z))) U12_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), pred(Y), succ(succ(Z))) U11_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), succ(Y), Z) U2_aaa(X, XS, Y, Res, isMinus_out_aga(Y, succ(zero), U)) -> U3_aaa(X, XS, Y, Res, =_in_aa(YP, U)) U3_aaa(X, XS, Y, Res, =_out_aa(YP, U)) -> U4_aaa(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U4_aaa(X, XS, Y, Res, get_out_aaa(XS, YP, Res)) -> get_out_aaa(.(X, XS), Y, Res) The argument filtering Pi contains the following mapping: get_in_aaa(x1, x2, x3) = get_in_aaa U1_aaa(x1, x2, x3, x4) = U1_aaa(x4) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa get_out_aaa(x1, x2, x3) = get_out_aaa U2_aaa(x1, x2, x3, x4, x5) = U2_aaa(x5) isMinus_in_aga(x1, x2, x3) = isMinus_in_aga(x2) zero = zero isMinus_out_aga(x1, x2, x3) = isMinus_out_aga succ(x1) = succ(x1) U9_aga(x1, x2, x3) = U9_aga(x3) isMinus_in_gga(x1, x2, x3) = isMinus_in_gga(x1, x2) isMinus_out_gga(x1, x2, x3) = isMinus_out_gga(x3) U9_gga(x1, x2, x3) = U9_gga(x3) pred(x1) = pred(x1) U10_gga(x1, x2, x3) = U10_gga(x3) U11_gga(x1, x2, x3, x4) = U11_gga(x4) U12_gga(x1, x2, x3, x4) = U12_gga(x4) U13_gga(x1, x2, x3, x4) = U13_gga(x4) U14_gga(x1, x2, x3, x4) = U14_gga(x4) U10_aga(x1, x2, x3) = U10_aga(x3) U11_aga(x1, x2, x3, x4) = U11_aga(x4) U12_aga(x1, x2, x3, x4) = U12_aga(x4) U13_aga(x1, x2, x3, x4) = U13_aga(x4) U14_aga(x1, x2, x3, x4) = U14_aga(x4) U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (8) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: get_in_aaa(.(X, XS), zero, Res) -> U1_aaa(X, XS, Res, =_in_aa(Res, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_aaa(X, XS, Res, =_out_aa(Res, X)) -> get_out_aaa(.(X, XS), zero, Res) get_in_aaa(.(X, XS), Y, Res) -> U2_aaa(X, XS, Y, Res, isMinus_in_aga(Y, succ(zero), U)) isMinus_in_aga(X, zero, X) -> isMinus_out_aga(X, zero, X) isMinus_in_aga(zero, succ(Y), pred(Z)) -> U9_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(X, zero, X) -> isMinus_out_gga(X, zero, X) isMinus_in_gga(zero, succ(Y), pred(Z)) -> U9_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(zero, pred(Y), succ(Z)) -> U10_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(succ(X), succ(Y), Z) -> U11_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(succ(X), pred(Y), succ(succ(Z))) -> U12_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), succ(Y), pred(pred(Z))) -> U13_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), pred(Y), Z) -> U14_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) U14_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), pred(Y), Z) U13_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), succ(Y), pred(pred(Z))) U12_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), pred(Y), succ(succ(Z))) U11_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), succ(Y), Z) U10_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, pred(Y), succ(Z)) U9_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, succ(Y), pred(Z)) U9_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, succ(Y), pred(Z)) isMinus_in_aga(zero, pred(Y), succ(Z)) -> U10_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) U10_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, pred(Y), succ(Z)) isMinus_in_aga(succ(X), succ(Y), Z) -> U11_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(succ(X), pred(Y), succ(succ(Z))) -> U12_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), succ(Y), pred(pred(Z))) -> U13_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), pred(Y), Z) -> U14_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) U14_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), pred(Y), Z) U13_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), succ(Y), pred(pred(Z))) U12_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), pred(Y), succ(succ(Z))) U11_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), succ(Y), Z) U2_aaa(X, XS, Y, Res, isMinus_out_aga(Y, succ(zero), U)) -> U3_aaa(X, XS, Y, Res, =_in_aa(YP, U)) U3_aaa(X, XS, Y, Res, =_out_aa(YP, U)) -> U4_aaa(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U4_aaa(X, XS, Y, Res, get_out_aaa(XS, YP, Res)) -> get_out_aaa(.(X, XS), Y, Res) The argument filtering Pi contains the following mapping: get_in_aaa(x1, x2, x3) = get_in_aaa U1_aaa(x1, x2, x3, x4) = U1_aaa(x4) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa get_out_aaa(x1, x2, x3) = get_out_aaa U2_aaa(x1, x2, x3, x4, x5) = U2_aaa(x5) isMinus_in_aga(x1, x2, x3) = isMinus_in_aga(x2) zero = zero isMinus_out_aga(x1, x2, x3) = isMinus_out_aga succ(x1) = succ(x1) U9_aga(x1, x2, x3) = U9_aga(x3) isMinus_in_gga(x1, x2, x3) = isMinus_in_gga(x1, x2) isMinus_out_gga(x1, x2, x3) = isMinus_out_gga(x3) U9_gga(x1, x2, x3) = U9_gga(x3) pred(x1) = pred(x1) U10_gga(x1, x2, x3) = U10_gga(x3) U11_gga(x1, x2, x3, x4) = U11_gga(x4) U12_gga(x1, x2, x3, x4) = U12_gga(x4) U13_gga(x1, x2, x3, x4) = U13_gga(x4) U14_gga(x1, x2, x3, x4) = U14_gga(x4) U10_aga(x1, x2, x3) = U10_aga(x3) U11_aga(x1, x2, x3, x4) = U11_aga(x4) U12_aga(x1, x2, x3, x4) = U12_aga(x4) U13_aga(x1, x2, x3, x4) = U13_aga(x4) U14_aga(x1, x2, x3, x4) = U14_aga(x4) U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) ---------------------------------------- (9) 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: GET_IN_AAA(.(X, XS), zero, Res) -> U1_AAA(X, XS, Res, =_in_aa(Res, X)) GET_IN_AAA(.(X, XS), zero, Res) -> =_IN_AA(Res, X) GET_IN_AAA(.(X, XS), Y, Res) -> U2_AAA(X, XS, Y, Res, isMinus_in_aga(Y, succ(zero), U)) GET_IN_AAA(.(X, XS), Y, Res) -> ISMINUS_IN_AGA(Y, succ(zero), U) ISMINUS_IN_AGA(zero, succ(Y), pred(Z)) -> U9_AGA(Y, Z, isMinus_in_gga(zero, Y, Z)) ISMINUS_IN_AGA(zero, succ(Y), pred(Z)) -> ISMINUS_IN_GGA(zero, Y, Z) ISMINUS_IN_GGA(zero, succ(Y), pred(Z)) -> U9_GGA(Y, Z, isMinus_in_gga(zero, Y, Z)) ISMINUS_IN_GGA(zero, succ(Y), pred(Z)) -> ISMINUS_IN_GGA(zero, Y, Z) ISMINUS_IN_GGA(zero, pred(Y), succ(Z)) -> U10_GGA(Y, Z, isMinus_in_gga(zero, Y, Z)) ISMINUS_IN_GGA(zero, pred(Y), succ(Z)) -> ISMINUS_IN_GGA(zero, Y, Z) ISMINUS_IN_GGA(succ(X), succ(Y), Z) -> U11_GGA(X, Y, Z, isMinus_in_gga(X, Y, Z)) ISMINUS_IN_GGA(succ(X), succ(Y), Z) -> ISMINUS_IN_GGA(X, Y, Z) ISMINUS_IN_GGA(succ(X), pred(Y), succ(succ(Z))) -> U12_GGA(X, Y, Z, isMinus_in_gga(X, Y, Z)) ISMINUS_IN_GGA(succ(X), pred(Y), succ(succ(Z))) -> ISMINUS_IN_GGA(X, Y, Z) ISMINUS_IN_GGA(pred(X), succ(Y), pred(pred(Z))) -> U13_GGA(X, Y, Z, isMinus_in_gga(X, Y, Z)) ISMINUS_IN_GGA(pred(X), succ(Y), pred(pred(Z))) -> ISMINUS_IN_GGA(X, Y, Z) ISMINUS_IN_GGA(pred(X), pred(Y), Z) -> U14_GGA(X, Y, Z, isMinus_in_gga(X, Y, Z)) ISMINUS_IN_GGA(pred(X), pred(Y), Z) -> ISMINUS_IN_GGA(X, Y, Z) ISMINUS_IN_AGA(zero, pred(Y), succ(Z)) -> U10_AGA(Y, Z, isMinus_in_gga(zero, Y, Z)) ISMINUS_IN_AGA(zero, pred(Y), succ(Z)) -> ISMINUS_IN_GGA(zero, Y, Z) ISMINUS_IN_AGA(succ(X), succ(Y), Z) -> U11_AGA(X, Y, Z, isMinus_in_aga(X, Y, Z)) ISMINUS_IN_AGA(succ(X), succ(Y), Z) -> ISMINUS_IN_AGA(X, Y, Z) ISMINUS_IN_AGA(succ(X), pred(Y), succ(succ(Z))) -> U12_AGA(X, Y, Z, isMinus_in_aga(X, Y, Z)) ISMINUS_IN_AGA(succ(X), pred(Y), succ(succ(Z))) -> ISMINUS_IN_AGA(X, Y, Z) ISMINUS_IN_AGA(pred(X), succ(Y), pred(pred(Z))) -> U13_AGA(X, Y, Z, isMinus_in_aga(X, Y, Z)) ISMINUS_IN_AGA(pred(X), succ(Y), pred(pred(Z))) -> ISMINUS_IN_AGA(X, Y, Z) ISMINUS_IN_AGA(pred(X), pred(Y), Z) -> U14_AGA(X, Y, Z, isMinus_in_aga(X, Y, Z)) ISMINUS_IN_AGA(pred(X), pred(Y), Z) -> ISMINUS_IN_AGA(X, Y, Z) U2_AAA(X, XS, Y, Res, isMinus_out_aga(Y, succ(zero), U)) -> U3_AAA(X, XS, Y, Res, =_in_aa(YP, U)) U2_AAA(X, XS, Y, Res, isMinus_out_aga(Y, succ(zero), U)) -> =_IN_AA(YP, U) U3_AAA(X, XS, Y, Res, =_out_aa(YP, U)) -> U4_AAA(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U3_AAA(X, XS, Y, Res, =_out_aa(YP, U)) -> GET_IN_AAA(XS, YP, Res) The TRS R consists of the following rules: get_in_aaa(.(X, XS), zero, Res) -> U1_aaa(X, XS, Res, =_in_aa(Res, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_aaa(X, XS, Res, =_out_aa(Res, X)) -> get_out_aaa(.(X, XS), zero, Res) get_in_aaa(.(X, XS), Y, Res) -> U2_aaa(X, XS, Y, Res, isMinus_in_aga(Y, succ(zero), U)) isMinus_in_aga(X, zero, X) -> isMinus_out_aga(X, zero, X) isMinus_in_aga(zero, succ(Y), pred(Z)) -> U9_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(X, zero, X) -> isMinus_out_gga(X, zero, X) isMinus_in_gga(zero, succ(Y), pred(Z)) -> U9_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(zero, pred(Y), succ(Z)) -> U10_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(succ(X), succ(Y), Z) -> U11_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(succ(X), pred(Y), succ(succ(Z))) -> U12_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), succ(Y), pred(pred(Z))) -> U13_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), pred(Y), Z) -> U14_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) U14_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), pred(Y), Z) U13_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), succ(Y), pred(pred(Z))) U12_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), pred(Y), succ(succ(Z))) U11_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), succ(Y), Z) U10_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, pred(Y), succ(Z)) U9_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, succ(Y), pred(Z)) U9_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, succ(Y), pred(Z)) isMinus_in_aga(zero, pred(Y), succ(Z)) -> U10_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) U10_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, pred(Y), succ(Z)) isMinus_in_aga(succ(X), succ(Y), Z) -> U11_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(succ(X), pred(Y), succ(succ(Z))) -> U12_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), succ(Y), pred(pred(Z))) -> U13_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), pred(Y), Z) -> U14_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) U14_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), pred(Y), Z) U13_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), succ(Y), pred(pred(Z))) U12_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), pred(Y), succ(succ(Z))) U11_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), succ(Y), Z) U2_aaa(X, XS, Y, Res, isMinus_out_aga(Y, succ(zero), U)) -> U3_aaa(X, XS, Y, Res, =_in_aa(YP, U)) U3_aaa(X, XS, Y, Res, =_out_aa(YP, U)) -> U4_aaa(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U4_aaa(X, XS, Y, Res, get_out_aaa(XS, YP, Res)) -> get_out_aaa(.(X, XS), Y, Res) The argument filtering Pi contains the following mapping: get_in_aaa(x1, x2, x3) = get_in_aaa U1_aaa(x1, x2, x3, x4) = U1_aaa(x4) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa get_out_aaa(x1, x2, x3) = get_out_aaa U2_aaa(x1, x2, x3, x4, x5) = U2_aaa(x5) isMinus_in_aga(x1, x2, x3) = isMinus_in_aga(x2) zero = zero isMinus_out_aga(x1, x2, x3) = isMinus_out_aga succ(x1) = succ(x1) U9_aga(x1, x2, x3) = U9_aga(x3) isMinus_in_gga(x1, x2, x3) = isMinus_in_gga(x1, x2) isMinus_out_gga(x1, x2, x3) = isMinus_out_gga(x3) U9_gga(x1, x2, x3) = U9_gga(x3) pred(x1) = pred(x1) U10_gga(x1, x2, x3) = U10_gga(x3) U11_gga(x1, x2, x3, x4) = U11_gga(x4) U12_gga(x1, x2, x3, x4) = U12_gga(x4) U13_gga(x1, x2, x3, x4) = U13_gga(x4) U14_gga(x1, x2, x3, x4) = U14_gga(x4) U10_aga(x1, x2, x3) = U10_aga(x3) U11_aga(x1, x2, x3, x4) = U11_aga(x4) U12_aga(x1, x2, x3, x4) = U12_aga(x4) U13_aga(x1, x2, x3, x4) = U13_aga(x4) U14_aga(x1, x2, x3, x4) = U14_aga(x4) U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) GET_IN_AAA(x1, x2, x3) = GET_IN_AAA U1_AAA(x1, x2, x3, x4) = U1_AAA(x4) =_IN_AA(x1, x2) = =_IN_AA U2_AAA(x1, x2, x3, x4, x5) = U2_AAA(x5) ISMINUS_IN_AGA(x1, x2, x3) = ISMINUS_IN_AGA(x2) U9_AGA(x1, x2, x3) = U9_AGA(x3) ISMINUS_IN_GGA(x1, x2, x3) = ISMINUS_IN_GGA(x1, x2) U9_GGA(x1, x2, x3) = U9_GGA(x3) U10_GGA(x1, x2, x3) = U10_GGA(x3) U11_GGA(x1, x2, x3, x4) = U11_GGA(x4) U12_GGA(x1, x2, x3, x4) = U12_GGA(x4) U13_GGA(x1, x2, x3, x4) = U13_GGA(x4) U14_GGA(x1, x2, x3, x4) = U14_GGA(x4) U10_AGA(x1, x2, x3) = U10_AGA(x3) U11_AGA(x1, x2, x3, x4) = U11_AGA(x4) U12_AGA(x1, x2, x3, x4) = U12_AGA(x4) U13_AGA(x1, x2, x3, x4) = U13_AGA(x4) U14_AGA(x1, x2, x3, x4) = U14_AGA(x4) U3_AAA(x1, x2, x3, x4, x5) = U3_AAA(x5) U4_AAA(x1, x2, x3, x4, x5) = U4_AAA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) Obligation: Pi DP problem: The TRS P consists of the following rules: GET_IN_AAA(.(X, XS), zero, Res) -> U1_AAA(X, XS, Res, =_in_aa(Res, X)) GET_IN_AAA(.(X, XS), zero, Res) -> =_IN_AA(Res, X) GET_IN_AAA(.(X, XS), Y, Res) -> U2_AAA(X, XS, Y, Res, isMinus_in_aga(Y, succ(zero), U)) GET_IN_AAA(.(X, XS), Y, Res) -> ISMINUS_IN_AGA(Y, succ(zero), U) ISMINUS_IN_AGA(zero, succ(Y), pred(Z)) -> U9_AGA(Y, Z, isMinus_in_gga(zero, Y, Z)) ISMINUS_IN_AGA(zero, succ(Y), pred(Z)) -> ISMINUS_IN_GGA(zero, Y, Z) ISMINUS_IN_GGA(zero, succ(Y), pred(Z)) -> U9_GGA(Y, Z, isMinus_in_gga(zero, Y, Z)) ISMINUS_IN_GGA(zero, succ(Y), pred(Z)) -> ISMINUS_IN_GGA(zero, Y, Z) ISMINUS_IN_GGA(zero, pred(Y), succ(Z)) -> U10_GGA(Y, Z, isMinus_in_gga(zero, Y, Z)) ISMINUS_IN_GGA(zero, pred(Y), succ(Z)) -> ISMINUS_IN_GGA(zero, Y, Z) ISMINUS_IN_GGA(succ(X), succ(Y), Z) -> U11_GGA(X, Y, Z, isMinus_in_gga(X, Y, Z)) ISMINUS_IN_GGA(succ(X), succ(Y), Z) -> ISMINUS_IN_GGA(X, Y, Z) ISMINUS_IN_GGA(succ(X), pred(Y), succ(succ(Z))) -> U12_GGA(X, Y, Z, isMinus_in_gga(X, Y, Z)) ISMINUS_IN_GGA(succ(X), pred(Y), succ(succ(Z))) -> ISMINUS_IN_GGA(X, Y, Z) ISMINUS_IN_GGA(pred(X), succ(Y), pred(pred(Z))) -> U13_GGA(X, Y, Z, isMinus_in_gga(X, Y, Z)) ISMINUS_IN_GGA(pred(X), succ(Y), pred(pred(Z))) -> ISMINUS_IN_GGA(X, Y, Z) ISMINUS_IN_GGA(pred(X), pred(Y), Z) -> U14_GGA(X, Y, Z, isMinus_in_gga(X, Y, Z)) ISMINUS_IN_GGA(pred(X), pred(Y), Z) -> ISMINUS_IN_GGA(X, Y, Z) ISMINUS_IN_AGA(zero, pred(Y), succ(Z)) -> U10_AGA(Y, Z, isMinus_in_gga(zero, Y, Z)) ISMINUS_IN_AGA(zero, pred(Y), succ(Z)) -> ISMINUS_IN_GGA(zero, Y, Z) ISMINUS_IN_AGA(succ(X), succ(Y), Z) -> U11_AGA(X, Y, Z, isMinus_in_aga(X, Y, Z)) ISMINUS_IN_AGA(succ(X), succ(Y), Z) -> ISMINUS_IN_AGA(X, Y, Z) ISMINUS_IN_AGA(succ(X), pred(Y), succ(succ(Z))) -> U12_AGA(X, Y, Z, isMinus_in_aga(X, Y, Z)) ISMINUS_IN_AGA(succ(X), pred(Y), succ(succ(Z))) -> ISMINUS_IN_AGA(X, Y, Z) ISMINUS_IN_AGA(pred(X), succ(Y), pred(pred(Z))) -> U13_AGA(X, Y, Z, isMinus_in_aga(X, Y, Z)) ISMINUS_IN_AGA(pred(X), succ(Y), pred(pred(Z))) -> ISMINUS_IN_AGA(X, Y, Z) ISMINUS_IN_AGA(pred(X), pred(Y), Z) -> U14_AGA(X, Y, Z, isMinus_in_aga(X, Y, Z)) ISMINUS_IN_AGA(pred(X), pred(Y), Z) -> ISMINUS_IN_AGA(X, Y, Z) U2_AAA(X, XS, Y, Res, isMinus_out_aga(Y, succ(zero), U)) -> U3_AAA(X, XS, Y, Res, =_in_aa(YP, U)) U2_AAA(X, XS, Y, Res, isMinus_out_aga(Y, succ(zero), U)) -> =_IN_AA(YP, U) U3_AAA(X, XS, Y, Res, =_out_aa(YP, U)) -> U4_AAA(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U3_AAA(X, XS, Y, Res, =_out_aa(YP, U)) -> GET_IN_AAA(XS, YP, Res) The TRS R consists of the following rules: get_in_aaa(.(X, XS), zero, Res) -> U1_aaa(X, XS, Res, =_in_aa(Res, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_aaa(X, XS, Res, =_out_aa(Res, X)) -> get_out_aaa(.(X, XS), zero, Res) get_in_aaa(.(X, XS), Y, Res) -> U2_aaa(X, XS, Y, Res, isMinus_in_aga(Y, succ(zero), U)) isMinus_in_aga(X, zero, X) -> isMinus_out_aga(X, zero, X) isMinus_in_aga(zero, succ(Y), pred(Z)) -> U9_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(X, zero, X) -> isMinus_out_gga(X, zero, X) isMinus_in_gga(zero, succ(Y), pred(Z)) -> U9_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(zero, pred(Y), succ(Z)) -> U10_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(succ(X), succ(Y), Z) -> U11_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(succ(X), pred(Y), succ(succ(Z))) -> U12_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), succ(Y), pred(pred(Z))) -> U13_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), pred(Y), Z) -> U14_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) U14_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), pred(Y), Z) U13_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), succ(Y), pred(pred(Z))) U12_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), pred(Y), succ(succ(Z))) U11_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), succ(Y), Z) U10_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, pred(Y), succ(Z)) U9_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, succ(Y), pred(Z)) U9_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, succ(Y), pred(Z)) isMinus_in_aga(zero, pred(Y), succ(Z)) -> U10_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) U10_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, pred(Y), succ(Z)) isMinus_in_aga(succ(X), succ(Y), Z) -> U11_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(succ(X), pred(Y), succ(succ(Z))) -> U12_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), succ(Y), pred(pred(Z))) -> U13_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), pred(Y), Z) -> U14_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) U14_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), pred(Y), Z) U13_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), succ(Y), pred(pred(Z))) U12_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), pred(Y), succ(succ(Z))) U11_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), succ(Y), Z) U2_aaa(X, XS, Y, Res, isMinus_out_aga(Y, succ(zero), U)) -> U3_aaa(X, XS, Y, Res, =_in_aa(YP, U)) U3_aaa(X, XS, Y, Res, =_out_aa(YP, U)) -> U4_aaa(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U4_aaa(X, XS, Y, Res, get_out_aaa(XS, YP, Res)) -> get_out_aaa(.(X, XS), Y, Res) The argument filtering Pi contains the following mapping: get_in_aaa(x1, x2, x3) = get_in_aaa U1_aaa(x1, x2, x3, x4) = U1_aaa(x4) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa get_out_aaa(x1, x2, x3) = get_out_aaa U2_aaa(x1, x2, x3, x4, x5) = U2_aaa(x5) isMinus_in_aga(x1, x2, x3) = isMinus_in_aga(x2) zero = zero isMinus_out_aga(x1, x2, x3) = isMinus_out_aga succ(x1) = succ(x1) U9_aga(x1, x2, x3) = U9_aga(x3) isMinus_in_gga(x1, x2, x3) = isMinus_in_gga(x1, x2) isMinus_out_gga(x1, x2, x3) = isMinus_out_gga(x3) U9_gga(x1, x2, x3) = U9_gga(x3) pred(x1) = pred(x1) U10_gga(x1, x2, x3) = U10_gga(x3) U11_gga(x1, x2, x3, x4) = U11_gga(x4) U12_gga(x1, x2, x3, x4) = U12_gga(x4) U13_gga(x1, x2, x3, x4) = U13_gga(x4) U14_gga(x1, x2, x3, x4) = U14_gga(x4) U10_aga(x1, x2, x3) = U10_aga(x3) U11_aga(x1, x2, x3, x4) = U11_aga(x4) U12_aga(x1, x2, x3, x4) = U12_aga(x4) U13_aga(x1, x2, x3, x4) = U13_aga(x4) U14_aga(x1, x2, x3, x4) = U14_aga(x4) U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) GET_IN_AAA(x1, x2, x3) = GET_IN_AAA U1_AAA(x1, x2, x3, x4) = U1_AAA(x4) =_IN_AA(x1, x2) = =_IN_AA U2_AAA(x1, x2, x3, x4, x5) = U2_AAA(x5) ISMINUS_IN_AGA(x1, x2, x3) = ISMINUS_IN_AGA(x2) U9_AGA(x1, x2, x3) = U9_AGA(x3) ISMINUS_IN_GGA(x1, x2, x3) = ISMINUS_IN_GGA(x1, x2) U9_GGA(x1, x2, x3) = U9_GGA(x3) U10_GGA(x1, x2, x3) = U10_GGA(x3) U11_GGA(x1, x2, x3, x4) = U11_GGA(x4) U12_GGA(x1, x2, x3, x4) = U12_GGA(x4) U13_GGA(x1, x2, x3, x4) = U13_GGA(x4) U14_GGA(x1, x2, x3, x4) = U14_GGA(x4) U10_AGA(x1, x2, x3) = U10_AGA(x3) U11_AGA(x1, x2, x3, x4) = U11_AGA(x4) U12_AGA(x1, x2, x3, x4) = U12_AGA(x4) U13_AGA(x1, x2, x3, x4) = U13_AGA(x4) U14_AGA(x1, x2, x3, x4) = U14_AGA(x4) U3_AAA(x1, x2, x3, x4, x5) = U3_AAA(x5) U4_AAA(x1, x2, x3, x4, x5) = U4_AAA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (11) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 4 SCCs with 19 less nodes. ---------------------------------------- (12) Complex Obligation (AND) ---------------------------------------- (13) Obligation: Pi DP problem: The TRS P consists of the following rules: ISMINUS_IN_GGA(zero, pred(Y), succ(Z)) -> ISMINUS_IN_GGA(zero, Y, Z) ISMINUS_IN_GGA(zero, succ(Y), pred(Z)) -> ISMINUS_IN_GGA(zero, Y, Z) The TRS R consists of the following rules: get_in_aaa(.(X, XS), zero, Res) -> U1_aaa(X, XS, Res, =_in_aa(Res, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_aaa(X, XS, Res, =_out_aa(Res, X)) -> get_out_aaa(.(X, XS), zero, Res) get_in_aaa(.(X, XS), Y, Res) -> U2_aaa(X, XS, Y, Res, isMinus_in_aga(Y, succ(zero), U)) isMinus_in_aga(X, zero, X) -> isMinus_out_aga(X, zero, X) isMinus_in_aga(zero, succ(Y), pred(Z)) -> U9_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(X, zero, X) -> isMinus_out_gga(X, zero, X) isMinus_in_gga(zero, succ(Y), pred(Z)) -> U9_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(zero, pred(Y), succ(Z)) -> U10_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(succ(X), succ(Y), Z) -> U11_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(succ(X), pred(Y), succ(succ(Z))) -> U12_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), succ(Y), pred(pred(Z))) -> U13_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), pred(Y), Z) -> U14_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) U14_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), pred(Y), Z) U13_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), succ(Y), pred(pred(Z))) U12_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), pred(Y), succ(succ(Z))) U11_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), succ(Y), Z) U10_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, pred(Y), succ(Z)) U9_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, succ(Y), pred(Z)) U9_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, succ(Y), pred(Z)) isMinus_in_aga(zero, pred(Y), succ(Z)) -> U10_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) U10_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, pred(Y), succ(Z)) isMinus_in_aga(succ(X), succ(Y), Z) -> U11_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(succ(X), pred(Y), succ(succ(Z))) -> U12_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), succ(Y), pred(pred(Z))) -> U13_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), pred(Y), Z) -> U14_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) U14_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), pred(Y), Z) U13_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), succ(Y), pred(pred(Z))) U12_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), pred(Y), succ(succ(Z))) U11_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), succ(Y), Z) U2_aaa(X, XS, Y, Res, isMinus_out_aga(Y, succ(zero), U)) -> U3_aaa(X, XS, Y, Res, =_in_aa(YP, U)) U3_aaa(X, XS, Y, Res, =_out_aa(YP, U)) -> U4_aaa(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U4_aaa(X, XS, Y, Res, get_out_aaa(XS, YP, Res)) -> get_out_aaa(.(X, XS), Y, Res) The argument filtering Pi contains the following mapping: get_in_aaa(x1, x2, x3) = get_in_aaa U1_aaa(x1, x2, x3, x4) = U1_aaa(x4) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa get_out_aaa(x1, x2, x3) = get_out_aaa U2_aaa(x1, x2, x3, x4, x5) = U2_aaa(x5) isMinus_in_aga(x1, x2, x3) = isMinus_in_aga(x2) zero = zero isMinus_out_aga(x1, x2, x3) = isMinus_out_aga succ(x1) = succ(x1) U9_aga(x1, x2, x3) = U9_aga(x3) isMinus_in_gga(x1, x2, x3) = isMinus_in_gga(x1, x2) isMinus_out_gga(x1, x2, x3) = isMinus_out_gga(x3) U9_gga(x1, x2, x3) = U9_gga(x3) pred(x1) = pred(x1) U10_gga(x1, x2, x3) = U10_gga(x3) U11_gga(x1, x2, x3, x4) = U11_gga(x4) U12_gga(x1, x2, x3, x4) = U12_gga(x4) U13_gga(x1, x2, x3, x4) = U13_gga(x4) U14_gga(x1, x2, x3, x4) = U14_gga(x4) U10_aga(x1, x2, x3) = U10_aga(x3) U11_aga(x1, x2, x3, x4) = U11_aga(x4) U12_aga(x1, x2, x3, x4) = U12_aga(x4) U13_aga(x1, x2, x3, x4) = U13_aga(x4) U14_aga(x1, x2, x3, x4) = U14_aga(x4) U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) ISMINUS_IN_GGA(x1, x2, x3) = ISMINUS_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (14) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (15) Obligation: Pi DP problem: The TRS P consists of the following rules: ISMINUS_IN_GGA(zero, pred(Y), succ(Z)) -> ISMINUS_IN_GGA(zero, Y, Z) ISMINUS_IN_GGA(zero, succ(Y), pred(Z)) -> ISMINUS_IN_GGA(zero, Y, Z) R is empty. The argument filtering Pi contains the following mapping: zero = zero succ(x1) = succ(x1) pred(x1) = pred(x1) ISMINUS_IN_GGA(x1, x2, x3) = ISMINUS_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (16) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (17) Obligation: Q DP problem: The TRS P consists of the following rules: ISMINUS_IN_GGA(zero, pred(Y)) -> ISMINUS_IN_GGA(zero, Y) ISMINUS_IN_GGA(zero, succ(Y)) -> ISMINUS_IN_GGA(zero, Y) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (18) 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: *ISMINUS_IN_GGA(zero, pred(Y)) -> ISMINUS_IN_GGA(zero, Y) The graph contains the following edges 1 >= 1, 2 > 2 *ISMINUS_IN_GGA(zero, succ(Y)) -> ISMINUS_IN_GGA(zero, Y) The graph contains the following edges 1 >= 1, 2 > 2 ---------------------------------------- (19) YES ---------------------------------------- (20) Obligation: Pi DP problem: The TRS P consists of the following rules: ISMINUS_IN_GGA(succ(X), pred(Y), succ(succ(Z))) -> ISMINUS_IN_GGA(X, Y, Z) ISMINUS_IN_GGA(succ(X), succ(Y), Z) -> ISMINUS_IN_GGA(X, Y, Z) ISMINUS_IN_GGA(pred(X), succ(Y), pred(pred(Z))) -> ISMINUS_IN_GGA(X, Y, Z) ISMINUS_IN_GGA(pred(X), pred(Y), Z) -> ISMINUS_IN_GGA(X, Y, Z) The TRS R consists of the following rules: get_in_aaa(.(X, XS), zero, Res) -> U1_aaa(X, XS, Res, =_in_aa(Res, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_aaa(X, XS, Res, =_out_aa(Res, X)) -> get_out_aaa(.(X, XS), zero, Res) get_in_aaa(.(X, XS), Y, Res) -> U2_aaa(X, XS, Y, Res, isMinus_in_aga(Y, succ(zero), U)) isMinus_in_aga(X, zero, X) -> isMinus_out_aga(X, zero, X) isMinus_in_aga(zero, succ(Y), pred(Z)) -> U9_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(X, zero, X) -> isMinus_out_gga(X, zero, X) isMinus_in_gga(zero, succ(Y), pred(Z)) -> U9_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(zero, pred(Y), succ(Z)) -> U10_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(succ(X), succ(Y), Z) -> U11_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(succ(X), pred(Y), succ(succ(Z))) -> U12_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), succ(Y), pred(pred(Z))) -> U13_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), pred(Y), Z) -> U14_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) U14_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), pred(Y), Z) U13_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), succ(Y), pred(pred(Z))) U12_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), pred(Y), succ(succ(Z))) U11_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), succ(Y), Z) U10_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, pred(Y), succ(Z)) U9_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, succ(Y), pred(Z)) U9_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, succ(Y), pred(Z)) isMinus_in_aga(zero, pred(Y), succ(Z)) -> U10_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) U10_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, pred(Y), succ(Z)) isMinus_in_aga(succ(X), succ(Y), Z) -> U11_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(succ(X), pred(Y), succ(succ(Z))) -> U12_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), succ(Y), pred(pred(Z))) -> U13_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), pred(Y), Z) -> U14_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) U14_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), pred(Y), Z) U13_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), succ(Y), pred(pred(Z))) U12_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), pred(Y), succ(succ(Z))) U11_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), succ(Y), Z) U2_aaa(X, XS, Y, Res, isMinus_out_aga(Y, succ(zero), U)) -> U3_aaa(X, XS, Y, Res, =_in_aa(YP, U)) U3_aaa(X, XS, Y, Res, =_out_aa(YP, U)) -> U4_aaa(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U4_aaa(X, XS, Y, Res, get_out_aaa(XS, YP, Res)) -> get_out_aaa(.(X, XS), Y, Res) The argument filtering Pi contains the following mapping: get_in_aaa(x1, x2, x3) = get_in_aaa U1_aaa(x1, x2, x3, x4) = U1_aaa(x4) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa get_out_aaa(x1, x2, x3) = get_out_aaa U2_aaa(x1, x2, x3, x4, x5) = U2_aaa(x5) isMinus_in_aga(x1, x2, x3) = isMinus_in_aga(x2) zero = zero isMinus_out_aga(x1, x2, x3) = isMinus_out_aga succ(x1) = succ(x1) U9_aga(x1, x2, x3) = U9_aga(x3) isMinus_in_gga(x1, x2, x3) = isMinus_in_gga(x1, x2) isMinus_out_gga(x1, x2, x3) = isMinus_out_gga(x3) U9_gga(x1, x2, x3) = U9_gga(x3) pred(x1) = pred(x1) U10_gga(x1, x2, x3) = U10_gga(x3) U11_gga(x1, x2, x3, x4) = U11_gga(x4) U12_gga(x1, x2, x3, x4) = U12_gga(x4) U13_gga(x1, x2, x3, x4) = U13_gga(x4) U14_gga(x1, x2, x3, x4) = U14_gga(x4) U10_aga(x1, x2, x3) = U10_aga(x3) U11_aga(x1, x2, x3, x4) = U11_aga(x4) U12_aga(x1, x2, x3, x4) = U12_aga(x4) U13_aga(x1, x2, x3, x4) = U13_aga(x4) U14_aga(x1, x2, x3, x4) = U14_aga(x4) U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) ISMINUS_IN_GGA(x1, x2, x3) = ISMINUS_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (21) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (22) Obligation: Pi DP problem: The TRS P consists of the following rules: ISMINUS_IN_GGA(succ(X), pred(Y), succ(succ(Z))) -> ISMINUS_IN_GGA(X, Y, Z) ISMINUS_IN_GGA(succ(X), succ(Y), Z) -> ISMINUS_IN_GGA(X, Y, Z) ISMINUS_IN_GGA(pred(X), succ(Y), pred(pred(Z))) -> ISMINUS_IN_GGA(X, Y, Z) ISMINUS_IN_GGA(pred(X), pred(Y), Z) -> ISMINUS_IN_GGA(X, Y, Z) R is empty. The argument filtering Pi contains the following mapping: succ(x1) = succ(x1) pred(x1) = pred(x1) ISMINUS_IN_GGA(x1, x2, x3) = ISMINUS_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (23) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: ISMINUS_IN_GGA(succ(X), pred(Y)) -> ISMINUS_IN_GGA(X, Y) ISMINUS_IN_GGA(succ(X), succ(Y)) -> ISMINUS_IN_GGA(X, Y) ISMINUS_IN_GGA(pred(X), succ(Y)) -> ISMINUS_IN_GGA(X, Y) ISMINUS_IN_GGA(pred(X), pred(Y)) -> ISMINUS_IN_GGA(X, Y) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (25) 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: *ISMINUS_IN_GGA(succ(X), pred(Y)) -> ISMINUS_IN_GGA(X, Y) The graph contains the following edges 1 > 1, 2 > 2 *ISMINUS_IN_GGA(succ(X), succ(Y)) -> ISMINUS_IN_GGA(X, Y) The graph contains the following edges 1 > 1, 2 > 2 *ISMINUS_IN_GGA(pred(X), succ(Y)) -> ISMINUS_IN_GGA(X, Y) The graph contains the following edges 1 > 1, 2 > 2 *ISMINUS_IN_GGA(pred(X), pred(Y)) -> ISMINUS_IN_GGA(X, Y) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (26) YES ---------------------------------------- (27) Obligation: Pi DP problem: The TRS P consists of the following rules: ISMINUS_IN_AGA(succ(X), pred(Y), succ(succ(Z))) -> ISMINUS_IN_AGA(X, Y, Z) ISMINUS_IN_AGA(succ(X), succ(Y), Z) -> ISMINUS_IN_AGA(X, Y, Z) ISMINUS_IN_AGA(pred(X), succ(Y), pred(pred(Z))) -> ISMINUS_IN_AGA(X, Y, Z) ISMINUS_IN_AGA(pred(X), pred(Y), Z) -> ISMINUS_IN_AGA(X, Y, Z) The TRS R consists of the following rules: get_in_aaa(.(X, XS), zero, Res) -> U1_aaa(X, XS, Res, =_in_aa(Res, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_aaa(X, XS, Res, =_out_aa(Res, X)) -> get_out_aaa(.(X, XS), zero, Res) get_in_aaa(.(X, XS), Y, Res) -> U2_aaa(X, XS, Y, Res, isMinus_in_aga(Y, succ(zero), U)) isMinus_in_aga(X, zero, X) -> isMinus_out_aga(X, zero, X) isMinus_in_aga(zero, succ(Y), pred(Z)) -> U9_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(X, zero, X) -> isMinus_out_gga(X, zero, X) isMinus_in_gga(zero, succ(Y), pred(Z)) -> U9_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(zero, pred(Y), succ(Z)) -> U10_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(succ(X), succ(Y), Z) -> U11_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(succ(X), pred(Y), succ(succ(Z))) -> U12_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), succ(Y), pred(pred(Z))) -> U13_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), pred(Y), Z) -> U14_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) U14_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), pred(Y), Z) U13_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), succ(Y), pred(pred(Z))) U12_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), pred(Y), succ(succ(Z))) U11_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), succ(Y), Z) U10_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, pred(Y), succ(Z)) U9_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, succ(Y), pred(Z)) U9_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, succ(Y), pred(Z)) isMinus_in_aga(zero, pred(Y), succ(Z)) -> U10_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) U10_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, pred(Y), succ(Z)) isMinus_in_aga(succ(X), succ(Y), Z) -> U11_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(succ(X), pred(Y), succ(succ(Z))) -> U12_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), succ(Y), pred(pred(Z))) -> U13_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), pred(Y), Z) -> U14_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) U14_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), pred(Y), Z) U13_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), succ(Y), pred(pred(Z))) U12_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), pred(Y), succ(succ(Z))) U11_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), succ(Y), Z) U2_aaa(X, XS, Y, Res, isMinus_out_aga(Y, succ(zero), U)) -> U3_aaa(X, XS, Y, Res, =_in_aa(YP, U)) U3_aaa(X, XS, Y, Res, =_out_aa(YP, U)) -> U4_aaa(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U4_aaa(X, XS, Y, Res, get_out_aaa(XS, YP, Res)) -> get_out_aaa(.(X, XS), Y, Res) The argument filtering Pi contains the following mapping: get_in_aaa(x1, x2, x3) = get_in_aaa U1_aaa(x1, x2, x3, x4) = U1_aaa(x4) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa get_out_aaa(x1, x2, x3) = get_out_aaa U2_aaa(x1, x2, x3, x4, x5) = U2_aaa(x5) isMinus_in_aga(x1, x2, x3) = isMinus_in_aga(x2) zero = zero isMinus_out_aga(x1, x2, x3) = isMinus_out_aga succ(x1) = succ(x1) U9_aga(x1, x2, x3) = U9_aga(x3) isMinus_in_gga(x1, x2, x3) = isMinus_in_gga(x1, x2) isMinus_out_gga(x1, x2, x3) = isMinus_out_gga(x3) U9_gga(x1, x2, x3) = U9_gga(x3) pred(x1) = pred(x1) U10_gga(x1, x2, x3) = U10_gga(x3) U11_gga(x1, x2, x3, x4) = U11_gga(x4) U12_gga(x1, x2, x3, x4) = U12_gga(x4) U13_gga(x1, x2, x3, x4) = U13_gga(x4) U14_gga(x1, x2, x3, x4) = U14_gga(x4) U10_aga(x1, x2, x3) = U10_aga(x3) U11_aga(x1, x2, x3, x4) = U11_aga(x4) U12_aga(x1, x2, x3, x4) = U12_aga(x4) U13_aga(x1, x2, x3, x4) = U13_aga(x4) U14_aga(x1, x2, x3, x4) = U14_aga(x4) U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) ISMINUS_IN_AGA(x1, x2, x3) = ISMINUS_IN_AGA(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (28) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (29) Obligation: Pi DP problem: The TRS P consists of the following rules: ISMINUS_IN_AGA(succ(X), pred(Y), succ(succ(Z))) -> ISMINUS_IN_AGA(X, Y, Z) ISMINUS_IN_AGA(succ(X), succ(Y), Z) -> ISMINUS_IN_AGA(X, Y, Z) ISMINUS_IN_AGA(pred(X), succ(Y), pred(pred(Z))) -> ISMINUS_IN_AGA(X, Y, Z) ISMINUS_IN_AGA(pred(X), pred(Y), Z) -> ISMINUS_IN_AGA(X, Y, Z) R is empty. The argument filtering Pi contains the following mapping: succ(x1) = succ(x1) pred(x1) = pred(x1) ISMINUS_IN_AGA(x1, x2, x3) = ISMINUS_IN_AGA(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (30) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (31) Obligation: Q DP problem: The TRS P consists of the following rules: ISMINUS_IN_AGA(pred(Y)) -> ISMINUS_IN_AGA(Y) ISMINUS_IN_AGA(succ(Y)) -> ISMINUS_IN_AGA(Y) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (32) 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: *ISMINUS_IN_AGA(pred(Y)) -> ISMINUS_IN_AGA(Y) The graph contains the following edges 1 > 1 *ISMINUS_IN_AGA(succ(Y)) -> ISMINUS_IN_AGA(Y) The graph contains the following edges 1 > 1 ---------------------------------------- (33) YES ---------------------------------------- (34) Obligation: Pi DP problem: The TRS P consists of the following rules: GET_IN_AAA(.(X, XS), Y, Res) -> U2_AAA(X, XS, Y, Res, isMinus_in_aga(Y, succ(zero), U)) U2_AAA(X, XS, Y, Res, isMinus_out_aga(Y, succ(zero), U)) -> U3_AAA(X, XS, Y, Res, =_in_aa(YP, U)) U3_AAA(X, XS, Y, Res, =_out_aa(YP, U)) -> GET_IN_AAA(XS, YP, Res) The TRS R consists of the following rules: get_in_aaa(.(X, XS), zero, Res) -> U1_aaa(X, XS, Res, =_in_aa(Res, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_aaa(X, XS, Res, =_out_aa(Res, X)) -> get_out_aaa(.(X, XS), zero, Res) get_in_aaa(.(X, XS), Y, Res) -> U2_aaa(X, XS, Y, Res, isMinus_in_aga(Y, succ(zero), U)) isMinus_in_aga(X, zero, X) -> isMinus_out_aga(X, zero, X) isMinus_in_aga(zero, succ(Y), pred(Z)) -> U9_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(X, zero, X) -> isMinus_out_gga(X, zero, X) isMinus_in_gga(zero, succ(Y), pred(Z)) -> U9_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(zero, pred(Y), succ(Z)) -> U10_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(succ(X), succ(Y), Z) -> U11_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(succ(X), pred(Y), succ(succ(Z))) -> U12_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), succ(Y), pred(pred(Z))) -> U13_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), pred(Y), Z) -> U14_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) U14_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), pred(Y), Z) U13_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), succ(Y), pred(pred(Z))) U12_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), pred(Y), succ(succ(Z))) U11_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), succ(Y), Z) U10_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, pred(Y), succ(Z)) U9_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, succ(Y), pred(Z)) U9_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, succ(Y), pred(Z)) isMinus_in_aga(zero, pred(Y), succ(Z)) -> U10_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) U10_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, pred(Y), succ(Z)) isMinus_in_aga(succ(X), succ(Y), Z) -> U11_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(succ(X), pred(Y), succ(succ(Z))) -> U12_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), succ(Y), pred(pred(Z))) -> U13_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), pred(Y), Z) -> U14_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) U14_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), pred(Y), Z) U13_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), succ(Y), pred(pred(Z))) U12_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), pred(Y), succ(succ(Z))) U11_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), succ(Y), Z) U2_aaa(X, XS, Y, Res, isMinus_out_aga(Y, succ(zero), U)) -> U3_aaa(X, XS, Y, Res, =_in_aa(YP, U)) U3_aaa(X, XS, Y, Res, =_out_aa(YP, U)) -> U4_aaa(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U4_aaa(X, XS, Y, Res, get_out_aaa(XS, YP, Res)) -> get_out_aaa(.(X, XS), Y, Res) The argument filtering Pi contains the following mapping: get_in_aaa(x1, x2, x3) = get_in_aaa U1_aaa(x1, x2, x3, x4) = U1_aaa(x4) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa get_out_aaa(x1, x2, x3) = get_out_aaa U2_aaa(x1, x2, x3, x4, x5) = U2_aaa(x5) isMinus_in_aga(x1, x2, x3) = isMinus_in_aga(x2) zero = zero isMinus_out_aga(x1, x2, x3) = isMinus_out_aga succ(x1) = succ(x1) U9_aga(x1, x2, x3) = U9_aga(x3) isMinus_in_gga(x1, x2, x3) = isMinus_in_gga(x1, x2) isMinus_out_gga(x1, x2, x3) = isMinus_out_gga(x3) U9_gga(x1, x2, x3) = U9_gga(x3) pred(x1) = pred(x1) U10_gga(x1, x2, x3) = U10_gga(x3) U11_gga(x1, x2, x3, x4) = U11_gga(x4) U12_gga(x1, x2, x3, x4) = U12_gga(x4) U13_gga(x1, x2, x3, x4) = U13_gga(x4) U14_gga(x1, x2, x3, x4) = U14_gga(x4) U10_aga(x1, x2, x3) = U10_aga(x3) U11_aga(x1, x2, x3, x4) = U11_aga(x4) U12_aga(x1, x2, x3, x4) = U12_aga(x4) U13_aga(x1, x2, x3, x4) = U13_aga(x4) U14_aga(x1, x2, x3, x4) = U14_aga(x4) U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) GET_IN_AAA(x1, x2, x3) = GET_IN_AAA U2_AAA(x1, x2, x3, x4, x5) = U2_AAA(x5) U3_AAA(x1, x2, x3, x4, x5) = U3_AAA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (35) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (36) Obligation: Pi DP problem: The TRS P consists of the following rules: GET_IN_AAA(.(X, XS), Y, Res) -> U2_AAA(X, XS, Y, Res, isMinus_in_aga(Y, succ(zero), U)) U2_AAA(X, XS, Y, Res, isMinus_out_aga(Y, succ(zero), U)) -> U3_AAA(X, XS, Y, Res, =_in_aa(YP, U)) U3_AAA(X, XS, Y, Res, =_out_aa(YP, U)) -> GET_IN_AAA(XS, YP, Res) The TRS R consists of the following rules: isMinus_in_aga(zero, succ(Y), pred(Z)) -> U9_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_aga(succ(X), succ(Y), Z) -> U11_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), succ(Y), pred(pred(Z))) -> U13_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) =_in_aa(X, X) -> =_out_aa(X, X) U9_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, succ(Y), pred(Z)) U11_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), succ(Y), Z) U13_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), succ(Y), pred(pred(Z))) isMinus_in_gga(X, zero, X) -> isMinus_out_gga(X, zero, X) isMinus_in_gga(zero, succ(Y), pred(Z)) -> U9_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(zero, pred(Y), succ(Z)) -> U10_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_aga(X, zero, X) -> isMinus_out_aga(X, zero, X) isMinus_in_aga(zero, pred(Y), succ(Z)) -> U10_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_aga(succ(X), pred(Y), succ(succ(Z))) -> U12_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), pred(Y), Z) -> U14_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) U9_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, succ(Y), pred(Z)) U10_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, pred(Y), succ(Z)) U10_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, pred(Y), succ(Z)) U12_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), pred(Y), succ(succ(Z))) U14_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), pred(Y), Z) The argument filtering Pi contains the following mapping: =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa isMinus_in_aga(x1, x2, x3) = isMinus_in_aga(x2) zero = zero isMinus_out_aga(x1, x2, x3) = isMinus_out_aga succ(x1) = succ(x1) U9_aga(x1, x2, x3) = U9_aga(x3) isMinus_in_gga(x1, x2, x3) = isMinus_in_gga(x1, x2) isMinus_out_gga(x1, x2, x3) = isMinus_out_gga(x3) U9_gga(x1, x2, x3) = U9_gga(x3) pred(x1) = pred(x1) U10_gga(x1, x2, x3) = U10_gga(x3) U10_aga(x1, x2, x3) = U10_aga(x3) U11_aga(x1, x2, x3, x4) = U11_aga(x4) U12_aga(x1, x2, x3, x4) = U12_aga(x4) U13_aga(x1, x2, x3, x4) = U13_aga(x4) U14_aga(x1, x2, x3, x4) = U14_aga(x4) GET_IN_AAA(x1, x2, x3) = GET_IN_AAA U2_AAA(x1, x2, x3, x4, x5) = U2_AAA(x5) U3_AAA(x1, x2, x3, x4, x5) = U3_AAA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (37) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: GET_IN_AAA -> U2_AAA(isMinus_in_aga(succ(zero))) U2_AAA(isMinus_out_aga) -> U3_AAA(=_in_aa) U3_AAA(=_out_aa) -> GET_IN_AAA The TRS R consists of the following rules: isMinus_in_aga(succ(Y)) -> U9_aga(isMinus_in_gga(zero, Y)) isMinus_in_aga(succ(Y)) -> U11_aga(isMinus_in_aga(Y)) isMinus_in_aga(succ(Y)) -> U13_aga(isMinus_in_aga(Y)) =_in_aa -> =_out_aa U9_aga(isMinus_out_gga(Z)) -> isMinus_out_aga U11_aga(isMinus_out_aga) -> isMinus_out_aga U13_aga(isMinus_out_aga) -> isMinus_out_aga isMinus_in_gga(X, zero) -> isMinus_out_gga(X) isMinus_in_gga(zero, succ(Y)) -> U9_gga(isMinus_in_gga(zero, Y)) isMinus_in_gga(zero, pred(Y)) -> U10_gga(isMinus_in_gga(zero, Y)) isMinus_in_aga(zero) -> isMinus_out_aga isMinus_in_aga(pred(Y)) -> U10_aga(isMinus_in_gga(zero, Y)) isMinus_in_aga(pred(Y)) -> U12_aga(isMinus_in_aga(Y)) isMinus_in_aga(pred(Y)) -> U14_aga(isMinus_in_aga(Y)) U9_gga(isMinus_out_gga(Z)) -> isMinus_out_gga(pred(Z)) U10_gga(isMinus_out_gga(Z)) -> isMinus_out_gga(succ(Z)) U10_aga(isMinus_out_gga(Z)) -> isMinus_out_aga U12_aga(isMinus_out_aga) -> isMinus_out_aga U14_aga(isMinus_out_aga) -> isMinus_out_aga The set Q consists of the following terms: isMinus_in_aga(x0) =_in_aa U9_aga(x0) U11_aga(x0) U13_aga(x0) isMinus_in_gga(x0, x1) U9_gga(x0) U10_gga(x0) U10_aga(x0) U12_aga(x0) U14_aga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (39) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: get_in_3: (f,f,f) isMinus_in_3: (f,b,f) (b,b,f) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: get_in_aaa(.(X, XS), zero, Res) -> U1_aaa(X, XS, Res, =_in_aa(Res, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_aaa(X, XS, Res, =_out_aa(Res, X)) -> get_out_aaa(.(X, XS), zero, Res) get_in_aaa(.(X, XS), Y, Res) -> U2_aaa(X, XS, Y, Res, isMinus_in_aga(Y, succ(zero), U)) isMinus_in_aga(X, zero, X) -> isMinus_out_aga(X, zero, X) isMinus_in_aga(zero, succ(Y), pred(Z)) -> U9_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(X, zero, X) -> isMinus_out_gga(X, zero, X) isMinus_in_gga(zero, succ(Y), pred(Z)) -> U9_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(zero, pred(Y), succ(Z)) -> U10_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(succ(X), succ(Y), Z) -> U11_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(succ(X), pred(Y), succ(succ(Z))) -> U12_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), succ(Y), pred(pred(Z))) -> U13_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), pred(Y), Z) -> U14_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) U14_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), pred(Y), Z) U13_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), succ(Y), pred(pred(Z))) U12_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), pred(Y), succ(succ(Z))) U11_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), succ(Y), Z) U10_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, pred(Y), succ(Z)) U9_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, succ(Y), pred(Z)) U9_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, succ(Y), pred(Z)) isMinus_in_aga(zero, pred(Y), succ(Z)) -> U10_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) U10_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, pred(Y), succ(Z)) isMinus_in_aga(succ(X), succ(Y), Z) -> U11_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(succ(X), pred(Y), succ(succ(Z))) -> U12_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), succ(Y), pred(pred(Z))) -> U13_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), pred(Y), Z) -> U14_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) U14_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), pred(Y), Z) U13_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), succ(Y), pred(pred(Z))) U12_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), pred(Y), succ(succ(Z))) U11_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), succ(Y), Z) U2_aaa(X, XS, Y, Res, isMinus_out_aga(Y, succ(zero), U)) -> U3_aaa(X, XS, Y, Res, =_in_aa(YP, U)) U3_aaa(X, XS, Y, Res, =_out_aa(YP, U)) -> U4_aaa(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U4_aaa(X, XS, Y, Res, get_out_aaa(XS, YP, Res)) -> get_out_aaa(.(X, XS), Y, Res) The argument filtering Pi contains the following mapping: get_in_aaa(x1, x2, x3) = get_in_aaa U1_aaa(x1, x2, x3, x4) = U1_aaa(x4) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa get_out_aaa(x1, x2, x3) = get_out_aaa U2_aaa(x1, x2, x3, x4, x5) = U2_aaa(x5) isMinus_in_aga(x1, x2, x3) = isMinus_in_aga(x2) zero = zero isMinus_out_aga(x1, x2, x3) = isMinus_out_aga(x2) succ(x1) = succ(x1) U9_aga(x1, x2, x3) = U9_aga(x1, x3) isMinus_in_gga(x1, x2, x3) = isMinus_in_gga(x1, x2) isMinus_out_gga(x1, x2, x3) = isMinus_out_gga(x1, x2, x3) U9_gga(x1, x2, x3) = U9_gga(x1, x3) pred(x1) = pred(x1) U10_gga(x1, x2, x3) = U10_gga(x1, x3) U11_gga(x1, x2, x3, x4) = U11_gga(x1, x2, x4) U12_gga(x1, x2, x3, x4) = U12_gga(x1, x2, x4) U13_gga(x1, x2, x3, x4) = U13_gga(x1, x2, x4) U14_gga(x1, x2, x3, x4) = U14_gga(x1, x2, x4) U10_aga(x1, x2, x3) = U10_aga(x1, x3) U11_aga(x1, x2, x3, x4) = U11_aga(x2, x4) U12_aga(x1, x2, x3, x4) = U12_aga(x2, x4) U13_aga(x1, x2, x3, x4) = U13_aga(x2, x4) U14_aga(x1, x2, x3, x4) = U14_aga(x2, x4) U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (40) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: get_in_aaa(.(X, XS), zero, Res) -> U1_aaa(X, XS, Res, =_in_aa(Res, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_aaa(X, XS, Res, =_out_aa(Res, X)) -> get_out_aaa(.(X, XS), zero, Res) get_in_aaa(.(X, XS), Y, Res) -> U2_aaa(X, XS, Y, Res, isMinus_in_aga(Y, succ(zero), U)) isMinus_in_aga(X, zero, X) -> isMinus_out_aga(X, zero, X) isMinus_in_aga(zero, succ(Y), pred(Z)) -> U9_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(X, zero, X) -> isMinus_out_gga(X, zero, X) isMinus_in_gga(zero, succ(Y), pred(Z)) -> U9_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(zero, pred(Y), succ(Z)) -> U10_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(succ(X), succ(Y), Z) -> U11_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(succ(X), pred(Y), succ(succ(Z))) -> U12_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), succ(Y), pred(pred(Z))) -> U13_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), pred(Y), Z) -> U14_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) U14_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), pred(Y), Z) U13_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), succ(Y), pred(pred(Z))) U12_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), pred(Y), succ(succ(Z))) U11_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), succ(Y), Z) U10_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, pred(Y), succ(Z)) U9_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, succ(Y), pred(Z)) U9_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, succ(Y), pred(Z)) isMinus_in_aga(zero, pred(Y), succ(Z)) -> U10_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) U10_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, pred(Y), succ(Z)) isMinus_in_aga(succ(X), succ(Y), Z) -> U11_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(succ(X), pred(Y), succ(succ(Z))) -> U12_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), succ(Y), pred(pred(Z))) -> U13_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), pred(Y), Z) -> U14_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) U14_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), pred(Y), Z) U13_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), succ(Y), pred(pred(Z))) U12_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), pred(Y), succ(succ(Z))) U11_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), succ(Y), Z) U2_aaa(X, XS, Y, Res, isMinus_out_aga(Y, succ(zero), U)) -> U3_aaa(X, XS, Y, Res, =_in_aa(YP, U)) U3_aaa(X, XS, Y, Res, =_out_aa(YP, U)) -> U4_aaa(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U4_aaa(X, XS, Y, Res, get_out_aaa(XS, YP, Res)) -> get_out_aaa(.(X, XS), Y, Res) The argument filtering Pi contains the following mapping: get_in_aaa(x1, x2, x3) = get_in_aaa U1_aaa(x1, x2, x3, x4) = U1_aaa(x4) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa get_out_aaa(x1, x2, x3) = get_out_aaa U2_aaa(x1, x2, x3, x4, x5) = U2_aaa(x5) isMinus_in_aga(x1, x2, x3) = isMinus_in_aga(x2) zero = zero isMinus_out_aga(x1, x2, x3) = isMinus_out_aga(x2) succ(x1) = succ(x1) U9_aga(x1, x2, x3) = U9_aga(x1, x3) isMinus_in_gga(x1, x2, x3) = isMinus_in_gga(x1, x2) isMinus_out_gga(x1, x2, x3) = isMinus_out_gga(x1, x2, x3) U9_gga(x1, x2, x3) = U9_gga(x1, x3) pred(x1) = pred(x1) U10_gga(x1, x2, x3) = U10_gga(x1, x3) U11_gga(x1, x2, x3, x4) = U11_gga(x1, x2, x4) U12_gga(x1, x2, x3, x4) = U12_gga(x1, x2, x4) U13_gga(x1, x2, x3, x4) = U13_gga(x1, x2, x4) U14_gga(x1, x2, x3, x4) = U14_gga(x1, x2, x4) U10_aga(x1, x2, x3) = U10_aga(x1, x3) U11_aga(x1, x2, x3, x4) = U11_aga(x2, x4) U12_aga(x1, x2, x3, x4) = U12_aga(x2, x4) U13_aga(x1, x2, x3, x4) = U13_aga(x2, x4) U14_aga(x1, x2, x3, x4) = U14_aga(x2, x4) U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) ---------------------------------------- (41) 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: GET_IN_AAA(.(X, XS), zero, Res) -> U1_AAA(X, XS, Res, =_in_aa(Res, X)) GET_IN_AAA(.(X, XS), zero, Res) -> =_IN_AA(Res, X) GET_IN_AAA(.(X, XS), Y, Res) -> U2_AAA(X, XS, Y, Res, isMinus_in_aga(Y, succ(zero), U)) GET_IN_AAA(.(X, XS), Y, Res) -> ISMINUS_IN_AGA(Y, succ(zero), U) ISMINUS_IN_AGA(zero, succ(Y), pred(Z)) -> U9_AGA(Y, Z, isMinus_in_gga(zero, Y, Z)) ISMINUS_IN_AGA(zero, succ(Y), pred(Z)) -> ISMINUS_IN_GGA(zero, Y, Z) ISMINUS_IN_GGA(zero, succ(Y), pred(Z)) -> U9_GGA(Y, Z, isMinus_in_gga(zero, Y, Z)) ISMINUS_IN_GGA(zero, succ(Y), pred(Z)) -> ISMINUS_IN_GGA(zero, Y, Z) ISMINUS_IN_GGA(zero, pred(Y), succ(Z)) -> U10_GGA(Y, Z, isMinus_in_gga(zero, Y, Z)) ISMINUS_IN_GGA(zero, pred(Y), succ(Z)) -> ISMINUS_IN_GGA(zero, Y, Z) ISMINUS_IN_GGA(succ(X), succ(Y), Z) -> U11_GGA(X, Y, Z, isMinus_in_gga(X, Y, Z)) ISMINUS_IN_GGA(succ(X), succ(Y), Z) -> ISMINUS_IN_GGA(X, Y, Z) ISMINUS_IN_GGA(succ(X), pred(Y), succ(succ(Z))) -> U12_GGA(X, Y, Z, isMinus_in_gga(X, Y, Z)) ISMINUS_IN_GGA(succ(X), pred(Y), succ(succ(Z))) -> ISMINUS_IN_GGA(X, Y, Z) ISMINUS_IN_GGA(pred(X), succ(Y), pred(pred(Z))) -> U13_GGA(X, Y, Z, isMinus_in_gga(X, Y, Z)) ISMINUS_IN_GGA(pred(X), succ(Y), pred(pred(Z))) -> ISMINUS_IN_GGA(X, Y, Z) ISMINUS_IN_GGA(pred(X), pred(Y), Z) -> U14_GGA(X, Y, Z, isMinus_in_gga(X, Y, Z)) ISMINUS_IN_GGA(pred(X), pred(Y), Z) -> ISMINUS_IN_GGA(X, Y, Z) ISMINUS_IN_AGA(zero, pred(Y), succ(Z)) -> U10_AGA(Y, Z, isMinus_in_gga(zero, Y, Z)) ISMINUS_IN_AGA(zero, pred(Y), succ(Z)) -> ISMINUS_IN_GGA(zero, Y, Z) ISMINUS_IN_AGA(succ(X), succ(Y), Z) -> U11_AGA(X, Y, Z, isMinus_in_aga(X, Y, Z)) ISMINUS_IN_AGA(succ(X), succ(Y), Z) -> ISMINUS_IN_AGA(X, Y, Z) ISMINUS_IN_AGA(succ(X), pred(Y), succ(succ(Z))) -> U12_AGA(X, Y, Z, isMinus_in_aga(X, Y, Z)) ISMINUS_IN_AGA(succ(X), pred(Y), succ(succ(Z))) -> ISMINUS_IN_AGA(X, Y, Z) ISMINUS_IN_AGA(pred(X), succ(Y), pred(pred(Z))) -> U13_AGA(X, Y, Z, isMinus_in_aga(X, Y, Z)) ISMINUS_IN_AGA(pred(X), succ(Y), pred(pred(Z))) -> ISMINUS_IN_AGA(X, Y, Z) ISMINUS_IN_AGA(pred(X), pred(Y), Z) -> U14_AGA(X, Y, Z, isMinus_in_aga(X, Y, Z)) ISMINUS_IN_AGA(pred(X), pred(Y), Z) -> ISMINUS_IN_AGA(X, Y, Z) U2_AAA(X, XS, Y, Res, isMinus_out_aga(Y, succ(zero), U)) -> U3_AAA(X, XS, Y, Res, =_in_aa(YP, U)) U2_AAA(X, XS, Y, Res, isMinus_out_aga(Y, succ(zero), U)) -> =_IN_AA(YP, U) U3_AAA(X, XS, Y, Res, =_out_aa(YP, U)) -> U4_AAA(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U3_AAA(X, XS, Y, Res, =_out_aa(YP, U)) -> GET_IN_AAA(XS, YP, Res) The TRS R consists of the following rules: get_in_aaa(.(X, XS), zero, Res) -> U1_aaa(X, XS, Res, =_in_aa(Res, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_aaa(X, XS, Res, =_out_aa(Res, X)) -> get_out_aaa(.(X, XS), zero, Res) get_in_aaa(.(X, XS), Y, Res) -> U2_aaa(X, XS, Y, Res, isMinus_in_aga(Y, succ(zero), U)) isMinus_in_aga(X, zero, X) -> isMinus_out_aga(X, zero, X) isMinus_in_aga(zero, succ(Y), pred(Z)) -> U9_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(X, zero, X) -> isMinus_out_gga(X, zero, X) isMinus_in_gga(zero, succ(Y), pred(Z)) -> U9_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(zero, pred(Y), succ(Z)) -> U10_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(succ(X), succ(Y), Z) -> U11_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(succ(X), pred(Y), succ(succ(Z))) -> U12_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), succ(Y), pred(pred(Z))) -> U13_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), pred(Y), Z) -> U14_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) U14_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), pred(Y), Z) U13_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), succ(Y), pred(pred(Z))) U12_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), pred(Y), succ(succ(Z))) U11_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), succ(Y), Z) U10_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, pred(Y), succ(Z)) U9_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, succ(Y), pred(Z)) U9_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, succ(Y), pred(Z)) isMinus_in_aga(zero, pred(Y), succ(Z)) -> U10_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) U10_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, pred(Y), succ(Z)) isMinus_in_aga(succ(X), succ(Y), Z) -> U11_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(succ(X), pred(Y), succ(succ(Z))) -> U12_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), succ(Y), pred(pred(Z))) -> U13_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), pred(Y), Z) -> U14_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) U14_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), pred(Y), Z) U13_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), succ(Y), pred(pred(Z))) U12_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), pred(Y), succ(succ(Z))) U11_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), succ(Y), Z) U2_aaa(X, XS, Y, Res, isMinus_out_aga(Y, succ(zero), U)) -> U3_aaa(X, XS, Y, Res, =_in_aa(YP, U)) U3_aaa(X, XS, Y, Res, =_out_aa(YP, U)) -> U4_aaa(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U4_aaa(X, XS, Y, Res, get_out_aaa(XS, YP, Res)) -> get_out_aaa(.(X, XS), Y, Res) The argument filtering Pi contains the following mapping: get_in_aaa(x1, x2, x3) = get_in_aaa U1_aaa(x1, x2, x3, x4) = U1_aaa(x4) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa get_out_aaa(x1, x2, x3) = get_out_aaa U2_aaa(x1, x2, x3, x4, x5) = U2_aaa(x5) isMinus_in_aga(x1, x2, x3) = isMinus_in_aga(x2) zero = zero isMinus_out_aga(x1, x2, x3) = isMinus_out_aga(x2) succ(x1) = succ(x1) U9_aga(x1, x2, x3) = U9_aga(x1, x3) isMinus_in_gga(x1, x2, x3) = isMinus_in_gga(x1, x2) isMinus_out_gga(x1, x2, x3) = isMinus_out_gga(x1, x2, x3) U9_gga(x1, x2, x3) = U9_gga(x1, x3) pred(x1) = pred(x1) U10_gga(x1, x2, x3) = U10_gga(x1, x3) U11_gga(x1, x2, x3, x4) = U11_gga(x1, x2, x4) U12_gga(x1, x2, x3, x4) = U12_gga(x1, x2, x4) U13_gga(x1, x2, x3, x4) = U13_gga(x1, x2, x4) U14_gga(x1, x2, x3, x4) = U14_gga(x1, x2, x4) U10_aga(x1, x2, x3) = U10_aga(x1, x3) U11_aga(x1, x2, x3, x4) = U11_aga(x2, x4) U12_aga(x1, x2, x3, x4) = U12_aga(x2, x4) U13_aga(x1, x2, x3, x4) = U13_aga(x2, x4) U14_aga(x1, x2, x3, x4) = U14_aga(x2, x4) U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) GET_IN_AAA(x1, x2, x3) = GET_IN_AAA U1_AAA(x1, x2, x3, x4) = U1_AAA(x4) =_IN_AA(x1, x2) = =_IN_AA U2_AAA(x1, x2, x3, x4, x5) = U2_AAA(x5) ISMINUS_IN_AGA(x1, x2, x3) = ISMINUS_IN_AGA(x2) U9_AGA(x1, x2, x3) = U9_AGA(x1, x3) ISMINUS_IN_GGA(x1, x2, x3) = ISMINUS_IN_GGA(x1, x2) U9_GGA(x1, x2, x3) = U9_GGA(x1, x3) U10_GGA(x1, x2, x3) = U10_GGA(x1, x3) U11_GGA(x1, x2, x3, x4) = U11_GGA(x1, x2, x4) U12_GGA(x1, x2, x3, x4) = U12_GGA(x1, x2, x4) U13_GGA(x1, x2, x3, x4) = U13_GGA(x1, x2, x4) U14_GGA(x1, x2, x3, x4) = U14_GGA(x1, x2, x4) U10_AGA(x1, x2, x3) = U10_AGA(x1, x3) U11_AGA(x1, x2, x3, x4) = U11_AGA(x2, x4) U12_AGA(x1, x2, x3, x4) = U12_AGA(x2, x4) U13_AGA(x1, x2, x3, x4) = U13_AGA(x2, x4) U14_AGA(x1, x2, x3, x4) = U14_AGA(x2, x4) U3_AAA(x1, x2, x3, x4, x5) = U3_AAA(x5) U4_AAA(x1, x2, x3, x4, x5) = U4_AAA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (42) Obligation: Pi DP problem: The TRS P consists of the following rules: GET_IN_AAA(.(X, XS), zero, Res) -> U1_AAA(X, XS, Res, =_in_aa(Res, X)) GET_IN_AAA(.(X, XS), zero, Res) -> =_IN_AA(Res, X) GET_IN_AAA(.(X, XS), Y, Res) -> U2_AAA(X, XS, Y, Res, isMinus_in_aga(Y, succ(zero), U)) GET_IN_AAA(.(X, XS), Y, Res) -> ISMINUS_IN_AGA(Y, succ(zero), U) ISMINUS_IN_AGA(zero, succ(Y), pred(Z)) -> U9_AGA(Y, Z, isMinus_in_gga(zero, Y, Z)) ISMINUS_IN_AGA(zero, succ(Y), pred(Z)) -> ISMINUS_IN_GGA(zero, Y, Z) ISMINUS_IN_GGA(zero, succ(Y), pred(Z)) -> U9_GGA(Y, Z, isMinus_in_gga(zero, Y, Z)) ISMINUS_IN_GGA(zero, succ(Y), pred(Z)) -> ISMINUS_IN_GGA(zero, Y, Z) ISMINUS_IN_GGA(zero, pred(Y), succ(Z)) -> U10_GGA(Y, Z, isMinus_in_gga(zero, Y, Z)) ISMINUS_IN_GGA(zero, pred(Y), succ(Z)) -> ISMINUS_IN_GGA(zero, Y, Z) ISMINUS_IN_GGA(succ(X), succ(Y), Z) -> U11_GGA(X, Y, Z, isMinus_in_gga(X, Y, Z)) ISMINUS_IN_GGA(succ(X), succ(Y), Z) -> ISMINUS_IN_GGA(X, Y, Z) ISMINUS_IN_GGA(succ(X), pred(Y), succ(succ(Z))) -> U12_GGA(X, Y, Z, isMinus_in_gga(X, Y, Z)) ISMINUS_IN_GGA(succ(X), pred(Y), succ(succ(Z))) -> ISMINUS_IN_GGA(X, Y, Z) ISMINUS_IN_GGA(pred(X), succ(Y), pred(pred(Z))) -> U13_GGA(X, Y, Z, isMinus_in_gga(X, Y, Z)) ISMINUS_IN_GGA(pred(X), succ(Y), pred(pred(Z))) -> ISMINUS_IN_GGA(X, Y, Z) ISMINUS_IN_GGA(pred(X), pred(Y), Z) -> U14_GGA(X, Y, Z, isMinus_in_gga(X, Y, Z)) ISMINUS_IN_GGA(pred(X), pred(Y), Z) -> ISMINUS_IN_GGA(X, Y, Z) ISMINUS_IN_AGA(zero, pred(Y), succ(Z)) -> U10_AGA(Y, Z, isMinus_in_gga(zero, Y, Z)) ISMINUS_IN_AGA(zero, pred(Y), succ(Z)) -> ISMINUS_IN_GGA(zero, Y, Z) ISMINUS_IN_AGA(succ(X), succ(Y), Z) -> U11_AGA(X, Y, Z, isMinus_in_aga(X, Y, Z)) ISMINUS_IN_AGA(succ(X), succ(Y), Z) -> ISMINUS_IN_AGA(X, Y, Z) ISMINUS_IN_AGA(succ(X), pred(Y), succ(succ(Z))) -> U12_AGA(X, Y, Z, isMinus_in_aga(X, Y, Z)) ISMINUS_IN_AGA(succ(X), pred(Y), succ(succ(Z))) -> ISMINUS_IN_AGA(X, Y, Z) ISMINUS_IN_AGA(pred(X), succ(Y), pred(pred(Z))) -> U13_AGA(X, Y, Z, isMinus_in_aga(X, Y, Z)) ISMINUS_IN_AGA(pred(X), succ(Y), pred(pred(Z))) -> ISMINUS_IN_AGA(X, Y, Z) ISMINUS_IN_AGA(pred(X), pred(Y), Z) -> U14_AGA(X, Y, Z, isMinus_in_aga(X, Y, Z)) ISMINUS_IN_AGA(pred(X), pred(Y), Z) -> ISMINUS_IN_AGA(X, Y, Z) U2_AAA(X, XS, Y, Res, isMinus_out_aga(Y, succ(zero), U)) -> U3_AAA(X, XS, Y, Res, =_in_aa(YP, U)) U2_AAA(X, XS, Y, Res, isMinus_out_aga(Y, succ(zero), U)) -> =_IN_AA(YP, U) U3_AAA(X, XS, Y, Res, =_out_aa(YP, U)) -> U4_AAA(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U3_AAA(X, XS, Y, Res, =_out_aa(YP, U)) -> GET_IN_AAA(XS, YP, Res) The TRS R consists of the following rules: get_in_aaa(.(X, XS), zero, Res) -> U1_aaa(X, XS, Res, =_in_aa(Res, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_aaa(X, XS, Res, =_out_aa(Res, X)) -> get_out_aaa(.(X, XS), zero, Res) get_in_aaa(.(X, XS), Y, Res) -> U2_aaa(X, XS, Y, Res, isMinus_in_aga(Y, succ(zero), U)) isMinus_in_aga(X, zero, X) -> isMinus_out_aga(X, zero, X) isMinus_in_aga(zero, succ(Y), pred(Z)) -> U9_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(X, zero, X) -> isMinus_out_gga(X, zero, X) isMinus_in_gga(zero, succ(Y), pred(Z)) -> U9_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(zero, pred(Y), succ(Z)) -> U10_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(succ(X), succ(Y), Z) -> U11_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(succ(X), pred(Y), succ(succ(Z))) -> U12_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), succ(Y), pred(pred(Z))) -> U13_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), pred(Y), Z) -> U14_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) U14_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), pred(Y), Z) U13_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), succ(Y), pred(pred(Z))) U12_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), pred(Y), succ(succ(Z))) U11_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), succ(Y), Z) U10_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, pred(Y), succ(Z)) U9_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, succ(Y), pred(Z)) U9_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, succ(Y), pred(Z)) isMinus_in_aga(zero, pred(Y), succ(Z)) -> U10_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) U10_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, pred(Y), succ(Z)) isMinus_in_aga(succ(X), succ(Y), Z) -> U11_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(succ(X), pred(Y), succ(succ(Z))) -> U12_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), succ(Y), pred(pred(Z))) -> U13_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), pred(Y), Z) -> U14_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) U14_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), pred(Y), Z) U13_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), succ(Y), pred(pred(Z))) U12_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), pred(Y), succ(succ(Z))) U11_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), succ(Y), Z) U2_aaa(X, XS, Y, Res, isMinus_out_aga(Y, succ(zero), U)) -> U3_aaa(X, XS, Y, Res, =_in_aa(YP, U)) U3_aaa(X, XS, Y, Res, =_out_aa(YP, U)) -> U4_aaa(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U4_aaa(X, XS, Y, Res, get_out_aaa(XS, YP, Res)) -> get_out_aaa(.(X, XS), Y, Res) The argument filtering Pi contains the following mapping: get_in_aaa(x1, x2, x3) = get_in_aaa U1_aaa(x1, x2, x3, x4) = U1_aaa(x4) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa get_out_aaa(x1, x2, x3) = get_out_aaa U2_aaa(x1, x2, x3, x4, x5) = U2_aaa(x5) isMinus_in_aga(x1, x2, x3) = isMinus_in_aga(x2) zero = zero isMinus_out_aga(x1, x2, x3) = isMinus_out_aga(x2) succ(x1) = succ(x1) U9_aga(x1, x2, x3) = U9_aga(x1, x3) isMinus_in_gga(x1, x2, x3) = isMinus_in_gga(x1, x2) isMinus_out_gga(x1, x2, x3) = isMinus_out_gga(x1, x2, x3) U9_gga(x1, x2, x3) = U9_gga(x1, x3) pred(x1) = pred(x1) U10_gga(x1, x2, x3) = U10_gga(x1, x3) U11_gga(x1, x2, x3, x4) = U11_gga(x1, x2, x4) U12_gga(x1, x2, x3, x4) = U12_gga(x1, x2, x4) U13_gga(x1, x2, x3, x4) = U13_gga(x1, x2, x4) U14_gga(x1, x2, x3, x4) = U14_gga(x1, x2, x4) U10_aga(x1, x2, x3) = U10_aga(x1, x3) U11_aga(x1, x2, x3, x4) = U11_aga(x2, x4) U12_aga(x1, x2, x3, x4) = U12_aga(x2, x4) U13_aga(x1, x2, x3, x4) = U13_aga(x2, x4) U14_aga(x1, x2, x3, x4) = U14_aga(x2, x4) U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) GET_IN_AAA(x1, x2, x3) = GET_IN_AAA U1_AAA(x1, x2, x3, x4) = U1_AAA(x4) =_IN_AA(x1, x2) = =_IN_AA U2_AAA(x1, x2, x3, x4, x5) = U2_AAA(x5) ISMINUS_IN_AGA(x1, x2, x3) = ISMINUS_IN_AGA(x2) U9_AGA(x1, x2, x3) = U9_AGA(x1, x3) ISMINUS_IN_GGA(x1, x2, x3) = ISMINUS_IN_GGA(x1, x2) U9_GGA(x1, x2, x3) = U9_GGA(x1, x3) U10_GGA(x1, x2, x3) = U10_GGA(x1, x3) U11_GGA(x1, x2, x3, x4) = U11_GGA(x1, x2, x4) U12_GGA(x1, x2, x3, x4) = U12_GGA(x1, x2, x4) U13_GGA(x1, x2, x3, x4) = U13_GGA(x1, x2, x4) U14_GGA(x1, x2, x3, x4) = U14_GGA(x1, x2, x4) U10_AGA(x1, x2, x3) = U10_AGA(x1, x3) U11_AGA(x1, x2, x3, x4) = U11_AGA(x2, x4) U12_AGA(x1, x2, x3, x4) = U12_AGA(x2, x4) U13_AGA(x1, x2, x3, x4) = U13_AGA(x2, x4) U14_AGA(x1, x2, x3, x4) = U14_AGA(x2, x4) U3_AAA(x1, x2, x3, x4, x5) = U3_AAA(x5) U4_AAA(x1, x2, x3, x4, x5) = U4_AAA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (43) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 4 SCCs with 19 less nodes. ---------------------------------------- (44) Complex Obligation (AND) ---------------------------------------- (45) Obligation: Pi DP problem: The TRS P consists of the following rules: ISMINUS_IN_GGA(zero, pred(Y), succ(Z)) -> ISMINUS_IN_GGA(zero, Y, Z) ISMINUS_IN_GGA(zero, succ(Y), pred(Z)) -> ISMINUS_IN_GGA(zero, Y, Z) The TRS R consists of the following rules: get_in_aaa(.(X, XS), zero, Res) -> U1_aaa(X, XS, Res, =_in_aa(Res, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_aaa(X, XS, Res, =_out_aa(Res, X)) -> get_out_aaa(.(X, XS), zero, Res) get_in_aaa(.(X, XS), Y, Res) -> U2_aaa(X, XS, Y, Res, isMinus_in_aga(Y, succ(zero), U)) isMinus_in_aga(X, zero, X) -> isMinus_out_aga(X, zero, X) isMinus_in_aga(zero, succ(Y), pred(Z)) -> U9_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(X, zero, X) -> isMinus_out_gga(X, zero, X) isMinus_in_gga(zero, succ(Y), pred(Z)) -> U9_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(zero, pred(Y), succ(Z)) -> U10_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(succ(X), succ(Y), Z) -> U11_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(succ(X), pred(Y), succ(succ(Z))) -> U12_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), succ(Y), pred(pred(Z))) -> U13_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), pred(Y), Z) -> U14_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) U14_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), pred(Y), Z) U13_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), succ(Y), pred(pred(Z))) U12_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), pred(Y), succ(succ(Z))) U11_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), succ(Y), Z) U10_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, pred(Y), succ(Z)) U9_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, succ(Y), pred(Z)) U9_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, succ(Y), pred(Z)) isMinus_in_aga(zero, pred(Y), succ(Z)) -> U10_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) U10_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, pred(Y), succ(Z)) isMinus_in_aga(succ(X), succ(Y), Z) -> U11_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(succ(X), pred(Y), succ(succ(Z))) -> U12_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), succ(Y), pred(pred(Z))) -> U13_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), pred(Y), Z) -> U14_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) U14_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), pred(Y), Z) U13_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), succ(Y), pred(pred(Z))) U12_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), pred(Y), succ(succ(Z))) U11_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), succ(Y), Z) U2_aaa(X, XS, Y, Res, isMinus_out_aga(Y, succ(zero), U)) -> U3_aaa(X, XS, Y, Res, =_in_aa(YP, U)) U3_aaa(X, XS, Y, Res, =_out_aa(YP, U)) -> U4_aaa(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U4_aaa(X, XS, Y, Res, get_out_aaa(XS, YP, Res)) -> get_out_aaa(.(X, XS), Y, Res) The argument filtering Pi contains the following mapping: get_in_aaa(x1, x2, x3) = get_in_aaa U1_aaa(x1, x2, x3, x4) = U1_aaa(x4) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa get_out_aaa(x1, x2, x3) = get_out_aaa U2_aaa(x1, x2, x3, x4, x5) = U2_aaa(x5) isMinus_in_aga(x1, x2, x3) = isMinus_in_aga(x2) zero = zero isMinus_out_aga(x1, x2, x3) = isMinus_out_aga(x2) succ(x1) = succ(x1) U9_aga(x1, x2, x3) = U9_aga(x1, x3) isMinus_in_gga(x1, x2, x3) = isMinus_in_gga(x1, x2) isMinus_out_gga(x1, x2, x3) = isMinus_out_gga(x1, x2, x3) U9_gga(x1, x2, x3) = U9_gga(x1, x3) pred(x1) = pred(x1) U10_gga(x1, x2, x3) = U10_gga(x1, x3) U11_gga(x1, x2, x3, x4) = U11_gga(x1, x2, x4) U12_gga(x1, x2, x3, x4) = U12_gga(x1, x2, x4) U13_gga(x1, x2, x3, x4) = U13_gga(x1, x2, x4) U14_gga(x1, x2, x3, x4) = U14_gga(x1, x2, x4) U10_aga(x1, x2, x3) = U10_aga(x1, x3) U11_aga(x1, x2, x3, x4) = U11_aga(x2, x4) U12_aga(x1, x2, x3, x4) = U12_aga(x2, x4) U13_aga(x1, x2, x3, x4) = U13_aga(x2, x4) U14_aga(x1, x2, x3, x4) = U14_aga(x2, x4) U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) ISMINUS_IN_GGA(x1, x2, x3) = ISMINUS_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (46) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (47) Obligation: Pi DP problem: The TRS P consists of the following rules: ISMINUS_IN_GGA(zero, pred(Y), succ(Z)) -> ISMINUS_IN_GGA(zero, Y, Z) ISMINUS_IN_GGA(zero, succ(Y), pred(Z)) -> ISMINUS_IN_GGA(zero, Y, Z) R is empty. The argument filtering Pi contains the following mapping: zero = zero succ(x1) = succ(x1) pred(x1) = pred(x1) ISMINUS_IN_GGA(x1, x2, x3) = ISMINUS_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (48) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (49) Obligation: Q DP problem: The TRS P consists of the following rules: ISMINUS_IN_GGA(zero, pred(Y)) -> ISMINUS_IN_GGA(zero, Y) ISMINUS_IN_GGA(zero, succ(Y)) -> ISMINUS_IN_GGA(zero, Y) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (50) 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: *ISMINUS_IN_GGA(zero, pred(Y)) -> ISMINUS_IN_GGA(zero, Y) The graph contains the following edges 1 >= 1, 2 > 2 *ISMINUS_IN_GGA(zero, succ(Y)) -> ISMINUS_IN_GGA(zero, Y) The graph contains the following edges 1 >= 1, 2 > 2 ---------------------------------------- (51) YES ---------------------------------------- (52) Obligation: Pi DP problem: The TRS P consists of the following rules: ISMINUS_IN_GGA(succ(X), pred(Y), succ(succ(Z))) -> ISMINUS_IN_GGA(X, Y, Z) ISMINUS_IN_GGA(succ(X), succ(Y), Z) -> ISMINUS_IN_GGA(X, Y, Z) ISMINUS_IN_GGA(pred(X), succ(Y), pred(pred(Z))) -> ISMINUS_IN_GGA(X, Y, Z) ISMINUS_IN_GGA(pred(X), pred(Y), Z) -> ISMINUS_IN_GGA(X, Y, Z) The TRS R consists of the following rules: get_in_aaa(.(X, XS), zero, Res) -> U1_aaa(X, XS, Res, =_in_aa(Res, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_aaa(X, XS, Res, =_out_aa(Res, X)) -> get_out_aaa(.(X, XS), zero, Res) get_in_aaa(.(X, XS), Y, Res) -> U2_aaa(X, XS, Y, Res, isMinus_in_aga(Y, succ(zero), U)) isMinus_in_aga(X, zero, X) -> isMinus_out_aga(X, zero, X) isMinus_in_aga(zero, succ(Y), pred(Z)) -> U9_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(X, zero, X) -> isMinus_out_gga(X, zero, X) isMinus_in_gga(zero, succ(Y), pred(Z)) -> U9_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(zero, pred(Y), succ(Z)) -> U10_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(succ(X), succ(Y), Z) -> U11_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(succ(X), pred(Y), succ(succ(Z))) -> U12_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), succ(Y), pred(pred(Z))) -> U13_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), pred(Y), Z) -> U14_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) U14_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), pred(Y), Z) U13_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), succ(Y), pred(pred(Z))) U12_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), pred(Y), succ(succ(Z))) U11_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), succ(Y), Z) U10_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, pred(Y), succ(Z)) U9_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, succ(Y), pred(Z)) U9_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, succ(Y), pred(Z)) isMinus_in_aga(zero, pred(Y), succ(Z)) -> U10_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) U10_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, pred(Y), succ(Z)) isMinus_in_aga(succ(X), succ(Y), Z) -> U11_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(succ(X), pred(Y), succ(succ(Z))) -> U12_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), succ(Y), pred(pred(Z))) -> U13_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), pred(Y), Z) -> U14_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) U14_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), pred(Y), Z) U13_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), succ(Y), pred(pred(Z))) U12_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), pred(Y), succ(succ(Z))) U11_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), succ(Y), Z) U2_aaa(X, XS, Y, Res, isMinus_out_aga(Y, succ(zero), U)) -> U3_aaa(X, XS, Y, Res, =_in_aa(YP, U)) U3_aaa(X, XS, Y, Res, =_out_aa(YP, U)) -> U4_aaa(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U4_aaa(X, XS, Y, Res, get_out_aaa(XS, YP, Res)) -> get_out_aaa(.(X, XS), Y, Res) The argument filtering Pi contains the following mapping: get_in_aaa(x1, x2, x3) = get_in_aaa U1_aaa(x1, x2, x3, x4) = U1_aaa(x4) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa get_out_aaa(x1, x2, x3) = get_out_aaa U2_aaa(x1, x2, x3, x4, x5) = U2_aaa(x5) isMinus_in_aga(x1, x2, x3) = isMinus_in_aga(x2) zero = zero isMinus_out_aga(x1, x2, x3) = isMinus_out_aga(x2) succ(x1) = succ(x1) U9_aga(x1, x2, x3) = U9_aga(x1, x3) isMinus_in_gga(x1, x2, x3) = isMinus_in_gga(x1, x2) isMinus_out_gga(x1, x2, x3) = isMinus_out_gga(x1, x2, x3) U9_gga(x1, x2, x3) = U9_gga(x1, x3) pred(x1) = pred(x1) U10_gga(x1, x2, x3) = U10_gga(x1, x3) U11_gga(x1, x2, x3, x4) = U11_gga(x1, x2, x4) U12_gga(x1, x2, x3, x4) = U12_gga(x1, x2, x4) U13_gga(x1, x2, x3, x4) = U13_gga(x1, x2, x4) U14_gga(x1, x2, x3, x4) = U14_gga(x1, x2, x4) U10_aga(x1, x2, x3) = U10_aga(x1, x3) U11_aga(x1, x2, x3, x4) = U11_aga(x2, x4) U12_aga(x1, x2, x3, x4) = U12_aga(x2, x4) U13_aga(x1, x2, x3, x4) = U13_aga(x2, x4) U14_aga(x1, x2, x3, x4) = U14_aga(x2, x4) U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) ISMINUS_IN_GGA(x1, x2, x3) = ISMINUS_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (53) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (54) Obligation: Pi DP problem: The TRS P consists of the following rules: ISMINUS_IN_GGA(succ(X), pred(Y), succ(succ(Z))) -> ISMINUS_IN_GGA(X, Y, Z) ISMINUS_IN_GGA(succ(X), succ(Y), Z) -> ISMINUS_IN_GGA(X, Y, Z) ISMINUS_IN_GGA(pred(X), succ(Y), pred(pred(Z))) -> ISMINUS_IN_GGA(X, Y, Z) ISMINUS_IN_GGA(pred(X), pred(Y), Z) -> ISMINUS_IN_GGA(X, Y, Z) R is empty. The argument filtering Pi contains the following mapping: succ(x1) = succ(x1) pred(x1) = pred(x1) ISMINUS_IN_GGA(x1, x2, x3) = ISMINUS_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (55) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (56) Obligation: Q DP problem: The TRS P consists of the following rules: ISMINUS_IN_GGA(succ(X), pred(Y)) -> ISMINUS_IN_GGA(X, Y) ISMINUS_IN_GGA(succ(X), succ(Y)) -> ISMINUS_IN_GGA(X, Y) ISMINUS_IN_GGA(pred(X), succ(Y)) -> ISMINUS_IN_GGA(X, Y) ISMINUS_IN_GGA(pred(X), pred(Y)) -> ISMINUS_IN_GGA(X, Y) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (57) 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: *ISMINUS_IN_GGA(succ(X), pred(Y)) -> ISMINUS_IN_GGA(X, Y) The graph contains the following edges 1 > 1, 2 > 2 *ISMINUS_IN_GGA(succ(X), succ(Y)) -> ISMINUS_IN_GGA(X, Y) The graph contains the following edges 1 > 1, 2 > 2 *ISMINUS_IN_GGA(pred(X), succ(Y)) -> ISMINUS_IN_GGA(X, Y) The graph contains the following edges 1 > 1, 2 > 2 *ISMINUS_IN_GGA(pred(X), pred(Y)) -> ISMINUS_IN_GGA(X, Y) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (58) YES ---------------------------------------- (59) Obligation: Pi DP problem: The TRS P consists of the following rules: ISMINUS_IN_AGA(succ(X), pred(Y), succ(succ(Z))) -> ISMINUS_IN_AGA(X, Y, Z) ISMINUS_IN_AGA(succ(X), succ(Y), Z) -> ISMINUS_IN_AGA(X, Y, Z) ISMINUS_IN_AGA(pred(X), succ(Y), pred(pred(Z))) -> ISMINUS_IN_AGA(X, Y, Z) ISMINUS_IN_AGA(pred(X), pred(Y), Z) -> ISMINUS_IN_AGA(X, Y, Z) The TRS R consists of the following rules: get_in_aaa(.(X, XS), zero, Res) -> U1_aaa(X, XS, Res, =_in_aa(Res, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_aaa(X, XS, Res, =_out_aa(Res, X)) -> get_out_aaa(.(X, XS), zero, Res) get_in_aaa(.(X, XS), Y, Res) -> U2_aaa(X, XS, Y, Res, isMinus_in_aga(Y, succ(zero), U)) isMinus_in_aga(X, zero, X) -> isMinus_out_aga(X, zero, X) isMinus_in_aga(zero, succ(Y), pred(Z)) -> U9_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(X, zero, X) -> isMinus_out_gga(X, zero, X) isMinus_in_gga(zero, succ(Y), pred(Z)) -> U9_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(zero, pred(Y), succ(Z)) -> U10_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(succ(X), succ(Y), Z) -> U11_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(succ(X), pred(Y), succ(succ(Z))) -> U12_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), succ(Y), pred(pred(Z))) -> U13_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), pred(Y), Z) -> U14_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) U14_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), pred(Y), Z) U13_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), succ(Y), pred(pred(Z))) U12_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), pred(Y), succ(succ(Z))) U11_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), succ(Y), Z) U10_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, pred(Y), succ(Z)) U9_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, succ(Y), pred(Z)) U9_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, succ(Y), pred(Z)) isMinus_in_aga(zero, pred(Y), succ(Z)) -> U10_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) U10_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, pred(Y), succ(Z)) isMinus_in_aga(succ(X), succ(Y), Z) -> U11_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(succ(X), pred(Y), succ(succ(Z))) -> U12_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), succ(Y), pred(pred(Z))) -> U13_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), pred(Y), Z) -> U14_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) U14_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), pred(Y), Z) U13_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), succ(Y), pred(pred(Z))) U12_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), pred(Y), succ(succ(Z))) U11_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), succ(Y), Z) U2_aaa(X, XS, Y, Res, isMinus_out_aga(Y, succ(zero), U)) -> U3_aaa(X, XS, Y, Res, =_in_aa(YP, U)) U3_aaa(X, XS, Y, Res, =_out_aa(YP, U)) -> U4_aaa(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U4_aaa(X, XS, Y, Res, get_out_aaa(XS, YP, Res)) -> get_out_aaa(.(X, XS), Y, Res) The argument filtering Pi contains the following mapping: get_in_aaa(x1, x2, x3) = get_in_aaa U1_aaa(x1, x2, x3, x4) = U1_aaa(x4) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa get_out_aaa(x1, x2, x3) = get_out_aaa U2_aaa(x1, x2, x3, x4, x5) = U2_aaa(x5) isMinus_in_aga(x1, x2, x3) = isMinus_in_aga(x2) zero = zero isMinus_out_aga(x1, x2, x3) = isMinus_out_aga(x2) succ(x1) = succ(x1) U9_aga(x1, x2, x3) = U9_aga(x1, x3) isMinus_in_gga(x1, x2, x3) = isMinus_in_gga(x1, x2) isMinus_out_gga(x1, x2, x3) = isMinus_out_gga(x1, x2, x3) U9_gga(x1, x2, x3) = U9_gga(x1, x3) pred(x1) = pred(x1) U10_gga(x1, x2, x3) = U10_gga(x1, x3) U11_gga(x1, x2, x3, x4) = U11_gga(x1, x2, x4) U12_gga(x1, x2, x3, x4) = U12_gga(x1, x2, x4) U13_gga(x1, x2, x3, x4) = U13_gga(x1, x2, x4) U14_gga(x1, x2, x3, x4) = U14_gga(x1, x2, x4) U10_aga(x1, x2, x3) = U10_aga(x1, x3) U11_aga(x1, x2, x3, x4) = U11_aga(x2, x4) U12_aga(x1, x2, x3, x4) = U12_aga(x2, x4) U13_aga(x1, x2, x3, x4) = U13_aga(x2, x4) U14_aga(x1, x2, x3, x4) = U14_aga(x2, x4) U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) ISMINUS_IN_AGA(x1, x2, x3) = ISMINUS_IN_AGA(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (60) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (61) Obligation: Pi DP problem: The TRS P consists of the following rules: ISMINUS_IN_AGA(succ(X), pred(Y), succ(succ(Z))) -> ISMINUS_IN_AGA(X, Y, Z) ISMINUS_IN_AGA(succ(X), succ(Y), Z) -> ISMINUS_IN_AGA(X, Y, Z) ISMINUS_IN_AGA(pred(X), succ(Y), pred(pred(Z))) -> ISMINUS_IN_AGA(X, Y, Z) ISMINUS_IN_AGA(pred(X), pred(Y), Z) -> ISMINUS_IN_AGA(X, Y, Z) R is empty. The argument filtering Pi contains the following mapping: succ(x1) = succ(x1) pred(x1) = pred(x1) ISMINUS_IN_AGA(x1, x2, x3) = ISMINUS_IN_AGA(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (62) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (63) Obligation: Q DP problem: The TRS P consists of the following rules: ISMINUS_IN_AGA(pred(Y)) -> ISMINUS_IN_AGA(Y) ISMINUS_IN_AGA(succ(Y)) -> ISMINUS_IN_AGA(Y) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (64) 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: *ISMINUS_IN_AGA(pred(Y)) -> ISMINUS_IN_AGA(Y) The graph contains the following edges 1 > 1 *ISMINUS_IN_AGA(succ(Y)) -> ISMINUS_IN_AGA(Y) The graph contains the following edges 1 > 1 ---------------------------------------- (65) YES ---------------------------------------- (66) Obligation: Pi DP problem: The TRS P consists of the following rules: GET_IN_AAA(.(X, XS), Y, Res) -> U2_AAA(X, XS, Y, Res, isMinus_in_aga(Y, succ(zero), U)) U2_AAA(X, XS, Y, Res, isMinus_out_aga(Y, succ(zero), U)) -> U3_AAA(X, XS, Y, Res, =_in_aa(YP, U)) U3_AAA(X, XS, Y, Res, =_out_aa(YP, U)) -> GET_IN_AAA(XS, YP, Res) The TRS R consists of the following rules: get_in_aaa(.(X, XS), zero, Res) -> U1_aaa(X, XS, Res, =_in_aa(Res, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_aaa(X, XS, Res, =_out_aa(Res, X)) -> get_out_aaa(.(X, XS), zero, Res) get_in_aaa(.(X, XS), Y, Res) -> U2_aaa(X, XS, Y, Res, isMinus_in_aga(Y, succ(zero), U)) isMinus_in_aga(X, zero, X) -> isMinus_out_aga(X, zero, X) isMinus_in_aga(zero, succ(Y), pred(Z)) -> U9_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(X, zero, X) -> isMinus_out_gga(X, zero, X) isMinus_in_gga(zero, succ(Y), pred(Z)) -> U9_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(zero, pred(Y), succ(Z)) -> U10_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(succ(X), succ(Y), Z) -> U11_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(succ(X), pred(Y), succ(succ(Z))) -> U12_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), succ(Y), pred(pred(Z))) -> U13_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) isMinus_in_gga(pred(X), pred(Y), Z) -> U14_gga(X, Y, Z, isMinus_in_gga(X, Y, Z)) U14_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), pred(Y), Z) U13_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(pred(X), succ(Y), pred(pred(Z))) U12_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), pred(Y), succ(succ(Z))) U11_gga(X, Y, Z, isMinus_out_gga(X, Y, Z)) -> isMinus_out_gga(succ(X), succ(Y), Z) U10_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, pred(Y), succ(Z)) U9_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, succ(Y), pred(Z)) U9_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, succ(Y), pred(Z)) isMinus_in_aga(zero, pred(Y), succ(Z)) -> U10_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) U10_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, pred(Y), succ(Z)) isMinus_in_aga(succ(X), succ(Y), Z) -> U11_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(succ(X), pred(Y), succ(succ(Z))) -> U12_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), succ(Y), pred(pred(Z))) -> U13_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), pred(Y), Z) -> U14_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) U14_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), pred(Y), Z) U13_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), succ(Y), pred(pred(Z))) U12_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), pred(Y), succ(succ(Z))) U11_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), succ(Y), Z) U2_aaa(X, XS, Y, Res, isMinus_out_aga(Y, succ(zero), U)) -> U3_aaa(X, XS, Y, Res, =_in_aa(YP, U)) U3_aaa(X, XS, Y, Res, =_out_aa(YP, U)) -> U4_aaa(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U4_aaa(X, XS, Y, Res, get_out_aaa(XS, YP, Res)) -> get_out_aaa(.(X, XS), Y, Res) The argument filtering Pi contains the following mapping: get_in_aaa(x1, x2, x3) = get_in_aaa U1_aaa(x1, x2, x3, x4) = U1_aaa(x4) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa get_out_aaa(x1, x2, x3) = get_out_aaa U2_aaa(x1, x2, x3, x4, x5) = U2_aaa(x5) isMinus_in_aga(x1, x2, x3) = isMinus_in_aga(x2) zero = zero isMinus_out_aga(x1, x2, x3) = isMinus_out_aga(x2) succ(x1) = succ(x1) U9_aga(x1, x2, x3) = U9_aga(x1, x3) isMinus_in_gga(x1, x2, x3) = isMinus_in_gga(x1, x2) isMinus_out_gga(x1, x2, x3) = isMinus_out_gga(x1, x2, x3) U9_gga(x1, x2, x3) = U9_gga(x1, x3) pred(x1) = pred(x1) U10_gga(x1, x2, x3) = U10_gga(x1, x3) U11_gga(x1, x2, x3, x4) = U11_gga(x1, x2, x4) U12_gga(x1, x2, x3, x4) = U12_gga(x1, x2, x4) U13_gga(x1, x2, x3, x4) = U13_gga(x1, x2, x4) U14_gga(x1, x2, x3, x4) = U14_gga(x1, x2, x4) U10_aga(x1, x2, x3) = U10_aga(x1, x3) U11_aga(x1, x2, x3, x4) = U11_aga(x2, x4) U12_aga(x1, x2, x3, x4) = U12_aga(x2, x4) U13_aga(x1, x2, x3, x4) = U13_aga(x2, x4) U14_aga(x1, x2, x3, x4) = U14_aga(x2, x4) U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) GET_IN_AAA(x1, x2, x3) = GET_IN_AAA U2_AAA(x1, x2, x3, x4, x5) = U2_AAA(x5) U3_AAA(x1, x2, x3, x4, x5) = U3_AAA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (67) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (68) Obligation: Pi DP problem: The TRS P consists of the following rules: GET_IN_AAA(.(X, XS), Y, Res) -> U2_AAA(X, XS, Y, Res, isMinus_in_aga(Y, succ(zero), U)) U2_AAA(X, XS, Y, Res, isMinus_out_aga(Y, succ(zero), U)) -> U3_AAA(X, XS, Y, Res, =_in_aa(YP, U)) U3_AAA(X, XS, Y, Res, =_out_aa(YP, U)) -> GET_IN_AAA(XS, YP, Res) The TRS R consists of the following rules: isMinus_in_aga(zero, succ(Y), pred(Z)) -> U9_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_aga(succ(X), succ(Y), Z) -> U11_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), succ(Y), pred(pred(Z))) -> U13_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) =_in_aa(X, X) -> =_out_aa(X, X) U9_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, succ(Y), pred(Z)) U11_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), succ(Y), Z) U13_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), succ(Y), pred(pred(Z))) isMinus_in_gga(X, zero, X) -> isMinus_out_gga(X, zero, X) isMinus_in_gga(zero, succ(Y), pred(Z)) -> U9_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_gga(zero, pred(Y), succ(Z)) -> U10_gga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_aga(X, zero, X) -> isMinus_out_aga(X, zero, X) isMinus_in_aga(zero, pred(Y), succ(Z)) -> U10_aga(Y, Z, isMinus_in_gga(zero, Y, Z)) isMinus_in_aga(succ(X), pred(Y), succ(succ(Z))) -> U12_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) isMinus_in_aga(pred(X), pred(Y), Z) -> U14_aga(X, Y, Z, isMinus_in_aga(X, Y, Z)) U9_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, succ(Y), pred(Z)) U10_gga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, pred(Y), succ(Z)) U10_aga(Y, Z, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(zero, pred(Y), succ(Z)) U12_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(succ(X), pred(Y), succ(succ(Z))) U14_aga(X, Y, Z, isMinus_out_aga(X, Y, Z)) -> isMinus_out_aga(pred(X), pred(Y), Z) The argument filtering Pi contains the following mapping: =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa isMinus_in_aga(x1, x2, x3) = isMinus_in_aga(x2) zero = zero isMinus_out_aga(x1, x2, x3) = isMinus_out_aga(x2) succ(x1) = succ(x1) U9_aga(x1, x2, x3) = U9_aga(x1, x3) isMinus_in_gga(x1, x2, x3) = isMinus_in_gga(x1, x2) isMinus_out_gga(x1, x2, x3) = isMinus_out_gga(x1, x2, x3) U9_gga(x1, x2, x3) = U9_gga(x1, x3) pred(x1) = pred(x1) U10_gga(x1, x2, x3) = U10_gga(x1, x3) U10_aga(x1, x2, x3) = U10_aga(x1, x3) U11_aga(x1, x2, x3, x4) = U11_aga(x2, x4) U12_aga(x1, x2, x3, x4) = U12_aga(x2, x4) U13_aga(x1, x2, x3, x4) = U13_aga(x2, x4) U14_aga(x1, x2, x3, x4) = U14_aga(x2, x4) GET_IN_AAA(x1, x2, x3) = GET_IN_AAA U2_AAA(x1, x2, x3, x4, x5) = U2_AAA(x5) U3_AAA(x1, x2, x3, x4, x5) = U3_AAA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (69) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (70) Obligation: Q DP problem: The TRS P consists of the following rules: GET_IN_AAA -> U2_AAA(isMinus_in_aga(succ(zero))) U2_AAA(isMinus_out_aga(succ(zero))) -> U3_AAA(=_in_aa) U3_AAA(=_out_aa) -> GET_IN_AAA The TRS R consists of the following rules: isMinus_in_aga(succ(Y)) -> U9_aga(Y, isMinus_in_gga(zero, Y)) isMinus_in_aga(succ(Y)) -> U11_aga(Y, isMinus_in_aga(Y)) isMinus_in_aga(succ(Y)) -> U13_aga(Y, isMinus_in_aga(Y)) =_in_aa -> =_out_aa U9_aga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(succ(Y)) U11_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(succ(Y)) U13_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(succ(Y)) isMinus_in_gga(X, zero) -> isMinus_out_gga(X, zero, X) isMinus_in_gga(zero, succ(Y)) -> U9_gga(Y, isMinus_in_gga(zero, Y)) isMinus_in_gga(zero, pred(Y)) -> U10_gga(Y, isMinus_in_gga(zero, Y)) isMinus_in_aga(zero) -> isMinus_out_aga(zero) isMinus_in_aga(pred(Y)) -> U10_aga(Y, isMinus_in_gga(zero, Y)) isMinus_in_aga(pred(Y)) -> U12_aga(Y, isMinus_in_aga(Y)) isMinus_in_aga(pred(Y)) -> U14_aga(Y, isMinus_in_aga(Y)) U9_gga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, succ(Y), pred(Z)) U10_gga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, pred(Y), succ(Z)) U10_aga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(pred(Y)) U12_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(pred(Y)) U14_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(pred(Y)) The set Q consists of the following terms: isMinus_in_aga(x0) =_in_aa U9_aga(x0, x1) U11_aga(x0, x1) U13_aga(x0, x1) isMinus_in_gga(x0, x1) U9_gga(x0, x1) U10_gga(x0, x1) U10_aga(x0, x1) U12_aga(x0, x1) U14_aga(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (71) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule U2_AAA(isMinus_out_aga(succ(zero))) -> U3_AAA(=_in_aa) at position [0] we obtained the following new rules [LPAR04]: (U2_AAA(isMinus_out_aga(succ(zero))) -> U3_AAA(=_out_aa),U2_AAA(isMinus_out_aga(succ(zero))) -> U3_AAA(=_out_aa)) ---------------------------------------- (72) Obligation: Q DP problem: The TRS P consists of the following rules: GET_IN_AAA -> U2_AAA(isMinus_in_aga(succ(zero))) U3_AAA(=_out_aa) -> GET_IN_AAA U2_AAA(isMinus_out_aga(succ(zero))) -> U3_AAA(=_out_aa) The TRS R consists of the following rules: isMinus_in_aga(succ(Y)) -> U9_aga(Y, isMinus_in_gga(zero, Y)) isMinus_in_aga(succ(Y)) -> U11_aga(Y, isMinus_in_aga(Y)) isMinus_in_aga(succ(Y)) -> U13_aga(Y, isMinus_in_aga(Y)) =_in_aa -> =_out_aa U9_aga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(succ(Y)) U11_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(succ(Y)) U13_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(succ(Y)) isMinus_in_gga(X, zero) -> isMinus_out_gga(X, zero, X) isMinus_in_gga(zero, succ(Y)) -> U9_gga(Y, isMinus_in_gga(zero, Y)) isMinus_in_gga(zero, pred(Y)) -> U10_gga(Y, isMinus_in_gga(zero, Y)) isMinus_in_aga(zero) -> isMinus_out_aga(zero) isMinus_in_aga(pred(Y)) -> U10_aga(Y, isMinus_in_gga(zero, Y)) isMinus_in_aga(pred(Y)) -> U12_aga(Y, isMinus_in_aga(Y)) isMinus_in_aga(pred(Y)) -> U14_aga(Y, isMinus_in_aga(Y)) U9_gga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, succ(Y), pred(Z)) U10_gga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, pred(Y), succ(Z)) U10_aga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(pred(Y)) U12_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(pred(Y)) U14_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(pred(Y)) The set Q consists of the following terms: isMinus_in_aga(x0) =_in_aa U9_aga(x0, x1) U11_aga(x0, x1) U13_aga(x0, x1) isMinus_in_gga(x0, x1) U9_gga(x0, x1) U10_gga(x0, x1) U10_aga(x0, x1) U12_aga(x0, x1) U14_aga(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (73) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (74) Obligation: Q DP problem: The TRS P consists of the following rules: GET_IN_AAA -> U2_AAA(isMinus_in_aga(succ(zero))) U3_AAA(=_out_aa) -> GET_IN_AAA U2_AAA(isMinus_out_aga(succ(zero))) -> U3_AAA(=_out_aa) The TRS R consists of the following rules: isMinus_in_aga(succ(Y)) -> U9_aga(Y, isMinus_in_gga(zero, Y)) isMinus_in_aga(succ(Y)) -> U11_aga(Y, isMinus_in_aga(Y)) isMinus_in_aga(succ(Y)) -> U13_aga(Y, isMinus_in_aga(Y)) isMinus_in_aga(zero) -> isMinus_out_aga(zero) isMinus_in_aga(pred(Y)) -> U10_aga(Y, isMinus_in_gga(zero, Y)) isMinus_in_aga(pred(Y)) -> U12_aga(Y, isMinus_in_aga(Y)) isMinus_in_aga(pred(Y)) -> U14_aga(Y, isMinus_in_aga(Y)) U13_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(succ(Y)) U14_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(pred(Y)) U12_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(pred(Y)) isMinus_in_gga(X, zero) -> isMinus_out_gga(X, zero, X) isMinus_in_gga(zero, succ(Y)) -> U9_gga(Y, isMinus_in_gga(zero, Y)) isMinus_in_gga(zero, pred(Y)) -> U10_gga(Y, isMinus_in_gga(zero, Y)) U10_aga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(pred(Y)) U10_gga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, pred(Y), succ(Z)) U9_gga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, succ(Y), pred(Z)) U11_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(succ(Y)) U9_aga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(succ(Y)) The set Q consists of the following terms: isMinus_in_aga(x0) =_in_aa U9_aga(x0, x1) U11_aga(x0, x1) U13_aga(x0, x1) isMinus_in_gga(x0, x1) U9_gga(x0, x1) U10_gga(x0, x1) U10_aga(x0, x1) U12_aga(x0, x1) U14_aga(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (75) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. =_in_aa ---------------------------------------- (76) Obligation: Q DP problem: The TRS P consists of the following rules: GET_IN_AAA -> U2_AAA(isMinus_in_aga(succ(zero))) U3_AAA(=_out_aa) -> GET_IN_AAA U2_AAA(isMinus_out_aga(succ(zero))) -> U3_AAA(=_out_aa) The TRS R consists of the following rules: isMinus_in_aga(succ(Y)) -> U9_aga(Y, isMinus_in_gga(zero, Y)) isMinus_in_aga(succ(Y)) -> U11_aga(Y, isMinus_in_aga(Y)) isMinus_in_aga(succ(Y)) -> U13_aga(Y, isMinus_in_aga(Y)) isMinus_in_aga(zero) -> isMinus_out_aga(zero) isMinus_in_aga(pred(Y)) -> U10_aga(Y, isMinus_in_gga(zero, Y)) isMinus_in_aga(pred(Y)) -> U12_aga(Y, isMinus_in_aga(Y)) isMinus_in_aga(pred(Y)) -> U14_aga(Y, isMinus_in_aga(Y)) U13_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(succ(Y)) U14_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(pred(Y)) U12_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(pred(Y)) isMinus_in_gga(X, zero) -> isMinus_out_gga(X, zero, X) isMinus_in_gga(zero, succ(Y)) -> U9_gga(Y, isMinus_in_gga(zero, Y)) isMinus_in_gga(zero, pred(Y)) -> U10_gga(Y, isMinus_in_gga(zero, Y)) U10_aga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(pred(Y)) U10_gga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, pred(Y), succ(Z)) U9_gga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, succ(Y), pred(Z)) U11_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(succ(Y)) U9_aga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(succ(Y)) The set Q consists of the following terms: isMinus_in_aga(x0) U9_aga(x0, x1) U11_aga(x0, x1) U13_aga(x0, x1) isMinus_in_gga(x0, x1) U9_gga(x0, x1) U10_gga(x0, x1) U10_aga(x0, x1) U12_aga(x0, x1) U14_aga(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (77) 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 rules of the TRS R: isMinus_in_aga(pred(Y)) -> U10_aga(Y, isMinus_in_gga(zero, Y)) isMinus_in_aga(pred(Y)) -> U12_aga(Y, isMinus_in_aga(Y)) isMinus_in_aga(pred(Y)) -> U14_aga(Y, isMinus_in_aga(Y)) U14_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(pred(Y)) U12_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(pred(Y)) Used ordering: Polynomial interpretation [POLO]: POL(=_out_aa) = 1 POL(GET_IN_AAA) = 0 POL(U10_aga(x_1, x_2)) = 0 POL(U10_gga(x_1, x_2)) = 0 POL(U11_aga(x_1, x_2)) = x_2 POL(U12_aga(x_1, x_2)) = 1 + x_2 POL(U13_aga(x_1, x_2)) = x_2 POL(U14_aga(x_1, x_2)) = 1 + 2*x_2 POL(U2_AAA(x_1)) = 2*x_1 POL(U3_AAA(x_1)) = 0 POL(U9_aga(x_1, x_2)) = 0 POL(U9_gga(x_1, x_2)) = 0 POL(isMinus_in_aga(x_1)) = 2*x_1 POL(isMinus_in_gga(x_1, x_2)) = 0 POL(isMinus_out_aga(x_1)) = 0 POL(isMinus_out_gga(x_1, x_2, x_3)) = 0 POL(pred(x_1)) = 1 + 2*x_1 POL(succ(x_1)) = x_1 POL(zero) = 0 ---------------------------------------- (78) Obligation: Q DP problem: The TRS P consists of the following rules: GET_IN_AAA -> U2_AAA(isMinus_in_aga(succ(zero))) U3_AAA(=_out_aa) -> GET_IN_AAA U2_AAA(isMinus_out_aga(succ(zero))) -> U3_AAA(=_out_aa) The TRS R consists of the following rules: isMinus_in_aga(succ(Y)) -> U9_aga(Y, isMinus_in_gga(zero, Y)) isMinus_in_aga(succ(Y)) -> U11_aga(Y, isMinus_in_aga(Y)) isMinus_in_aga(succ(Y)) -> U13_aga(Y, isMinus_in_aga(Y)) isMinus_in_aga(zero) -> isMinus_out_aga(zero) U13_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(succ(Y)) isMinus_in_gga(X, zero) -> isMinus_out_gga(X, zero, X) isMinus_in_gga(zero, succ(Y)) -> U9_gga(Y, isMinus_in_gga(zero, Y)) isMinus_in_gga(zero, pred(Y)) -> U10_gga(Y, isMinus_in_gga(zero, Y)) U10_aga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(pred(Y)) U10_gga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, pred(Y), succ(Z)) U9_gga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, succ(Y), pred(Z)) U11_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(succ(Y)) U9_aga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(succ(Y)) The set Q consists of the following terms: isMinus_in_aga(x0) U9_aga(x0, x1) U11_aga(x0, x1) U13_aga(x0, x1) isMinus_in_gga(x0, x1) U9_gga(x0, x1) U10_gga(x0, x1) U10_aga(x0, x1) U12_aga(x0, x1) U14_aga(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (79) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (80) Obligation: Q DP problem: The TRS P consists of the following rules: GET_IN_AAA -> U2_AAA(isMinus_in_aga(succ(zero))) U3_AAA(=_out_aa) -> GET_IN_AAA U2_AAA(isMinus_out_aga(succ(zero))) -> U3_AAA(=_out_aa) The TRS R consists of the following rules: isMinus_in_aga(succ(Y)) -> U9_aga(Y, isMinus_in_gga(zero, Y)) isMinus_in_aga(succ(Y)) -> U11_aga(Y, isMinus_in_aga(Y)) isMinus_in_aga(succ(Y)) -> U13_aga(Y, isMinus_in_aga(Y)) isMinus_in_aga(zero) -> isMinus_out_aga(zero) U13_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(succ(Y)) U11_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(succ(Y)) isMinus_in_gga(X, zero) -> isMinus_out_gga(X, zero, X) isMinus_in_gga(zero, succ(Y)) -> U9_gga(Y, isMinus_in_gga(zero, Y)) isMinus_in_gga(zero, pred(Y)) -> U10_gga(Y, isMinus_in_gga(zero, Y)) U9_aga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(succ(Y)) U10_gga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, pred(Y), succ(Z)) U9_gga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, succ(Y), pred(Z)) The set Q consists of the following terms: isMinus_in_aga(x0) U9_aga(x0, x1) U11_aga(x0, x1) U13_aga(x0, x1) isMinus_in_gga(x0, x1) U9_gga(x0, x1) U10_gga(x0, x1) U10_aga(x0, x1) U12_aga(x0, x1) U14_aga(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (81) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. U10_aga(x0, x1) U12_aga(x0, x1) U14_aga(x0, x1) ---------------------------------------- (82) Obligation: Q DP problem: The TRS P consists of the following rules: GET_IN_AAA -> U2_AAA(isMinus_in_aga(succ(zero))) U3_AAA(=_out_aa) -> GET_IN_AAA U2_AAA(isMinus_out_aga(succ(zero))) -> U3_AAA(=_out_aa) The TRS R consists of the following rules: isMinus_in_aga(succ(Y)) -> U9_aga(Y, isMinus_in_gga(zero, Y)) isMinus_in_aga(succ(Y)) -> U11_aga(Y, isMinus_in_aga(Y)) isMinus_in_aga(succ(Y)) -> U13_aga(Y, isMinus_in_aga(Y)) isMinus_in_aga(zero) -> isMinus_out_aga(zero) U13_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(succ(Y)) U11_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(succ(Y)) isMinus_in_gga(X, zero) -> isMinus_out_gga(X, zero, X) isMinus_in_gga(zero, succ(Y)) -> U9_gga(Y, isMinus_in_gga(zero, Y)) isMinus_in_gga(zero, pred(Y)) -> U10_gga(Y, isMinus_in_gga(zero, Y)) U9_aga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(succ(Y)) U10_gga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, pred(Y), succ(Z)) U9_gga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, succ(Y), pred(Z)) The set Q consists of the following terms: isMinus_in_aga(x0) U9_aga(x0, x1) U11_aga(x0, x1) U13_aga(x0, x1) isMinus_in_gga(x0, x1) U9_gga(x0, x1) U10_gga(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (83) 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 rules of the TRS R: isMinus_in_gga(zero, pred(Y)) -> U10_gga(Y, isMinus_in_gga(zero, Y)) Used ordering: Polynomial interpretation [POLO]: POL(=_out_aa) = 0 POL(GET_IN_AAA) = 0 POL(U10_gga(x_1, x_2)) = 2*x_2 POL(U11_aga(x_1, x_2)) = x_2 POL(U13_aga(x_1, x_2)) = x_2 POL(U2_AAA(x_1)) = 2*x_1 POL(U3_AAA(x_1)) = 2*x_1 POL(U9_aga(x_1, x_2)) = 2*x_2 POL(U9_gga(x_1, x_2)) = x_2 POL(isMinus_in_aga(x_1)) = 2*x_1 POL(isMinus_in_gga(x_1, x_2)) = x_2 POL(isMinus_out_aga(x_1)) = 0 POL(isMinus_out_gga(x_1, x_2, x_3)) = 0 POL(pred(x_1)) = 2 + 2*x_1 POL(succ(x_1)) = x_1 POL(zero) = 0 ---------------------------------------- (84) Obligation: Q DP problem: The TRS P consists of the following rules: GET_IN_AAA -> U2_AAA(isMinus_in_aga(succ(zero))) U3_AAA(=_out_aa) -> GET_IN_AAA U2_AAA(isMinus_out_aga(succ(zero))) -> U3_AAA(=_out_aa) The TRS R consists of the following rules: isMinus_in_aga(succ(Y)) -> U9_aga(Y, isMinus_in_gga(zero, Y)) isMinus_in_aga(succ(Y)) -> U11_aga(Y, isMinus_in_aga(Y)) isMinus_in_aga(succ(Y)) -> U13_aga(Y, isMinus_in_aga(Y)) isMinus_in_aga(zero) -> isMinus_out_aga(zero) U13_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(succ(Y)) U11_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(succ(Y)) isMinus_in_gga(X, zero) -> isMinus_out_gga(X, zero, X) isMinus_in_gga(zero, succ(Y)) -> U9_gga(Y, isMinus_in_gga(zero, Y)) U9_aga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(succ(Y)) U10_gga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, pred(Y), succ(Z)) U9_gga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, succ(Y), pred(Z)) The set Q consists of the following terms: isMinus_in_aga(x0) U9_aga(x0, x1) U11_aga(x0, x1) U13_aga(x0, x1) isMinus_in_gga(x0, x1) U9_gga(x0, x1) U10_gga(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (85) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (86) Obligation: Q DP problem: The TRS P consists of the following rules: GET_IN_AAA -> U2_AAA(isMinus_in_aga(succ(zero))) U3_AAA(=_out_aa) -> GET_IN_AAA U2_AAA(isMinus_out_aga(succ(zero))) -> U3_AAA(=_out_aa) The TRS R consists of the following rules: isMinus_in_aga(succ(Y)) -> U9_aga(Y, isMinus_in_gga(zero, Y)) isMinus_in_aga(succ(Y)) -> U11_aga(Y, isMinus_in_aga(Y)) isMinus_in_aga(succ(Y)) -> U13_aga(Y, isMinus_in_aga(Y)) isMinus_in_aga(zero) -> isMinus_out_aga(zero) U13_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(succ(Y)) U11_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(succ(Y)) isMinus_in_gga(X, zero) -> isMinus_out_gga(X, zero, X) isMinus_in_gga(zero, succ(Y)) -> U9_gga(Y, isMinus_in_gga(zero, Y)) U9_aga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(succ(Y)) U9_gga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, succ(Y), pred(Z)) The set Q consists of the following terms: isMinus_in_aga(x0) U9_aga(x0, x1) U11_aga(x0, x1) U13_aga(x0, x1) isMinus_in_gga(x0, x1) U9_gga(x0, x1) U10_gga(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (87) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. U10_gga(x0, x1) ---------------------------------------- (88) Obligation: Q DP problem: The TRS P consists of the following rules: GET_IN_AAA -> U2_AAA(isMinus_in_aga(succ(zero))) U3_AAA(=_out_aa) -> GET_IN_AAA U2_AAA(isMinus_out_aga(succ(zero))) -> U3_AAA(=_out_aa) The TRS R consists of the following rules: isMinus_in_aga(succ(Y)) -> U9_aga(Y, isMinus_in_gga(zero, Y)) isMinus_in_aga(succ(Y)) -> U11_aga(Y, isMinus_in_aga(Y)) isMinus_in_aga(succ(Y)) -> U13_aga(Y, isMinus_in_aga(Y)) isMinus_in_aga(zero) -> isMinus_out_aga(zero) U13_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(succ(Y)) U11_aga(Y, isMinus_out_aga(Y)) -> isMinus_out_aga(succ(Y)) isMinus_in_gga(X, zero) -> isMinus_out_gga(X, zero, X) isMinus_in_gga(zero, succ(Y)) -> U9_gga(Y, isMinus_in_gga(zero, Y)) U9_aga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_aga(succ(Y)) U9_gga(Y, isMinus_out_gga(zero, Y, Z)) -> isMinus_out_gga(zero, succ(Y), pred(Z)) The set Q consists of the following terms: isMinus_in_aga(x0) U9_aga(x0, x1) U11_aga(x0, x1) U13_aga(x0, x1) isMinus_in_gga(x0, x1) U9_gga(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (89) CutEliminatorProof (SOUND) Eliminated all cuts by simply ignoring them[PROLOG]. ---------------------------------------- (90) Obligation: Clauses: get(.(X, XS), 0, Res) :- =(Res, X). get(.(X, XS), Y, Res) :- ','(is(YP, -(Y, 1)), get(XS, YP, Res)). Query: get(a,a,a) ---------------------------------------- (91) UnifyTransformerProof (EQUIVALENT) Added a fact for the built-in = predicate [PROLOG]. ---------------------------------------- (92) Obligation: Clauses: get(.(X, XS), 0, Res) :- =(Res, X). get(.(X, XS), Y, Res) :- ','(is(YP, -(Y, 1)), get(XS, YP, Res)). =(X, X). Query: get(a,a,a) ---------------------------------------- (93) UndefinedPredicateHandlerProof (SOUND) Added facts for all undefined predicates [PROLOG]. ---------------------------------------- (94) Obligation: Clauses: get(.(X, XS), 0, Res) :- =(Res, X). get(.(X, XS), Y, Res) :- ','(is(YP, -(Y, 1)), get(XS, YP, Res)). =(X, X). is(X0, X1). Query: get(a,a,a) ---------------------------------------- (95) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: get_in_3: (f,f,f) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: get_in_aaa(.(X, XS), 0, Res) -> U1_aaa(X, XS, Res, =_in_aa(Res, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_aaa(X, XS, Res, =_out_aa(Res, X)) -> get_out_aaa(.(X, XS), 0, Res) get_in_aaa(.(X, XS), Y, Res) -> U2_aaa(X, XS, Y, Res, is_in_ag(YP, -(Y, 1))) is_in_ag(X0, X1) -> is_out_ag(X0, X1) U2_aaa(X, XS, Y, Res, is_out_ag(YP, -(Y, 1))) -> U3_aaa(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U3_aaa(X, XS, Y, Res, get_out_aaa(XS, YP, Res)) -> get_out_aaa(.(X, XS), Y, Res) The argument filtering Pi contains the following mapping: get_in_aaa(x1, x2, x3) = get_in_aaa U1_aaa(x1, x2, x3, x4) = U1_aaa(x4) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa get_out_aaa(x1, x2, x3) = get_out_aaa .(x1, x2) = .(x2) U2_aaa(x1, x2, x3, x4, x5) = U2_aaa(x5) is_in_ag(x1, x2) = is_in_ag(x2) -(x1, x2) = -(x2) is_out_ag(x1, x2) = is_out_ag(x2) 1 = 1 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (96) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: get_in_aaa(.(X, XS), 0, Res) -> U1_aaa(X, XS, Res, =_in_aa(Res, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_aaa(X, XS, Res, =_out_aa(Res, X)) -> get_out_aaa(.(X, XS), 0, Res) get_in_aaa(.(X, XS), Y, Res) -> U2_aaa(X, XS, Y, Res, is_in_ag(YP, -(Y, 1))) is_in_ag(X0, X1) -> is_out_ag(X0, X1) U2_aaa(X, XS, Y, Res, is_out_ag(YP, -(Y, 1))) -> U3_aaa(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U3_aaa(X, XS, Y, Res, get_out_aaa(XS, YP, Res)) -> get_out_aaa(.(X, XS), Y, Res) The argument filtering Pi contains the following mapping: get_in_aaa(x1, x2, x3) = get_in_aaa U1_aaa(x1, x2, x3, x4) = U1_aaa(x4) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa get_out_aaa(x1, x2, x3) = get_out_aaa .(x1, x2) = .(x2) U2_aaa(x1, x2, x3, x4, x5) = U2_aaa(x5) is_in_ag(x1, x2) = is_in_ag(x2) -(x1, x2) = -(x2) is_out_ag(x1, x2) = is_out_ag(x2) 1 = 1 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) ---------------------------------------- (97) 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: GET_IN_AAA(.(X, XS), 0, Res) -> U1_AAA(X, XS, Res, =_in_aa(Res, X)) GET_IN_AAA(.(X, XS), 0, Res) -> =_IN_AA(Res, X) GET_IN_AAA(.(X, XS), Y, Res) -> U2_AAA(X, XS, Y, Res, is_in_ag(YP, -(Y, 1))) GET_IN_AAA(.(X, XS), Y, Res) -> IS_IN_AG(YP, -(Y, 1)) U2_AAA(X, XS, Y, Res, is_out_ag(YP, -(Y, 1))) -> U3_AAA(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U2_AAA(X, XS, Y, Res, is_out_ag(YP, -(Y, 1))) -> GET_IN_AAA(XS, YP, Res) The TRS R consists of the following rules: get_in_aaa(.(X, XS), 0, Res) -> U1_aaa(X, XS, Res, =_in_aa(Res, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_aaa(X, XS, Res, =_out_aa(Res, X)) -> get_out_aaa(.(X, XS), 0, Res) get_in_aaa(.(X, XS), Y, Res) -> U2_aaa(X, XS, Y, Res, is_in_ag(YP, -(Y, 1))) is_in_ag(X0, X1) -> is_out_ag(X0, X1) U2_aaa(X, XS, Y, Res, is_out_ag(YP, -(Y, 1))) -> U3_aaa(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U3_aaa(X, XS, Y, Res, get_out_aaa(XS, YP, Res)) -> get_out_aaa(.(X, XS), Y, Res) The argument filtering Pi contains the following mapping: get_in_aaa(x1, x2, x3) = get_in_aaa U1_aaa(x1, x2, x3, x4) = U1_aaa(x4) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa get_out_aaa(x1, x2, x3) = get_out_aaa .(x1, x2) = .(x2) U2_aaa(x1, x2, x3, x4, x5) = U2_aaa(x5) is_in_ag(x1, x2) = is_in_ag(x2) -(x1, x2) = -(x2) is_out_ag(x1, x2) = is_out_ag(x2) 1 = 1 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) GET_IN_AAA(x1, x2, x3) = GET_IN_AAA U1_AAA(x1, x2, x3, x4) = U1_AAA(x4) =_IN_AA(x1, x2) = =_IN_AA U2_AAA(x1, x2, x3, x4, x5) = U2_AAA(x5) IS_IN_AG(x1, x2) = IS_IN_AG(x2) U3_AAA(x1, x2, x3, x4, x5) = U3_AAA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (98) Obligation: Pi DP problem: The TRS P consists of the following rules: GET_IN_AAA(.(X, XS), 0, Res) -> U1_AAA(X, XS, Res, =_in_aa(Res, X)) GET_IN_AAA(.(X, XS), 0, Res) -> =_IN_AA(Res, X) GET_IN_AAA(.(X, XS), Y, Res) -> U2_AAA(X, XS, Y, Res, is_in_ag(YP, -(Y, 1))) GET_IN_AAA(.(X, XS), Y, Res) -> IS_IN_AG(YP, -(Y, 1)) U2_AAA(X, XS, Y, Res, is_out_ag(YP, -(Y, 1))) -> U3_AAA(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U2_AAA(X, XS, Y, Res, is_out_ag(YP, -(Y, 1))) -> GET_IN_AAA(XS, YP, Res) The TRS R consists of the following rules: get_in_aaa(.(X, XS), 0, Res) -> U1_aaa(X, XS, Res, =_in_aa(Res, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_aaa(X, XS, Res, =_out_aa(Res, X)) -> get_out_aaa(.(X, XS), 0, Res) get_in_aaa(.(X, XS), Y, Res) -> U2_aaa(X, XS, Y, Res, is_in_ag(YP, -(Y, 1))) is_in_ag(X0, X1) -> is_out_ag(X0, X1) U2_aaa(X, XS, Y, Res, is_out_ag(YP, -(Y, 1))) -> U3_aaa(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U3_aaa(X, XS, Y, Res, get_out_aaa(XS, YP, Res)) -> get_out_aaa(.(X, XS), Y, Res) The argument filtering Pi contains the following mapping: get_in_aaa(x1, x2, x3) = get_in_aaa U1_aaa(x1, x2, x3, x4) = U1_aaa(x4) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa get_out_aaa(x1, x2, x3) = get_out_aaa .(x1, x2) = .(x2) U2_aaa(x1, x2, x3, x4, x5) = U2_aaa(x5) is_in_ag(x1, x2) = is_in_ag(x2) -(x1, x2) = -(x2) is_out_ag(x1, x2) = is_out_ag(x2) 1 = 1 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) GET_IN_AAA(x1, x2, x3) = GET_IN_AAA U1_AAA(x1, x2, x3, x4) = U1_AAA(x4) =_IN_AA(x1, x2) = =_IN_AA U2_AAA(x1, x2, x3, x4, x5) = U2_AAA(x5) IS_IN_AG(x1, x2) = IS_IN_AG(x2) U3_AAA(x1, x2, x3, x4, x5) = U3_AAA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (99) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 4 less nodes. ---------------------------------------- (100) Obligation: Pi DP problem: The TRS P consists of the following rules: GET_IN_AAA(.(X, XS), Y, Res) -> U2_AAA(X, XS, Y, Res, is_in_ag(YP, -(Y, 1))) U2_AAA(X, XS, Y, Res, is_out_ag(YP, -(Y, 1))) -> GET_IN_AAA(XS, YP, Res) The TRS R consists of the following rules: get_in_aaa(.(X, XS), 0, Res) -> U1_aaa(X, XS, Res, =_in_aa(Res, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_aaa(X, XS, Res, =_out_aa(Res, X)) -> get_out_aaa(.(X, XS), 0, Res) get_in_aaa(.(X, XS), Y, Res) -> U2_aaa(X, XS, Y, Res, is_in_ag(YP, -(Y, 1))) is_in_ag(X0, X1) -> is_out_ag(X0, X1) U2_aaa(X, XS, Y, Res, is_out_ag(YP, -(Y, 1))) -> U3_aaa(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U3_aaa(X, XS, Y, Res, get_out_aaa(XS, YP, Res)) -> get_out_aaa(.(X, XS), Y, Res) The argument filtering Pi contains the following mapping: get_in_aaa(x1, x2, x3) = get_in_aaa U1_aaa(x1, x2, x3, x4) = U1_aaa(x4) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa get_out_aaa(x1, x2, x3) = get_out_aaa .(x1, x2) = .(x2) U2_aaa(x1, x2, x3, x4, x5) = U2_aaa(x5) is_in_ag(x1, x2) = is_in_ag(x2) -(x1, x2) = -(x2) is_out_ag(x1, x2) = is_out_ag(x2) 1 = 1 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) GET_IN_AAA(x1, x2, x3) = GET_IN_AAA U2_AAA(x1, x2, x3, x4, x5) = U2_AAA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (101) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (102) Obligation: Pi DP problem: The TRS P consists of the following rules: GET_IN_AAA(.(X, XS), Y, Res) -> U2_AAA(X, XS, Y, Res, is_in_ag(YP, -(Y, 1))) U2_AAA(X, XS, Y, Res, is_out_ag(YP, -(Y, 1))) -> GET_IN_AAA(XS, YP, Res) The TRS R consists of the following rules: is_in_ag(X0, X1) -> is_out_ag(X0, X1) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) is_in_ag(x1, x2) = is_in_ag(x2) -(x1, x2) = -(x2) is_out_ag(x1, x2) = is_out_ag(x2) 1 = 1 GET_IN_AAA(x1, x2, x3) = GET_IN_AAA U2_AAA(x1, x2, x3, x4, x5) = U2_AAA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (103) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (104) Obligation: Q DP problem: The TRS P consists of the following rules: GET_IN_AAA -> U2_AAA(is_in_ag(-(1))) U2_AAA(is_out_ag(-(1))) -> GET_IN_AAA The TRS R consists of the following rules: is_in_ag(X1) -> is_out_ag(X1) The set Q consists of the following terms: is_in_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (105) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule GET_IN_AAA -> U2_AAA(is_in_ag(-(1))) at position [0] we obtained the following new rules [LPAR04]: (GET_IN_AAA -> U2_AAA(is_out_ag(-(1))),GET_IN_AAA -> U2_AAA(is_out_ag(-(1)))) ---------------------------------------- (106) Obligation: Q DP problem: The TRS P consists of the following rules: U2_AAA(is_out_ag(-(1))) -> GET_IN_AAA GET_IN_AAA -> U2_AAA(is_out_ag(-(1))) The TRS R consists of the following rules: is_in_ag(X1) -> is_out_ag(X1) The set Q consists of the following terms: is_in_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (107) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (108) Obligation: Q DP problem: The TRS P consists of the following rules: U2_AAA(is_out_ag(-(1))) -> GET_IN_AAA GET_IN_AAA -> U2_AAA(is_out_ag(-(1))) R is empty. The set Q consists of the following terms: is_in_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (109) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. is_in_ag(x0) ---------------------------------------- (110) Obligation: Q DP problem: The TRS P consists of the following rules: U2_AAA(is_out_ag(-(1))) -> GET_IN_AAA GET_IN_AAA -> U2_AAA(is_out_ag(-(1))) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (111) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: get_in_3: (f,f,f) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: get_in_aaa(.(X, XS), 0, Res) -> U1_aaa(X, XS, Res, =_in_aa(Res, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_aaa(X, XS, Res, =_out_aa(Res, X)) -> get_out_aaa(.(X, XS), 0, Res) get_in_aaa(.(X, XS), Y, Res) -> U2_aaa(X, XS, Y, Res, is_in_ag(YP, -(Y, 1))) is_in_ag(X0, X1) -> is_out_ag(X0, X1) U2_aaa(X, XS, Y, Res, is_out_ag(YP, -(Y, 1))) -> U3_aaa(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U3_aaa(X, XS, Y, Res, get_out_aaa(XS, YP, Res)) -> get_out_aaa(.(X, XS), Y, Res) The argument filtering Pi contains the following mapping: get_in_aaa(x1, x2, x3) = get_in_aaa U1_aaa(x1, x2, x3, x4) = U1_aaa(x4) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa get_out_aaa(x1, x2, x3) = get_out_aaa .(x1, x2) = .(x2) U2_aaa(x1, x2, x3, x4, x5) = U2_aaa(x5) is_in_ag(x1, x2) = is_in_ag(x2) -(x1, x2) = -(x2) is_out_ag(x1, x2) = is_out_ag 1 = 1 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (112) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: get_in_aaa(.(X, XS), 0, Res) -> U1_aaa(X, XS, Res, =_in_aa(Res, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_aaa(X, XS, Res, =_out_aa(Res, X)) -> get_out_aaa(.(X, XS), 0, Res) get_in_aaa(.(X, XS), Y, Res) -> U2_aaa(X, XS, Y, Res, is_in_ag(YP, -(Y, 1))) is_in_ag(X0, X1) -> is_out_ag(X0, X1) U2_aaa(X, XS, Y, Res, is_out_ag(YP, -(Y, 1))) -> U3_aaa(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U3_aaa(X, XS, Y, Res, get_out_aaa(XS, YP, Res)) -> get_out_aaa(.(X, XS), Y, Res) The argument filtering Pi contains the following mapping: get_in_aaa(x1, x2, x3) = get_in_aaa U1_aaa(x1, x2, x3, x4) = U1_aaa(x4) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa get_out_aaa(x1, x2, x3) = get_out_aaa .(x1, x2) = .(x2) U2_aaa(x1, x2, x3, x4, x5) = U2_aaa(x5) is_in_ag(x1, x2) = is_in_ag(x2) -(x1, x2) = -(x2) is_out_ag(x1, x2) = is_out_ag 1 = 1 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) ---------------------------------------- (113) 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: GET_IN_AAA(.(X, XS), 0, Res) -> U1_AAA(X, XS, Res, =_in_aa(Res, X)) GET_IN_AAA(.(X, XS), 0, Res) -> =_IN_AA(Res, X) GET_IN_AAA(.(X, XS), Y, Res) -> U2_AAA(X, XS, Y, Res, is_in_ag(YP, -(Y, 1))) GET_IN_AAA(.(X, XS), Y, Res) -> IS_IN_AG(YP, -(Y, 1)) U2_AAA(X, XS, Y, Res, is_out_ag(YP, -(Y, 1))) -> U3_AAA(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U2_AAA(X, XS, Y, Res, is_out_ag(YP, -(Y, 1))) -> GET_IN_AAA(XS, YP, Res) The TRS R consists of the following rules: get_in_aaa(.(X, XS), 0, Res) -> U1_aaa(X, XS, Res, =_in_aa(Res, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_aaa(X, XS, Res, =_out_aa(Res, X)) -> get_out_aaa(.(X, XS), 0, Res) get_in_aaa(.(X, XS), Y, Res) -> U2_aaa(X, XS, Y, Res, is_in_ag(YP, -(Y, 1))) is_in_ag(X0, X1) -> is_out_ag(X0, X1) U2_aaa(X, XS, Y, Res, is_out_ag(YP, -(Y, 1))) -> U3_aaa(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U3_aaa(X, XS, Y, Res, get_out_aaa(XS, YP, Res)) -> get_out_aaa(.(X, XS), Y, Res) The argument filtering Pi contains the following mapping: get_in_aaa(x1, x2, x3) = get_in_aaa U1_aaa(x1, x2, x3, x4) = U1_aaa(x4) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa get_out_aaa(x1, x2, x3) = get_out_aaa .(x1, x2) = .(x2) U2_aaa(x1, x2, x3, x4, x5) = U2_aaa(x5) is_in_ag(x1, x2) = is_in_ag(x2) -(x1, x2) = -(x2) is_out_ag(x1, x2) = is_out_ag 1 = 1 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) GET_IN_AAA(x1, x2, x3) = GET_IN_AAA U1_AAA(x1, x2, x3, x4) = U1_AAA(x4) =_IN_AA(x1, x2) = =_IN_AA U2_AAA(x1, x2, x3, x4, x5) = U2_AAA(x5) IS_IN_AG(x1, x2) = IS_IN_AG(x2) U3_AAA(x1, x2, x3, x4, x5) = U3_AAA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (114) Obligation: Pi DP problem: The TRS P consists of the following rules: GET_IN_AAA(.(X, XS), 0, Res) -> U1_AAA(X, XS, Res, =_in_aa(Res, X)) GET_IN_AAA(.(X, XS), 0, Res) -> =_IN_AA(Res, X) GET_IN_AAA(.(X, XS), Y, Res) -> U2_AAA(X, XS, Y, Res, is_in_ag(YP, -(Y, 1))) GET_IN_AAA(.(X, XS), Y, Res) -> IS_IN_AG(YP, -(Y, 1)) U2_AAA(X, XS, Y, Res, is_out_ag(YP, -(Y, 1))) -> U3_AAA(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U2_AAA(X, XS, Y, Res, is_out_ag(YP, -(Y, 1))) -> GET_IN_AAA(XS, YP, Res) The TRS R consists of the following rules: get_in_aaa(.(X, XS), 0, Res) -> U1_aaa(X, XS, Res, =_in_aa(Res, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_aaa(X, XS, Res, =_out_aa(Res, X)) -> get_out_aaa(.(X, XS), 0, Res) get_in_aaa(.(X, XS), Y, Res) -> U2_aaa(X, XS, Y, Res, is_in_ag(YP, -(Y, 1))) is_in_ag(X0, X1) -> is_out_ag(X0, X1) U2_aaa(X, XS, Y, Res, is_out_ag(YP, -(Y, 1))) -> U3_aaa(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U3_aaa(X, XS, Y, Res, get_out_aaa(XS, YP, Res)) -> get_out_aaa(.(X, XS), Y, Res) The argument filtering Pi contains the following mapping: get_in_aaa(x1, x2, x3) = get_in_aaa U1_aaa(x1, x2, x3, x4) = U1_aaa(x4) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa get_out_aaa(x1, x2, x3) = get_out_aaa .(x1, x2) = .(x2) U2_aaa(x1, x2, x3, x4, x5) = U2_aaa(x5) is_in_ag(x1, x2) = is_in_ag(x2) -(x1, x2) = -(x2) is_out_ag(x1, x2) = is_out_ag 1 = 1 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) GET_IN_AAA(x1, x2, x3) = GET_IN_AAA U1_AAA(x1, x2, x3, x4) = U1_AAA(x4) =_IN_AA(x1, x2) = =_IN_AA U2_AAA(x1, x2, x3, x4, x5) = U2_AAA(x5) IS_IN_AG(x1, x2) = IS_IN_AG(x2) U3_AAA(x1, x2, x3, x4, x5) = U3_AAA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (115) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 4 less nodes. ---------------------------------------- (116) Obligation: Pi DP problem: The TRS P consists of the following rules: GET_IN_AAA(.(X, XS), Y, Res) -> U2_AAA(X, XS, Y, Res, is_in_ag(YP, -(Y, 1))) U2_AAA(X, XS, Y, Res, is_out_ag(YP, -(Y, 1))) -> GET_IN_AAA(XS, YP, Res) The TRS R consists of the following rules: get_in_aaa(.(X, XS), 0, Res) -> U1_aaa(X, XS, Res, =_in_aa(Res, X)) =_in_aa(X, X) -> =_out_aa(X, X) U1_aaa(X, XS, Res, =_out_aa(Res, X)) -> get_out_aaa(.(X, XS), 0, Res) get_in_aaa(.(X, XS), Y, Res) -> U2_aaa(X, XS, Y, Res, is_in_ag(YP, -(Y, 1))) is_in_ag(X0, X1) -> is_out_ag(X0, X1) U2_aaa(X, XS, Y, Res, is_out_ag(YP, -(Y, 1))) -> U3_aaa(X, XS, Y, Res, get_in_aaa(XS, YP, Res)) U3_aaa(X, XS, Y, Res, get_out_aaa(XS, YP, Res)) -> get_out_aaa(.(X, XS), Y, Res) The argument filtering Pi contains the following mapping: get_in_aaa(x1, x2, x3) = get_in_aaa U1_aaa(x1, x2, x3, x4) = U1_aaa(x4) =_in_aa(x1, x2) = =_in_aa =_out_aa(x1, x2) = =_out_aa get_out_aaa(x1, x2, x3) = get_out_aaa .(x1, x2) = .(x2) U2_aaa(x1, x2, x3, x4, x5) = U2_aaa(x5) is_in_ag(x1, x2) = is_in_ag(x2) -(x1, x2) = -(x2) is_out_ag(x1, x2) = is_out_ag 1 = 1 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) GET_IN_AAA(x1, x2, x3) = GET_IN_AAA U2_AAA(x1, x2, x3, x4, x5) = U2_AAA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (117) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (118) Obligation: Pi DP problem: The TRS P consists of the following rules: GET_IN_AAA(.(X, XS), Y, Res) -> U2_AAA(X, XS, Y, Res, is_in_ag(YP, -(Y, 1))) U2_AAA(X, XS, Y, Res, is_out_ag(YP, -(Y, 1))) -> GET_IN_AAA(XS, YP, Res) The TRS R consists of the following rules: is_in_ag(X0, X1) -> is_out_ag(X0, X1) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) is_in_ag(x1, x2) = is_in_ag(x2) -(x1, x2) = -(x2) is_out_ag(x1, x2) = is_out_ag 1 = 1 GET_IN_AAA(x1, x2, x3) = GET_IN_AAA U2_AAA(x1, x2, x3, x4, x5) = U2_AAA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (119) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (120) Obligation: Q DP problem: The TRS P consists of the following rules: GET_IN_AAA -> U2_AAA(is_in_ag(-(1))) U2_AAA(is_out_ag) -> GET_IN_AAA The TRS R consists of the following rules: is_in_ag(X1) -> is_out_ag The set Q consists of the following terms: is_in_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (121) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule GET_IN_AAA -> U2_AAA(is_in_ag(-(1))) at position [0] we obtained the following new rules [LPAR04]: (GET_IN_AAA -> U2_AAA(is_out_ag),GET_IN_AAA -> U2_AAA(is_out_ag)) ---------------------------------------- (122) Obligation: Q DP problem: The TRS P consists of the following rules: U2_AAA(is_out_ag) -> GET_IN_AAA GET_IN_AAA -> U2_AAA(is_out_ag) The TRS R consists of the following rules: is_in_ag(X1) -> is_out_ag The set Q consists of the following terms: is_in_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (123) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (124) Obligation: Q DP problem: The TRS P consists of the following rules: U2_AAA(is_out_ag) -> GET_IN_AAA GET_IN_AAA -> U2_AAA(is_out_ag) R is empty. The set Q consists of the following terms: is_in_ag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (125) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. is_in_ag(x0) ---------------------------------------- (126) Obligation: Q DP problem: The TRS P consists of the following rules: U2_AAA(is_out_ag) -> GET_IN_AAA GET_IN_AAA -> U2_AAA(is_out_ag) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (127) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 2, "program": { "directives": [], "clauses": [ [ "(get (. X XS) (0) Res)", "(',' (!) (= Res X))" ], [ "(get (. X XS) Y Res)", "(',' (!) (',' (is YP (- Y (1))) (get XS YP Res)))" ] ] }, "graph": { "nodes": { "22": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "44": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "23": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "45": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T25", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" } ] }, "ground": [], "free": [], "exprvars": [ "T25", "T22" ] } }, "24": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (!_1) (',' (is X15 (- T22 (1))) (get T23 X15 T24)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X15"], "exprvars": [] } }, "46": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "48": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (!_2) (',' (is X38 (- T49 (1))) (get T51 X38 T52)))" }], "kb": { "nonunifying": [[ "(get T23 T49 T24)", "(get (. X22 X23) (0) X24)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T25", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" } ] }, "ground": ["T49"], "free": [ "X22", "X23", "X24", "X38" ], "exprvars": [ "T25", "T22", "T49" ] } }, "27": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "49": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T25", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }] }, "ground": [], "free": [], "exprvars": [ "T25", "T22" ] } }, "29": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X15 (- T22 (1))) (get T23 X15 T24))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X15"], "exprvars": [] } }, "type": "Nodes", "51": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X38 (- T49 (1))) (get T51 X38 T52))" }], "kb": { "nonunifying": [[ "(get T23 T49 T24)", "(get (. X22 X23) (0) X24)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T25", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" } ] }, "ground": ["T49"], "free": [ "X22", "X23", "X24", "X38" ], "exprvars": [ "T25", "T22", "T49" ] } }, "30": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "53": { "goal": [{ "clause": -1, "scope": -1, "term": "(get T51 T53 T52)" }], "kb": { "nonunifying": [[ "(get T23 T49 T24)", "(get (. X22 X23) (0) X24)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T25", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T53", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T49", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" } ] }, "ground": [ "T53", "T49" ], "free": [ "X22", "X23", "X24", "X38" ], "exprvars": [ "T53", "T25", "T22", "T49" ] } }, "17": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_1) (= T10 T11))" }, { "clause": 1, "scope": 1, "term": "(get T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "39": { "goal": [{ "clause": -1, "scope": -1, "term": "(get T23 T25 T24)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T25", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }] }, "ground": [ "T25", "T22" ], "free": ["X15"], "exprvars": [ "T25", "T22" ] } }, "19": { "goal": [{ "clause": 1, "scope": 1, "term": "(get T1 T2 T3)" }], "kb": { "nonunifying": [[ "(get T1 T2 T3)", "(get (. X4 X5) (0) X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X4", "X5", "X6" ], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(get T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "6": { "goal": [ { "clause": 0, "scope": 1, "term": "(get T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(get T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "40": { "goal": [ { "clause": 0, "scope": 2, "term": "(get T23 T25 T24)" }, { "clause": 1, "scope": 2, "term": "(get T23 T25 T24)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T25", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }] }, "ground": ["T25"], "free": [], "exprvars": [ "T25", "T22" ] } }, "41": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_2) (= T35 T36))" }, { "clause": 1, "scope": 2, "term": "(get T23 (0) T24)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T25", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" } ] }, "ground": [], "free": [], "exprvars": [ "T25", "T22" ] } }, "20": { "goal": [{ "clause": -1, "scope": -1, "term": "(= T10 T11)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "42": { "goal": [{ "clause": 1, "scope": 2, "term": "(get T23 T25 T24)" }], "kb": { "nonunifying": [[ "(get T23 T25 T24)", "(get (. X22 X23) (0) X24)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T25", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }] }, "ground": ["T25"], "free": [ "X22", "X23", "X24" ], "exprvars": [ "T25", "T22" ] } }, "21": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "43": { "goal": [{ "clause": -1, "scope": -1, "term": "(= T35 T36)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T25", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" } ] }, "ground": [], "free": [], "exprvars": [ "T25", "T22" ] } } }, "edges": [ { "from": 2, "to": 6, "label": "CASE" }, { "from": 6, "to": 17, "label": "EVAL with clause\nget(.(X4, X5), 0, X6) :- ','(!_1, =(X6, X4)).\nand substitutionX4 -> T11,\nX5 -> T8,\nT1 -> .(T11, T8),\nT2 -> 0,\nT3 -> T10,\nX6 -> T10,\nT9 -> T10,\nT7 -> T11" }, { "from": 6, "to": 19, "label": "EVAL-BACKTRACK" }, { "from": 17, "to": 20, "label": "CUT" }, { "from": 19, "to": 24, "label": "EVAL with clause\nget(.(X11, X12), X13, X14) :- ','(!_1, ','(is(X15, -(X13, 1)), get(X12, X15, X14))).\nand substitutionX11 -> T18,\nX12 -> T23,\nT1 -> .(T18, T23),\nT2 -> T22,\nX13 -> T22,\nT3 -> T24,\nX14 -> T24,\nT20 -> T22,\nT19 -> T23,\nT21 -> T24" }, { "from": 19, "to": 27, "label": "EVAL-BACKTRACK" }, { "from": 20, "to": 21, "label": "UNIFY CASE with substitutionT10 -> T13,\nT11 -> T13" }, { "from": 20, "to": 22, "label": "UNIFY-BACKTRACK" }, { "from": 21, "to": 23, "label": "SUCCESS" }, { "from": 24, "to": 29, "label": "CUT" }, { "from": 29, "to": 30, "label": "IS ERROR" }, { "from": 29, "to": 39, "label": "\nX15 -> T25" }, { "from": 39, "to": 40, "label": "CASE" }, { "from": 40, "to": 41, "label": "EVAL with clause\nget(.(X22, X23), 0, X24) :- ','(!_2, =(X24, X22)).\nand substitutionX22 -> T36,\nX23 -> T33,\nT23 -> .(T36, T33),\nT25 -> 0,\nT24 -> T35,\nX24 -> T35,\nT34 -> T35,\nT32 -> T36" }, { "from": 40, "to": 42, "label": "EVAL-BACKTRACK" }, { "from": 41, "to": 43, "label": "CUT" }, { "from": 42, "to": 48, "label": "EVAL with clause\nget(.(X34, X35), X36, X37) :- ','(!_2, ','(is(X38, -(X36, 1)), get(X35, X38, X37))).\nand substitutionX34 -> T47,\nX35 -> T51,\nT23 -> .(T47, T51),\nT25 -> T49,\nX36 -> T49,\nT24 -> T52,\nX37 -> T52,\nT48 -> T51,\nT50 -> T52" }, { "from": 42, "to": 49, "label": "EVAL-BACKTRACK" }, { "from": 43, "to": 44, "label": "UNIFY CASE with substitutionT35 -> T38,\nT36 -> T38" }, { "from": 43, "to": 45, "label": "UNIFY-BACKTRACK" }, { "from": 44, "to": 46, "label": "SUCCESS" }, { "from": 48, "to": 51, "label": "CUT" }, { "from": 51, "to": 53, "label": "\nX38 -> T53" }, { "from": 53, "to": 2, "label": "INSTANCE with matching:\nT1 -> T51\nT2 -> T53\nT3 -> T52" } ], "type": "Graph" } } ---------------------------------------- (128) Obligation: Triples: getA(.(X1, .(X2, X3)), X4, X5) :- getA(X3, X6, X5). Clauses: getcA(.(X1, X2), 0, X1). getcA(.(X1, .(X2, X3)), X4, X2). getcA(.(X1, .(X2, X3)), X4, X5) :- getcA(X3, X6, X5). Afs: getA(x1, x2, x3) = getA ---------------------------------------- (129) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: getA_in_3: (f,f,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: GETA_IN_AAA(.(X1, .(X2, X3)), X4, X5) -> U1_AAA(X1, X2, X3, X4, X5, getA_in_aaa(X3, X6, X5)) GETA_IN_AAA(.(X1, .(X2, X3)), X4, X5) -> GETA_IN_AAA(X3, X6, X5) R is empty. The argument filtering Pi contains the following mapping: getA_in_aaa(x1, x2, x3) = getA_in_aaa .(x1, x2) = .(x2) GETA_IN_AAA(x1, x2, x3) = GETA_IN_AAA U1_AAA(x1, x2, x3, x4, x5, x6) = U1_AAA(x6) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (130) Obligation: Pi DP problem: The TRS P consists of the following rules: GETA_IN_AAA(.(X1, .(X2, X3)), X4, X5) -> U1_AAA(X1, X2, X3, X4, X5, getA_in_aaa(X3, X6, X5)) GETA_IN_AAA(.(X1, .(X2, X3)), X4, X5) -> GETA_IN_AAA(X3, X6, X5) R is empty. The argument filtering Pi contains the following mapping: getA_in_aaa(x1, x2, x3) = getA_in_aaa .(x1, x2) = .(x2) GETA_IN_AAA(x1, x2, x3) = GETA_IN_AAA U1_AAA(x1, x2, x3, x4, x5, x6) = U1_AAA(x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (131) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 1 less node. ---------------------------------------- (132) Obligation: Pi DP problem: The TRS P consists of the following rules: GETA_IN_AAA(.(X1, .(X2, X3)), X4, X5) -> GETA_IN_AAA(X3, X6, X5) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) GETA_IN_AAA(x1, x2, x3) = GETA_IN_AAA We have to consider all (P,R,Pi)-chains ---------------------------------------- (133) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (134) Obligation: Q DP problem: The TRS P consists of the following rules: GETA_IN_AAA -> GETA_IN_AAA R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (135) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by semiunifying a rule from P directly. s = GETA_IN_AAA evaluates to t =GETA_IN_AAA Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence The DP semiunifies directly so there is only one rewrite step from GETA_IN_AAA to GETA_IN_AAA. ---------------------------------------- (136) NO ---------------------------------------- (137) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 3, "program": { "directives": [], "clauses": [ [ "(get (. X XS) (0) Res)", "(',' (!) (= Res X))" ], [ "(get (. X XS) Y Res)", "(',' (!) (',' (is YP (- Y (1))) (get XS YP Res)))" ] ] }, "graph": { "nodes": { "66": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T32", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T29", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }] }, "ground": [], "free": [], "exprvars": [ "T29", "T32" ] } }, "67": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X49 (- T59 (1))) (get T61 X49 T62))" }], "kb": { "nonunifying": [[ "(get T30 T59 T31)", "(get (. X33 X34) (0) X35)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T32", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T29", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T29", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T29", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" } ] }, "ground": ["T59"], "free": [ "X33", "X34", "X35", "X49" ], "exprvars": [ "T29", "T32", "T59" ] } }, "68": { "goal": [{ "clause": -1, "scope": -1, "term": "(get T61 T63 T62)" }], "kb": { "nonunifying": [[ "(get T30 T59 T31)", "(get (. X33 X34) (0) X35)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T32", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T29", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T29", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T29", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T63", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T59", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" } ] }, "ground": [ "T63", "T59" ], "free": [ "X33", "X34", "X35", "X49" ], "exprvars": [ "T63", "T29", "T32", "T59" ] } }, "47": { "goal": [ { "clause": 0, "scope": 2, "term": "(get T30 T32 T31)" }, { "clause": 1, "scope": 2, "term": "(get T30 T32 T31)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T32", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T29", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }] }, "ground": ["T32"], "free": [], "exprvars": [ "T29", "T32" ] } }, "26": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "50": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_2) (= T45 T46))" }, { "clause": 1, "scope": 2, "term": "(get T30 (0) T31)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T32", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T29", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T29", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T29", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" } ] }, "ground": [], "free": [], "exprvars": [ "T29", "T32" ] } }, "52": { "goal": [{ "clause": 1, "scope": 2, "term": "(get T30 T32 T31)" }], "kb": { "nonunifying": [[ "(get T30 T32 T31)", "(get (. X33 X34) (0) X35)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T32", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T29", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }] }, "ground": ["T32"], "free": [ "X33", "X34", "X35" ], "exprvars": [ "T29", "T32" ] } }, "31": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (!_1) (',' (is X23 (- T29 (1))) (get T30 X23 T31)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X23"], "exprvars": [] } }, "32": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "54": { "goal": [{ "clause": -1, "scope": -1, "term": "(= T45 T46)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T32", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T29", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T29", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T29", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" } ] }, "ground": [], "free": [], "exprvars": [ "T29", "T32" ] } }, "11": { "goal": [{ "clause": 1, "scope": 1, "term": "(get T1 T2 T3)" }], "kb": { "nonunifying": [[ "(get T1 T2 T3)", "(get (. X7 X8) (0) X9)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X7", "X8", "X9" ], "exprvars": [] } }, "33": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X23 (- T29 (1))) (get T30 X23 T31))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X23"], "exprvars": [] } }, "55": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "12": { "goal": [{ "clause": -1, "scope": -1, "term": "(= T13 T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "34": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "56": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T32", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T29", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T29", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T29", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" } ] }, "ground": [], "free": [], "exprvars": [ "T29", "T32" ] } }, "14": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "58": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "37": { "goal": [{ "clause": -1, "scope": -1, "term": "(get T30 T32 T31)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T32", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T29", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }] }, "ground": [ "T29", "T32" ], "free": ["X23"], "exprvars": [ "T29", "T32" ] } }, "16": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(get T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "4": { "goal": [ { "clause": 0, "scope": 1, "term": "(get T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(get T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "9": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_1) (= T13 T14))" }, { "clause": 1, "scope": 1, "term": "(get T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "64": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (!_2) (',' (is X49 (- T59 (1))) (get T61 X49 T62)))" }], "kb": { "nonunifying": [[ "(get T30 T59 T31)", "(get (. X33 X34) (0) X35)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T32", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T29", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T29", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T29", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" } ] }, "ground": ["T59"], "free": [ "X33", "X34", "X35", "X49" ], "exprvars": [ "T29", "T32", "T59" ] } } }, "edges": [ { "from": 3, "to": 4, "label": "CASE" }, { "from": 4, "to": 9, "label": "EVAL with clause\nget(.(X7, X8), 0, X9) :- ','(!_1, =(X9, X7)).\nand substitutionX7 -> T14,\nX8 -> T11,\nT1 -> .(T14, T11),\nT2 -> 0,\nT3 -> T13,\nX9 -> T13,\nT12 -> T13,\nT10 -> T14" }, { "from": 4, "to": 11, "label": "EVAL-BACKTRACK" }, { "from": 9, "to": 12, "label": "CUT" }, { "from": 11, "to": 31, "label": "EVAL with clause\nget(.(X19, X20), X21, X22) :- ','(!_1, ','(is(X23, -(X21, 1)), get(X20, X23, X22))).\nand substitutionX19 -> T25,\nX20 -> T30,\nT1 -> .(T25, T30),\nT2 -> T29,\nX21 -> T29,\nT3 -> T31,\nX22 -> T31,\nT27 -> T29,\nT26 -> T30,\nT28 -> T31" }, { "from": 11, "to": 32, "label": "EVAL-BACKTRACK" }, { "from": 12, "to": 14, "label": "UNIFY CASE with substitutionT13 -> T16,\nT14 -> T16" }, { "from": 12, "to": 16, "label": "UNIFY-BACKTRACK" }, { "from": 14, "to": 26, "label": "SUCCESS" }, { "from": 31, "to": 33, "label": "CUT" }, { "from": 33, "to": 34, "label": "IS ERROR" }, { "from": 33, "to": 37, "label": "\nX23 -> T32" }, { "from": 37, "to": 47, "label": "CASE" }, { "from": 47, "to": 50, "label": "EVAL with clause\nget(.(X33, X34), 0, X35) :- ','(!_2, =(X35, X33)).\nand substitutionX33 -> T46,\nX34 -> T43,\nT30 -> .(T46, T43),\nT32 -> 0,\nT31 -> T45,\nX35 -> T45,\nT44 -> T45,\nT42 -> T46" }, { "from": 47, "to": 52, "label": "EVAL-BACKTRACK" }, { "from": 50, "to": 54, "label": "CUT" }, { "from": 52, "to": 64, "label": "EVAL with clause\nget(.(X45, X46), X47, X48) :- ','(!_2, ','(is(X49, -(X47, 1)), get(X46, X49, X48))).\nand substitutionX45 -> T57,\nX46 -> T61,\nT30 -> .(T57, T61),\nT32 -> T59,\nX47 -> T59,\nT31 -> T62,\nX48 -> T62,\nT58 -> T61,\nT60 -> T62" }, { "from": 52, "to": 66, "label": "EVAL-BACKTRACK" }, { "from": 54, "to": 55, "label": "UNIFY CASE with substitutionT45 -> T48,\nT46 -> T48" }, { "from": 54, "to": 56, "label": "UNIFY-BACKTRACK" }, { "from": 55, "to": 58, "label": "SUCCESS" }, { "from": 64, "to": 67, "label": "CUT" }, { "from": 67, "to": 68, "label": "\nX49 -> T63" }, { "from": 68, "to": 37, "label": "INSTANCE with matching:\nT30 -> T61\nT32 -> T63\nT31 -> T62\nX23 -> X33" } ], "type": "Graph" } } ---------------------------------------- (138) Obligation: Rules: f50_out -> f47_out(0) :|: TRUE f47_in(0) -> f50_in :|: TRUE f47_in(T32) -> f52_in(T32) :|: TRUE f52_out(x) -> f47_out(x) :|: TRUE f52_in(T59) -> f64_in(T59) :|: TRUE f52_in(x1) -> f66_in :|: TRUE f64_out(x2) -> f52_out(x2) :|: TRUE f66_out -> f52_out(x3) :|: TRUE f37_in(x4, x5) -> f47_in(x4) :|: TRUE f47_out(x6) -> f37_out(x6, x7) :|: TRUE f37_out(x8, x9) -> f68_out(x8, x10) :|: TRUE f68_in(x11, x12) -> f37_in(x11, x13) :|: TRUE f67_in(x14) -> f68_in(x15, x14) :|: x15 = x14 - 1 f68_out(x16, x17) -> f67_out(x17) :|: TRUE f64_in(x18) -> f67_in(x18) :|: TRUE f67_out(x19) -> f64_out(x19) :|: TRUE f4_out -> f3_out :|: TRUE f3_in -> f4_in :|: TRUE f11_out -> f4_out :|: TRUE f4_in -> f9_in :|: TRUE f4_in -> f11_in :|: TRUE f9_out -> f4_out :|: TRUE f11_in -> f32_in :|: TRUE f11_in -> f31_in :|: TRUE f31_out -> f11_out :|: TRUE f32_out -> f11_out :|: TRUE f31_in -> f33_in :|: TRUE f33_out -> f31_out :|: TRUE f34_out -> f33_out :|: TRUE f37_out(x20, x21) -> f33_out :|: TRUE f33_in -> f34_in :|: TRUE f33_in -> f37_in(x22, x23) :|: x22 = x23 - 1 Start term: f3_in ---------------------------------------- (139) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f47_in(T32) -> f52_in(T32) :|: TRUE f52_in(T59) -> f64_in(T59) :|: TRUE f37_in(x4, x5) -> f47_in(x4) :|: TRUE f68_in(x11, x12) -> f37_in(x11, x13) :|: TRUE f67_in(x14) -> f68_in(x15, x14) :|: x15 = x14 - 1 f64_in(x18) -> f67_in(x18) :|: TRUE ---------------------------------------- (140) Obligation: Rules: f47_in(T32) -> f52_in(T32) :|: TRUE f52_in(T59) -> f64_in(T59) :|: TRUE f37_in(x4, x5) -> f47_in(x4) :|: TRUE f68_in(x11, x12) -> f37_in(x11, x13) :|: TRUE f67_in(x14) -> f68_in(x15, x14) :|: x15 = x14 - 1 f64_in(x18) -> f67_in(x18) :|: TRUE ---------------------------------------- (141) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (142) Obligation: Rules: f67_in(x14:0) -> f67_in(x14:0 - 1) :|: TRUE ---------------------------------------- (143) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (144) Obligation: Rules: f67_in(x14:0) -> f67_in(arith) :|: TRUE && arith = x14:0 - 1 ---------------------------------------- (145) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f67_in(x14:0) -> f67_in(arith) :|: TRUE && arith = x14:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (146) Obligation: Termination digraph: Nodes: (1) f67_in(x14:0) -> f67_in(arith) :|: TRUE && arith = x14:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (147) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (148) Obligation: Rules: f67_in(x14:0:0) -> f67_in(x14:0:0 - 1) :|: TRUE ---------------------------------------- (149) IRSwTToIntTRSProof (SOUND) Applied path-length measure to transform intTRS with terms to intTRS. ---------------------------------------- (150) Obligation: Rules: f67_in(x) -> f67_in(x - 1) :|: TRUE ---------------------------------------- (151) IntTRSNonPeriodicNontermProof (COMPLETE) Normalized system to the following form: f(pc, x) -> f(1, x - 1) :|: pc = 1 && TRUE Proved unsatisfiability of the following formula, indicating that the system is never left after entering: (((run2_0 = ((1 * 1)) and run2_1 = ((run1_1 * 1) + (1 * -1))) and (((run1_0 * 1)) = ((1 * 1)) and T)) and !(((run2_0 * 1)) = ((1 * 1)) and T)) Proved satisfiability of the following formula, indicating that the system is entered at least once: ((run2_0 = ((1 * 1)) and run2_1 = ((run1_1 * 1) + (1 * -1))) and (((run1_0 * 1)) = ((1 * 1)) and T)) ---------------------------------------- (152) NO