5.62/2.39 MAYBE 5.62/2.41 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 5.62/2.41 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.62/2.41 5.62/2.41 5.62/2.41 Left Termination of the query pattern 5.62/2.41 5.62/2.41 select(g,a,a) 5.62/2.41 5.62/2.41 w.r.t. the given Prolog program could not be shown: 5.62/2.41 5.62/2.41 (0) Prolog 5.62/2.41 (1) PrologToPiTRSProof [SOUND, 0 ms] 5.62/2.41 (2) PiTRS 5.62/2.41 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 5.62/2.41 (4) PiDP 5.62/2.41 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 5.62/2.41 (6) PiDP 5.62/2.41 (7) UsableRulesProof [EQUIVALENT, 1 ms] 5.62/2.41 (8) PiDP 5.62/2.41 (9) PiDPToQDPProof [SOUND, 0 ms] 5.62/2.41 (10) QDP 5.62/2.41 (11) PrologToPiTRSProof [SOUND, 0 ms] 5.62/2.41 (12) PiTRS 5.62/2.41 (13) DependencyPairsProof [EQUIVALENT, 0 ms] 5.62/2.41 (14) PiDP 5.62/2.41 (15) DependencyGraphProof [EQUIVALENT, 0 ms] 5.62/2.41 (16) PiDP 5.62/2.41 (17) UsableRulesProof [EQUIVALENT, 0 ms] 5.62/2.41 (18) PiDP 5.62/2.41 (19) PiDPToQDPProof [SOUND, 0 ms] 5.62/2.41 (20) QDP 5.62/2.41 (21) PrologToTRSTransformerProof [SOUND, 0 ms] 5.62/2.41 (22) QTRS 5.62/2.41 (23) DependencyPairsProof [EQUIVALENT, 2 ms] 5.62/2.41 (24) QDP 5.62/2.41 (25) DependencyGraphProof [EQUIVALENT, 0 ms] 5.62/2.41 (26) QDP 5.62/2.41 (27) MNOCProof [EQUIVALENT, 0 ms] 5.62/2.41 (28) QDP 5.62/2.41 (29) UsableRulesProof [EQUIVALENT, 0 ms] 5.62/2.41 (30) QDP 5.62/2.41 (31) QReductionProof [EQUIVALENT, 0 ms] 5.62/2.41 (32) QDP 5.62/2.41 (33) PrologToIRSwTTransformerProof [SOUND, 0 ms] 5.62/2.41 (34) IRSwT 5.62/2.41 (35) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] 5.62/2.41 (36) IRSwT 5.62/2.41 (37) IntTRSCompressionProof [EQUIVALENT, 19 ms] 5.62/2.41 (38) IRSwT 5.62/2.41 (39) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 5.62/2.41 (40) IRSwT 5.62/2.41 (41) IRSwTTerminationDigraphProof [EQUIVALENT, 5 ms] 5.62/2.41 (42) IRSwT 5.62/2.41 (43) FilterProof [EQUIVALENT, 0 ms] 5.62/2.41 (44) IntTRS 5.62/2.41 (45) IntTRSPeriodicNontermProof [COMPLETE, 0 ms] 5.62/2.41 (46) NO 5.62/2.41 (47) PrologToDTProblemTransformerProof [SOUND, 0 ms] 5.62/2.41 (48) TRIPLES 5.62/2.41 (49) TriplesToPiDPProof [SOUND, 0 ms] 5.62/2.41 (50) PiDP 5.62/2.41 (51) DependencyGraphProof [EQUIVALENT, 0 ms] 5.62/2.41 (52) PiDP 5.62/2.41 (53) PiDPToQDPProof [SOUND, 0 ms] 5.62/2.41 (54) QDP 5.62/2.41 5.62/2.41 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (0) 5.62/2.41 Obligation: 5.62/2.41 Clauses: 5.62/2.41 5.62/2.41 select(X, .(X, Xs), Xs). 5.62/2.41 select(X, .(Y, Xs), .(Y, Zs)) :- select(X, Xs, Zs). 5.62/2.41 5.62/2.41 5.62/2.41 Query: select(g,a,a) 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (1) PrologToPiTRSProof (SOUND) 5.62/2.41 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 5.62/2.41 5.62/2.41 select_in_3: (b,f,f) 5.62/2.41 5.62/2.41 Transforming Prolog into the following Term Rewriting System: 5.62/2.41 5.62/2.41 Pi-finite rewrite system: 5.62/2.41 The TRS R consists of the following rules: 5.62/2.41 5.62/2.41 select_in_gaa(X, .(X, Xs), Xs) -> select_out_gaa(X, .(X, Xs), Xs) 5.62/2.41 select_in_gaa(X, .(Y, Xs), .(Y, Zs)) -> U1_gaa(X, Y, Xs, Zs, select_in_gaa(X, Xs, Zs)) 5.62/2.41 U1_gaa(X, Y, Xs, Zs, select_out_gaa(X, Xs, Zs)) -> select_out_gaa(X, .(Y, Xs), .(Y, Zs)) 5.62/2.41 5.62/2.41 The argument filtering Pi contains the following mapping: 5.62/2.41 select_in_gaa(x1, x2, x3) = select_in_gaa(x1) 5.62/2.41 5.62/2.41 select_out_gaa(x1, x2, x3) = select_out_gaa 5.62/2.41 5.62/2.41 U1_gaa(x1, x2, x3, x4, x5) = U1_gaa(x5) 5.62/2.41 5.62/2.41 5.62/2.41 5.62/2.41 5.62/2.41 5.62/2.41 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 5.62/2.41 5.62/2.41 5.62/2.41 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (2) 5.62/2.41 Obligation: 5.62/2.41 Pi-finite rewrite system: 5.62/2.41 The TRS R consists of the following rules: 5.62/2.41 5.62/2.41 select_in_gaa(X, .(X, Xs), Xs) -> select_out_gaa(X, .(X, Xs), Xs) 5.62/2.41 select_in_gaa(X, .(Y, Xs), .(Y, Zs)) -> U1_gaa(X, Y, Xs, Zs, select_in_gaa(X, Xs, Zs)) 5.62/2.41 U1_gaa(X, Y, Xs, Zs, select_out_gaa(X, Xs, Zs)) -> select_out_gaa(X, .(Y, Xs), .(Y, Zs)) 5.62/2.41 5.62/2.41 The argument filtering Pi contains the following mapping: 5.62/2.41 select_in_gaa(x1, x2, x3) = select_in_gaa(x1) 5.62/2.41 5.62/2.41 select_out_gaa(x1, x2, x3) = select_out_gaa 5.62/2.41 5.62/2.41 U1_gaa(x1, x2, x3, x4, x5) = U1_gaa(x5) 5.62/2.41 5.62/2.41 5.62/2.41 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (3) DependencyPairsProof (EQUIVALENT) 5.62/2.41 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 5.62/2.41 Pi DP problem: 5.62/2.41 The TRS P consists of the following rules: 5.62/2.41 5.62/2.41 SELECT_IN_GAA(X, .(Y, Xs), .(Y, Zs)) -> U1_GAA(X, Y, Xs, Zs, select_in_gaa(X, Xs, Zs)) 5.62/2.41 SELECT_IN_GAA(X, .(Y, Xs), .(Y, Zs)) -> SELECT_IN_GAA(X, Xs, Zs) 5.62/2.41 5.62/2.41 The TRS R consists of the following rules: 5.62/2.41 5.62/2.41 select_in_gaa(X, .(X, Xs), Xs) -> select_out_gaa(X, .(X, Xs), Xs) 5.62/2.41 select_in_gaa(X, .(Y, Xs), .(Y, Zs)) -> U1_gaa(X, Y, Xs, Zs, select_in_gaa(X, Xs, Zs)) 5.62/2.41 U1_gaa(X, Y, Xs, Zs, select_out_gaa(X, Xs, Zs)) -> select_out_gaa(X, .(Y, Xs), .(Y, Zs)) 5.62/2.41 5.62/2.41 The argument filtering Pi contains the following mapping: 5.62/2.41 select_in_gaa(x1, x2, x3) = select_in_gaa(x1) 5.62/2.41 5.62/2.41 select_out_gaa(x1, x2, x3) = select_out_gaa 5.62/2.41 5.62/2.41 U1_gaa(x1, x2, x3, x4, x5) = U1_gaa(x5) 5.62/2.41 5.62/2.41 SELECT_IN_GAA(x1, x2, x3) = SELECT_IN_GAA(x1) 5.62/2.41 5.62/2.41 U1_GAA(x1, x2, x3, x4, x5) = U1_GAA(x5) 5.62/2.41 5.62/2.41 5.62/2.41 We have to consider all (P,R,Pi)-chains 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (4) 5.62/2.41 Obligation: 5.62/2.41 Pi DP problem: 5.62/2.41 The TRS P consists of the following rules: 5.62/2.41 5.62/2.41 SELECT_IN_GAA(X, .(Y, Xs), .(Y, Zs)) -> U1_GAA(X, Y, Xs, Zs, select_in_gaa(X, Xs, Zs)) 5.62/2.41 SELECT_IN_GAA(X, .(Y, Xs), .(Y, Zs)) -> SELECT_IN_GAA(X, Xs, Zs) 5.62/2.41 5.62/2.41 The TRS R consists of the following rules: 5.62/2.41 5.62/2.41 select_in_gaa(X, .(X, Xs), Xs) -> select_out_gaa(X, .(X, Xs), Xs) 5.62/2.41 select_in_gaa(X, .(Y, Xs), .(Y, Zs)) -> U1_gaa(X, Y, Xs, Zs, select_in_gaa(X, Xs, Zs)) 5.62/2.41 U1_gaa(X, Y, Xs, Zs, select_out_gaa(X, Xs, Zs)) -> select_out_gaa(X, .(Y, Xs), .(Y, Zs)) 5.62/2.41 5.62/2.41 The argument filtering Pi contains the following mapping: 5.62/2.41 select_in_gaa(x1, x2, x3) = select_in_gaa(x1) 5.62/2.41 5.62/2.41 select_out_gaa(x1, x2, x3) = select_out_gaa 5.62/2.41 5.62/2.41 U1_gaa(x1, x2, x3, x4, x5) = U1_gaa(x5) 5.62/2.41 5.62/2.41 SELECT_IN_GAA(x1, x2, x3) = SELECT_IN_GAA(x1) 5.62/2.41 5.62/2.41 U1_GAA(x1, x2, x3, x4, x5) = U1_GAA(x5) 5.62/2.41 5.62/2.41 5.62/2.41 We have to consider all (P,R,Pi)-chains 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (5) DependencyGraphProof (EQUIVALENT) 5.62/2.41 The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 1 less node. 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (6) 5.62/2.41 Obligation: 5.62/2.41 Pi DP problem: 5.62/2.41 The TRS P consists of the following rules: 5.62/2.41 5.62/2.41 SELECT_IN_GAA(X, .(Y, Xs), .(Y, Zs)) -> SELECT_IN_GAA(X, Xs, Zs) 5.62/2.41 5.62/2.41 The TRS R consists of the following rules: 5.62/2.41 5.62/2.41 select_in_gaa(X, .(X, Xs), Xs) -> select_out_gaa(X, .(X, Xs), Xs) 5.62/2.41 select_in_gaa(X, .(Y, Xs), .(Y, Zs)) -> U1_gaa(X, Y, Xs, Zs, select_in_gaa(X, Xs, Zs)) 5.62/2.41 U1_gaa(X, Y, Xs, Zs, select_out_gaa(X, Xs, Zs)) -> select_out_gaa(X, .(Y, Xs), .(Y, Zs)) 5.62/2.41 5.62/2.41 The argument filtering Pi contains the following mapping: 5.62/2.41 select_in_gaa(x1, x2, x3) = select_in_gaa(x1) 5.62/2.41 5.62/2.41 select_out_gaa(x1, x2, x3) = select_out_gaa 5.62/2.41 5.62/2.41 U1_gaa(x1, x2, x3, x4, x5) = U1_gaa(x5) 5.62/2.41 5.62/2.41 SELECT_IN_GAA(x1, x2, x3) = SELECT_IN_GAA(x1) 5.62/2.41 5.62/2.41 5.62/2.41 We have to consider all (P,R,Pi)-chains 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (7) UsableRulesProof (EQUIVALENT) 5.62/2.41 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (8) 5.62/2.41 Obligation: 5.62/2.41 Pi DP problem: 5.62/2.41 The TRS P consists of the following rules: 5.62/2.41 5.62/2.41 SELECT_IN_GAA(X, .(Y, Xs), .(Y, Zs)) -> SELECT_IN_GAA(X, Xs, Zs) 5.62/2.41 5.62/2.41 R is empty. 5.62/2.41 The argument filtering Pi contains the following mapping: 5.62/2.41 SELECT_IN_GAA(x1, x2, x3) = SELECT_IN_GAA(x1) 5.62/2.41 5.62/2.41 5.62/2.41 We have to consider all (P,R,Pi)-chains 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (9) PiDPToQDPProof (SOUND) 5.62/2.41 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (10) 5.62/2.41 Obligation: 5.62/2.41 Q DP problem: 5.62/2.41 The TRS P consists of the following rules: 5.62/2.41 5.62/2.41 SELECT_IN_GAA(X) -> SELECT_IN_GAA(X) 5.62/2.41 5.62/2.41 R is empty. 5.62/2.41 Q is empty. 5.62/2.41 We have to consider all (P,Q,R)-chains. 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (11) PrologToPiTRSProof (SOUND) 5.62/2.41 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 5.62/2.41 5.62/2.41 select_in_3: (b,f,f) 5.62/2.41 5.62/2.41 Transforming Prolog into the following Term Rewriting System: 5.62/2.41 5.62/2.41 Pi-finite rewrite system: 5.62/2.41 The TRS R consists of the following rules: 5.62/2.41 5.62/2.41 select_in_gaa(X, .(X, Xs), Xs) -> select_out_gaa(X, .(X, Xs), Xs) 5.62/2.41 select_in_gaa(X, .(Y, Xs), .(Y, Zs)) -> U1_gaa(X, Y, Xs, Zs, select_in_gaa(X, Xs, Zs)) 5.62/2.41 U1_gaa(X, Y, Xs, Zs, select_out_gaa(X, Xs, Zs)) -> select_out_gaa(X, .(Y, Xs), .(Y, Zs)) 5.62/2.41 5.62/2.41 The argument filtering Pi contains the following mapping: 5.62/2.41 select_in_gaa(x1, x2, x3) = select_in_gaa(x1) 5.62/2.41 5.62/2.41 select_out_gaa(x1, x2, x3) = select_out_gaa(x1) 5.62/2.41 5.62/2.41 U1_gaa(x1, x2, x3, x4, x5) = U1_gaa(x1, x5) 5.62/2.41 5.62/2.41 5.62/2.41 5.62/2.41 5.62/2.41 5.62/2.41 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 5.62/2.41 5.62/2.41 5.62/2.41 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (12) 5.62/2.41 Obligation: 5.62/2.41 Pi-finite rewrite system: 5.62/2.41 The TRS R consists of the following rules: 5.62/2.41 5.62/2.41 select_in_gaa(X, .(X, Xs), Xs) -> select_out_gaa(X, .(X, Xs), Xs) 5.62/2.41 select_in_gaa(X, .(Y, Xs), .(Y, Zs)) -> U1_gaa(X, Y, Xs, Zs, select_in_gaa(X, Xs, Zs)) 5.62/2.41 U1_gaa(X, Y, Xs, Zs, select_out_gaa(X, Xs, Zs)) -> select_out_gaa(X, .(Y, Xs), .(Y, Zs)) 5.62/2.41 5.62/2.41 The argument filtering Pi contains the following mapping: 5.62/2.41 select_in_gaa(x1, x2, x3) = select_in_gaa(x1) 5.62/2.41 5.62/2.41 select_out_gaa(x1, x2, x3) = select_out_gaa(x1) 5.62/2.41 5.62/2.41 U1_gaa(x1, x2, x3, x4, x5) = U1_gaa(x1, x5) 5.62/2.41 5.62/2.41 5.62/2.41 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (13) DependencyPairsProof (EQUIVALENT) 5.62/2.41 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 5.62/2.41 Pi DP problem: 5.62/2.41 The TRS P consists of the following rules: 5.62/2.41 5.62/2.41 SELECT_IN_GAA(X, .(Y, Xs), .(Y, Zs)) -> U1_GAA(X, Y, Xs, Zs, select_in_gaa(X, Xs, Zs)) 5.62/2.41 SELECT_IN_GAA(X, .(Y, Xs), .(Y, Zs)) -> SELECT_IN_GAA(X, Xs, Zs) 5.62/2.41 5.62/2.41 The TRS R consists of the following rules: 5.62/2.41 5.62/2.41 select_in_gaa(X, .(X, Xs), Xs) -> select_out_gaa(X, .(X, Xs), Xs) 5.62/2.41 select_in_gaa(X, .(Y, Xs), .(Y, Zs)) -> U1_gaa(X, Y, Xs, Zs, select_in_gaa(X, Xs, Zs)) 5.62/2.41 U1_gaa(X, Y, Xs, Zs, select_out_gaa(X, Xs, Zs)) -> select_out_gaa(X, .(Y, Xs), .(Y, Zs)) 5.62/2.41 5.62/2.41 The argument filtering Pi contains the following mapping: 5.62/2.41 select_in_gaa(x1, x2, x3) = select_in_gaa(x1) 5.62/2.41 5.62/2.41 select_out_gaa(x1, x2, x3) = select_out_gaa(x1) 5.62/2.41 5.62/2.41 U1_gaa(x1, x2, x3, x4, x5) = U1_gaa(x1, x5) 5.62/2.41 5.62/2.41 SELECT_IN_GAA(x1, x2, x3) = SELECT_IN_GAA(x1) 5.62/2.41 5.62/2.41 U1_GAA(x1, x2, x3, x4, x5) = U1_GAA(x1, x5) 5.62/2.41 5.62/2.41 5.62/2.41 We have to consider all (P,R,Pi)-chains 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (14) 5.62/2.41 Obligation: 5.62/2.41 Pi DP problem: 5.62/2.41 The TRS P consists of the following rules: 5.62/2.41 5.62/2.41 SELECT_IN_GAA(X, .(Y, Xs), .(Y, Zs)) -> U1_GAA(X, Y, Xs, Zs, select_in_gaa(X, Xs, Zs)) 5.62/2.41 SELECT_IN_GAA(X, .(Y, Xs), .(Y, Zs)) -> SELECT_IN_GAA(X, Xs, Zs) 5.62/2.41 5.62/2.41 The TRS R consists of the following rules: 5.62/2.41 5.62/2.41 select_in_gaa(X, .(X, Xs), Xs) -> select_out_gaa(X, .(X, Xs), Xs) 5.62/2.41 select_in_gaa(X, .(Y, Xs), .(Y, Zs)) -> U1_gaa(X, Y, Xs, Zs, select_in_gaa(X, Xs, Zs)) 5.62/2.41 U1_gaa(X, Y, Xs, Zs, select_out_gaa(X, Xs, Zs)) -> select_out_gaa(X, .(Y, Xs), .(Y, Zs)) 5.62/2.41 5.62/2.41 The argument filtering Pi contains the following mapping: 5.62/2.41 select_in_gaa(x1, x2, x3) = select_in_gaa(x1) 5.62/2.41 5.62/2.41 select_out_gaa(x1, x2, x3) = select_out_gaa(x1) 5.62/2.41 5.62/2.41 U1_gaa(x1, x2, x3, x4, x5) = U1_gaa(x1, x5) 5.62/2.41 5.62/2.41 SELECT_IN_GAA(x1, x2, x3) = SELECT_IN_GAA(x1) 5.62/2.41 5.62/2.41 U1_GAA(x1, x2, x3, x4, x5) = U1_GAA(x1, x5) 5.62/2.41 5.62/2.41 5.62/2.41 We have to consider all (P,R,Pi)-chains 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (15) DependencyGraphProof (EQUIVALENT) 5.62/2.41 The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 1 less node. 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (16) 5.62/2.41 Obligation: 5.62/2.41 Pi DP problem: 5.62/2.41 The TRS P consists of the following rules: 5.62/2.41 5.62/2.41 SELECT_IN_GAA(X, .(Y, Xs), .(Y, Zs)) -> SELECT_IN_GAA(X, Xs, Zs) 5.62/2.41 5.62/2.41 The TRS R consists of the following rules: 5.62/2.41 5.62/2.41 select_in_gaa(X, .(X, Xs), Xs) -> select_out_gaa(X, .(X, Xs), Xs) 5.62/2.41 select_in_gaa(X, .(Y, Xs), .(Y, Zs)) -> U1_gaa(X, Y, Xs, Zs, select_in_gaa(X, Xs, Zs)) 5.62/2.41 U1_gaa(X, Y, Xs, Zs, select_out_gaa(X, Xs, Zs)) -> select_out_gaa(X, .(Y, Xs), .(Y, Zs)) 5.62/2.41 5.62/2.41 The argument filtering Pi contains the following mapping: 5.62/2.41 select_in_gaa(x1, x2, x3) = select_in_gaa(x1) 5.62/2.41 5.62/2.41 select_out_gaa(x1, x2, x3) = select_out_gaa(x1) 5.62/2.41 5.62/2.41 U1_gaa(x1, x2, x3, x4, x5) = U1_gaa(x1, x5) 5.62/2.41 5.62/2.41 SELECT_IN_GAA(x1, x2, x3) = SELECT_IN_GAA(x1) 5.62/2.41 5.62/2.41 5.62/2.41 We have to consider all (P,R,Pi)-chains 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (17) UsableRulesProof (EQUIVALENT) 5.62/2.41 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (18) 5.62/2.41 Obligation: 5.62/2.41 Pi DP problem: 5.62/2.41 The TRS P consists of the following rules: 5.62/2.41 5.62/2.41 SELECT_IN_GAA(X, .(Y, Xs), .(Y, Zs)) -> SELECT_IN_GAA(X, Xs, Zs) 5.62/2.41 5.62/2.41 R is empty. 5.62/2.41 The argument filtering Pi contains the following mapping: 5.62/2.41 SELECT_IN_GAA(x1, x2, x3) = SELECT_IN_GAA(x1) 5.62/2.41 5.62/2.41 5.62/2.41 We have to consider all (P,R,Pi)-chains 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (19) PiDPToQDPProof (SOUND) 5.62/2.41 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (20) 5.62/2.41 Obligation: 5.62/2.41 Q DP problem: 5.62/2.41 The TRS P consists of the following rules: 5.62/2.41 5.62/2.41 SELECT_IN_GAA(X) -> SELECT_IN_GAA(X) 5.62/2.41 5.62/2.41 R is empty. 5.62/2.41 Q is empty. 5.62/2.41 We have to consider all (P,Q,R)-chains. 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (21) PrologToTRSTransformerProof (SOUND) 5.62/2.41 Transformed Prolog program to TRS. 5.62/2.41 5.62/2.41 { 5.62/2.41 "root": 3, 5.62/2.41 "program": { 5.62/2.41 "directives": [], 5.62/2.41 "clauses": [ 5.62/2.41 [ 5.62/2.41 "(select X (. X Xs) Xs)", 5.62/2.41 null 5.62/2.41 ], 5.62/2.41 [ 5.62/2.41 "(select X (. Y Xs) (. Y Zs))", 5.62/2.41 "(select X Xs Zs)" 5.62/2.41 ] 5.62/2.41 ] 5.62/2.41 }, 5.62/2.41 "graph": { 5.62/2.41 "nodes": { 5.62/2.41 "77": { 5.62/2.41 "goal": [], 5.62/2.41 "kb": { 5.62/2.41 "nonunifying": [], 5.62/2.41 "intvars": {}, 5.62/2.41 "arithmetic": { 5.62/2.41 "type": "PlainIntegerRelationState", 5.62/2.41 "relations": [] 5.62/2.41 }, 5.62/2.41 "ground": [], 5.62/2.41 "free": [], 5.62/2.41 "exprvars": [] 5.62/2.41 } 5.62/2.41 }, 5.62/2.41 "3": { 5.62/2.41 "goal": [{ 5.62/2.41 "clause": -1, 5.62/2.41 "scope": -1, 5.62/2.41 "term": "(select T1 T2 T3)" 5.62/2.41 }], 5.62/2.41 "kb": { 5.62/2.41 "nonunifying": [], 5.62/2.41 "intvars": {}, 5.62/2.41 "arithmetic": { 5.62/2.41 "type": "PlainIntegerRelationState", 5.62/2.41 "relations": [] 5.62/2.41 }, 5.62/2.41 "ground": ["T1"], 5.62/2.41 "free": [], 5.62/2.41 "exprvars": [] 5.62/2.41 } 5.62/2.41 }, 5.62/2.41 "14": { 5.62/2.41 "goal": [{ 5.62/2.41 "clause": 0, 5.62/2.41 "scope": 1, 5.62/2.41 "term": "(select T1 T2 T3)" 5.62/2.41 }], 5.62/2.41 "kb": { 5.62/2.41 "nonunifying": [], 5.62/2.41 "intvars": {}, 5.62/2.41 "arithmetic": { 5.62/2.41 "type": "PlainIntegerRelationState", 5.62/2.41 "relations": [] 5.62/2.41 }, 5.62/2.41 "ground": ["T1"], 5.62/2.41 "free": [], 5.62/2.41 "exprvars": [] 5.62/2.41 } 5.62/2.41 }, 5.62/2.41 "15": { 5.62/2.41 "goal": [{ 5.62/2.41 "clause": 1, 5.62/2.41 "scope": 1, 5.62/2.41 "term": "(select T1 T2 T3)" 5.62/2.41 }], 5.62/2.41 "kb": { 5.62/2.41 "nonunifying": [], 5.62/2.41 "intvars": {}, 5.62/2.41 "arithmetic": { 5.62/2.41 "type": "PlainIntegerRelationState", 5.62/2.41 "relations": [] 5.62/2.41 }, 5.62/2.41 "ground": ["T1"], 5.62/2.41 "free": [], 5.62/2.41 "exprvars": [] 5.62/2.41 } 5.62/2.41 }, 5.62/2.41 "6": { 5.62/2.41 "goal": [ 5.62/2.41 { 5.62/2.41 "clause": 0, 5.62/2.41 "scope": 1, 5.62/2.41 "term": "(select T1 T2 T3)" 5.62/2.41 }, 5.62/2.41 { 5.62/2.41 "clause": 1, 5.62/2.41 "scope": 1, 5.62/2.41 "term": "(select T1 T2 T3)" 5.62/2.41 } 5.62/2.41 ], 5.62/2.41 "kb": { 5.62/2.41 "nonunifying": [], 5.62/2.41 "intvars": {}, 5.62/2.41 "arithmetic": { 5.62/2.41 "type": "PlainIntegerRelationState", 5.62/2.41 "relations": [] 5.62/2.41 }, 5.62/2.41 "ground": ["T1"], 5.62/2.41 "free": [], 5.62/2.41 "exprvars": [] 5.62/2.41 } 5.62/2.41 }, 5.62/2.41 "70": { 5.62/2.41 "goal": [{ 5.62/2.41 "clause": -1, 5.62/2.41 "scope": -1, 5.62/2.41 "term": "(true)" 5.62/2.41 }], 5.62/2.41 "kb": { 5.62/2.41 "nonunifying": [], 5.62/2.41 "intvars": {}, 5.62/2.41 "arithmetic": { 5.62/2.41 "type": "PlainIntegerRelationState", 5.62/2.41 "relations": [] 5.62/2.41 }, 5.62/2.41 "ground": [], 5.62/2.41 "free": [], 5.62/2.41 "exprvars": [] 5.62/2.41 } 5.62/2.41 }, 5.62/2.41 "72": { 5.62/2.41 "goal": [], 5.62/2.41 "kb": { 5.62/2.41 "nonunifying": [], 5.62/2.41 "intvars": {}, 5.62/2.41 "arithmetic": { 5.62/2.41 "type": "PlainIntegerRelationState", 5.62/2.41 "relations": [] 5.62/2.41 }, 5.62/2.41 "ground": [], 5.62/2.41 "free": [], 5.62/2.41 "exprvars": [] 5.62/2.41 } 5.62/2.41 }, 5.62/2.41 "type": "Nodes", 5.62/2.41 "73": { 5.62/2.41 "goal": [], 5.62/2.41 "kb": { 5.62/2.41 "nonunifying": [], 5.62/2.41 "intvars": {}, 5.62/2.41 "arithmetic": { 5.62/2.41 "type": "PlainIntegerRelationState", 5.62/2.41 "relations": [] 5.62/2.41 }, 5.62/2.41 "ground": [], 5.62/2.41 "free": [], 5.62/2.41 "exprvars": [] 5.62/2.41 } 5.62/2.41 }, 5.62/2.41 "76": { 5.62/2.41 "goal": [{ 5.62/2.41 "clause": -1, 5.62/2.41 "scope": -1, 5.62/2.41 "term": "(select T22 T26 T27)" 5.62/2.41 }], 5.62/2.41 "kb": { 5.62/2.41 "nonunifying": [], 5.62/2.41 "intvars": {}, 5.62/2.41 "arithmetic": { 5.62/2.41 "type": "PlainIntegerRelationState", 5.62/2.41 "relations": [] 5.62/2.41 }, 5.62/2.41 "ground": ["T22"], 5.62/2.41 "free": [], 5.62/2.41 "exprvars": [] 5.62/2.41 } 5.62/2.41 } 5.62/2.41 }, 5.62/2.41 "edges": [ 5.62/2.41 { 5.62/2.41 "from": 3, 5.62/2.41 "to": 6, 5.62/2.41 "label": "CASE" 5.62/2.41 }, 5.62/2.41 { 5.62/2.41 "from": 6, 5.62/2.41 "to": 14, 5.62/2.41 "label": "PARALLEL" 5.62/2.41 }, 5.62/2.41 { 5.62/2.41 "from": 6, 5.62/2.41 "to": 15, 5.62/2.41 "label": "PARALLEL" 5.62/2.41 }, 5.62/2.41 { 5.62/2.41 "from": 14, 5.62/2.41 "to": 70, 5.62/2.41 "label": "EVAL with clause\nselect(X9, .(X9, X10), X10).\nand substitutionT1 -> T12,\nX9 -> T12,\nX10 -> T13,\nT2 -> .(T12, T13),\nT3 -> T13" 5.62/2.41 }, 5.62/2.41 { 5.62/2.41 "from": 14, 5.62/2.41 "to": 72, 5.62/2.41 "label": "EVAL-BACKTRACK" 5.62/2.41 }, 5.62/2.41 { 5.62/2.41 "from": 15, 5.62/2.41 "to": 76, 5.62/2.41 "label": "EVAL with clause\nselect(X19, .(X20, X21), .(X20, X22)) :- select(X19, X21, X22).\nand substitutionT1 -> T22,\nX19 -> T22,\nX20 -> T23,\nX21 -> T26,\nT2 -> .(T23, T26),\nX22 -> T27,\nT3 -> .(T23, T27),\nT24 -> T26,\nT25 -> T27" 5.62/2.41 }, 5.62/2.41 { 5.62/2.41 "from": 15, 5.62/2.41 "to": 77, 5.62/2.41 "label": "EVAL-BACKTRACK" 5.62/2.41 }, 5.62/2.41 { 5.62/2.41 "from": 70, 5.62/2.41 "to": 73, 5.62/2.41 "label": "SUCCESS" 5.62/2.41 }, 5.62/2.41 { 5.62/2.41 "from": 76, 5.62/2.41 "to": 3, 5.62/2.41 "label": "INSTANCE with matching:\nT1 -> T22\nT2 -> T26\nT3 -> T27" 5.62/2.41 } 5.62/2.41 ], 5.62/2.41 "type": "Graph" 5.62/2.41 } 5.62/2.41 } 5.62/2.41 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (22) 5.62/2.41 Obligation: 5.62/2.41 Q restricted rewrite system: 5.62/2.41 The TRS R consists of the following rules: 5.62/2.41 5.62/2.41 f3_in(T12) -> f3_out1 5.62/2.41 f3_in(T22) -> U1(f3_in(T22), T22) 5.62/2.41 U1(f3_out1, T22) -> f3_out1 5.62/2.41 5.62/2.41 Q is empty. 5.62/2.41 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (23) DependencyPairsProof (EQUIVALENT) 5.62/2.41 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (24) 5.62/2.41 Obligation: 5.62/2.41 Q DP problem: 5.62/2.41 The TRS P consists of the following rules: 5.62/2.41 5.62/2.41 F3_IN(T22) -> U1^1(f3_in(T22), T22) 5.62/2.41 F3_IN(T22) -> F3_IN(T22) 5.62/2.41 5.62/2.41 The TRS R consists of the following rules: 5.62/2.41 5.62/2.41 f3_in(T12) -> f3_out1 5.62/2.41 f3_in(T22) -> U1(f3_in(T22), T22) 5.62/2.41 U1(f3_out1, T22) -> f3_out1 5.62/2.41 5.62/2.41 Q is empty. 5.62/2.41 We have to consider all minimal (P,Q,R)-chains. 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (25) DependencyGraphProof (EQUIVALENT) 5.62/2.41 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (26) 5.62/2.41 Obligation: 5.62/2.41 Q DP problem: 5.62/2.41 The TRS P consists of the following rules: 5.62/2.41 5.62/2.41 F3_IN(T22) -> F3_IN(T22) 5.62/2.41 5.62/2.41 The TRS R consists of the following rules: 5.62/2.41 5.62/2.41 f3_in(T12) -> f3_out1 5.62/2.41 f3_in(T22) -> U1(f3_in(T22), T22) 5.62/2.41 U1(f3_out1, T22) -> f3_out1 5.62/2.41 5.62/2.41 Q is empty. 5.62/2.41 We have to consider all minimal (P,Q,R)-chains. 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (27) MNOCProof (EQUIVALENT) 5.62/2.41 We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (28) 5.62/2.41 Obligation: 5.62/2.41 Q DP problem: 5.62/2.41 The TRS P consists of the following rules: 5.62/2.41 5.62/2.41 F3_IN(T22) -> F3_IN(T22) 5.62/2.41 5.62/2.41 The TRS R consists of the following rules: 5.62/2.41 5.62/2.41 f3_in(T12) -> f3_out1 5.62/2.41 f3_in(T22) -> U1(f3_in(T22), T22) 5.62/2.41 U1(f3_out1, T22) -> f3_out1 5.62/2.41 5.62/2.41 The set Q consists of the following terms: 5.62/2.41 5.62/2.41 f3_in(x0) 5.62/2.41 U1(f3_out1, x0) 5.62/2.41 5.62/2.41 We have to consider all minimal (P,Q,R)-chains. 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (29) UsableRulesProof (EQUIVALENT) 5.62/2.41 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. 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (30) 5.62/2.41 Obligation: 5.62/2.41 Q DP problem: 5.62/2.41 The TRS P consists of the following rules: 5.62/2.41 5.62/2.41 F3_IN(T22) -> F3_IN(T22) 5.62/2.41 5.62/2.41 R is empty. 5.62/2.41 The set Q consists of the following terms: 5.62/2.41 5.62/2.41 f3_in(x0) 5.62/2.41 U1(f3_out1, x0) 5.62/2.41 5.62/2.41 We have to consider all minimal (P,Q,R)-chains. 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (31) QReductionProof (EQUIVALENT) 5.62/2.41 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 5.62/2.41 5.62/2.41 f3_in(x0) 5.62/2.41 U1(f3_out1, x0) 5.62/2.41 5.62/2.41 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (32) 5.62/2.41 Obligation: 5.62/2.41 Q DP problem: 5.62/2.41 The TRS P consists of the following rules: 5.62/2.41 5.62/2.41 F3_IN(T22) -> F3_IN(T22) 5.62/2.41 5.62/2.41 R is empty. 5.62/2.41 Q is empty. 5.62/2.41 We have to consider all minimal (P,Q,R)-chains. 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (33) PrologToIRSwTTransformerProof (SOUND) 5.62/2.41 Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert 5.62/2.41 5.62/2.41 { 5.62/2.41 "root": 2, 5.62/2.41 "program": { 5.62/2.41 "directives": [], 5.62/2.41 "clauses": [ 5.62/2.41 [ 5.62/2.41 "(select X (. X Xs) Xs)", 5.62/2.41 null 5.62/2.41 ], 5.62/2.41 [ 5.62/2.41 "(select X (. Y Xs) (. Y Zs))", 5.62/2.41 "(select X Xs Zs)" 5.62/2.41 ] 5.62/2.41 ] 5.62/2.41 }, 5.62/2.41 "graph": { 5.62/2.41 "nodes": { 5.62/2.41 "88": { 5.62/2.41 "goal": [], 5.62/2.41 "kb": { 5.62/2.41 "nonunifying": [], 5.62/2.41 "intvars": {}, 5.62/2.41 "arithmetic": { 5.62/2.41 "type": "PlainIntegerRelationState", 5.62/2.41 "relations": [] 5.62/2.41 }, 5.62/2.41 "ground": [], 5.62/2.41 "free": [], 5.62/2.41 "exprvars": [] 5.62/2.41 } 5.62/2.41 }, 5.62/2.41 "78": { 5.62/2.41 "goal": [{ 5.62/2.41 "clause": -1, 5.62/2.41 "scope": -1, 5.62/2.41 "term": "(true)" 5.62/2.41 }], 5.62/2.41 "kb": { 5.62/2.41 "nonunifying": [], 5.62/2.41 "intvars": {}, 5.62/2.41 "arithmetic": { 5.62/2.41 "type": "PlainIntegerRelationState", 5.62/2.41 "relations": [] 5.62/2.41 }, 5.62/2.41 "ground": [], 5.62/2.41 "free": [], 5.62/2.41 "exprvars": [] 5.62/2.41 } 5.62/2.41 }, 5.62/2.41 "2": { 5.62/2.41 "goal": [{ 5.62/2.41 "clause": -1, 5.62/2.41 "scope": -1, 5.62/2.41 "term": "(select T1 T2 T3)" 5.62/2.41 }], 5.62/2.41 "kb": { 5.62/2.41 "nonunifying": [], 5.62/2.41 "intvars": {}, 5.62/2.41 "arithmetic": { 5.62/2.41 "type": "PlainIntegerRelationState", 5.62/2.41 "relations": [] 5.62/2.41 }, 5.62/2.41 "ground": ["T1"], 5.62/2.41 "free": [], 5.62/2.41 "exprvars": [] 5.62/2.41 } 5.62/2.41 }, 5.62/2.41 "79": { 5.62/2.41 "goal": [], 5.62/2.41 "kb": { 5.62/2.41 "nonunifying": [], 5.62/2.41 "intvars": {}, 5.62/2.41 "arithmetic": { 5.62/2.41 "type": "PlainIntegerRelationState", 5.62/2.41 "relations": [] 5.62/2.41 }, 5.62/2.41 "ground": [], 5.62/2.41 "free": [], 5.62/2.41 "exprvars": [] 5.62/2.41 } 5.62/2.41 }, 5.62/2.41 "18": { 5.62/2.41 "goal": [{ 5.62/2.41 "clause": 0, 5.62/2.41 "scope": 1, 5.62/2.41 "term": "(select T1 T2 T3)" 5.62/2.41 }], 5.62/2.41 "kb": { 5.62/2.41 "nonunifying": [], 5.62/2.41 "intvars": {}, 5.62/2.41 "arithmetic": { 5.62/2.41 "type": "PlainIntegerRelationState", 5.62/2.41 "relations": [] 5.62/2.41 }, 5.62/2.41 "ground": ["T1"], 5.62/2.41 "free": [], 5.62/2.41 "exprvars": [] 5.62/2.41 } 5.62/2.41 }, 5.62/2.41 "19": { 5.62/2.41 "goal": [{ 5.62/2.41 "clause": 1, 5.62/2.41 "scope": 1, 5.62/2.41 "term": "(select T1 T2 T3)" 5.62/2.41 }], 5.62/2.41 "kb": { 5.62/2.41 "nonunifying": [], 5.62/2.41 "intvars": {}, 5.62/2.41 "arithmetic": { 5.62/2.41 "type": "PlainIntegerRelationState", 5.62/2.41 "relations": [] 5.62/2.41 }, 5.62/2.41 "ground": ["T1"], 5.62/2.41 "free": [], 5.62/2.41 "exprvars": [] 5.62/2.41 } 5.62/2.41 }, 5.62/2.41 "80": { 5.62/2.41 "goal": [], 5.62/2.41 "kb": { 5.62/2.41 "nonunifying": [], 5.62/2.41 "intvars": {}, 5.62/2.41 "arithmetic": { 5.62/2.41 "type": "PlainIntegerRelationState", 5.62/2.41 "relations": [] 5.62/2.41 }, 5.62/2.41 "ground": [], 5.62/2.41 "free": [], 5.62/2.41 "exprvars": [] 5.62/2.41 } 5.62/2.41 }, 5.62/2.41 "9": { 5.62/2.41 "goal": [ 5.62/2.41 { 5.62/2.41 "clause": 0, 5.62/2.41 "scope": 1, 5.62/2.41 "term": "(select T1 T2 T3)" 5.62/2.41 }, 5.62/2.41 { 5.62/2.41 "clause": 1, 5.62/2.41 "scope": 1, 5.62/2.41 "term": "(select T1 T2 T3)" 5.62/2.41 } 5.62/2.41 ], 5.62/2.41 "kb": { 5.62/2.41 "nonunifying": [], 5.62/2.41 "intvars": {}, 5.62/2.41 "arithmetic": { 5.62/2.41 "type": "PlainIntegerRelationState", 5.62/2.41 "relations": [] 5.62/2.41 }, 5.62/2.41 "ground": ["T1"], 5.62/2.41 "free": [], 5.62/2.41 "exprvars": [] 5.62/2.41 } 5.62/2.41 }, 5.62/2.41 "type": "Nodes", 5.62/2.41 "87": { 5.62/2.41 "goal": [{ 5.62/2.41 "clause": -1, 5.62/2.41 "scope": -1, 5.62/2.41 "term": "(select T22 T26 T27)" 5.62/2.41 }], 5.62/2.41 "kb": { 5.62/2.41 "nonunifying": [], 5.62/2.41 "intvars": {}, 5.62/2.41 "arithmetic": { 5.62/2.41 "type": "PlainIntegerRelationState", 5.62/2.41 "relations": [] 5.62/2.41 }, 5.62/2.41 "ground": ["T22"], 5.62/2.41 "free": [], 5.62/2.41 "exprvars": [] 5.62/2.41 } 5.62/2.41 } 5.62/2.41 }, 5.62/2.41 "edges": [ 5.62/2.41 { 5.62/2.41 "from": 2, 5.62/2.41 "to": 9, 5.62/2.41 "label": "CASE" 5.62/2.41 }, 5.62/2.41 { 5.62/2.41 "from": 9, 5.62/2.41 "to": 18, 5.62/2.41 "label": "PARALLEL" 5.62/2.41 }, 5.62/2.41 { 5.62/2.41 "from": 9, 5.62/2.41 "to": 19, 5.62/2.41 "label": "PARALLEL" 5.62/2.41 }, 5.62/2.41 { 5.62/2.41 "from": 18, 5.62/2.41 "to": 78, 5.62/2.41 "label": "EVAL with clause\nselect(X9, .(X9, X10), X10).\nand substitutionT1 -> T12,\nX9 -> T12,\nX10 -> T13,\nT2 -> .(T12, T13),\nT3 -> T13" 5.62/2.41 }, 5.62/2.41 { 5.62/2.41 "from": 18, 5.62/2.41 "to": 79, 5.62/2.41 "label": "EVAL-BACKTRACK" 5.62/2.41 }, 5.62/2.41 { 5.62/2.41 "from": 19, 5.62/2.41 "to": 87, 5.62/2.41 "label": "EVAL with clause\nselect(X19, .(X20, X21), .(X20, X22)) :- select(X19, X21, X22).\nand substitutionT1 -> T22,\nX19 -> T22,\nX20 -> T23,\nX21 -> T26,\nT2 -> .(T23, T26),\nX22 -> T27,\nT3 -> .(T23, T27),\nT24 -> T26,\nT25 -> T27" 5.62/2.41 }, 5.62/2.41 { 5.62/2.41 "from": 19, 5.62/2.41 "to": 88, 5.62/2.41 "label": "EVAL-BACKTRACK" 5.62/2.41 }, 5.62/2.41 { 5.62/2.41 "from": 78, 5.62/2.41 "to": 80, 5.62/2.41 "label": "SUCCESS" 5.62/2.41 }, 5.62/2.41 { 5.62/2.41 "from": 87, 5.62/2.41 "to": 2, 5.62/2.41 "label": "INSTANCE with matching:\nT1 -> T22\nT2 -> T26\nT3 -> T27" 5.62/2.41 } 5.62/2.41 ], 5.62/2.41 "type": "Graph" 5.62/2.41 } 5.62/2.41 } 5.62/2.41 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (34) 5.62/2.41 Obligation: 5.62/2.41 Rules: 5.62/2.41 f87_out(T22) -> f19_out(T22) :|: TRUE 5.62/2.41 f19_in(T1) -> f88_in :|: TRUE 5.62/2.41 f19_in(x) -> f87_in(x) :|: TRUE 5.62/2.41 f88_out -> f19_out(x1) :|: TRUE 5.62/2.41 f87_in(x2) -> f2_in(x2) :|: TRUE 5.62/2.41 f2_out(x3) -> f87_out(x3) :|: TRUE 5.62/2.41 f9_in(x4) -> f19_in(x4) :|: TRUE 5.62/2.41 f19_out(x5) -> f9_out(x5) :|: TRUE 5.62/2.41 f9_in(x6) -> f18_in(x6) :|: TRUE 5.62/2.41 f18_out(x7) -> f9_out(x7) :|: TRUE 5.62/2.41 f9_out(x8) -> f2_out(x8) :|: TRUE 5.62/2.41 f2_in(x9) -> f9_in(x9) :|: TRUE 5.62/2.41 Start term: f2_in(T1) 5.62/2.41 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (35) IRSwTSimpleDependencyGraphProof (EQUIVALENT) 5.62/2.41 Constructed simple dependency graph. 5.62/2.41 5.62/2.41 Simplified to the following IRSwTs: 5.62/2.41 5.62/2.41 intTRSProblem: 5.62/2.41 f19_in(x) -> f87_in(x) :|: TRUE 5.62/2.41 f87_in(x2) -> f2_in(x2) :|: TRUE 5.62/2.41 f9_in(x4) -> f19_in(x4) :|: TRUE 5.62/2.41 f2_in(x9) -> f9_in(x9) :|: TRUE 5.62/2.41 5.62/2.41 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (36) 5.62/2.41 Obligation: 5.62/2.41 Rules: 5.62/2.41 f19_in(x) -> f87_in(x) :|: TRUE 5.62/2.41 f87_in(x2) -> f2_in(x2) :|: TRUE 5.62/2.41 f9_in(x4) -> f19_in(x4) :|: TRUE 5.62/2.41 f2_in(x9) -> f9_in(x9) :|: TRUE 5.62/2.41 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (37) IntTRSCompressionProof (EQUIVALENT) 5.62/2.41 Compressed rules. 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (38) 5.62/2.41 Obligation: 5.62/2.41 Rules: 5.62/2.41 f9_in(x4:0) -> f9_in(x4:0) :|: TRUE 5.62/2.41 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (39) IRSFormatTransformerProof (EQUIVALENT) 5.62/2.41 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (40) 5.62/2.41 Obligation: 5.62/2.41 Rules: 5.62/2.41 f9_in(x4:0) -> f9_in(x4:0) :|: TRUE 5.62/2.41 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (41) IRSwTTerminationDigraphProof (EQUIVALENT) 5.62/2.41 Constructed termination digraph! 5.62/2.41 Nodes: 5.62/2.41 (1) f9_in(x4:0) -> f9_in(x4:0) :|: TRUE 5.62/2.41 5.62/2.41 Arcs: 5.62/2.41 (1) -> (1) 5.62/2.41 5.62/2.41 This digraph is fully evaluated! 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (42) 5.62/2.41 Obligation: 5.62/2.41 5.62/2.41 Termination digraph: 5.62/2.41 Nodes: 5.62/2.41 (1) f9_in(x4:0) -> f9_in(x4:0) :|: TRUE 5.62/2.41 5.62/2.41 Arcs: 5.62/2.41 (1) -> (1) 5.62/2.41 5.62/2.41 This digraph is fully evaluated! 5.62/2.41 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (43) FilterProof (EQUIVALENT) 5.62/2.41 Used the following sort dictionary for filtering: 5.62/2.41 f9_in(VARIABLE) 5.62/2.41 Replaced non-predefined constructor symbols by 0. 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (44) 5.62/2.41 Obligation: 5.62/2.41 Rules: 5.62/2.41 f9_in(x4:0) -> f9_in(x4:0) :|: TRUE 5.62/2.41 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (45) IntTRSPeriodicNontermProof (COMPLETE) 5.62/2.41 Normalized system to the following form: 5.62/2.41 f(pc, x4:0) -> f(1, x4:0) :|: pc = 1 && TRUE 5.62/2.41 Witness term starting non-terminating reduction: f(1, -8) 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (46) 5.62/2.41 NO 5.62/2.41 5.62/2.41 ---------------------------------------- 5.62/2.41 5.62/2.41 (47) PrologToDTProblemTransformerProof (SOUND) 5.62/2.41 Built DT problem from termination graph DT10. 5.62/2.41 5.62/2.41 { 5.62/2.41 "root": 1, 5.62/2.41 "program": { 5.62/2.41 "directives": [], 5.62/2.41 "clauses": [ 5.62/2.41 [ 5.62/2.41 "(select X (. X Xs) Xs)", 5.62/2.41 null 5.62/2.41 ], 5.62/2.41 [ 5.62/2.41 "(select X (. Y Xs) (. Y Zs))", 5.62/2.41 "(select X Xs Zs)" 5.62/2.41 ] 5.62/2.41 ] 5.62/2.41 }, 5.62/2.41 "graph": { 5.62/2.41 "nodes": { 5.62/2.41 "89": { 5.62/2.41 "goal": [ 5.62/2.41 { 5.62/2.41 "clause": 0, 5.62/2.41 "scope": 1, 5.62/2.41 "term": "(select T1 T2 T3)" 5.62/2.41 }, 5.62/2.41 { 5.62/2.41 "clause": 1, 5.62/2.41 "scope": 1, 5.62/2.41 "term": "(select T1 T2 T3)" 5.62/2.41 } 5.62/2.41 ], 5.62/2.41 "kb": { 5.62/2.41 "nonunifying": [], 5.62/2.41 "intvars": {}, 5.62/2.41 "arithmetic": { 5.62/2.41 "type": "PlainIntegerRelationState", 5.62/2.41 "relations": [] 5.62/2.41 }, 5.62/2.41 "ground": ["T1"], 5.62/2.41 "free": [], 5.62/2.41 "exprvars": [] 5.62/2.41 } 5.62/2.41 }, 5.62/2.41 "type": "Nodes", 5.62/2.41 "112": { 5.62/2.41 "goal": [{ 5.62/2.41 "clause": -1, 5.62/2.41 "scope": -1, 5.62/2.41 "term": "(true)" 5.62/2.41 }], 5.62/2.41 "kb": { 5.62/2.41 "nonunifying": [], 5.62/2.41 "intvars": {}, 5.62/2.41 "arithmetic": { 5.62/2.41 "type": "PlainIntegerRelationState", 5.62/2.41 "relations": [] 5.62/2.41 }, 5.62/2.41 "ground": [], 5.62/2.41 "free": [], 5.90/2.41 "exprvars": [] 5.90/2.41 } 5.90/2.41 }, 5.90/2.41 "113": { 5.90/2.41 "goal": [], 5.90/2.41 "kb": { 5.90/2.41 "nonunifying": [], 5.90/2.41 "intvars": {}, 5.90/2.41 "arithmetic": { 5.90/2.41 "type": "PlainIntegerRelationState", 5.90/2.41 "relations": [] 5.90/2.41 }, 5.90/2.41 "ground": [], 5.90/2.41 "free": [], 5.90/2.41 "exprvars": [] 5.90/2.41 } 5.90/2.41 }, 5.90/2.41 "114": { 5.90/2.41 "goal": [], 5.90/2.41 "kb": { 5.90/2.41 "nonunifying": [], 5.90/2.41 "intvars": {}, 5.90/2.41 "arithmetic": { 5.90/2.41 "type": "PlainIntegerRelationState", 5.90/2.41 "relations": [] 5.90/2.41 }, 5.90/2.41 "ground": [], 5.90/2.41 "free": [], 5.90/2.41 "exprvars": [] 5.90/2.41 } 5.90/2.41 }, 5.90/2.41 "90": { 5.90/2.41 "goal": [ 5.90/2.41 { 5.90/2.41 "clause": -1, 5.90/2.41 "scope": -1, 5.90/2.41 "term": "(true)" 5.90/2.41 }, 5.90/2.41 { 5.90/2.41 "clause": 1, 5.90/2.41 "scope": 1, 5.90/2.41 "term": "(select T6 T2 T3)" 5.90/2.41 } 5.90/2.41 ], 5.90/2.41 "kb": { 5.90/2.41 "nonunifying": [], 5.90/2.41 "intvars": {}, 5.90/2.41 "arithmetic": { 5.90/2.41 "type": "PlainIntegerRelationState", 5.90/2.41 "relations": [] 5.90/2.41 }, 5.90/2.41 "ground": ["T6"], 5.90/2.41 "free": [], 5.90/2.41 "exprvars": [] 5.90/2.41 } 5.90/2.41 }, 5.90/2.41 "91": { 5.90/2.41 "goal": [{ 5.90/2.41 "clause": 1, 5.90/2.41 "scope": 1, 5.90/2.41 "term": "(select T1 T2 T3)" 5.90/2.41 }], 5.90/2.41 "kb": { 5.90/2.41 "nonunifying": [[ 5.90/2.41 "(select T1 T2 T3)", 5.90/2.42 "(select X3 (. X3 X4) X4)" 5.90/2.42 ]], 5.90/2.42 "intvars": {}, 5.90/2.42 "arithmetic": { 5.90/2.42 "type": "PlainIntegerRelationState", 5.90/2.42 "relations": [] 5.90/2.42 }, 5.90/2.42 "ground": ["T1"], 5.90/2.42 "free": [ 5.90/2.42 "X3", 5.90/2.42 "X4" 5.90/2.42 ], 5.90/2.42 "exprvars": [] 5.90/2.42 } 5.90/2.42 }, 5.90/2.42 "92": { 5.90/2.42 "goal": [{ 5.90/2.42 "clause": 1, 5.90/2.42 "scope": 1, 5.90/2.42 "term": "(select T6 T2 T3)" 5.90/2.42 }], 5.90/2.42 "kb": { 5.90/2.42 "nonunifying": [], 5.90/2.42 "intvars": {}, 5.90/2.42 "arithmetic": { 5.90/2.42 "type": "PlainIntegerRelationState", 5.90/2.42 "relations": [] 5.90/2.42 }, 5.90/2.42 "ground": ["T6"], 5.90/2.42 "free": [], 5.90/2.42 "exprvars": [] 5.90/2.42 } 5.90/2.42 }, 5.90/2.42 "95": { 5.90/2.42 "goal": [{ 5.90/2.42 "clause": -1, 5.90/2.42 "scope": -1, 5.90/2.42 "term": "(select T12 T16 T17)" 5.90/2.42 }], 5.90/2.42 "kb": { 5.90/2.42 "nonunifying": [], 5.90/2.42 "intvars": {}, 5.90/2.42 "arithmetic": { 5.90/2.42 "type": "PlainIntegerRelationState", 5.90/2.42 "relations": [] 5.90/2.42 }, 5.90/2.42 "ground": ["T12"], 5.90/2.42 "free": [], 5.90/2.42 "exprvars": [] 5.90/2.42 } 5.90/2.42 }, 5.90/2.42 "96": { 5.90/2.42 "goal": [], 5.90/2.42 "kb": { 5.90/2.42 "nonunifying": [], 5.90/2.42 "intvars": {}, 5.90/2.42 "arithmetic": { 5.90/2.42 "type": "PlainIntegerRelationState", 5.90/2.42 "relations": [] 5.90/2.42 }, 5.90/2.42 "ground": [], 5.90/2.42 "free": [], 5.90/2.42 "exprvars": [] 5.90/2.42 } 5.90/2.42 }, 5.90/2.42 "97": { 5.90/2.42 "goal": [ 5.90/2.42 { 5.90/2.42 "clause": 0, 5.90/2.42 "scope": 2, 5.90/2.42 "term": "(select T12 T16 T17)" 5.90/2.42 }, 5.90/2.42 { 5.90/2.42 "clause": 1, 5.90/2.42 "scope": 2, 5.90/2.42 "term": "(select T12 T16 T17)" 5.90/2.42 } 5.90/2.42 ], 5.90/2.42 "kb": { 5.90/2.42 "nonunifying": [], 5.90/2.42 "intvars": {}, 5.90/2.42 "arithmetic": { 5.90/2.42 "type": "PlainIntegerRelationState", 5.90/2.42 "relations": [] 5.90/2.42 }, 5.90/2.42 "ground": ["T12"], 5.90/2.42 "free": [], 5.90/2.42 "exprvars": [] 5.90/2.42 } 5.90/2.42 }, 5.90/2.42 "98": { 5.90/2.42 "goal": [{ 5.90/2.42 "clause": 0, 5.90/2.42 "scope": 2, 5.90/2.42 "term": "(select T12 T16 T17)" 5.90/2.42 }], 5.90/2.42 "kb": { 5.90/2.42 "nonunifying": [], 5.90/2.42 "intvars": {}, 5.90/2.42 "arithmetic": { 5.90/2.42 "type": "PlainIntegerRelationState", 5.90/2.42 "relations": [] 5.90/2.42 }, 5.90/2.42 "ground": ["T12"], 5.90/2.42 "free": [], 5.90/2.42 "exprvars": [] 5.90/2.42 } 5.90/2.42 }, 5.90/2.42 "99": { 5.90/2.42 "goal": [{ 5.90/2.42 "clause": 1, 5.90/2.42 "scope": 2, 5.90/2.42 "term": "(select T12 T16 T17)" 5.90/2.42 }], 5.90/2.42 "kb": { 5.90/2.42 "nonunifying": [], 5.90/2.42 "intvars": {}, 5.90/2.42 "arithmetic": { 5.90/2.42 "type": "PlainIntegerRelationState", 5.90/2.42 "relations": [] 5.90/2.42 }, 5.90/2.42 "ground": ["T12"], 5.90/2.42 "free": [], 5.90/2.42 "exprvars": [] 5.90/2.42 } 5.90/2.42 }, 5.90/2.42 "1": { 5.90/2.42 "goal": [{ 5.90/2.42 "clause": -1, 5.90/2.42 "scope": -1, 5.90/2.42 "term": "(select T1 T2 T3)" 5.90/2.42 }], 5.90/2.42 "kb": { 5.90/2.42 "nonunifying": [], 5.90/2.42 "intvars": {}, 5.90/2.42 "arithmetic": { 5.90/2.42 "type": "PlainIntegerRelationState", 5.90/2.42 "relations": [] 5.90/2.42 }, 5.90/2.42 "ground": ["T1"], 5.90/2.42 "free": [], 5.90/2.42 "exprvars": [] 5.90/2.42 } 5.90/2.42 }, 5.90/2.42 "100": { 5.90/2.42 "goal": [{ 5.90/2.42 "clause": -1, 5.90/2.42 "scope": -1, 5.90/2.42 "term": "(true)" 5.90/2.42 }], 5.90/2.42 "kb": { 5.90/2.42 "nonunifying": [], 5.90/2.42 "intvars": {}, 5.90/2.42 "arithmetic": { 5.90/2.42 "type": "PlainIntegerRelationState", 5.90/2.42 "relations": [] 5.90/2.42 }, 5.90/2.42 "ground": [], 5.90/2.42 "free": [], 5.90/2.42 "exprvars": [] 5.90/2.42 } 5.90/2.42 }, 5.90/2.42 "101": { 5.90/2.42 "goal": [], 5.90/2.42 "kb": { 5.90/2.42 "nonunifying": [], 5.90/2.42 "intvars": {}, 5.90/2.42 "arithmetic": { 5.90/2.42 "type": "PlainIntegerRelationState", 5.90/2.42 "relations": [] 5.90/2.42 }, 5.90/2.42 "ground": [], 5.90/2.42 "free": [], 5.90/2.42 "exprvars": [] 5.90/2.42 } 5.90/2.42 }, 5.90/2.42 "102": { 5.90/2.42 "goal": [], 5.90/2.42 "kb": { 5.90/2.42 "nonunifying": [], 5.90/2.42 "intvars": {}, 5.90/2.42 "arithmetic": { 5.90/2.42 "type": "PlainIntegerRelationState", 5.90/2.42 "relations": [] 5.90/2.42 }, 5.90/2.42 "ground": [], 5.90/2.42 "free": [], 5.90/2.42 "exprvars": [] 5.90/2.42 } 5.90/2.42 }, 5.90/2.42 "103": { 5.90/2.42 "goal": [{ 5.90/2.42 "clause": -1, 5.90/2.42 "scope": -1, 5.90/2.42 "term": "(select T36 T40 T41)" 5.90/2.42 }], 5.90/2.42 "kb": { 5.90/2.42 "nonunifying": [], 5.90/2.42 "intvars": {}, 5.90/2.42 "arithmetic": { 5.90/2.42 "type": "PlainIntegerRelationState", 5.90/2.42 "relations": [] 5.90/2.42 }, 5.90/2.42 "ground": ["T36"], 5.90/2.42 "free": [], 5.90/2.42 "exprvars": [] 5.90/2.42 } 5.90/2.42 }, 5.90/2.42 "125": { 5.90/2.42 "goal": [{ 5.90/2.42 "clause": -1, 5.90/2.42 "scope": -1, 5.90/2.42 "term": "(select T74 T78 T79)" 5.90/2.42 }], 5.90/2.42 "kb": { 5.90/2.42 "nonunifying": [[ 5.90/2.42 "(select T74 T2 T3)", 5.90/2.42 "(select X3 (. X3 X4) X4)" 5.90/2.42 ]], 5.90/2.42 "intvars": {}, 5.90/2.42 "arithmetic": { 5.90/2.42 "type": "PlainIntegerRelationState", 5.90/2.42 "relations": [] 5.90/2.42 }, 5.90/2.42 "ground": ["T74"], 5.90/2.42 "free": [ 5.90/2.42 "X3", 5.90/2.42 "X4" 5.90/2.42 ], 5.90/2.42 "exprvars": [] 5.90/2.42 } 5.90/2.42 }, 5.90/2.42 "104": { 5.90/2.42 "goal": [], 5.90/2.42 "kb": { 5.90/2.42 "nonunifying": [], 5.90/2.42 "intvars": {}, 5.90/2.42 "arithmetic": { 5.90/2.42 "type": "PlainIntegerRelationState", 5.90/2.42 "relations": [] 5.90/2.42 }, 5.90/2.42 "ground": [], 5.90/2.42 "free": [], 5.90/2.42 "exprvars": [] 5.90/2.42 } 5.90/2.42 }, 5.90/2.42 "126": { 5.90/2.42 "goal": [], 5.90/2.42 "kb": { 5.90/2.42 "nonunifying": [], 5.90/2.42 "intvars": {}, 5.90/2.42 "arithmetic": { 5.90/2.42 "type": "PlainIntegerRelationState", 5.90/2.42 "relations": [] 5.90/2.42 }, 5.90/2.42 "ground": [], 5.90/2.42 "free": [], 5.90/2.42 "exprvars": [] 5.90/2.42 } 5.90/2.42 }, 5.90/2.42 "105": { 5.90/2.42 "goal": [{ 5.90/2.42 "clause": -1, 5.90/2.42 "scope": -1, 5.90/2.42 "term": "(select T50 T54 T55)" 5.90/2.42 }], 5.90/2.42 "kb": { 5.90/2.42 "nonunifying": [[ 5.90/2.42 "(select T50 T2 T3)", 5.90/2.42 "(select X3 (. X3 X4) X4)" 5.90/2.42 ]], 5.90/2.42 "intvars": {}, 5.90/2.42 "arithmetic": { 5.90/2.42 "type": "PlainIntegerRelationState", 5.90/2.42 "relations": [] 5.90/2.42 }, 5.90/2.42 "ground": ["T50"], 5.90/2.42 "free": [ 5.90/2.42 "X3", 5.90/2.42 "X4" 5.90/2.42 ], 5.90/2.42 "exprvars": [] 5.90/2.42 } 5.90/2.42 }, 5.90/2.42 "106": { 5.90/2.42 "goal": [], 5.90/2.42 "kb": { 5.90/2.42 "nonunifying": [], 5.90/2.42 "intvars": {}, 5.90/2.42 "arithmetic": { 5.90/2.42 "type": "PlainIntegerRelationState", 5.90/2.42 "relations": [] 5.90/2.42 }, 5.90/2.42 "ground": [], 5.90/2.42 "free": [], 5.90/2.42 "exprvars": [] 5.90/2.42 } 5.90/2.42 }, 5.90/2.42 "107": { 5.90/2.42 "goal": [ 5.90/2.42 { 5.90/2.42 "clause": 0, 5.90/2.42 "scope": 3, 5.90/2.42 "term": "(select T50 T54 T55)" 5.90/2.42 }, 5.90/2.42 { 5.90/2.42 "clause": 1, 5.90/2.42 "scope": 3, 5.90/2.42 "term": "(select T50 T54 T55)" 5.90/2.42 } 5.90/2.42 ], 5.90/2.42 "kb": { 5.90/2.42 "nonunifying": [[ 5.90/2.42 "(select T50 T2 T3)", 5.90/2.42 "(select X3 (. X3 X4) X4)" 5.90/2.42 ]], 5.90/2.42 "intvars": {}, 5.90/2.42 "arithmetic": { 5.90/2.42 "type": "PlainIntegerRelationState", 5.90/2.42 "relations": [] 5.90/2.42 }, 5.90/2.42 "ground": ["T50"], 5.90/2.42 "free": [ 5.90/2.42 "X3", 5.90/2.42 "X4" 5.90/2.42 ], 5.90/2.42 "exprvars": [] 5.90/2.42 } 5.90/2.42 }, 5.90/2.42 "108": { 5.90/2.42 "goal": [{ 5.90/2.42 "clause": 0, 5.90/2.42 "scope": 3, 5.90/2.42 "term": "(select T50 T54 T55)" 5.90/2.42 }], 5.90/2.42 "kb": { 5.90/2.42 "nonunifying": [[ 5.90/2.42 "(select T50 T2 T3)", 5.90/2.42 "(select X3 (. X3 X4) X4)" 5.90/2.42 ]], 5.90/2.42 "intvars": {}, 5.90/2.42 "arithmetic": { 5.90/2.42 "type": "PlainIntegerRelationState", 5.90/2.42 "relations": [] 5.90/2.42 }, 5.90/2.42 "ground": ["T50"], 5.90/2.42 "free": [ 5.90/2.42 "X3", 5.90/2.42 "X4" 5.90/2.42 ], 5.90/2.42 "exprvars": [] 5.90/2.42 } 5.90/2.42 }, 5.90/2.42 "109": { 5.90/2.42 "goal": [{ 5.90/2.42 "clause": 1, 5.90/2.42 "scope": 3, 5.90/2.42 "term": "(select T50 T54 T55)" 5.90/2.42 }], 5.90/2.42 "kb": { 5.90/2.42 "nonunifying": [[ 5.90/2.42 "(select T50 T2 T3)", 5.90/2.42 "(select X3 (. X3 X4) X4)" 5.90/2.42 ]], 5.90/2.42 "intvars": {}, 5.90/2.42 "arithmetic": { 5.90/2.42 "type": "PlainIntegerRelationState", 5.90/2.42 "relations": [] 5.90/2.42 }, 5.90/2.42 "ground": ["T50"], 5.90/2.42 "free": [ 5.90/2.42 "X3", 5.90/2.42 "X4" 5.90/2.42 ], 5.90/2.42 "exprvars": [] 5.90/2.42 } 5.90/2.42 } 5.90/2.42 }, 5.90/2.42 "edges": [ 5.90/2.42 { 5.90/2.42 "from": 1, 5.90/2.42 "to": 89, 5.90/2.42 "label": "CASE" 5.90/2.42 }, 5.90/2.42 { 5.90/2.42 "from": 89, 5.90/2.42 "to": 90, 5.90/2.42 "label": "EVAL with clause\nselect(X3, .(X3, X4), X4).\nand substitutionT1 -> T6,\nX3 -> T6,\nX4 -> T7,\nT2 -> .(T6, T7),\nT3 -> T7" 5.90/2.42 }, 5.90/2.42 { 5.90/2.42 "from": 89, 5.90/2.42 "to": 91, 5.90/2.42 "label": "EVAL-BACKTRACK" 5.90/2.42 }, 5.90/2.42 { 5.90/2.42 "from": 90, 5.90/2.42 "to": 92, 5.90/2.42 "label": "SUCCESS" 5.90/2.42 }, 5.90/2.42 { 5.90/2.42 "from": 91, 5.90/2.42 "to": 105, 5.90/2.42 "label": "EVAL with clause\nselect(X43, .(X44, X45), .(X44, X46)) :- select(X43, X45, X46).\nand substitutionT1 -> T50,\nX43 -> T50,\nX44 -> T51,\nX45 -> T54,\nT2 -> .(T51, T54),\nX46 -> T55,\nT3 -> .(T51, T55),\nT52 -> T54,\nT53 -> T55" 5.90/2.42 }, 5.90/2.42 { 5.90/2.42 "from": 91, 5.90/2.42 "to": 106, 5.90/2.42 "label": "EVAL-BACKTRACK" 5.90/2.42 }, 5.90/2.42 { 5.90/2.42 "from": 92, 5.90/2.42 "to": 95, 5.90/2.42 "label": "EVAL with clause\nselect(X9, .(X10, X11), .(X10, X12)) :- select(X9, X11, X12).\nand substitutionT6 -> T12,\nX9 -> T12,\nX10 -> T13,\nX11 -> T16,\nT2 -> .(T13, T16),\nX12 -> T17,\nT3 -> .(T13, T17),\nT14 -> T16,\nT15 -> T17" 5.90/2.42 }, 5.90/2.42 { 5.90/2.42 "from": 92, 5.90/2.42 "to": 96, 5.90/2.42 "label": "EVAL-BACKTRACK" 5.90/2.42 }, 5.90/2.42 { 5.90/2.42 "from": 95, 5.90/2.42 "to": 97, 5.90/2.42 "label": "CASE" 5.90/2.42 }, 5.90/2.42 { 5.90/2.42 "from": 97, 5.90/2.42 "to": 98, 5.90/2.42 "label": "PARALLEL" 5.90/2.42 }, 5.90/2.42 { 5.90/2.42 "from": 97, 5.90/2.42 "to": 99, 5.90/2.42 "label": "PARALLEL" 5.90/2.42 }, 5.90/2.42 { 5.90/2.42 "from": 98, 5.90/2.42 "to": 100, 5.90/2.42 "label": "EVAL with clause\nselect(X21, .(X21, X22), X22).\nand substitutionT12 -> T26,\nX21 -> T26,\nX22 -> T27,\nT16 -> .(T26, T27),\nT17 -> T27" 5.90/2.42 }, 5.90/2.42 { 5.90/2.42 "from": 98, 5.90/2.42 "to": 101, 5.90/2.42 "label": "EVAL-BACKTRACK" 5.90/2.42 }, 5.90/2.42 { 5.90/2.42 "from": 99, 5.90/2.42 "to": 103, 5.90/2.42 "label": "EVAL with clause\nselect(X31, .(X32, X33), .(X32, X34)) :- select(X31, X33, X34).\nand substitutionT12 -> T36,\nX31 -> T36,\nX32 -> T37,\nX33 -> T40,\nT16 -> .(T37, T40),\nX34 -> T41,\nT17 -> .(T37, T41),\nT38 -> T40,\nT39 -> T41" 5.90/2.42 }, 5.90/2.42 { 5.90/2.42 "from": 99, 5.90/2.42 "to": 104, 5.90/2.42 "label": "EVAL-BACKTRACK" 5.90/2.42 }, 5.90/2.42 { 5.90/2.42 "from": 100, 5.90/2.42 "to": 102, 5.90/2.42 "label": "SUCCESS" 5.90/2.42 }, 5.90/2.42 { 5.90/2.42 "from": 103, 5.90/2.42 "to": 1, 5.90/2.42 "label": "INSTANCE with matching:\nT1 -> T36\nT2 -> T40\nT3 -> T41" 5.90/2.42 }, 5.90/2.42 { 5.90/2.42 "from": 105, 5.90/2.42 "to": 107, 5.90/2.42 "label": "CASE" 5.90/2.42 }, 5.90/2.42 { 5.90/2.42 "from": 107, 5.90/2.42 "to": 108, 5.90/2.42 "label": "PARALLEL" 5.90/2.42 }, 5.90/2.42 { 5.90/2.42 "from": 107, 5.90/2.42 "to": 109, 5.90/2.42 "label": "PARALLEL" 5.90/2.42 }, 5.90/2.42 { 5.90/2.42 "from": 108, 5.90/2.42 "to": 112, 5.90/2.42 "label": "EVAL with clause\nselect(X55, .(X55, X56), X56).\nand substitutionT50 -> T64,\nX55 -> T64,\nX56 -> T65,\nT54 -> .(T64, T65),\nT55 -> T65" 5.90/2.42 }, 5.90/2.42 { 5.90/2.42 "from": 108, 5.90/2.42 "to": 113, 5.90/2.42 "label": "EVAL-BACKTRACK" 5.90/2.42 }, 5.90/2.42 { 5.90/2.42 "from": 109, 5.90/2.42 "to": 125, 5.90/2.42 "label": "EVAL with clause\nselect(X65, .(X66, X67), .(X66, X68)) :- select(X65, X67, X68).\nand substitutionT50 -> T74,\nX65 -> T74,\nX66 -> T75,\nX67 -> T78,\nT54 -> .(T75, T78),\nX68 -> T79,\nT55 -> .(T75, T79),\nT76 -> T78,\nT77 -> T79" 5.90/2.42 }, 5.90/2.42 { 5.90/2.42 "from": 109, 5.90/2.42 "to": 126, 5.90/2.42 "label": "EVAL-BACKTRACK" 5.90/2.42 }, 5.90/2.42 { 5.90/2.42 "from": 112, 5.90/2.42 "to": 114, 5.90/2.42 "label": "SUCCESS" 5.90/2.42 }, 5.90/2.42 { 5.90/2.42 "from": 125, 5.90/2.42 "to": 1, 5.90/2.42 "label": "INSTANCE with matching:\nT1 -> T74\nT2 -> T78\nT3 -> T79" 5.90/2.42 } 5.90/2.42 ], 5.90/2.42 "type": "Graph" 5.90/2.42 } 5.90/2.42 } 5.90/2.42 5.90/2.42 ---------------------------------------- 5.90/2.42 5.90/2.42 (48) 5.90/2.42 Obligation: 5.90/2.42 Triples: 5.90/2.42 5.90/2.42 selectA(X1, .(X2, .(X3, X4)), .(X2, .(X3, X5))) :- selectA(X1, X4, X5). 5.90/2.42 selectA(X1, .(X2, .(X3, X4)), .(X2, .(X3, X5))) :- selectA(X1, X4, X5). 5.90/2.42 5.90/2.42 Clauses: 5.90/2.42 5.90/2.42 selectcA(X1, .(X1, X2), X2). 5.90/2.42 selectcA(X1, .(X2, .(X1, X3)), .(X2, X3)). 5.90/2.42 selectcA(X1, .(X2, .(X3, X4)), .(X2, .(X3, X5))) :- selectcA(X1, X4, X5). 5.90/2.42 selectcA(X1, .(X2, .(X1, X3)), .(X2, X3)). 5.90/2.42 selectcA(X1, .(X2, .(X3, X4)), .(X2, .(X3, X5))) :- selectcA(X1, X4, X5). 5.90/2.42 5.90/2.42 Afs: 5.90/2.42 5.90/2.42 selectA(x1, x2, x3) = selectA(x1) 5.90/2.42 5.90/2.42 5.90/2.42 ---------------------------------------- 5.90/2.42 5.90/2.42 (49) TriplesToPiDPProof (SOUND) 5.90/2.42 We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: 5.90/2.42 5.90/2.42 selectA_in_3: (b,f,f) 5.90/2.42 5.90/2.42 Transforming TRIPLES into the following Term Rewriting System: 5.90/2.42 5.90/2.42 Pi DP problem: 5.90/2.42 The TRS P consists of the following rules: 5.90/2.42 5.90/2.42 SELECTA_IN_GAA(X1, .(X2, .(X3, X4)), .(X2, .(X3, X5))) -> U1_GAA(X1, X2, X3, X4, X5, selectA_in_gaa(X1, X4, X5)) 5.90/2.42 SELECTA_IN_GAA(X1, .(X2, .(X3, X4)), .(X2, .(X3, X5))) -> SELECTA_IN_GAA(X1, X4, X5) 5.90/2.42 5.90/2.42 R is empty. 5.90/2.42 The argument filtering Pi contains the following mapping: 5.90/2.42 selectA_in_gaa(x1, x2, x3) = selectA_in_gaa(x1) 5.90/2.42 5.90/2.42 .(x1, x2) = .(x2) 5.90/2.42 5.90/2.42 SELECTA_IN_GAA(x1, x2, x3) = SELECTA_IN_GAA(x1) 5.90/2.42 5.90/2.42 U1_GAA(x1, x2, x3, x4, x5, x6) = U1_GAA(x1, x6) 5.90/2.42 5.90/2.42 5.90/2.42 We have to consider all (P,R,Pi)-chains 5.90/2.42 5.90/2.42 5.90/2.42 Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES 5.90/2.42 5.90/2.42 5.90/2.42 5.90/2.42 ---------------------------------------- 5.90/2.42 5.90/2.42 (50) 5.90/2.42 Obligation: 5.90/2.42 Pi DP problem: 5.90/2.42 The TRS P consists of the following rules: 5.90/2.42 5.90/2.42 SELECTA_IN_GAA(X1, .(X2, .(X3, X4)), .(X2, .(X3, X5))) -> U1_GAA(X1, X2, X3, X4, X5, selectA_in_gaa(X1, X4, X5)) 5.90/2.42 SELECTA_IN_GAA(X1, .(X2, .(X3, X4)), .(X2, .(X3, X5))) -> SELECTA_IN_GAA(X1, X4, X5) 5.90/2.42 5.90/2.42 R is empty. 5.90/2.42 The argument filtering Pi contains the following mapping: 5.90/2.42 selectA_in_gaa(x1, x2, x3) = selectA_in_gaa(x1) 5.90/2.42 5.90/2.42 .(x1, x2) = .(x2) 5.90/2.42 5.90/2.42 SELECTA_IN_GAA(x1, x2, x3) = SELECTA_IN_GAA(x1) 5.90/2.42 5.90/2.42 U1_GAA(x1, x2, x3, x4, x5, x6) = U1_GAA(x1, x6) 5.90/2.42 5.90/2.42 5.90/2.42 We have to consider all (P,R,Pi)-chains 5.90/2.42 ---------------------------------------- 5.90/2.42 5.90/2.42 (51) DependencyGraphProof (EQUIVALENT) 5.90/2.42 The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 1 less node. 5.90/2.42 ---------------------------------------- 5.90/2.42 5.90/2.42 (52) 5.90/2.42 Obligation: 5.90/2.42 Pi DP problem: 5.90/2.42 The TRS P consists of the following rules: 5.90/2.42 5.90/2.42 SELECTA_IN_GAA(X1, .(X2, .(X3, X4)), .(X2, .(X3, X5))) -> SELECTA_IN_GAA(X1, X4, X5) 5.90/2.42 5.90/2.42 R is empty. 5.90/2.42 The argument filtering Pi contains the following mapping: 5.90/2.42 .(x1, x2) = .(x2) 5.90/2.42 5.90/2.42 SELECTA_IN_GAA(x1, x2, x3) = SELECTA_IN_GAA(x1) 5.90/2.42 5.90/2.42 5.90/2.42 We have to consider all (P,R,Pi)-chains 5.90/2.42 ---------------------------------------- 5.90/2.42 5.90/2.42 (53) PiDPToQDPProof (SOUND) 5.90/2.42 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.90/2.42 ---------------------------------------- 5.90/2.42 5.90/2.42 (54) 5.90/2.42 Obligation: 5.90/2.42 Q DP problem: 5.90/2.42 The TRS P consists of the following rules: 5.90/2.42 5.90/2.42 SELECTA_IN_GAA(X1) -> SELECTA_IN_GAA(X1) 5.90/2.42 5.90/2.42 R is empty. 5.90/2.42 Q is empty. 5.90/2.42 We have to consider all (P,Q,R)-chains. 5.90/2.43 EOF