/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.pl /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern my_is(g) w.r.t. the given Prolog program could not be shown: (0) Prolog (1) IntegerArithmeticTransformerProof [SOUND, 0 ms] (2) Prolog (3) UnifyTransformerProof [EQUIVALENT, 0 ms] (4) Prolog (5) PrologToPiTRSProof [SOUND, 0 ms] (6) PiTRS (7) DependencyPairsProof [EQUIVALENT, 0 ms] (8) PiDP (9) DependencyGraphProof [EQUIVALENT, 0 ms] (10) PiDP (11) UsableRulesProof [EQUIVALENT, 0 ms] (12) PiDP (13) PiDPToQDPProof [SOUND, 0 ms] (14) QDP (15) TransformationProof [SOUND, 0 ms] (16) QDP (17) UsableRulesProof [EQUIVALENT, 0 ms] (18) QDP (19) QReductionProof [EQUIVALENT, 0 ms] (20) QDP (21) TransformationProof [EQUIVALENT, 0 ms] (22) QDP (23) NonTerminationLoopProof [COMPLETE, 0 ms] (24) NO (25) PrologToPiTRSProof [SOUND, 0 ms] (26) PiTRS (27) DependencyPairsProof [EQUIVALENT, 0 ms] (28) PiDP (29) DependencyGraphProof [EQUIVALENT, 0 ms] (30) PiDP (31) UsableRulesProof [EQUIVALENT, 0 ms] (32) PiDP (33) PiDPToQDPProof [EQUIVALENT, 0 ms] (34) QDP (35) TransformationProof [SOUND, 0 ms] (36) QDP (37) UsableRulesProof [EQUIVALENT, 0 ms] (38) QDP (39) QReductionProof [EQUIVALENT, 0 ms] (40) QDP (41) TransformationProof [EQUIVALENT, 0 ms] (42) QDP (43) NonTerminationLoopProof [COMPLETE, 0 ms] (44) NO (45) UndefinedPredicateHandlerProof [SOUND, 0 ms] (46) Prolog (47) PrologToPiTRSProof [SOUND, 0 ms] (48) PiTRS (49) DependencyPairsProof [EQUIVALENT, 0 ms] (50) PiDP (51) DependencyGraphProof [EQUIVALENT, 0 ms] (52) PiDP (53) UsableRulesProof [EQUIVALENT, 0 ms] (54) PiDP (55) PiDPToQDPProof [SOUND, 0 ms] (56) QDP (57) TransformationProof [EQUIVALENT, 0 ms] (58) QDP (59) UsableRulesProof [EQUIVALENT, 0 ms] (60) QDP (61) QReductionProof [EQUIVALENT, 0 ms] (62) QDP (63) PrologToPiTRSProof [SOUND, 0 ms] (64) PiTRS (65) DependencyPairsProof [EQUIVALENT, 0 ms] (66) PiDP (67) DependencyGraphProof [EQUIVALENT, 0 ms] (68) PiDP (69) UsableRulesProof [EQUIVALENT, 0 ms] (70) PiDP (71) PiDPToQDPProof [EQUIVALENT, 0 ms] (72) QDP (73) TransformationProof [EQUIVALENT, 0 ms] (74) QDP (75) UsableRulesProof [EQUIVALENT, 0 ms] (76) QDP (77) QReductionProof [EQUIVALENT, 0 ms] (78) QDP (79) NonTerminationLoopProof [COMPLETE, 0 ms] (80) NO (81) PrologToDTProblemTransformerProof [SOUND, 0 ms] (82) TRIPLES (83) TriplesToPiDPProof [SOUND, 0 ms] (84) PiDP (85) DependencyGraphProof [EQUIVALENT, 0 ms] (86) PiDP (87) PiDPToQDPProof [SOUND, 0 ms] (88) QDP (89) NonTerminationLoopProof [COMPLETE, 0 ms] (90) NO (91) PrologToIRSwTTransformerProof [SOUND, 0 ms] (92) IRSwT (93) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (94) IRSwT (95) IntTRSCompressionProof [EQUIVALENT, 8 ms] (96) IRSwT (97) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (98) IRSwT (99) IRSwTTerminationDigraphProof [EQUIVALENT, 16 ms] (100) IRSwT (101) IntTRSCompressionProof [EQUIVALENT, 0 ms] (102) IRSwT (103) IRSwTToIntTRSProof [SOUND, 0 ms] (104) IRSwT (105) IntTRSCompressionProof [EQUIVALENT, 0 ms] (106) IRSwT (107) IntTRSNonPeriodicNontermProof [COMPLETE, 0 ms] (108) NO ---------------------------------------- (0) Obligation: Clauses: my_is(X) :- ','(is(X, 1), my_is(X)). Query: my_is(g) ---------------------------------------- (1) IntegerArithmeticTransformerProof (SOUND) Added definitions of predefined predicates [PROLOG]. ---------------------------------------- (2) Obligation: Clauses: my_is(X) :- ','(=(X, succ(zero)), my_is(X)). 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: my_is(g) ---------------------------------------- (3) UnifyTransformerProof (EQUIVALENT) Added a fact for the built-in = predicate [PROLOG]. ---------------------------------------- (4) Obligation: Clauses: my_is(X) :- ','(=(X, succ(zero)), my_is(X)). 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: my_is(g) ---------------------------------------- (5) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: my_is_in_1: (b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: my_is_in_g(X) -> U1_g(X, =_in_gg(X, succ(zero))) =_in_gg(X, X) -> =_out_gg(X, X) U1_g(X, =_out_gg(X, succ(zero))) -> U2_g(X, my_is_in_g(X)) U2_g(X, my_is_out_g(X)) -> my_is_out_g(X) The argument filtering Pi contains the following mapping: my_is_in_g(x1) = my_is_in_g(x1) U1_g(x1, x2) = U1_g(x1, x2) =_in_gg(x1, x2) = =_in_gg(x1, x2) =_out_gg(x1, x2) = =_out_gg succ(x1) = succ(x1) zero = zero U2_g(x1, x2) = U2_g(x2) my_is_out_g(x1) = my_is_out_g Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (6) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: my_is_in_g(X) -> U1_g(X, =_in_gg(X, succ(zero))) =_in_gg(X, X) -> =_out_gg(X, X) U1_g(X, =_out_gg(X, succ(zero))) -> U2_g(X, my_is_in_g(X)) U2_g(X, my_is_out_g(X)) -> my_is_out_g(X) The argument filtering Pi contains the following mapping: my_is_in_g(x1) = my_is_in_g(x1) U1_g(x1, x2) = U1_g(x1, x2) =_in_gg(x1, x2) = =_in_gg(x1, x2) =_out_gg(x1, x2) = =_out_gg succ(x1) = succ(x1) zero = zero U2_g(x1, x2) = U2_g(x2) my_is_out_g(x1) = my_is_out_g ---------------------------------------- (7) 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: MY_IS_IN_G(X) -> U1_G(X, =_in_gg(X, succ(zero))) MY_IS_IN_G(X) -> =_IN_GG(X, succ(zero)) U1_G(X, =_out_gg(X, succ(zero))) -> U2_G(X, my_is_in_g(X)) U1_G(X, =_out_gg(X, succ(zero))) -> MY_IS_IN_G(X) The TRS R consists of the following rules: my_is_in_g(X) -> U1_g(X, =_in_gg(X, succ(zero))) =_in_gg(X, X) -> =_out_gg(X, X) U1_g(X, =_out_gg(X, succ(zero))) -> U2_g(X, my_is_in_g(X)) U2_g(X, my_is_out_g(X)) -> my_is_out_g(X) The argument filtering Pi contains the following mapping: my_is_in_g(x1) = my_is_in_g(x1) U1_g(x1, x2) = U1_g(x1, x2) =_in_gg(x1, x2) = =_in_gg(x1, x2) =_out_gg(x1, x2) = =_out_gg succ(x1) = succ(x1) zero = zero U2_g(x1, x2) = U2_g(x2) my_is_out_g(x1) = my_is_out_g MY_IS_IN_G(x1) = MY_IS_IN_G(x1) U1_G(x1, x2) = U1_G(x1, x2) =_IN_GG(x1, x2) = =_IN_GG(x1, x2) U2_G(x1, x2) = U2_G(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (8) Obligation: Pi DP problem: The TRS P consists of the following rules: MY_IS_IN_G(X) -> U1_G(X, =_in_gg(X, succ(zero))) MY_IS_IN_G(X) -> =_IN_GG(X, succ(zero)) U1_G(X, =_out_gg(X, succ(zero))) -> U2_G(X, my_is_in_g(X)) U1_G(X, =_out_gg(X, succ(zero))) -> MY_IS_IN_G(X) The TRS R consists of the following rules: my_is_in_g(X) -> U1_g(X, =_in_gg(X, succ(zero))) =_in_gg(X, X) -> =_out_gg(X, X) U1_g(X, =_out_gg(X, succ(zero))) -> U2_g(X, my_is_in_g(X)) U2_g(X, my_is_out_g(X)) -> my_is_out_g(X) The argument filtering Pi contains the following mapping: my_is_in_g(x1) = my_is_in_g(x1) U1_g(x1, x2) = U1_g(x1, x2) =_in_gg(x1, x2) = =_in_gg(x1, x2) =_out_gg(x1, x2) = =_out_gg succ(x1) = succ(x1) zero = zero U2_g(x1, x2) = U2_g(x2) my_is_out_g(x1) = my_is_out_g MY_IS_IN_G(x1) = MY_IS_IN_G(x1) U1_G(x1, x2) = U1_G(x1, x2) =_IN_GG(x1, x2) = =_IN_GG(x1, x2) U2_G(x1, x2) = U2_G(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (9) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 2 less nodes. ---------------------------------------- (10) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_G(X, =_out_gg(X, succ(zero))) -> MY_IS_IN_G(X) MY_IS_IN_G(X) -> U1_G(X, =_in_gg(X, succ(zero))) The TRS R consists of the following rules: my_is_in_g(X) -> U1_g(X, =_in_gg(X, succ(zero))) =_in_gg(X, X) -> =_out_gg(X, X) U1_g(X, =_out_gg(X, succ(zero))) -> U2_g(X, my_is_in_g(X)) U2_g(X, my_is_out_g(X)) -> my_is_out_g(X) The argument filtering Pi contains the following mapping: my_is_in_g(x1) = my_is_in_g(x1) U1_g(x1, x2) = U1_g(x1, x2) =_in_gg(x1, x2) = =_in_gg(x1, x2) =_out_gg(x1, x2) = =_out_gg succ(x1) = succ(x1) zero = zero U2_g(x1, x2) = U2_g(x2) my_is_out_g(x1) = my_is_out_g MY_IS_IN_G(x1) = MY_IS_IN_G(x1) U1_G(x1, x2) = U1_G(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (11) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (12) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_G(X, =_out_gg(X, succ(zero))) -> MY_IS_IN_G(X) MY_IS_IN_G(X) -> U1_G(X, =_in_gg(X, succ(zero))) The TRS R consists of the following rules: =_in_gg(X, X) -> =_out_gg(X, X) The argument filtering Pi contains the following mapping: =_in_gg(x1, x2) = =_in_gg(x1, x2) =_out_gg(x1, x2) = =_out_gg succ(x1) = succ(x1) zero = zero MY_IS_IN_G(x1) = MY_IS_IN_G(x1) U1_G(x1, x2) = U1_G(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (13) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: U1_G(X, =_out_gg) -> MY_IS_IN_G(X) MY_IS_IN_G(X) -> U1_G(X, =_in_gg(X, succ(zero))) The TRS R consists of the following rules: =_in_gg(X, X) -> =_out_gg The set Q consists of the following terms: =_in_gg(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (15) TransformationProof (SOUND) By narrowing [LPAR04] the rule MY_IS_IN_G(X) -> U1_G(X, =_in_gg(X, succ(zero))) at position [1] we obtained the following new rules [LPAR04]: (MY_IS_IN_G(succ(zero)) -> U1_G(succ(zero), =_out_gg),MY_IS_IN_G(succ(zero)) -> U1_G(succ(zero), =_out_gg)) ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: U1_G(X, =_out_gg) -> MY_IS_IN_G(X) MY_IS_IN_G(succ(zero)) -> U1_G(succ(zero), =_out_gg) The TRS R consists of the following rules: =_in_gg(X, X) -> =_out_gg The set Q consists of the following terms: =_in_gg(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (17) 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. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: U1_G(X, =_out_gg) -> MY_IS_IN_G(X) MY_IS_IN_G(succ(zero)) -> U1_G(succ(zero), =_out_gg) R is empty. The set Q consists of the following terms: =_in_gg(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) 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_gg(x0, x1) ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: U1_G(X, =_out_gg) -> MY_IS_IN_G(X) MY_IS_IN_G(succ(zero)) -> U1_G(succ(zero), =_out_gg) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (21) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U1_G(X, =_out_gg) -> MY_IS_IN_G(X) we obtained the following new rules [LPAR04]: (U1_G(succ(zero), =_out_gg) -> MY_IS_IN_G(succ(zero)),U1_G(succ(zero), =_out_gg) -> MY_IS_IN_G(succ(zero))) ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: MY_IS_IN_G(succ(zero)) -> U1_G(succ(zero), =_out_gg) U1_G(succ(zero), =_out_gg) -> MY_IS_IN_G(succ(zero)) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (23) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by narrowing to the left: s = U1_G(succ(zero), =_out_gg) evaluates to t =U1_G(succ(zero), =_out_gg) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence U1_G(succ(zero), =_out_gg) -> MY_IS_IN_G(succ(zero)) with rule U1_G(succ(zero), =_out_gg) -> MY_IS_IN_G(succ(zero)) at position [] and matcher [ ] MY_IS_IN_G(succ(zero)) -> U1_G(succ(zero), =_out_gg) with rule MY_IS_IN_G(succ(zero)) -> U1_G(succ(zero), =_out_gg) Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence All these steps are and every following step will be a correct step w.r.t to Q. ---------------------------------------- (24) NO ---------------------------------------- (25) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: my_is_in_1: (b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: my_is_in_g(X) -> U1_g(X, =_in_gg(X, succ(zero))) =_in_gg(X, X) -> =_out_gg(X, X) U1_g(X, =_out_gg(X, succ(zero))) -> U2_g(X, my_is_in_g(X)) U2_g(X, my_is_out_g(X)) -> my_is_out_g(X) Pi is empty. Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (26) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: my_is_in_g(X) -> U1_g(X, =_in_gg(X, succ(zero))) =_in_gg(X, X) -> =_out_gg(X, X) U1_g(X, =_out_gg(X, succ(zero))) -> U2_g(X, my_is_in_g(X)) U2_g(X, my_is_out_g(X)) -> my_is_out_g(X) Pi is empty. ---------------------------------------- (27) 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: MY_IS_IN_G(X) -> U1_G(X, =_in_gg(X, succ(zero))) MY_IS_IN_G(X) -> =_IN_GG(X, succ(zero)) U1_G(X, =_out_gg(X, succ(zero))) -> U2_G(X, my_is_in_g(X)) U1_G(X, =_out_gg(X, succ(zero))) -> MY_IS_IN_G(X) The TRS R consists of the following rules: my_is_in_g(X) -> U1_g(X, =_in_gg(X, succ(zero))) =_in_gg(X, X) -> =_out_gg(X, X) U1_g(X, =_out_gg(X, succ(zero))) -> U2_g(X, my_is_in_g(X)) U2_g(X, my_is_out_g(X)) -> my_is_out_g(X) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (28) Obligation: Pi DP problem: The TRS P consists of the following rules: MY_IS_IN_G(X) -> U1_G(X, =_in_gg(X, succ(zero))) MY_IS_IN_G(X) -> =_IN_GG(X, succ(zero)) U1_G(X, =_out_gg(X, succ(zero))) -> U2_G(X, my_is_in_g(X)) U1_G(X, =_out_gg(X, succ(zero))) -> MY_IS_IN_G(X) The TRS R consists of the following rules: my_is_in_g(X) -> U1_g(X, =_in_gg(X, succ(zero))) =_in_gg(X, X) -> =_out_gg(X, X) U1_g(X, =_out_gg(X, succ(zero))) -> U2_g(X, my_is_in_g(X)) U2_g(X, my_is_out_g(X)) -> my_is_out_g(X) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (29) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 2 less nodes. ---------------------------------------- (30) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_G(X, =_out_gg(X, succ(zero))) -> MY_IS_IN_G(X) MY_IS_IN_G(X) -> U1_G(X, =_in_gg(X, succ(zero))) The TRS R consists of the following rules: my_is_in_g(X) -> U1_g(X, =_in_gg(X, succ(zero))) =_in_gg(X, X) -> =_out_gg(X, X) U1_g(X, =_out_gg(X, succ(zero))) -> U2_g(X, my_is_in_g(X)) U2_g(X, my_is_out_g(X)) -> my_is_out_g(X) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (31) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (32) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_G(X, =_out_gg(X, succ(zero))) -> MY_IS_IN_G(X) MY_IS_IN_G(X) -> U1_G(X, =_in_gg(X, succ(zero))) The TRS R consists of the following rules: =_in_gg(X, X) -> =_out_gg(X, X) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (33) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: U1_G(X, =_out_gg(X, succ(zero))) -> MY_IS_IN_G(X) MY_IS_IN_G(X) -> U1_G(X, =_in_gg(X, succ(zero))) The TRS R consists of the following rules: =_in_gg(X, X) -> =_out_gg(X, X) The set Q consists of the following terms: =_in_gg(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (35) TransformationProof (SOUND) By narrowing [LPAR04] the rule MY_IS_IN_G(X) -> U1_G(X, =_in_gg(X, succ(zero))) at position [1] we obtained the following new rules [LPAR04]: (MY_IS_IN_G(succ(zero)) -> U1_G(succ(zero), =_out_gg(succ(zero), succ(zero))),MY_IS_IN_G(succ(zero)) -> U1_G(succ(zero), =_out_gg(succ(zero), succ(zero)))) ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: U1_G(X, =_out_gg(X, succ(zero))) -> MY_IS_IN_G(X) MY_IS_IN_G(succ(zero)) -> U1_G(succ(zero), =_out_gg(succ(zero), succ(zero))) The TRS R consists of the following rules: =_in_gg(X, X) -> =_out_gg(X, X) The set Q consists of the following terms: =_in_gg(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (37) 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. ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: U1_G(X, =_out_gg(X, succ(zero))) -> MY_IS_IN_G(X) MY_IS_IN_G(succ(zero)) -> U1_G(succ(zero), =_out_gg(succ(zero), succ(zero))) R is empty. The set Q consists of the following terms: =_in_gg(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (39) 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_gg(x0, x1) ---------------------------------------- (40) Obligation: Q DP problem: The TRS P consists of the following rules: U1_G(X, =_out_gg(X, succ(zero))) -> MY_IS_IN_G(X) MY_IS_IN_G(succ(zero)) -> U1_G(succ(zero), =_out_gg(succ(zero), succ(zero))) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (41) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U1_G(X, =_out_gg(X, succ(zero))) -> MY_IS_IN_G(X) we obtained the following new rules [LPAR04]: (U1_G(succ(zero), =_out_gg(succ(zero), succ(zero))) -> MY_IS_IN_G(succ(zero)),U1_G(succ(zero), =_out_gg(succ(zero), succ(zero))) -> MY_IS_IN_G(succ(zero))) ---------------------------------------- (42) Obligation: Q DP problem: The TRS P consists of the following rules: MY_IS_IN_G(succ(zero)) -> U1_G(succ(zero), =_out_gg(succ(zero), succ(zero))) U1_G(succ(zero), =_out_gg(succ(zero), succ(zero))) -> MY_IS_IN_G(succ(zero)) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (43) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by narrowing to the left: s = U1_G(succ(zero), =_out_gg(succ(zero), succ(zero))) evaluates to t =U1_G(succ(zero), =_out_gg(succ(zero), succ(zero))) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence U1_G(succ(zero), =_out_gg(succ(zero), succ(zero))) -> MY_IS_IN_G(succ(zero)) with rule U1_G(succ(zero), =_out_gg(succ(zero), succ(zero))) -> MY_IS_IN_G(succ(zero)) at position [] and matcher [ ] MY_IS_IN_G(succ(zero)) -> U1_G(succ(zero), =_out_gg(succ(zero), succ(zero))) with rule MY_IS_IN_G(succ(zero)) -> U1_G(succ(zero), =_out_gg(succ(zero), succ(zero))) Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence All these steps are and every following step will be a correct step w.r.t to Q. ---------------------------------------- (44) NO ---------------------------------------- (45) UndefinedPredicateHandlerProof (SOUND) Added facts for all undefined predicates [PROLOG]. ---------------------------------------- (46) Obligation: Clauses: my_is(X) :- ','(is(X, 1), my_is(X)). is(X0, X1). Query: my_is(g) ---------------------------------------- (47) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: my_is_in_1: (b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: my_is_in_g(X) -> U1_g(X, is_in_gg(X, 1)) is_in_gg(X0, X1) -> is_out_gg(X0, X1) U1_g(X, is_out_gg(X, 1)) -> U2_g(X, my_is_in_g(X)) U2_g(X, my_is_out_g(X)) -> my_is_out_g(X) The argument filtering Pi contains the following mapping: my_is_in_g(x1) = my_is_in_g(x1) U1_g(x1, x2) = U1_g(x1, x2) is_in_gg(x1, x2) = is_in_gg(x1, x2) is_out_gg(x1, x2) = is_out_gg 1 = 1 U2_g(x1, x2) = U2_g(x2) my_is_out_g(x1) = my_is_out_g Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (48) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: my_is_in_g(X) -> U1_g(X, is_in_gg(X, 1)) is_in_gg(X0, X1) -> is_out_gg(X0, X1) U1_g(X, is_out_gg(X, 1)) -> U2_g(X, my_is_in_g(X)) U2_g(X, my_is_out_g(X)) -> my_is_out_g(X) The argument filtering Pi contains the following mapping: my_is_in_g(x1) = my_is_in_g(x1) U1_g(x1, x2) = U1_g(x1, x2) is_in_gg(x1, x2) = is_in_gg(x1, x2) is_out_gg(x1, x2) = is_out_gg 1 = 1 U2_g(x1, x2) = U2_g(x2) my_is_out_g(x1) = my_is_out_g ---------------------------------------- (49) 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: MY_IS_IN_G(X) -> U1_G(X, is_in_gg(X, 1)) MY_IS_IN_G(X) -> IS_IN_GG(X, 1) U1_G(X, is_out_gg(X, 1)) -> U2_G(X, my_is_in_g(X)) U1_G(X, is_out_gg(X, 1)) -> MY_IS_IN_G(X) The TRS R consists of the following rules: my_is_in_g(X) -> U1_g(X, is_in_gg(X, 1)) is_in_gg(X0, X1) -> is_out_gg(X0, X1) U1_g(X, is_out_gg(X, 1)) -> U2_g(X, my_is_in_g(X)) U2_g(X, my_is_out_g(X)) -> my_is_out_g(X) The argument filtering Pi contains the following mapping: my_is_in_g(x1) = my_is_in_g(x1) U1_g(x1, x2) = U1_g(x1, x2) is_in_gg(x1, x2) = is_in_gg(x1, x2) is_out_gg(x1, x2) = is_out_gg 1 = 1 U2_g(x1, x2) = U2_g(x2) my_is_out_g(x1) = my_is_out_g MY_IS_IN_G(x1) = MY_IS_IN_G(x1) U1_G(x1, x2) = U1_G(x1, x2) IS_IN_GG(x1, x2) = IS_IN_GG(x1, x2) U2_G(x1, x2) = U2_G(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (50) Obligation: Pi DP problem: The TRS P consists of the following rules: MY_IS_IN_G(X) -> U1_G(X, is_in_gg(X, 1)) MY_IS_IN_G(X) -> IS_IN_GG(X, 1) U1_G(X, is_out_gg(X, 1)) -> U2_G(X, my_is_in_g(X)) U1_G(X, is_out_gg(X, 1)) -> MY_IS_IN_G(X) The TRS R consists of the following rules: my_is_in_g(X) -> U1_g(X, is_in_gg(X, 1)) is_in_gg(X0, X1) -> is_out_gg(X0, X1) U1_g(X, is_out_gg(X, 1)) -> U2_g(X, my_is_in_g(X)) U2_g(X, my_is_out_g(X)) -> my_is_out_g(X) The argument filtering Pi contains the following mapping: my_is_in_g(x1) = my_is_in_g(x1) U1_g(x1, x2) = U1_g(x1, x2) is_in_gg(x1, x2) = is_in_gg(x1, x2) is_out_gg(x1, x2) = is_out_gg 1 = 1 U2_g(x1, x2) = U2_g(x2) my_is_out_g(x1) = my_is_out_g MY_IS_IN_G(x1) = MY_IS_IN_G(x1) U1_G(x1, x2) = U1_G(x1, x2) IS_IN_GG(x1, x2) = IS_IN_GG(x1, x2) U2_G(x1, x2) = U2_G(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (51) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 2 less nodes. ---------------------------------------- (52) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_G(X, is_out_gg(X, 1)) -> MY_IS_IN_G(X) MY_IS_IN_G(X) -> U1_G(X, is_in_gg(X, 1)) The TRS R consists of the following rules: my_is_in_g(X) -> U1_g(X, is_in_gg(X, 1)) is_in_gg(X0, X1) -> is_out_gg(X0, X1) U1_g(X, is_out_gg(X, 1)) -> U2_g(X, my_is_in_g(X)) U2_g(X, my_is_out_g(X)) -> my_is_out_g(X) The argument filtering Pi contains the following mapping: my_is_in_g(x1) = my_is_in_g(x1) U1_g(x1, x2) = U1_g(x1, x2) is_in_gg(x1, x2) = is_in_gg(x1, x2) is_out_gg(x1, x2) = is_out_gg 1 = 1 U2_g(x1, x2) = U2_g(x2) my_is_out_g(x1) = my_is_out_g MY_IS_IN_G(x1) = MY_IS_IN_G(x1) U1_G(x1, x2) = U1_G(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: U1_G(X, is_out_gg(X, 1)) -> MY_IS_IN_G(X) MY_IS_IN_G(X) -> U1_G(X, is_in_gg(X, 1)) The TRS R consists of the following rules: is_in_gg(X0, X1) -> is_out_gg(X0, X1) The argument filtering Pi contains the following mapping: is_in_gg(x1, x2) = is_in_gg(x1, x2) is_out_gg(x1, x2) = is_out_gg 1 = 1 MY_IS_IN_G(x1) = MY_IS_IN_G(x1) U1_G(x1, x2) = U1_G(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: U1_G(X, is_out_gg) -> MY_IS_IN_G(X) MY_IS_IN_G(X) -> U1_G(X, is_in_gg(X, 1)) The TRS R consists of the following rules: is_in_gg(X0, X1) -> is_out_gg The set Q consists of the following terms: is_in_gg(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (57) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule MY_IS_IN_G(X) -> U1_G(X, is_in_gg(X, 1)) at position [1] we obtained the following new rules [LPAR04]: (MY_IS_IN_G(X) -> U1_G(X, is_out_gg),MY_IS_IN_G(X) -> U1_G(X, is_out_gg)) ---------------------------------------- (58) Obligation: Q DP problem: The TRS P consists of the following rules: U1_G(X, is_out_gg) -> MY_IS_IN_G(X) MY_IS_IN_G(X) -> U1_G(X, is_out_gg) The TRS R consists of the following rules: is_in_gg(X0, X1) -> is_out_gg The set Q consists of the following terms: is_in_gg(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (59) 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. ---------------------------------------- (60) Obligation: Q DP problem: The TRS P consists of the following rules: U1_G(X, is_out_gg) -> MY_IS_IN_G(X) MY_IS_IN_G(X) -> U1_G(X, is_out_gg) R is empty. The set Q consists of the following terms: is_in_gg(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (61) 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_gg(x0, x1) ---------------------------------------- (62) Obligation: Q DP problem: The TRS P consists of the following rules: U1_G(X, is_out_gg) -> MY_IS_IN_G(X) MY_IS_IN_G(X) -> U1_G(X, is_out_gg) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (63) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: my_is_in_1: (b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: my_is_in_g(X) -> U1_g(X, is_in_gg(X, 1)) is_in_gg(X0, X1) -> is_out_gg(X0, X1) U1_g(X, is_out_gg(X, 1)) -> U2_g(X, my_is_in_g(X)) U2_g(X, my_is_out_g(X)) -> my_is_out_g(X) Pi is empty. Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (64) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: my_is_in_g(X) -> U1_g(X, is_in_gg(X, 1)) is_in_gg(X0, X1) -> is_out_gg(X0, X1) U1_g(X, is_out_gg(X, 1)) -> U2_g(X, my_is_in_g(X)) U2_g(X, my_is_out_g(X)) -> my_is_out_g(X) Pi is empty. ---------------------------------------- (65) 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: MY_IS_IN_G(X) -> U1_G(X, is_in_gg(X, 1)) MY_IS_IN_G(X) -> IS_IN_GG(X, 1) U1_G(X, is_out_gg(X, 1)) -> U2_G(X, my_is_in_g(X)) U1_G(X, is_out_gg(X, 1)) -> MY_IS_IN_G(X) The TRS R consists of the following rules: my_is_in_g(X) -> U1_g(X, is_in_gg(X, 1)) is_in_gg(X0, X1) -> is_out_gg(X0, X1) U1_g(X, is_out_gg(X, 1)) -> U2_g(X, my_is_in_g(X)) U2_g(X, my_is_out_g(X)) -> my_is_out_g(X) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (66) Obligation: Pi DP problem: The TRS P consists of the following rules: MY_IS_IN_G(X) -> U1_G(X, is_in_gg(X, 1)) MY_IS_IN_G(X) -> IS_IN_GG(X, 1) U1_G(X, is_out_gg(X, 1)) -> U2_G(X, my_is_in_g(X)) U1_G(X, is_out_gg(X, 1)) -> MY_IS_IN_G(X) The TRS R consists of the following rules: my_is_in_g(X) -> U1_g(X, is_in_gg(X, 1)) is_in_gg(X0, X1) -> is_out_gg(X0, X1) U1_g(X, is_out_gg(X, 1)) -> U2_g(X, my_is_in_g(X)) U2_g(X, my_is_out_g(X)) -> my_is_out_g(X) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (67) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 2 less nodes. ---------------------------------------- (68) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_G(X, is_out_gg(X, 1)) -> MY_IS_IN_G(X) MY_IS_IN_G(X) -> U1_G(X, is_in_gg(X, 1)) The TRS R consists of the following rules: my_is_in_g(X) -> U1_g(X, is_in_gg(X, 1)) is_in_gg(X0, X1) -> is_out_gg(X0, X1) U1_g(X, is_out_gg(X, 1)) -> U2_g(X, my_is_in_g(X)) U2_g(X, my_is_out_g(X)) -> my_is_out_g(X) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (69) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (70) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_G(X, is_out_gg(X, 1)) -> MY_IS_IN_G(X) MY_IS_IN_G(X) -> U1_G(X, is_in_gg(X, 1)) The TRS R consists of the following rules: is_in_gg(X0, X1) -> is_out_gg(X0, X1) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (71) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (72) Obligation: Q DP problem: The TRS P consists of the following rules: U1_G(X, is_out_gg(X, 1)) -> MY_IS_IN_G(X) MY_IS_IN_G(X) -> U1_G(X, is_in_gg(X, 1)) The TRS R consists of the following rules: is_in_gg(X0, X1) -> is_out_gg(X0, X1) The set Q consists of the following terms: is_in_gg(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (73) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule MY_IS_IN_G(X) -> U1_G(X, is_in_gg(X, 1)) at position [1] we obtained the following new rules [LPAR04]: (MY_IS_IN_G(X) -> U1_G(X, is_out_gg(X, 1)),MY_IS_IN_G(X) -> U1_G(X, is_out_gg(X, 1))) ---------------------------------------- (74) Obligation: Q DP problem: The TRS P consists of the following rules: U1_G(X, is_out_gg(X, 1)) -> MY_IS_IN_G(X) MY_IS_IN_G(X) -> U1_G(X, is_out_gg(X, 1)) The TRS R consists of the following rules: is_in_gg(X0, X1) -> is_out_gg(X0, X1) The set Q consists of the following terms: is_in_gg(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (75) 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. ---------------------------------------- (76) Obligation: Q DP problem: The TRS P consists of the following rules: U1_G(X, is_out_gg(X, 1)) -> MY_IS_IN_G(X) MY_IS_IN_G(X) -> U1_G(X, is_out_gg(X, 1)) R is empty. The set Q consists of the following terms: is_in_gg(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (77) 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_gg(x0, x1) ---------------------------------------- (78) Obligation: Q DP problem: The TRS P consists of the following rules: U1_G(X, is_out_gg(X, 1)) -> MY_IS_IN_G(X) MY_IS_IN_G(X) -> U1_G(X, is_out_gg(X, 1)) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (79) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by narrowing to the left: s = MY_IS_IN_G(X') evaluates to t =MY_IS_IN_G(X') Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence MY_IS_IN_G(X') -> U1_G(X', is_out_gg(X', 1)) with rule MY_IS_IN_G(X'') -> U1_G(X'', is_out_gg(X'', 1)) at position [] and matcher [X'' / X'] U1_G(X', is_out_gg(X', 1)) -> MY_IS_IN_G(X') with rule U1_G(X, is_out_gg(X, 1)) -> MY_IS_IN_G(X) Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence All these steps are and every following step will be a correct step w.r.t to Q. ---------------------------------------- (80) NO ---------------------------------------- (81) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 3, "program": { "directives": [], "clauses": [[ "(my_is X)", "(',' (is X (1)) (my_is X))" ]] }, "graph": { "nodes": { "11": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T3"], "free": [], "exprvars": [] } }, "12": { "goal": [{ "clause": 0, "scope": 2, "term": "(my_is T4)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T4", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "1" }, "operation": "=" }] }, "ground": ["T4"], "free": [], "exprvars": ["T4"] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(my_is T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "4": { "goal": [{ "clause": 0, "scope": 1, "term": "(my_is T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "15": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is T7 (1)) (my_is T7))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T4", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "1" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "1" }, "operation": "=" } ] }, "ground": ["T7"], "free": [], "exprvars": [ "T4", "T7" ] } }, "16": { "goal": [{ "clause": -1, "scope": -1, "term": "(my_is T8)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T4", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "1" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "1" }, "operation": "=" }, { "lhs": { "name": "T8", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "1" }, "operation": "=" } ] }, "ground": [ "T7", "T8" ], "free": [], "exprvars": [ "T4", "T7", "T8" ] } }, "17": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T4", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "1" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "1" }, "operation": "=" } ] }, "ground": ["T7"], "free": [], "exprvars": [ "T4", "T7" ] } }, "7": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is T3 (1)) (my_is T3))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T3"], "free": [], "exprvars": [] } }, "type": "Nodes", "10": { "goal": [{ "clause": -1, "scope": -1, "term": "(my_is T4)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T4", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "1" }, "operation": "=" }] }, "ground": [ "T4", "T3" ], "free": [], "exprvars": ["T4"] } } }, "edges": [ { "from": 3, "to": 4, "label": "CASE" }, { "from": 4, "to": 7, "label": "ONLY EVAL with clause\nmy_is(X2) :- ','(is(X2, 1), my_is(X2)).\nand substitutionT1 -> T3,\nX2 -> T3" }, { "from": 7, "to": 10, "label": "\nT3 -> T4" }, { "from": 7, "to": 11, "label": "IS FAIL" }, { "from": 10, "to": 12, "label": "CASE" }, { "from": 12, "to": 15, "label": "ONLY EVAL with clause\nmy_is(X5) :- ','(is(X5, 1), my_is(X5)).\nand substitutionT4 -> T7,\nX5 -> T7" }, { "from": 15, "to": 16, "label": "\nT7 -> T8" }, { "from": 15, "to": 17, "label": "IS FAIL" }, { "from": 16, "to": 3, "label": "INSTANCE with matching:\nT1 -> T8" } ], "type": "Graph" } } ---------------------------------------- (82) Obligation: Triples: my_isA(X1) :- my_isA(X2). Clauses: my_iscA(X1) :- my_iscA(X2). Afs: my_isA(x1) = my_isA(x1) ---------------------------------------- (83) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: my_isA_in_1: (b) (f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: MY_ISA_IN_G(X1) -> U1_G(X1, my_isA_in_a(X2)) MY_ISA_IN_G(X1) -> MY_ISA_IN_A(X2) MY_ISA_IN_A(X1) -> U1_A(X1, my_isA_in_a(X2)) MY_ISA_IN_A(X1) -> MY_ISA_IN_A(X2) R is empty. The argument filtering Pi contains the following mapping: my_isA_in_a(x1) = my_isA_in_a MY_ISA_IN_G(x1) = MY_ISA_IN_G(x1) U1_G(x1, x2) = U1_G(x1, x2) MY_ISA_IN_A(x1) = MY_ISA_IN_A U1_A(x1, x2) = U1_A(x2) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (84) Obligation: Pi DP problem: The TRS P consists of the following rules: MY_ISA_IN_G(X1) -> U1_G(X1, my_isA_in_a(X2)) MY_ISA_IN_G(X1) -> MY_ISA_IN_A(X2) MY_ISA_IN_A(X1) -> U1_A(X1, my_isA_in_a(X2)) MY_ISA_IN_A(X1) -> MY_ISA_IN_A(X2) R is empty. The argument filtering Pi contains the following mapping: my_isA_in_a(x1) = my_isA_in_a MY_ISA_IN_G(x1) = MY_ISA_IN_G(x1) U1_G(x1, x2) = U1_G(x1, x2) MY_ISA_IN_A(x1) = MY_ISA_IN_A U1_A(x1, x2) = U1_A(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (85) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 3 less nodes. ---------------------------------------- (86) Obligation: Pi DP problem: The TRS P consists of the following rules: MY_ISA_IN_A(X1) -> MY_ISA_IN_A(X2) R is empty. The argument filtering Pi contains the following mapping: MY_ISA_IN_A(x1) = MY_ISA_IN_A We have to consider all (P,R,Pi)-chains ---------------------------------------- (87) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (88) Obligation: Q DP problem: The TRS P consists of the following rules: MY_ISA_IN_A -> MY_ISA_IN_A R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (89) 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 = MY_ISA_IN_A evaluates to t =MY_ISA_IN_A 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 MY_ISA_IN_A to MY_ISA_IN_A. ---------------------------------------- (90) NO ---------------------------------------- (91) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 1, "program": { "directives": [], "clauses": [[ "(my_is X)", "(',' (is X (1)) (my_is X))" ]] }, "graph": { "nodes": { "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(my_is T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "2": { "goal": [{ "clause": 0, "scope": 1, "term": "(my_is T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "18": { "goal": [{ "clause": -1, "scope": -1, "term": "(my_is T5)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T5", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "1" }, "operation": "=" }] }, "ground": [ "T4", "T5" ], "free": [], "exprvars": ["T5"] } }, "8": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is T4 (1)) (my_is T4))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T4"], "free": [], "exprvars": [] } }, "19": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T4"], "free": [], "exprvars": [] } }, "type": "Nodes" }, "edges": [ { "from": 1, "to": 2, "label": "CASE" }, { "from": 2, "to": 8, "label": "ONLY EVAL with clause\nmy_is(X3) :- ','(is(X3, 1), my_is(X3)).\nand substitutionT1 -> T4,\nX3 -> T4" }, { "from": 8, "to": 18, "label": "\nT4 -> T5" }, { "from": 8, "to": 19, "label": "IS FAIL" }, { "from": 18, "to": 1, "label": "INSTANCE with matching:\nT1 -> T5" } ], "type": "Graph" } } ---------------------------------------- (92) Obligation: Rules: f2_out(T1) -> f1_out(T1) :|: TRUE f1_in(x) -> f2_in(x) :|: TRUE f8_in(T5) -> f18_in(T5, T4) :|: T5 = 1 f18_out(x1, x2) -> f8_out(x1) :|: TRUE f8_in(x3) -> f19_in(x3) :|: !(x3 = 1) f19_out(x4) -> f8_out(x4) :|: TRUE f2_in(x5) -> f8_in(x5) :|: TRUE f8_out(x6) -> f2_out(x6) :|: TRUE f18_in(x7, x8) -> f1_in(x7) :|: TRUE f1_out(x9) -> f18_out(x9, x10) :|: TRUE Start term: f1_in(T1) ---------------------------------------- (93) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f1_in(x) -> f2_in(x) :|: TRUE f8_in(T5) -> f18_in(T5, T4) :|: T5 = 1 f2_in(x5) -> f8_in(x5) :|: TRUE f18_in(x7, x8) -> f1_in(x7) :|: TRUE ---------------------------------------- (94) Obligation: Rules: f1_in(x) -> f2_in(x) :|: TRUE f8_in(T5) -> f18_in(T5, T4) :|: T5 = 1 f2_in(x5) -> f8_in(x5) :|: TRUE f18_in(x7, x8) -> f1_in(x7) :|: TRUE ---------------------------------------- (95) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (96) Obligation: Rules: f1_in(cons_1) -> f1_in(1) :|: TRUE && cons_1 = 1 ---------------------------------------- (97) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (98) Obligation: Rules: f1_in(cons_1) -> f1_in(1) :|: TRUE && cons_1 = 1 ---------------------------------------- (99) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f1_in(cons_1) -> f1_in(1) :|: TRUE && cons_1 = 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (100) Obligation: Termination digraph: Nodes: (1) f1_in(cons_1) -> f1_in(1) :|: TRUE && cons_1 = 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (101) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (102) Obligation: Rules: f1_in(cons_1) -> f1_in(1) :|: TRUE && cons_1 = 1 ---------------------------------------- (103) IRSwTToIntTRSProof (SOUND) Applied path-length measure to transform intTRS with terms to intTRS. ---------------------------------------- (104) Obligation: Rules: f1_in(cons_1) -> f1_in(1) :|: TRUE && cons_1 = 1 ---------------------------------------- (105) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (106) Obligation: Rules: f1_in(cons_1) -> f1_in(1) :|: TRUE && cons_1 = 1 ---------------------------------------- (107) IntTRSNonPeriodicNontermProof (COMPLETE) Normalized system to the following form: f(pc, cons_1) -> f(1, 1) :|: pc = 1 && (TRUE && cons_1 = 1) Proved unsatisfiability of the following formula, indicating that the system is never left after entering: (((run2_0 = ((1 * 1)) and run2_1 = ((1 * 1))) and (((run1_0 * 1)) = ((1 * 1)) and (T and ((run1_1 * 1)) = ((1 * 1))))) and !(((run2_0 * 1)) = ((1 * 1)) and (T and ((run2_1 * 1)) = ((1 * 1))))) Proved satisfiability of the following formula, indicating that the system is entered at least once: ((run2_0 = ((1 * 1)) and run2_1 = ((1 * 1))) and (((run1_0 * 1)) = ((1 * 1)) and (T and ((run1_1 * 1)) = ((1 * 1))))) ---------------------------------------- (108) NO