5.84/2.34 MAYBE 5.98/2.38 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 5.98/2.38 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.98/2.38 5.98/2.38 5.98/2.38 Left Termination of the query pattern 5.98/2.38 5.98/2.38 p(a) 5.98/2.38 5.98/2.38 w.r.t. the given Prolog program could not be shown: 5.98/2.38 5.98/2.38 (0) Prolog 5.98/2.38 (1) PrologToPiTRSProof [SOUND, 0 ms] 5.98/2.38 (2) PiTRS 5.98/2.38 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 5.98/2.38 (4) PiDP 5.98/2.38 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 5.98/2.38 (6) PiDP 5.98/2.38 (7) UsableRulesProof [EQUIVALENT, 0 ms] 5.98/2.38 (8) PiDP 5.98/2.38 (9) PiDPToQDPProof [SOUND, 0 ms] 5.98/2.38 (10) QDP 5.98/2.38 (11) PrologToPiTRSProof [SOUND, 0 ms] 5.98/2.38 (12) PiTRS 5.98/2.38 (13) DependencyPairsProof [EQUIVALENT, 0 ms] 5.98/2.38 (14) PiDP 5.98/2.38 (15) DependencyGraphProof [EQUIVALENT, 0 ms] 5.98/2.38 (16) PiDP 5.98/2.38 (17) UsableRulesProof [EQUIVALENT, 0 ms] 5.98/2.38 (18) PiDP 5.98/2.38 (19) PiDPToQDPProof [SOUND, 0 ms] 5.98/2.38 (20) QDP 5.98/2.38 (21) PrologToDTProblemTransformerProof [SOUND, 0 ms] 5.98/2.38 (22) TRIPLES 5.98/2.38 (23) TriplesToPiDPProof [SOUND, 7 ms] 5.98/2.38 (24) PiDP 5.98/2.38 (25) DependencyGraphProof [EQUIVALENT, 0 ms] 5.98/2.38 (26) PiDP 5.98/2.38 (27) PiDPToQDPProof [SOUND, 0 ms] 5.98/2.38 (28) QDP 5.98/2.38 (29) PrologToTRSTransformerProof [SOUND, 0 ms] 5.98/2.38 (30) QTRS 5.98/2.38 (31) QTRSRRRProof [EQUIVALENT, 63 ms] 5.98/2.38 (32) QTRS 5.98/2.38 (33) QTRSRRRProof [EQUIVALENT, 0 ms] 5.98/2.38 (34) QTRS 5.98/2.38 (35) QTRSRRRProof [EQUIVALENT, 4 ms] 5.98/2.38 (36) QTRS 5.98/2.38 (37) QTRSRRRProof [EQUIVALENT, 6 ms] 5.98/2.38 (38) QTRS 5.98/2.38 (39) QTRSRRRProof [EQUIVALENT, 2 ms] 5.98/2.38 (40) QTRS 5.98/2.38 (41) QTRSRRRProof [EQUIVALENT, 3 ms] 5.98/2.38 (42) QTRS 5.98/2.38 (43) PrologToIRSwTTransformerProof [SOUND, 0 ms] 5.98/2.38 (44) IRSwT 5.98/2.38 (45) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] 5.98/2.38 (46) IRSwT 5.98/2.38 (47) IntTRSCompressionProof [EQUIVALENT, 44 ms] 5.98/2.38 (48) IRSwT 5.98/2.38 (49) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 5.98/2.38 (50) IRSwT 5.98/2.38 (51) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] 5.98/2.38 (52) IRSwT 5.98/2.38 (53) FilterProof [EQUIVALENT, 0 ms] 5.98/2.38 (54) IntTRS 5.98/2.38 (55) IntTRSNonPeriodicNontermProof [COMPLETE, 8 ms] 5.98/2.38 (56) NO 5.98/2.38 5.98/2.38 5.98/2.38 ---------------------------------------- 5.98/2.38 5.98/2.38 (0) 5.98/2.38 Obligation: 5.98/2.38 Clauses: 5.98/2.38 5.98/2.38 p(X) :- ','(l(X), q(X)). 5.98/2.38 q(.(A, [])). 5.98/2.38 r(1). 5.98/2.38 l([]). 5.98/2.38 l(.(H, T)) :- ','(r(H), l(T)). 5.98/2.38 5.98/2.38 5.98/2.38 Query: p(a) 5.98/2.38 ---------------------------------------- 5.98/2.38 5.98/2.38 (1) PrologToPiTRSProof (SOUND) 5.98/2.38 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 5.98/2.38 5.98/2.38 p_in_1: (f) 5.98/2.38 5.98/2.38 l_in_1: (f) 5.98/2.38 5.98/2.38 Transforming Prolog into the following Term Rewriting System: 5.98/2.38 5.98/2.38 Pi-finite rewrite system: 5.98/2.38 The TRS R consists of the following rules: 5.98/2.38 5.98/2.38 p_in_a(X) -> U1_a(X, l_in_a(X)) 5.98/2.38 l_in_a([]) -> l_out_a([]) 5.98/2.38 l_in_a(.(H, T)) -> U3_a(H, T, r_in_a(H)) 5.98/2.38 r_in_a(1) -> r_out_a(1) 5.98/2.38 U3_a(H, T, r_out_a(H)) -> U4_a(H, T, l_in_a(T)) 5.98/2.38 U4_a(H, T, l_out_a(T)) -> l_out_a(.(H, T)) 5.98/2.38 U1_a(X, l_out_a(X)) -> U2_a(X, q_in_g(X)) 5.98/2.38 q_in_g(.(A, [])) -> q_out_g(.(A, [])) 5.98/2.38 U2_a(X, q_out_g(X)) -> p_out_a(X) 5.98/2.38 5.98/2.38 The argument filtering Pi contains the following mapping: 5.98/2.38 p_in_a(x1) = p_in_a 5.98/2.38 5.98/2.38 U1_a(x1, x2) = U1_a(x2) 5.98/2.38 5.98/2.38 l_in_a(x1) = l_in_a 5.98/2.38 5.98/2.38 l_out_a(x1) = l_out_a(x1) 5.98/2.38 5.98/2.38 U3_a(x1, x2, x3) = U3_a(x3) 5.98/2.38 5.98/2.38 r_in_a(x1) = r_in_a 5.98/2.38 5.98/2.38 r_out_a(x1) = r_out_a(x1) 5.98/2.38 5.98/2.38 U4_a(x1, x2, x3) = U4_a(x1, x3) 5.98/2.38 5.98/2.38 U2_a(x1, x2) = U2_a(x1, x2) 5.98/2.38 5.98/2.38 q_in_g(x1) = q_in_g(x1) 5.98/2.38 5.98/2.38 .(x1, x2) = .(x1, x2) 5.98/2.38 5.98/2.38 [] = [] 5.98/2.38 5.98/2.38 q_out_g(x1) = q_out_g 5.98/2.38 5.98/2.38 p_out_a(x1) = p_out_a(x1) 5.98/2.38 5.98/2.38 5.98/2.38 5.98/2.38 5.98/2.38 5.98/2.38 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 5.98/2.38 5.98/2.38 5.98/2.38 5.98/2.38 ---------------------------------------- 5.98/2.38 5.98/2.38 (2) 5.98/2.38 Obligation: 5.98/2.38 Pi-finite rewrite system: 5.98/2.38 The TRS R consists of the following rules: 5.98/2.38 5.98/2.38 p_in_a(X) -> U1_a(X, l_in_a(X)) 5.98/2.38 l_in_a([]) -> l_out_a([]) 5.98/2.38 l_in_a(.(H, T)) -> U3_a(H, T, r_in_a(H)) 5.98/2.38 r_in_a(1) -> r_out_a(1) 5.98/2.38 U3_a(H, T, r_out_a(H)) -> U4_a(H, T, l_in_a(T)) 5.98/2.38 U4_a(H, T, l_out_a(T)) -> l_out_a(.(H, T)) 5.98/2.38 U1_a(X, l_out_a(X)) -> U2_a(X, q_in_g(X)) 5.98/2.38 q_in_g(.(A, [])) -> q_out_g(.(A, [])) 5.98/2.38 U2_a(X, q_out_g(X)) -> p_out_a(X) 5.98/2.38 5.98/2.38 The argument filtering Pi contains the following mapping: 5.98/2.38 p_in_a(x1) = p_in_a 5.98/2.38 5.98/2.38 U1_a(x1, x2) = U1_a(x2) 5.98/2.38 5.98/2.38 l_in_a(x1) = l_in_a 5.98/2.38 5.98/2.38 l_out_a(x1) = l_out_a(x1) 5.98/2.38 5.98/2.38 U3_a(x1, x2, x3) = U3_a(x3) 5.98/2.38 5.98/2.38 r_in_a(x1) = r_in_a 5.98/2.38 5.98/2.38 r_out_a(x1) = r_out_a(x1) 5.98/2.38 5.98/2.38 U4_a(x1, x2, x3) = U4_a(x1, x3) 5.98/2.38 5.98/2.38 U2_a(x1, x2) = U2_a(x1, x2) 5.98/2.38 5.98/2.38 q_in_g(x1) = q_in_g(x1) 5.98/2.38 5.98/2.38 .(x1, x2) = .(x1, x2) 5.98/2.38 5.98/2.38 [] = [] 5.98/2.38 5.98/2.38 q_out_g(x1) = q_out_g 5.98/2.38 5.98/2.38 p_out_a(x1) = p_out_a(x1) 5.98/2.38 5.98/2.38 5.98/2.38 5.98/2.38 ---------------------------------------- 5.98/2.38 5.98/2.38 (3) DependencyPairsProof (EQUIVALENT) 5.98/2.38 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 5.98/2.38 Pi DP problem: 5.98/2.38 The TRS P consists of the following rules: 5.98/2.38 5.98/2.38 P_IN_A(X) -> U1_A(X, l_in_a(X)) 5.98/2.38 P_IN_A(X) -> L_IN_A(X) 5.98/2.38 L_IN_A(.(H, T)) -> U3_A(H, T, r_in_a(H)) 5.98/2.38 L_IN_A(.(H, T)) -> R_IN_A(H) 5.98/2.38 U3_A(H, T, r_out_a(H)) -> U4_A(H, T, l_in_a(T)) 5.98/2.38 U3_A(H, T, r_out_a(H)) -> L_IN_A(T) 5.98/2.38 U1_A(X, l_out_a(X)) -> U2_A(X, q_in_g(X)) 5.98/2.38 U1_A(X, l_out_a(X)) -> Q_IN_G(X) 5.98/2.38 5.98/2.38 The TRS R consists of the following rules: 5.98/2.38 5.98/2.38 p_in_a(X) -> U1_a(X, l_in_a(X)) 5.98/2.38 l_in_a([]) -> l_out_a([]) 5.98/2.38 l_in_a(.(H, T)) -> U3_a(H, T, r_in_a(H)) 5.98/2.38 r_in_a(1) -> r_out_a(1) 5.98/2.38 U3_a(H, T, r_out_a(H)) -> U4_a(H, T, l_in_a(T)) 5.98/2.38 U4_a(H, T, l_out_a(T)) -> l_out_a(.(H, T)) 5.98/2.38 U1_a(X, l_out_a(X)) -> U2_a(X, q_in_g(X)) 5.98/2.38 q_in_g(.(A, [])) -> q_out_g(.(A, [])) 5.98/2.38 U2_a(X, q_out_g(X)) -> p_out_a(X) 5.98/2.38 5.98/2.38 The argument filtering Pi contains the following mapping: 5.98/2.38 p_in_a(x1) = p_in_a 5.98/2.38 5.98/2.38 U1_a(x1, x2) = U1_a(x2) 5.98/2.38 5.98/2.38 l_in_a(x1) = l_in_a 5.98/2.38 5.98/2.38 l_out_a(x1) = l_out_a(x1) 5.98/2.38 5.98/2.38 U3_a(x1, x2, x3) = U3_a(x3) 5.98/2.38 5.98/2.38 r_in_a(x1) = r_in_a 5.98/2.38 5.98/2.38 r_out_a(x1) = r_out_a(x1) 5.98/2.38 5.98/2.38 U4_a(x1, x2, x3) = U4_a(x1, x3) 5.98/2.38 5.98/2.38 U2_a(x1, x2) = U2_a(x1, x2) 5.98/2.38 5.98/2.38 q_in_g(x1) = q_in_g(x1) 5.98/2.38 5.98/2.38 .(x1, x2) = .(x1, x2) 5.98/2.38 5.98/2.38 [] = [] 5.98/2.38 5.98/2.38 q_out_g(x1) = q_out_g 5.98/2.38 5.98/2.38 p_out_a(x1) = p_out_a(x1) 5.98/2.38 5.98/2.38 P_IN_A(x1) = P_IN_A 5.98/2.38 5.98/2.38 U1_A(x1, x2) = U1_A(x2) 5.98/2.38 5.98/2.38 L_IN_A(x1) = L_IN_A 5.98/2.38 5.98/2.38 U3_A(x1, x2, x3) = U3_A(x3) 5.98/2.38 5.98/2.38 R_IN_A(x1) = R_IN_A 5.98/2.38 5.98/2.38 U4_A(x1, x2, x3) = U4_A(x1, x3) 5.98/2.38 5.98/2.38 U2_A(x1, x2) = U2_A(x1, x2) 5.98/2.38 5.98/2.38 Q_IN_G(x1) = Q_IN_G(x1) 5.98/2.38 5.98/2.38 5.98/2.38 We have to consider all (P,R,Pi)-chains 5.98/2.38 ---------------------------------------- 5.98/2.38 5.98/2.38 (4) 5.98/2.38 Obligation: 5.98/2.38 Pi DP problem: 5.98/2.38 The TRS P consists of the following rules: 5.98/2.38 5.98/2.38 P_IN_A(X) -> U1_A(X, l_in_a(X)) 5.98/2.38 P_IN_A(X) -> L_IN_A(X) 5.98/2.38 L_IN_A(.(H, T)) -> U3_A(H, T, r_in_a(H)) 5.98/2.38 L_IN_A(.(H, T)) -> R_IN_A(H) 5.98/2.38 U3_A(H, T, r_out_a(H)) -> U4_A(H, T, l_in_a(T)) 5.98/2.38 U3_A(H, T, r_out_a(H)) -> L_IN_A(T) 5.98/2.38 U1_A(X, l_out_a(X)) -> U2_A(X, q_in_g(X)) 5.98/2.38 U1_A(X, l_out_a(X)) -> Q_IN_G(X) 5.98/2.38 5.98/2.38 The TRS R consists of the following rules: 5.98/2.38 5.98/2.38 p_in_a(X) -> U1_a(X, l_in_a(X)) 5.98/2.38 l_in_a([]) -> l_out_a([]) 5.98/2.38 l_in_a(.(H, T)) -> U3_a(H, T, r_in_a(H)) 5.98/2.38 r_in_a(1) -> r_out_a(1) 5.98/2.38 U3_a(H, T, r_out_a(H)) -> U4_a(H, T, l_in_a(T)) 5.98/2.38 U4_a(H, T, l_out_a(T)) -> l_out_a(.(H, T)) 5.98/2.38 U1_a(X, l_out_a(X)) -> U2_a(X, q_in_g(X)) 5.98/2.38 q_in_g(.(A, [])) -> q_out_g(.(A, [])) 5.98/2.38 U2_a(X, q_out_g(X)) -> p_out_a(X) 5.98/2.38 5.98/2.38 The argument filtering Pi contains the following mapping: 5.98/2.38 p_in_a(x1) = p_in_a 5.98/2.38 5.98/2.38 U1_a(x1, x2) = U1_a(x2) 5.98/2.38 5.98/2.38 l_in_a(x1) = l_in_a 5.98/2.38 5.98/2.38 l_out_a(x1) = l_out_a(x1) 5.98/2.38 5.98/2.38 U3_a(x1, x2, x3) = U3_a(x3) 5.98/2.38 5.98/2.38 r_in_a(x1) = r_in_a 5.98/2.38 5.98/2.38 r_out_a(x1) = r_out_a(x1) 5.98/2.38 5.98/2.38 U4_a(x1, x2, x3) = U4_a(x1, x3) 5.98/2.38 5.98/2.38 U2_a(x1, x2) = U2_a(x1, x2) 5.98/2.38 5.98/2.38 q_in_g(x1) = q_in_g(x1) 5.98/2.38 5.98/2.38 .(x1, x2) = .(x1, x2) 5.98/2.38 5.98/2.38 [] = [] 5.98/2.38 5.98/2.38 q_out_g(x1) = q_out_g 5.98/2.38 5.98/2.38 p_out_a(x1) = p_out_a(x1) 5.98/2.38 5.98/2.38 P_IN_A(x1) = P_IN_A 5.98/2.38 5.98/2.38 U1_A(x1, x2) = U1_A(x2) 5.98/2.38 5.98/2.38 L_IN_A(x1) = L_IN_A 5.98/2.38 5.98/2.38 U3_A(x1, x2, x3) = U3_A(x3) 5.98/2.38 5.98/2.38 R_IN_A(x1) = R_IN_A 5.98/2.38 5.98/2.38 U4_A(x1, x2, x3) = U4_A(x1, x3) 5.98/2.38 5.98/2.38 U2_A(x1, x2) = U2_A(x1, x2) 5.98/2.38 5.98/2.38 Q_IN_G(x1) = Q_IN_G(x1) 5.98/2.38 5.98/2.38 5.98/2.38 We have to consider all (P,R,Pi)-chains 5.98/2.38 ---------------------------------------- 5.98/2.38 5.98/2.38 (5) DependencyGraphProof (EQUIVALENT) 5.98/2.38 The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 6 less nodes. 5.98/2.38 ---------------------------------------- 5.98/2.38 5.98/2.38 (6) 5.98/2.38 Obligation: 5.98/2.38 Pi DP problem: 5.98/2.38 The TRS P consists of the following rules: 5.98/2.38 5.98/2.38 U3_A(H, T, r_out_a(H)) -> L_IN_A(T) 5.98/2.38 L_IN_A(.(H, T)) -> U3_A(H, T, r_in_a(H)) 5.98/2.38 5.98/2.38 The TRS R consists of the following rules: 5.98/2.38 5.98/2.38 p_in_a(X) -> U1_a(X, l_in_a(X)) 5.98/2.38 l_in_a([]) -> l_out_a([]) 5.98/2.38 l_in_a(.(H, T)) -> U3_a(H, T, r_in_a(H)) 5.98/2.38 r_in_a(1) -> r_out_a(1) 5.98/2.38 U3_a(H, T, r_out_a(H)) -> U4_a(H, T, l_in_a(T)) 5.98/2.38 U4_a(H, T, l_out_a(T)) -> l_out_a(.(H, T)) 5.98/2.38 U1_a(X, l_out_a(X)) -> U2_a(X, q_in_g(X)) 5.98/2.38 q_in_g(.(A, [])) -> q_out_g(.(A, [])) 5.98/2.38 U2_a(X, q_out_g(X)) -> p_out_a(X) 5.98/2.38 5.98/2.38 The argument filtering Pi contains the following mapping: 5.98/2.38 p_in_a(x1) = p_in_a 5.98/2.39 5.98/2.39 U1_a(x1, x2) = U1_a(x2) 5.98/2.39 5.98/2.39 l_in_a(x1) = l_in_a 5.98/2.39 5.98/2.39 l_out_a(x1) = l_out_a(x1) 5.98/2.39 5.98/2.39 U3_a(x1, x2, x3) = U3_a(x3) 5.98/2.39 5.98/2.39 r_in_a(x1) = r_in_a 5.98/2.39 5.98/2.39 r_out_a(x1) = r_out_a(x1) 5.98/2.39 5.98/2.39 U4_a(x1, x2, x3) = U4_a(x1, x3) 5.98/2.39 5.98/2.39 U2_a(x1, x2) = U2_a(x1, x2) 5.98/2.39 5.98/2.39 q_in_g(x1) = q_in_g(x1) 5.98/2.39 5.98/2.39 .(x1, x2) = .(x1, x2) 5.98/2.39 5.98/2.39 [] = [] 5.98/2.39 5.98/2.39 q_out_g(x1) = q_out_g 5.98/2.39 5.98/2.39 p_out_a(x1) = p_out_a(x1) 5.98/2.39 5.98/2.39 L_IN_A(x1) = L_IN_A 5.98/2.39 5.98/2.39 U3_A(x1, x2, x3) = U3_A(x3) 5.98/2.39 5.98/2.39 5.98/2.39 We have to consider all (P,R,Pi)-chains 5.98/2.39 ---------------------------------------- 5.98/2.39 5.98/2.39 (7) UsableRulesProof (EQUIVALENT) 5.98/2.39 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.98/2.39 ---------------------------------------- 5.98/2.39 5.98/2.39 (8) 5.98/2.39 Obligation: 5.98/2.39 Pi DP problem: 5.98/2.39 The TRS P consists of the following rules: 5.98/2.39 5.98/2.39 U3_A(H, T, r_out_a(H)) -> L_IN_A(T) 5.98/2.39 L_IN_A(.(H, T)) -> U3_A(H, T, r_in_a(H)) 5.98/2.39 5.98/2.39 The TRS R consists of the following rules: 5.98/2.39 5.98/2.39 r_in_a(1) -> r_out_a(1) 5.98/2.39 5.98/2.39 The argument filtering Pi contains the following mapping: 5.98/2.39 r_in_a(x1) = r_in_a 5.98/2.39 5.98/2.39 r_out_a(x1) = r_out_a(x1) 5.98/2.39 5.98/2.39 .(x1, x2) = .(x1, x2) 5.98/2.39 5.98/2.39 L_IN_A(x1) = L_IN_A 5.98/2.39 5.98/2.39 U3_A(x1, x2, x3) = U3_A(x3) 5.98/2.39 5.98/2.39 5.98/2.39 We have to consider all (P,R,Pi)-chains 5.98/2.39 ---------------------------------------- 5.98/2.39 5.98/2.39 (9) PiDPToQDPProof (SOUND) 5.98/2.39 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.98/2.39 ---------------------------------------- 5.98/2.39 5.98/2.39 (10) 5.98/2.39 Obligation: 5.98/2.39 Q DP problem: 5.98/2.39 The TRS P consists of the following rules: 5.98/2.39 5.98/2.39 U3_A(r_out_a(H)) -> L_IN_A 5.98/2.39 L_IN_A -> U3_A(r_in_a) 5.98/2.39 5.98/2.39 The TRS R consists of the following rules: 5.98/2.39 5.98/2.39 r_in_a -> r_out_a(1) 5.98/2.39 5.98/2.39 The set Q consists of the following terms: 5.98/2.39 5.98/2.39 r_in_a 5.98/2.39 5.98/2.39 We have to consider all (P,Q,R)-chains. 5.98/2.39 ---------------------------------------- 5.98/2.39 5.98/2.39 (11) PrologToPiTRSProof (SOUND) 5.98/2.39 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 5.98/2.39 5.98/2.39 p_in_1: (f) 5.98/2.39 5.98/2.39 l_in_1: (f) 5.98/2.39 5.98/2.39 Transforming Prolog into the following Term Rewriting System: 5.98/2.39 5.98/2.39 Pi-finite rewrite system: 5.98/2.39 The TRS R consists of the following rules: 5.98/2.39 5.98/2.39 p_in_a(X) -> U1_a(X, l_in_a(X)) 5.98/2.39 l_in_a([]) -> l_out_a([]) 5.98/2.39 l_in_a(.(H, T)) -> U3_a(H, T, r_in_a(H)) 5.98/2.39 r_in_a(1) -> r_out_a(1) 5.98/2.39 U3_a(H, T, r_out_a(H)) -> U4_a(H, T, l_in_a(T)) 5.98/2.39 U4_a(H, T, l_out_a(T)) -> l_out_a(.(H, T)) 5.98/2.39 U1_a(X, l_out_a(X)) -> U2_a(X, q_in_g(X)) 5.98/2.39 q_in_g(.(A, [])) -> q_out_g(.(A, [])) 5.98/2.39 U2_a(X, q_out_g(X)) -> p_out_a(X) 5.98/2.39 5.98/2.39 The argument filtering Pi contains the following mapping: 5.98/2.39 p_in_a(x1) = p_in_a 5.98/2.39 5.98/2.39 U1_a(x1, x2) = U1_a(x2) 5.98/2.39 5.98/2.39 l_in_a(x1) = l_in_a 5.98/2.39 5.98/2.39 l_out_a(x1) = l_out_a(x1) 5.98/2.39 5.98/2.39 U3_a(x1, x2, x3) = U3_a(x3) 5.98/2.39 5.98/2.39 r_in_a(x1) = r_in_a 5.98/2.39 5.98/2.39 r_out_a(x1) = r_out_a(x1) 5.98/2.39 5.98/2.39 U4_a(x1, x2, x3) = U4_a(x1, x3) 5.98/2.39 5.98/2.39 U2_a(x1, x2) = U2_a(x1, x2) 5.98/2.39 5.98/2.39 q_in_g(x1) = q_in_g(x1) 5.98/2.39 5.98/2.39 .(x1, x2) = .(x1, x2) 5.98/2.39 5.98/2.39 [] = [] 5.98/2.39 5.98/2.39 q_out_g(x1) = q_out_g(x1) 5.98/2.39 5.98/2.39 p_out_a(x1) = p_out_a(x1) 5.98/2.39 5.98/2.39 5.98/2.39 5.98/2.39 5.98/2.39 5.98/2.39 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 5.98/2.39 5.98/2.39 5.98/2.39 5.98/2.39 ---------------------------------------- 5.98/2.39 5.98/2.39 (12) 5.98/2.39 Obligation: 5.98/2.39 Pi-finite rewrite system: 5.98/2.39 The TRS R consists of the following rules: 5.98/2.39 5.98/2.39 p_in_a(X) -> U1_a(X, l_in_a(X)) 5.98/2.39 l_in_a([]) -> l_out_a([]) 5.98/2.39 l_in_a(.(H, T)) -> U3_a(H, T, r_in_a(H)) 5.98/2.39 r_in_a(1) -> r_out_a(1) 5.98/2.39 U3_a(H, T, r_out_a(H)) -> U4_a(H, T, l_in_a(T)) 5.98/2.39 U4_a(H, T, l_out_a(T)) -> l_out_a(.(H, T)) 5.98/2.39 U1_a(X, l_out_a(X)) -> U2_a(X, q_in_g(X)) 5.98/2.39 q_in_g(.(A, [])) -> q_out_g(.(A, [])) 5.98/2.39 U2_a(X, q_out_g(X)) -> p_out_a(X) 5.98/2.39 5.98/2.39 The argument filtering Pi contains the following mapping: 5.98/2.39 p_in_a(x1) = p_in_a 5.98/2.39 5.98/2.39 U1_a(x1, x2) = U1_a(x2) 5.98/2.39 5.98/2.39 l_in_a(x1) = l_in_a 5.98/2.39 5.98/2.39 l_out_a(x1) = l_out_a(x1) 5.98/2.39 5.98/2.39 U3_a(x1, x2, x3) = U3_a(x3) 5.98/2.39 5.98/2.39 r_in_a(x1) = r_in_a 5.98/2.39 5.98/2.39 r_out_a(x1) = r_out_a(x1) 5.98/2.39 5.98/2.39 U4_a(x1, x2, x3) = U4_a(x1, x3) 5.98/2.39 5.98/2.39 U2_a(x1, x2) = U2_a(x1, x2) 5.98/2.39 5.98/2.39 q_in_g(x1) = q_in_g(x1) 5.98/2.39 5.98/2.39 .(x1, x2) = .(x1, x2) 5.98/2.39 5.98/2.39 [] = [] 5.98/2.39 5.98/2.39 q_out_g(x1) = q_out_g(x1) 5.98/2.39 5.98/2.39 p_out_a(x1) = p_out_a(x1) 5.98/2.39 5.98/2.39 5.98/2.39 5.98/2.39 ---------------------------------------- 5.98/2.39 5.98/2.39 (13) DependencyPairsProof (EQUIVALENT) 5.98/2.39 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 5.98/2.39 Pi DP problem: 5.98/2.39 The TRS P consists of the following rules: 5.98/2.39 5.98/2.39 P_IN_A(X) -> U1_A(X, l_in_a(X)) 5.98/2.39 P_IN_A(X) -> L_IN_A(X) 5.98/2.39 L_IN_A(.(H, T)) -> U3_A(H, T, r_in_a(H)) 5.98/2.39 L_IN_A(.(H, T)) -> R_IN_A(H) 5.98/2.39 U3_A(H, T, r_out_a(H)) -> U4_A(H, T, l_in_a(T)) 5.98/2.39 U3_A(H, T, r_out_a(H)) -> L_IN_A(T) 5.98/2.39 U1_A(X, l_out_a(X)) -> U2_A(X, q_in_g(X)) 5.98/2.39 U1_A(X, l_out_a(X)) -> Q_IN_G(X) 5.98/2.39 5.98/2.39 The TRS R consists of the following rules: 5.98/2.39 5.98/2.39 p_in_a(X) -> U1_a(X, l_in_a(X)) 5.98/2.39 l_in_a([]) -> l_out_a([]) 5.98/2.39 l_in_a(.(H, T)) -> U3_a(H, T, r_in_a(H)) 5.98/2.39 r_in_a(1) -> r_out_a(1) 5.98/2.39 U3_a(H, T, r_out_a(H)) -> U4_a(H, T, l_in_a(T)) 5.98/2.39 U4_a(H, T, l_out_a(T)) -> l_out_a(.(H, T)) 5.98/2.39 U1_a(X, l_out_a(X)) -> U2_a(X, q_in_g(X)) 5.98/2.39 q_in_g(.(A, [])) -> q_out_g(.(A, [])) 5.98/2.39 U2_a(X, q_out_g(X)) -> p_out_a(X) 5.98/2.39 5.98/2.39 The argument filtering Pi contains the following mapping: 5.98/2.39 p_in_a(x1) = p_in_a 5.98/2.39 5.98/2.39 U1_a(x1, x2) = U1_a(x2) 5.98/2.39 5.98/2.39 l_in_a(x1) = l_in_a 5.98/2.39 5.98/2.39 l_out_a(x1) = l_out_a(x1) 5.98/2.39 5.98/2.39 U3_a(x1, x2, x3) = U3_a(x3) 5.98/2.39 5.98/2.39 r_in_a(x1) = r_in_a 5.98/2.39 5.98/2.39 r_out_a(x1) = r_out_a(x1) 5.98/2.39 5.98/2.39 U4_a(x1, x2, x3) = U4_a(x1, x3) 5.98/2.39 5.98/2.39 U2_a(x1, x2) = U2_a(x1, x2) 5.98/2.39 5.98/2.39 q_in_g(x1) = q_in_g(x1) 5.98/2.39 5.98/2.39 .(x1, x2) = .(x1, x2) 5.98/2.39 5.98/2.39 [] = [] 5.98/2.39 5.98/2.39 q_out_g(x1) = q_out_g(x1) 5.98/2.39 5.98/2.39 p_out_a(x1) = p_out_a(x1) 5.98/2.39 5.98/2.39 P_IN_A(x1) = P_IN_A 5.98/2.39 5.98/2.39 U1_A(x1, x2) = U1_A(x2) 5.98/2.39 5.98/2.39 L_IN_A(x1) = L_IN_A 5.98/2.39 5.98/2.39 U3_A(x1, x2, x3) = U3_A(x3) 5.98/2.39 5.98/2.39 R_IN_A(x1) = R_IN_A 5.98/2.39 5.98/2.39 U4_A(x1, x2, x3) = U4_A(x1, x3) 5.98/2.39 5.98/2.39 U2_A(x1, x2) = U2_A(x1, x2) 5.98/2.39 5.98/2.39 Q_IN_G(x1) = Q_IN_G(x1) 5.98/2.39 5.98/2.39 5.98/2.39 We have to consider all (P,R,Pi)-chains 5.98/2.39 ---------------------------------------- 5.98/2.39 5.98/2.39 (14) 5.98/2.39 Obligation: 5.98/2.39 Pi DP problem: 5.98/2.39 The TRS P consists of the following rules: 5.98/2.39 5.98/2.39 P_IN_A(X) -> U1_A(X, l_in_a(X)) 5.98/2.39 P_IN_A(X) -> L_IN_A(X) 5.98/2.39 L_IN_A(.(H, T)) -> U3_A(H, T, r_in_a(H)) 5.98/2.39 L_IN_A(.(H, T)) -> R_IN_A(H) 5.98/2.39 U3_A(H, T, r_out_a(H)) -> U4_A(H, T, l_in_a(T)) 5.98/2.39 U3_A(H, T, r_out_a(H)) -> L_IN_A(T) 5.98/2.39 U1_A(X, l_out_a(X)) -> U2_A(X, q_in_g(X)) 5.98/2.39 U1_A(X, l_out_a(X)) -> Q_IN_G(X) 5.98/2.39 5.98/2.39 The TRS R consists of the following rules: 5.98/2.39 5.98/2.39 p_in_a(X) -> U1_a(X, l_in_a(X)) 5.98/2.39 l_in_a([]) -> l_out_a([]) 5.98/2.39 l_in_a(.(H, T)) -> U3_a(H, T, r_in_a(H)) 5.98/2.39 r_in_a(1) -> r_out_a(1) 5.98/2.39 U3_a(H, T, r_out_a(H)) -> U4_a(H, T, l_in_a(T)) 5.98/2.39 U4_a(H, T, l_out_a(T)) -> l_out_a(.(H, T)) 5.98/2.39 U1_a(X, l_out_a(X)) -> U2_a(X, q_in_g(X)) 5.98/2.39 q_in_g(.(A, [])) -> q_out_g(.(A, [])) 5.98/2.39 U2_a(X, q_out_g(X)) -> p_out_a(X) 5.98/2.39 5.98/2.39 The argument filtering Pi contains the following mapping: 5.98/2.39 p_in_a(x1) = p_in_a 5.98/2.39 5.98/2.39 U1_a(x1, x2) = U1_a(x2) 5.98/2.39 5.98/2.39 l_in_a(x1) = l_in_a 5.98/2.39 5.98/2.39 l_out_a(x1) = l_out_a(x1) 5.98/2.39 5.98/2.39 U3_a(x1, x2, x3) = U3_a(x3) 5.98/2.39 5.98/2.39 r_in_a(x1) = r_in_a 5.98/2.39 5.98/2.39 r_out_a(x1) = r_out_a(x1) 5.98/2.39 5.98/2.39 U4_a(x1, x2, x3) = U4_a(x1, x3) 5.98/2.39 5.98/2.39 U2_a(x1, x2) = U2_a(x1, x2) 5.98/2.39 5.98/2.39 q_in_g(x1) = q_in_g(x1) 5.98/2.39 5.98/2.39 .(x1, x2) = .(x1, x2) 5.98/2.39 5.98/2.39 [] = [] 5.98/2.39 5.98/2.39 q_out_g(x1) = q_out_g(x1) 5.98/2.39 5.98/2.39 p_out_a(x1) = p_out_a(x1) 5.98/2.39 5.98/2.39 P_IN_A(x1) = P_IN_A 5.98/2.39 5.98/2.39 U1_A(x1, x2) = U1_A(x2) 5.98/2.39 5.98/2.39 L_IN_A(x1) = L_IN_A 5.98/2.39 5.98/2.39 U3_A(x1, x2, x3) = U3_A(x3) 5.98/2.39 5.98/2.39 R_IN_A(x1) = R_IN_A 5.98/2.39 5.98/2.39 U4_A(x1, x2, x3) = U4_A(x1, x3) 5.98/2.39 5.98/2.39 U2_A(x1, x2) = U2_A(x1, x2) 5.98/2.39 5.98/2.39 Q_IN_G(x1) = Q_IN_G(x1) 5.98/2.39 5.98/2.39 5.98/2.39 We have to consider all (P,R,Pi)-chains 5.98/2.39 ---------------------------------------- 5.98/2.39 5.98/2.39 (15) DependencyGraphProof (EQUIVALENT) 5.98/2.39 The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 6 less nodes. 5.98/2.39 ---------------------------------------- 5.98/2.39 5.98/2.39 (16) 5.98/2.39 Obligation: 5.98/2.39 Pi DP problem: 5.98/2.39 The TRS P consists of the following rules: 5.98/2.39 5.98/2.39 U3_A(H, T, r_out_a(H)) -> L_IN_A(T) 5.98/2.39 L_IN_A(.(H, T)) -> U3_A(H, T, r_in_a(H)) 5.98/2.39 5.98/2.39 The TRS R consists of the following rules: 5.98/2.39 5.98/2.39 p_in_a(X) -> U1_a(X, l_in_a(X)) 5.98/2.39 l_in_a([]) -> l_out_a([]) 5.98/2.39 l_in_a(.(H, T)) -> U3_a(H, T, r_in_a(H)) 5.98/2.39 r_in_a(1) -> r_out_a(1) 5.98/2.39 U3_a(H, T, r_out_a(H)) -> U4_a(H, T, l_in_a(T)) 5.98/2.39 U4_a(H, T, l_out_a(T)) -> l_out_a(.(H, T)) 5.98/2.39 U1_a(X, l_out_a(X)) -> U2_a(X, q_in_g(X)) 5.98/2.39 q_in_g(.(A, [])) -> q_out_g(.(A, [])) 5.98/2.39 U2_a(X, q_out_g(X)) -> p_out_a(X) 5.98/2.39 5.98/2.39 The argument filtering Pi contains the following mapping: 5.98/2.39 p_in_a(x1) = p_in_a 5.98/2.39 5.98/2.39 U1_a(x1, x2) = U1_a(x2) 5.98/2.39 5.98/2.39 l_in_a(x1) = l_in_a 5.98/2.39 5.98/2.39 l_out_a(x1) = l_out_a(x1) 5.98/2.39 5.98/2.39 U3_a(x1, x2, x3) = U3_a(x3) 5.98/2.39 5.98/2.39 r_in_a(x1) = r_in_a 5.98/2.39 5.98/2.39 r_out_a(x1) = r_out_a(x1) 5.98/2.39 5.98/2.39 U4_a(x1, x2, x3) = U4_a(x1, x3) 5.98/2.39 5.98/2.39 U2_a(x1, x2) = U2_a(x1, x2) 5.98/2.39 5.98/2.39 q_in_g(x1) = q_in_g(x1) 5.98/2.39 5.98/2.39 .(x1, x2) = .(x1, x2) 5.98/2.39 5.98/2.39 [] = [] 5.98/2.39 5.98/2.39 q_out_g(x1) = q_out_g(x1) 5.98/2.39 5.98/2.39 p_out_a(x1) = p_out_a(x1) 5.98/2.39 5.98/2.39 L_IN_A(x1) = L_IN_A 5.98/2.39 5.98/2.39 U3_A(x1, x2, x3) = U3_A(x3) 5.98/2.39 5.98/2.39 5.98/2.39 We have to consider all (P,R,Pi)-chains 5.98/2.39 ---------------------------------------- 5.98/2.39 5.98/2.39 (17) UsableRulesProof (EQUIVALENT) 5.98/2.39 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.98/2.39 ---------------------------------------- 5.98/2.39 5.98/2.39 (18) 5.98/2.39 Obligation: 5.98/2.39 Pi DP problem: 5.98/2.39 The TRS P consists of the following rules: 5.98/2.39 5.98/2.39 U3_A(H, T, r_out_a(H)) -> L_IN_A(T) 5.98/2.39 L_IN_A(.(H, T)) -> U3_A(H, T, r_in_a(H)) 5.98/2.39 5.98/2.39 The TRS R consists of the following rules: 5.98/2.39 5.98/2.39 r_in_a(1) -> r_out_a(1) 5.98/2.39 5.98/2.39 The argument filtering Pi contains the following mapping: 5.98/2.39 r_in_a(x1) = r_in_a 5.98/2.39 5.98/2.39 r_out_a(x1) = r_out_a(x1) 5.98/2.39 5.98/2.39 .(x1, x2) = .(x1, x2) 5.98/2.39 5.98/2.39 L_IN_A(x1) = L_IN_A 5.98/2.39 5.98/2.39 U3_A(x1, x2, x3) = U3_A(x3) 5.98/2.39 5.98/2.39 5.98/2.39 We have to consider all (P,R,Pi)-chains 5.98/2.39 ---------------------------------------- 5.98/2.39 5.98/2.39 (19) PiDPToQDPProof (SOUND) 5.98/2.39 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.98/2.39 ---------------------------------------- 5.98/2.39 5.98/2.39 (20) 5.98/2.39 Obligation: 5.98/2.39 Q DP problem: 5.98/2.39 The TRS P consists of the following rules: 5.98/2.39 5.98/2.39 U3_A(r_out_a(H)) -> L_IN_A 5.98/2.39 L_IN_A -> U3_A(r_in_a) 5.98/2.39 5.98/2.39 The TRS R consists of the following rules: 5.98/2.39 5.98/2.39 r_in_a -> r_out_a(1) 5.98/2.39 5.98/2.39 The set Q consists of the following terms: 5.98/2.39 5.98/2.39 r_in_a 5.98/2.39 5.98/2.39 We have to consider all (P,Q,R)-chains. 5.98/2.39 ---------------------------------------- 5.98/2.39 5.98/2.39 (21) PrologToDTProblemTransformerProof (SOUND) 5.98/2.39 Built DT problem from termination graph DT10. 5.98/2.39 5.98/2.39 { 5.98/2.39 "root": 2, 5.98/2.39 "program": { 5.98/2.39 "directives": [], 5.98/2.39 "clauses": [ 5.98/2.39 [ 5.98/2.39 "(p X)", 5.98/2.39 "(',' (l X) (q X))" 5.98/2.39 ], 5.98/2.39 [ 5.98/2.39 "(q (. A ([])))", 5.98/2.39 null 5.98/2.39 ], 5.98/2.39 [ 5.98/2.39 "(r (1))", 5.98/2.39 null 5.98/2.39 ], 5.98/2.39 [ 5.98/2.39 "(l ([]))", 5.98/2.39 null 5.98/2.39 ], 5.98/2.39 [ 5.98/2.39 "(l (. H T))", 5.98/2.39 "(',' (r H) (l T))" 5.98/2.39 ] 5.98/2.39 ] 5.98/2.39 }, 5.98/2.39 "graph": { 5.98/2.39 "nodes": { 5.98/2.39 "29": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": -1, 5.98/2.39 "scope": -1, 5.98/2.39 "term": "(',' (l T4) (q T4))" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "type": "Nodes", 5.98/2.39 "150": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": -1, 5.98/2.39 "scope": -1, 5.98/2.39 "term": "(q (. (1) T14))" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": ["T14"], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "194": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": 1, 5.98/2.39 "scope": 7, 5.98/2.39 "term": "(q (. (1) T14))" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": ["T14"], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "151": { 5.98/2.39 "goal": [ 5.98/2.39 { 5.98/2.39 "clause": 3, 5.98/2.39 "scope": 5, 5.98/2.39 "term": "(l T13)" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "clause": 4, 5.98/2.39 "scope": 5, 5.98/2.39 "term": "(l T13)" 5.98/2.39 } 5.98/2.39 ], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "195": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": -1, 5.98/2.39 "scope": -1, 5.98/2.39 "term": "(true)" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "152": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": 3, 5.98/2.39 "scope": 5, 5.98/2.39 "term": "(l T13)" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "196": { 5.98/2.39 "goal": [], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "153": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": 4, 5.98/2.39 "scope": 5, 5.98/2.39 "term": "(l T13)" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "197": { 5.98/2.39 "goal": [], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "133": { 5.98/2.39 "goal": [], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "134": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": 1, 5.98/2.39 "scope": 3, 5.98/2.39 "term": "(q ([]))" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "156": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": -1, 5.98/2.39 "scope": -1, 5.98/2.39 "term": "(true)" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "135": { 5.98/2.39 "goal": [], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "157": { 5.98/2.39 "goal": [], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "136": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": -1, 5.98/2.39 "scope": -1, 5.98/2.39 "term": "(',' (',' (r T11) (l T12)) (q (. T11 T12)))" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "158": { 5.98/2.39 "goal": [], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "137": { 5.98/2.39 "goal": [], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "138": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": 2, 5.98/2.39 "scope": 4, 5.98/2.39 "term": "(',' (',' (r T11) (l T12)) (q (. T11 T12)))" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "32": { 5.98/2.39 "goal": [ 5.98/2.39 { 5.98/2.39 "clause": 3, 5.98/2.39 "scope": 2, 5.98/2.39 "term": "(',' (l T4) (q T4))" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "clause": 4, 5.98/2.39 "scope": 2, 5.98/2.39 "term": "(',' (l T4) (q T4))" 5.98/2.39 } 5.98/2.39 ], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "13": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": 0, 5.98/2.39 "scope": 1, 5.98/2.39 "term": "(p T1)" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "162": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": -1, 5.98/2.39 "scope": -1, 5.98/2.39 "term": "(',' (r T21) (l T22))" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "141": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": -1, 5.98/2.39 "scope": -1, 5.98/2.39 "term": "(',' (l T13) (q (. (1) T13)))" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "163": { 5.98/2.39 "goal": [], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "120": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": 3, 5.98/2.39 "scope": 2, 5.98/2.39 "term": "(',' (l T4) (q T4))" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "164": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": 2, 5.98/2.39 "scope": 6, 5.98/2.39 "term": "(',' (r T21) (l T22))" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "143": { 5.98/2.39 "goal": [], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "165": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": -1, 5.98/2.39 "scope": -1, 5.98/2.39 "term": "(l T23)" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "122": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": 4, 5.98/2.39 "scope": 2, 5.98/2.39 "term": "(',' (l T4) (q T4))" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "166": { 5.98/2.39 "goal": [], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "2": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": -1, 5.98/2.39 "scope": -1, 5.98/2.39 "term": "(p T1)" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "149": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": -1, 5.98/2.39 "scope": -1, 5.98/2.39 "term": "(l T13)" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "129": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": -1, 5.98/2.39 "scope": -1, 5.98/2.39 "term": "(q ([]))" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "edges": [ 5.98/2.39 { 5.98/2.39 "from": 2, 5.98/2.39 "to": 13, 5.98/2.39 "label": "CASE" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 13, 5.98/2.39 "to": 29, 5.98/2.39 "label": "ONLY EVAL with clause\np(X2) :- ','(l(X2), q(X2)).\nand substitutionT1 -> T4,\nX2 -> T4,\nT3 -> T4" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 29, 5.98/2.39 "to": 32, 5.98/2.39 "label": "CASE" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 32, 5.98/2.39 "to": 120, 5.98/2.39 "label": "PARALLEL" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 32, 5.98/2.39 "to": 122, 5.98/2.39 "label": "PARALLEL" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 120, 5.98/2.39 "to": 129, 5.98/2.39 "label": "EVAL with clause\nl([]).\nand substitutionT4 -> []" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 120, 5.98/2.39 "to": 133, 5.98/2.39 "label": "EVAL-BACKTRACK" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 122, 5.98/2.39 "to": 136, 5.98/2.39 "label": "EVAL with clause\nl(.(X8, X9)) :- ','(r(X8), l(X9)).\nand substitutionX8 -> T11,\nX9 -> T12,\nT4 -> .(T11, T12),\nT9 -> T11,\nT10 -> T12" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 122, 5.98/2.39 "to": 137, 5.98/2.39 "label": "EVAL-BACKTRACK" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 129, 5.98/2.39 "to": 134, 5.98/2.39 "label": "CASE" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 134, 5.98/2.39 "to": 135, 5.98/2.39 "label": "BACKTRACK\nfor clause: q(.(A, []))because of non-unification" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 136, 5.98/2.39 "to": 138, 5.98/2.39 "label": "CASE" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 138, 5.98/2.39 "to": 141, 5.98/2.39 "label": "EVAL with clause\nr(1).\nand substitutionT11 -> 1,\nT12 -> T13" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 138, 5.98/2.39 "to": 143, 5.98/2.39 "label": "EVAL-BACKTRACK" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 141, 5.98/2.39 "to": 149, 5.98/2.39 "label": "SPLIT 1" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 141, 5.98/2.39 "to": 150, 5.98/2.39 "label": "SPLIT 2\nnew knowledge:\nT14 is ground\nreplacements:T13 -> T14" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 149, 5.98/2.39 "to": 151, 5.98/2.39 "label": "CASE" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 150, 5.98/2.39 "to": 194, 5.98/2.39 "label": "CASE" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 151, 5.98/2.39 "to": 152, 5.98/2.39 "label": "PARALLEL" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 151, 5.98/2.39 "to": 153, 5.98/2.39 "label": "PARALLEL" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 152, 5.98/2.39 "to": 156, 5.98/2.39 "label": "EVAL with clause\nl([]).\nand substitutionT13 -> []" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 152, 5.98/2.39 "to": 157, 5.98/2.39 "label": "EVAL-BACKTRACK" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 153, 5.98/2.39 "to": 162, 5.98/2.39 "label": "EVAL with clause\nl(.(X14, X15)) :- ','(r(X14), l(X15)).\nand substitutionX14 -> T21,\nX15 -> T22,\nT13 -> .(T21, T22),\nT19 -> T21,\nT20 -> T22" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 153, 5.98/2.39 "to": 163, 5.98/2.39 "label": "EVAL-BACKTRACK" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 156, 5.98/2.39 "to": 158, 5.98/2.39 "label": "SUCCESS" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 162, 5.98/2.39 "to": 164, 5.98/2.39 "label": "CASE" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 164, 5.98/2.39 "to": 165, 5.98/2.39 "label": "EVAL with clause\nr(1).\nand substitutionT21 -> 1,\nT22 -> T23" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 164, 5.98/2.39 "to": 166, 5.98/2.39 "label": "EVAL-BACKTRACK" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 165, 5.98/2.39 "to": 149, 5.98/2.39 "label": "INSTANCE with matching:\nT13 -> T23" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 194, 5.98/2.39 "to": 195, 5.98/2.39 "label": "EVAL with clause\nq(.(X18, [])).\nand substitutionX18 -> 1,\nT14 -> []" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 194, 5.98/2.39 "to": 196, 5.98/2.39 "label": "EVAL-BACKTRACK" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 195, 5.98/2.39 "to": 197, 5.98/2.39 "label": "SUCCESS" 5.98/2.39 } 5.98/2.39 ], 5.98/2.39 "type": "Graph" 5.98/2.39 } 5.98/2.39 } 5.98/2.39 5.98/2.39 ---------------------------------------- 5.98/2.39 5.98/2.39 (22) 5.98/2.39 Obligation: 5.98/2.39 Triples: 5.98/2.39 5.98/2.39 lA(.(1, X1)) :- lA(X1). 5.98/2.39 pB(.(1, X1)) :- lA(X1). 5.98/2.39 5.98/2.39 Clauses: 5.98/2.39 5.98/2.39 lcA([]). 5.98/2.39 lcA(.(1, X1)) :- lcA(X1). 5.98/2.39 5.98/2.39 Afs: 5.98/2.39 5.98/2.39 pB(x1) = pB 5.98/2.39 5.98/2.39 5.98/2.39 ---------------------------------------- 5.98/2.39 5.98/2.39 (23) TriplesToPiDPProof (SOUND) 5.98/2.39 We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: 5.98/2.39 5.98/2.39 pB_in_1: (f) 5.98/2.39 5.98/2.39 lA_in_1: (f) 5.98/2.39 5.98/2.39 Transforming TRIPLES into the following Term Rewriting System: 5.98/2.39 5.98/2.39 Pi DP problem: 5.98/2.39 The TRS P consists of the following rules: 5.98/2.39 5.98/2.39 PB_IN_A(.(1, X1)) -> U2_A(X1, lA_in_a(X1)) 5.98/2.39 PB_IN_A(.(1, X1)) -> LA_IN_A(X1) 5.98/2.39 LA_IN_A(.(1, X1)) -> U1_A(X1, lA_in_a(X1)) 5.98/2.39 LA_IN_A(.(1, X1)) -> LA_IN_A(X1) 5.98/2.39 5.98/2.39 R is empty. 5.98/2.39 The argument filtering Pi contains the following mapping: 5.98/2.39 lA_in_a(x1) = lA_in_a 5.98/2.39 5.98/2.39 .(x1, x2) = .(x1, x2) 5.98/2.39 5.98/2.39 1 = 1 5.98/2.39 5.98/2.39 PB_IN_A(x1) = PB_IN_A 5.98/2.39 5.98/2.39 U2_A(x1, x2) = U2_A(x2) 5.98/2.39 5.98/2.39 LA_IN_A(x1) = LA_IN_A 5.98/2.39 5.98/2.39 U1_A(x1, x2) = U1_A(x2) 5.98/2.39 5.98/2.39 5.98/2.39 We have to consider all (P,R,Pi)-chains 5.98/2.39 5.98/2.39 5.98/2.39 Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES 5.98/2.39 5.98/2.39 5.98/2.39 5.98/2.39 ---------------------------------------- 5.98/2.39 5.98/2.39 (24) 5.98/2.39 Obligation: 5.98/2.39 Pi DP problem: 5.98/2.39 The TRS P consists of the following rules: 5.98/2.39 5.98/2.39 PB_IN_A(.(1, X1)) -> U2_A(X1, lA_in_a(X1)) 5.98/2.39 PB_IN_A(.(1, X1)) -> LA_IN_A(X1) 5.98/2.39 LA_IN_A(.(1, X1)) -> U1_A(X1, lA_in_a(X1)) 5.98/2.39 LA_IN_A(.(1, X1)) -> LA_IN_A(X1) 5.98/2.39 5.98/2.39 R is empty. 5.98/2.39 The argument filtering Pi contains the following mapping: 5.98/2.39 lA_in_a(x1) = lA_in_a 5.98/2.39 5.98/2.39 .(x1, x2) = .(x1, x2) 5.98/2.39 5.98/2.39 1 = 1 5.98/2.39 5.98/2.39 PB_IN_A(x1) = PB_IN_A 5.98/2.39 5.98/2.39 U2_A(x1, x2) = U2_A(x2) 5.98/2.39 5.98/2.39 LA_IN_A(x1) = LA_IN_A 5.98/2.39 5.98/2.39 U1_A(x1, x2) = U1_A(x2) 5.98/2.39 5.98/2.39 5.98/2.39 We have to consider all (P,R,Pi)-chains 5.98/2.39 ---------------------------------------- 5.98/2.39 5.98/2.39 (25) DependencyGraphProof (EQUIVALENT) 5.98/2.39 The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 3 less nodes. 5.98/2.39 ---------------------------------------- 5.98/2.39 5.98/2.39 (26) 5.98/2.39 Obligation: 5.98/2.39 Pi DP problem: 5.98/2.39 The TRS P consists of the following rules: 5.98/2.39 5.98/2.39 LA_IN_A(.(1, X1)) -> LA_IN_A(X1) 5.98/2.39 5.98/2.39 R is empty. 5.98/2.39 The argument filtering Pi contains the following mapping: 5.98/2.39 .(x1, x2) = .(x1, x2) 5.98/2.39 5.98/2.39 1 = 1 5.98/2.39 5.98/2.39 LA_IN_A(x1) = LA_IN_A 5.98/2.39 5.98/2.39 5.98/2.39 We have to consider all (P,R,Pi)-chains 5.98/2.39 ---------------------------------------- 5.98/2.39 5.98/2.39 (27) PiDPToQDPProof (SOUND) 5.98/2.39 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.98/2.39 ---------------------------------------- 5.98/2.39 5.98/2.39 (28) 5.98/2.39 Obligation: 5.98/2.39 Q DP problem: 5.98/2.39 The TRS P consists of the following rules: 5.98/2.39 5.98/2.39 LA_IN_A -> LA_IN_A 5.98/2.39 5.98/2.39 R is empty. 5.98/2.39 Q is empty. 5.98/2.39 We have to consider all (P,Q,R)-chains. 5.98/2.39 ---------------------------------------- 5.98/2.39 5.98/2.39 (29) PrologToTRSTransformerProof (SOUND) 5.98/2.39 Transformed Prolog program to TRS. 5.98/2.39 5.98/2.39 { 5.98/2.39 "root": 24, 5.98/2.39 "program": { 5.98/2.39 "directives": [], 5.98/2.39 "clauses": [ 5.98/2.39 [ 5.98/2.39 "(p X)", 5.98/2.39 "(',' (l X) (q X))" 5.98/2.39 ], 5.98/2.39 [ 5.98/2.39 "(q (. A ([])))", 5.98/2.39 null 5.98/2.39 ], 5.98/2.39 [ 5.98/2.39 "(r (1))", 5.98/2.39 null 5.98/2.39 ], 5.98/2.39 [ 5.98/2.39 "(l ([]))", 5.98/2.39 null 5.98/2.39 ], 5.98/2.39 [ 5.98/2.39 "(l (. H T))", 5.98/2.39 "(',' (r H) (l T))" 5.98/2.39 ] 5.98/2.39 ] 5.98/2.39 }, 5.98/2.39 "graph": { 5.98/2.39 "nodes": { 5.98/2.39 "24": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": -1, 5.98/2.39 "scope": -1, 5.98/2.39 "term": "(p T1)" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "25": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": 0, 5.98/2.39 "scope": 1, 5.98/2.39 "term": "(p T1)" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "27": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": -1, 5.98/2.39 "scope": -1, 5.98/2.39 "term": "(',' (l T6) (q T6))" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "180": { 5.98/2.39 "goal": [], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "181": { 5.98/2.39 "goal": [], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "160": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": -1, 5.98/2.39 "scope": -1, 5.98/2.39 "term": "(l T16)" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "type": "Nodes", 5.98/2.39 "161": { 5.98/2.39 "goal": [], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "140": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": -1, 5.98/2.39 "scope": -1, 5.98/2.39 "term": "(q T7)" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": ["T7"], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "142": { 5.98/2.39 "goal": [ 5.98/2.39 { 5.98/2.39 "clause": 3, 5.98/2.39 "scope": 2, 5.98/2.39 "term": "(l T6)" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "clause": 4, 5.98/2.39 "scope": 2, 5.98/2.39 "term": "(l T6)" 5.98/2.39 } 5.98/2.39 ], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "154": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": -1, 5.98/2.39 "scope": -1, 5.98/2.39 "term": "(',' (r T14) (l T15))" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "176": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": 1, 5.98/2.39 "scope": 4, 5.98/2.39 "term": "(q T7)" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": ["T7"], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "144": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": 3, 5.98/2.39 "scope": 2, 5.98/2.39 "term": "(l T6)" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "155": { 5.98/2.39 "goal": [], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "145": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": 4, 5.98/2.39 "scope": 2, 5.98/2.39 "term": "(l T6)" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "146": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": -1, 5.98/2.39 "scope": -1, 5.98/2.39 "term": "(true)" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "179": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": -1, 5.98/2.39 "scope": -1, 5.98/2.39 "term": "(true)" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "147": { 5.98/2.39 "goal": [], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "148": { 5.98/2.39 "goal": [], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "159": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": 2, 5.98/2.39 "scope": 3, 5.98/2.39 "term": "(',' (r T14) (l T15))" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "139": { 5.98/2.39 "goal": [{ 5.98/2.39 "clause": -1, 5.98/2.39 "scope": -1, 5.98/2.39 "term": "(l T6)" 5.98/2.39 }], 5.98/2.39 "kb": { 5.98/2.39 "nonunifying": [], 5.98/2.39 "intvars": {}, 5.98/2.39 "arithmetic": { 5.98/2.39 "type": "PlainIntegerRelationState", 5.98/2.39 "relations": [] 5.98/2.39 }, 5.98/2.39 "ground": [], 5.98/2.39 "free": [], 5.98/2.39 "exprvars": [] 5.98/2.39 } 5.98/2.39 } 5.98/2.39 }, 5.98/2.39 "edges": [ 5.98/2.39 { 5.98/2.39 "from": 24, 5.98/2.39 "to": 25, 5.98/2.39 "label": "CASE" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 25, 5.98/2.39 "to": 27, 5.98/2.39 "label": "ONLY EVAL with clause\np(X3) :- ','(l(X3), q(X3)).\nand substitutionT1 -> T6,\nX3 -> T6,\nT5 -> T6" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 27, 5.98/2.39 "to": 139, 5.98/2.39 "label": "SPLIT 1" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 27, 5.98/2.39 "to": 140, 5.98/2.39 "label": "SPLIT 2\nnew knowledge:\nT7 is ground\nreplacements:T6 -> T7" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 139, 5.98/2.39 "to": 142, 5.98/2.39 "label": "CASE" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 140, 5.98/2.39 "to": 176, 5.98/2.39 "label": "CASE" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 142, 5.98/2.39 "to": 144, 5.98/2.39 "label": "PARALLEL" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 142, 5.98/2.39 "to": 145, 5.98/2.39 "label": "PARALLEL" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 144, 5.98/2.39 "to": 146, 5.98/2.39 "label": "EVAL with clause\nl([]).\nand substitutionT6 -> []" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 144, 5.98/2.39 "to": 147, 5.98/2.39 "label": "EVAL-BACKTRACK" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 145, 5.98/2.39 "to": 154, 5.98/2.39 "label": "EVAL with clause\nl(.(X8, X9)) :- ','(r(X8), l(X9)).\nand substitutionX8 -> T14,\nX9 -> T15,\nT6 -> .(T14, T15),\nT12 -> T14,\nT13 -> T15" 5.98/2.39 }, 5.98/2.39 { 5.98/2.39 "from": 145, 5.98/2.39 "to": 155, 5.98/2.39 "label": "EVAL-BACKTRACK" 5.98/2.39 }, 5.98/2.39 { 5.98/2.40 "from": 146, 5.98/2.40 "to": 148, 5.98/2.40 "label": "SUCCESS" 5.98/2.40 }, 5.98/2.40 { 5.98/2.40 "from": 154, 5.98/2.40 "to": 159, 5.98/2.40 "label": "CASE" 5.98/2.40 }, 5.98/2.40 { 5.98/2.40 "from": 159, 5.98/2.40 "to": 160, 5.98/2.40 "label": "EVAL with clause\nr(1).\nand substitutionT14 -> 1,\nT15 -> T16" 5.98/2.40 }, 5.98/2.40 { 5.98/2.40 "from": 159, 5.98/2.40 "to": 161, 5.98/2.40 "label": "EVAL-BACKTRACK" 5.98/2.40 }, 5.98/2.40 { 5.98/2.40 "from": 160, 5.98/2.40 "to": 139, 5.98/2.40 "label": "INSTANCE with matching:\nT6 -> T16" 5.98/2.40 }, 5.98/2.40 { 5.98/2.40 "from": 176, 5.98/2.40 "to": 179, 5.98/2.40 "label": "EVAL with clause\nq(.(X12, [])).\nand substitutionX12 -> T19,\nT7 -> .(T19, [])" 5.98/2.40 }, 5.98/2.40 { 5.98/2.40 "from": 176, 5.98/2.40 "to": 180, 5.98/2.40 "label": "EVAL-BACKTRACK" 5.98/2.40 }, 5.98/2.40 { 5.98/2.40 "from": 179, 5.98/2.40 "to": 181, 5.98/2.40 "label": "SUCCESS" 5.98/2.40 } 5.98/2.40 ], 5.98/2.40 "type": "Graph" 5.98/2.40 } 5.98/2.40 } 5.98/2.40 5.98/2.40 ---------------------------------------- 5.98/2.40 5.98/2.40 (30) 5.98/2.40 Obligation: 5.98/2.40 Q restricted rewrite system: 5.98/2.40 The TRS R consists of the following rules: 5.98/2.40 5.98/2.40 f24_in -> U1(f27_in) 5.98/2.40 U1(f27_out1(T6)) -> f24_out1(T6) 5.98/2.40 f139_in -> f139_out1([]) 5.98/2.40 f139_in -> U2(f139_in) 5.98/2.40 U2(f139_out1(T16)) -> f139_out1(.(1, T16)) 5.98/2.40 f140_in(.(T19, [])) -> f140_out1 5.98/2.40 f27_in -> U3(f139_in) 5.98/2.40 U3(f139_out1(T7)) -> U4(f140_in(T7), T7) 5.98/2.40 U4(f140_out1, T7) -> f27_out1(T7) 5.98/2.40 5.98/2.40 Q is empty. 5.98/2.40 5.98/2.40 ---------------------------------------- 5.98/2.40 5.98/2.40 (31) QTRSRRRProof (EQUIVALENT) 5.98/2.40 Used ordering: 5.98/2.40 Polynomial interpretation [POLO]: 5.98/2.40 5.98/2.40 POL(.(x_1, x_2)) = x_1 + 2*x_2 5.98/2.40 POL(1) = 0 5.98/2.40 POL(U1(x_1)) = 2*x_1 5.98/2.40 POL(U2(x_1)) = 2*x_1 5.98/2.40 POL(U3(x_1)) = 2*x_1 5.98/2.40 POL(U4(x_1, x_2)) = x_1 + x_2 5.98/2.40 POL([]) = 0 5.98/2.40 POL(f139_in) = 0 5.98/2.40 POL(f139_out1(x_1)) = x_1 5.98/2.40 POL(f140_in(x_1)) = x_1 5.98/2.40 POL(f140_out1) = 0 5.98/2.40 POL(f24_in) = 1 5.98/2.40 POL(f24_out1(x_1)) = 2*x_1 5.98/2.40 POL(f27_in) = 0 5.98/2.40 POL(f27_out1(x_1)) = x_1 5.98/2.40 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.98/2.40 5.98/2.40 f24_in -> U1(f27_in) 5.98/2.40 5.98/2.40 5.98/2.40 5.98/2.40 5.98/2.40 ---------------------------------------- 5.98/2.40 5.98/2.40 (32) 5.98/2.40 Obligation: 5.98/2.40 Q restricted rewrite system: 5.98/2.40 The TRS R consists of the following rules: 5.98/2.40 5.98/2.40 U1(f27_out1(T6)) -> f24_out1(T6) 5.98/2.40 f139_in -> f139_out1([]) 5.98/2.40 f139_in -> U2(f139_in) 5.98/2.40 U2(f139_out1(T16)) -> f139_out1(.(1, T16)) 5.98/2.40 f140_in(.(T19, [])) -> f140_out1 5.98/2.40 f27_in -> U3(f139_in) 5.98/2.40 U3(f139_out1(T7)) -> U4(f140_in(T7), T7) 5.98/2.40 U4(f140_out1, T7) -> f27_out1(T7) 5.98/2.40 5.98/2.40 Q is empty. 5.98/2.40 5.98/2.40 ---------------------------------------- 5.98/2.40 5.98/2.40 (33) QTRSRRRProof (EQUIVALENT) 5.98/2.40 Used ordering: 5.98/2.40 Polynomial interpretation [POLO]: 5.98/2.40 5.98/2.40 POL(.(x_1, x_2)) = 2*x_1 + x_2 5.98/2.40 POL(1) = 0 5.98/2.40 POL(U1(x_1)) = 2*x_1 5.98/2.40 POL(U2(x_1)) = x_1 5.98/2.40 POL(U3(x_1)) = 2*x_1 5.98/2.40 POL(U4(x_1, x_2)) = x_1 + 2*x_2 5.98/2.40 POL([]) = 0 5.98/2.40 POL(f139_in) = 0 5.98/2.40 POL(f139_out1(x_1)) = 2*x_1 5.98/2.40 POL(f140_in(x_1)) = x_1 5.98/2.40 POL(f140_out1) = 0 5.98/2.40 POL(f24_out1(x_1)) = 2*x_1 5.98/2.40 POL(f27_in) = 2 5.98/2.40 POL(f27_out1(x_1)) = x_1 5.98/2.40 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.98/2.40 5.98/2.40 f27_in -> U3(f139_in) 5.98/2.40 5.98/2.40 5.98/2.40 5.98/2.40 5.98/2.40 ---------------------------------------- 5.98/2.40 5.98/2.40 (34) 5.98/2.40 Obligation: 5.98/2.40 Q restricted rewrite system: 5.98/2.40 The TRS R consists of the following rules: 5.98/2.40 5.98/2.40 U1(f27_out1(T6)) -> f24_out1(T6) 5.98/2.40 f139_in -> f139_out1([]) 5.98/2.40 f139_in -> U2(f139_in) 5.98/2.40 U2(f139_out1(T16)) -> f139_out1(.(1, T16)) 5.98/2.40 f140_in(.(T19, [])) -> f140_out1 5.98/2.40 U3(f139_out1(T7)) -> U4(f140_in(T7), T7) 5.98/2.40 U4(f140_out1, T7) -> f27_out1(T7) 5.98/2.40 5.98/2.40 Q is empty. 5.98/2.40 5.98/2.40 ---------------------------------------- 5.98/2.40 5.98/2.40 (35) QTRSRRRProof (EQUIVALENT) 5.98/2.40 Used ordering: 5.98/2.40 Polynomial interpretation [POLO]: 5.98/2.40 5.98/2.40 POL(.(x_1, x_2)) = 2*x_1 + x_2 5.98/2.40 POL(1) = 0 5.98/2.40 POL(U1(x_1)) = 2*x_1 5.98/2.40 POL(U2(x_1)) = x_1 5.98/2.40 POL(U3(x_1)) = 1 + 2*x_1 5.98/2.40 POL(U4(x_1, x_2)) = 2 + 2*x_1 + x_2 5.98/2.40 POL([]) = 0 5.98/2.40 POL(f139_in) = 2 5.98/2.40 POL(f139_out1(x_1)) = 2 + 2*x_1 5.98/2.40 POL(f140_in(x_1)) = x_1 5.98/2.40 POL(f140_out1) = 0 5.98/2.40 POL(f24_out1(x_1)) = 2 + 2*x_1 5.98/2.40 POL(f27_out1(x_1)) = 1 + x_1 5.98/2.40 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.98/2.40 5.98/2.40 U3(f139_out1(T7)) -> U4(f140_in(T7), T7) 5.98/2.40 U4(f140_out1, T7) -> f27_out1(T7) 5.98/2.40 5.98/2.40 5.98/2.40 5.98/2.40 5.98/2.40 ---------------------------------------- 5.98/2.40 5.98/2.40 (36) 5.98/2.40 Obligation: 5.98/2.40 Q restricted rewrite system: 5.98/2.40 The TRS R consists of the following rules: 5.98/2.40 5.98/2.40 U1(f27_out1(T6)) -> f24_out1(T6) 5.98/2.40 f139_in -> f139_out1([]) 5.98/2.40 f139_in -> U2(f139_in) 5.98/2.40 U2(f139_out1(T16)) -> f139_out1(.(1, T16)) 5.98/2.40 f140_in(.(T19, [])) -> f140_out1 5.98/2.40 5.98/2.40 Q is empty. 5.98/2.40 5.98/2.40 ---------------------------------------- 5.98/2.40 5.98/2.40 (37) QTRSRRRProof (EQUIVALENT) 5.98/2.40 Used ordering: 5.98/2.40 Polynomial interpretation [POLO]: 5.98/2.40 5.98/2.40 POL(.(x_1, x_2)) = 2*x_1 + x_2 5.98/2.40 POL(1) = 0 5.98/2.40 POL(U1(x_1)) = 2 + x_1 5.98/2.40 POL(U2(x_1)) = 2*x_1 5.98/2.40 POL([]) = 0 5.98/2.40 POL(f139_in) = 0 5.98/2.40 POL(f139_out1(x_1)) = x_1 5.98/2.40 POL(f140_in(x_1)) = 1 + x_1 5.98/2.40 POL(f140_out1) = 1 5.98/2.40 POL(f24_out1(x_1)) = 2*x_1 5.98/2.40 POL(f27_out1(x_1)) = 2 + 2*x_1 5.98/2.40 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.98/2.40 5.98/2.40 U1(f27_out1(T6)) -> f24_out1(T6) 5.98/2.40 5.98/2.40 5.98/2.40 5.98/2.40 5.98/2.40 ---------------------------------------- 5.98/2.40 5.98/2.40 (38) 5.98/2.40 Obligation: 5.98/2.40 Q restricted rewrite system: 5.98/2.40 The TRS R consists of the following rules: 5.98/2.40 5.98/2.40 f139_in -> f139_out1([]) 5.98/2.40 f139_in -> U2(f139_in) 5.98/2.40 U2(f139_out1(T16)) -> f139_out1(.(1, T16)) 5.98/2.40 f140_in(.(T19, [])) -> f140_out1 5.98/2.40 5.98/2.40 Q is empty. 5.98/2.40 5.98/2.40 ---------------------------------------- 5.98/2.40 5.98/2.40 (39) QTRSRRRProof (EQUIVALENT) 5.98/2.40 Used ordering: 5.98/2.40 Polynomial interpretation [POLO]: 5.98/2.40 5.98/2.40 POL(.(x_1, x_2)) = 2*x_1 + x_2 5.98/2.40 POL(1) = 0 5.98/2.40 POL(U2(x_1)) = 2*x_1 5.98/2.40 POL([]) = 0 5.98/2.40 POL(f139_in) = 0 5.98/2.40 POL(f139_out1(x_1)) = 2*x_1 5.98/2.40 POL(f140_in(x_1)) = 1 + 2*x_1 5.98/2.40 POL(f140_out1) = 0 5.98/2.40 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.98/2.40 5.98/2.40 f140_in(.(T19, [])) -> f140_out1 5.98/2.40 5.98/2.40 5.98/2.40 5.98/2.40 5.98/2.40 ---------------------------------------- 5.98/2.40 5.98/2.40 (40) 5.98/2.40 Obligation: 5.98/2.40 Q restricted rewrite system: 5.98/2.40 The TRS R consists of the following rules: 5.98/2.40 5.98/2.40 f139_in -> f139_out1([]) 5.98/2.40 f139_in -> U2(f139_in) 5.98/2.40 U2(f139_out1(T16)) -> f139_out1(.(1, T16)) 5.98/2.40 5.98/2.40 Q is empty. 5.98/2.40 5.98/2.40 ---------------------------------------- 5.98/2.40 5.98/2.40 (41) QTRSRRRProof (EQUIVALENT) 5.98/2.40 Used ordering: 5.98/2.40 Polynomial interpretation [POLO]: 5.98/2.40 5.98/2.40 POL(.(x_1, x_2)) = x_1 + x_2 5.98/2.40 POL(1) = 0 5.98/2.40 POL(U2(x_1)) = x_1 5.98/2.40 POL([]) = 0 5.98/2.40 POL(f139_in) = 1 5.98/2.40 POL(f139_out1(x_1)) = 2*x_1 5.98/2.40 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.98/2.40 5.98/2.40 f139_in -> f139_out1([]) 5.98/2.40 5.98/2.40 5.98/2.40 5.98/2.40 5.98/2.40 ---------------------------------------- 5.98/2.40 5.98/2.40 (42) 5.98/2.40 Obligation: 5.98/2.40 Q restricted rewrite system: 5.98/2.40 The TRS R consists of the following rules: 5.98/2.40 5.98/2.40 f139_in -> U2(f139_in) 5.98/2.40 U2(f139_out1(T16)) -> f139_out1(.(1, T16)) 5.98/2.40 5.98/2.40 Q is empty. 5.98/2.40 5.98/2.40 ---------------------------------------- 5.98/2.40 5.98/2.40 (43) PrologToIRSwTTransformerProof (SOUND) 5.98/2.40 Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert 5.98/2.40 5.98/2.40 { 5.98/2.40 "root": 9, 5.98/2.40 "program": { 5.98/2.40 "directives": [], 5.98/2.40 "clauses": [ 5.98/2.40 [ 5.98/2.40 "(p X)", 5.98/2.40 "(',' (l X) (q X))" 5.98/2.40 ], 5.98/2.40 [ 5.98/2.40 "(q (. A ([])))", 5.98/2.40 null 5.98/2.40 ], 5.98/2.40 [ 5.98/2.40 "(r (1))", 5.98/2.40 null 5.98/2.40 ], 5.98/2.40 [ 5.98/2.40 "(l ([]))", 5.98/2.40 null 5.98/2.40 ], 5.98/2.40 [ 5.98/2.40 "(l (. H T))", 5.98/2.40 "(',' (r H) (l T))" 5.98/2.40 ] 5.98/2.40 ] 5.98/2.40 }, 5.98/2.40 "graph": { 5.98/2.40 "nodes": { 5.98/2.40 "26": { 5.98/2.40 "goal": [{ 5.98/2.40 "clause": 0, 5.98/2.40 "scope": 1, 5.98/2.40 "term": "(p T1)" 5.98/2.40 }], 5.98/2.40 "kb": { 5.98/2.40 "nonunifying": [], 5.98/2.40 "intvars": {}, 5.98/2.40 "arithmetic": { 5.98/2.40 "type": "PlainIntegerRelationState", 5.98/2.40 "relations": [] 5.98/2.40 }, 5.98/2.40 "ground": [], 5.98/2.40 "free": [], 5.98/2.40 "exprvars": [] 5.98/2.40 } 5.98/2.40 }, 5.98/2.40 "28": { 5.98/2.40 "goal": [{ 5.98/2.40 "clause": -1, 5.98/2.40 "scope": -1, 5.98/2.40 "term": "(',' (l T6) (q T6))" 5.98/2.40 }], 5.98/2.40 "kb": { 5.98/2.40 "nonunifying": [], 5.98/2.40 "intvars": {}, 5.98/2.40 "arithmetic": { 5.98/2.40 "type": "PlainIntegerRelationState", 5.98/2.40 "relations": [] 5.98/2.40 }, 5.98/2.40 "ground": [], 5.98/2.40 "free": [], 5.98/2.40 "exprvars": [] 5.98/2.40 } 5.98/2.40 }, 5.98/2.40 "170": { 5.98/2.40 "goal": [], 5.98/2.40 "kb": { 5.98/2.40 "nonunifying": [], 5.98/2.40 "intvars": {}, 5.98/2.40 "arithmetic": { 5.98/2.40 "type": "PlainIntegerRelationState", 5.98/2.40 "relations": [] 5.98/2.40 }, 5.98/2.40 "ground": [], 5.98/2.40 "free": [], 5.98/2.40 "exprvars": [] 5.98/2.40 } 5.98/2.40 }, 5.98/2.40 "171": { 5.98/2.40 "goal": [], 5.98/2.40 "kb": { 5.98/2.40 "nonunifying": [], 5.98/2.40 "intvars": {}, 5.98/2.40 "arithmetic": { 5.98/2.40 "type": "PlainIntegerRelationState", 5.98/2.40 "relations": [] 5.98/2.40 }, 5.98/2.40 "ground": [], 5.98/2.40 "free": [], 5.98/2.40 "exprvars": [] 5.98/2.40 } 5.98/2.40 }, 5.98/2.40 "182": { 5.98/2.40 "goal": [{ 5.98/2.40 "clause": -1, 5.98/2.40 "scope": -1, 5.98/2.40 "term": "(true)" 5.98/2.40 }], 5.98/2.40 "kb": { 5.98/2.40 "nonunifying": [], 5.98/2.40 "intvars": {}, 5.98/2.40 "arithmetic": { 5.98/2.40 "type": "PlainIntegerRelationState", 5.98/2.40 "relations": [] 5.98/2.40 }, 5.98/2.40 "ground": [], 5.98/2.40 "free": [], 5.98/2.40 "exprvars": [] 5.98/2.40 } 5.98/2.40 }, 5.98/2.40 "type": "Nodes", 5.98/2.40 "172": { 5.98/2.40 "goal": [{ 5.98/2.40 "clause": -1, 5.98/2.40 "scope": -1, 5.98/2.40 "term": "(',' (r T14) (l T15))" 5.98/2.40 }], 5.98/2.40 "kb": { 5.98/2.40 "nonunifying": [], 5.98/2.40 "intvars": {}, 5.98/2.40 "arithmetic": { 5.98/2.40 "type": "PlainIntegerRelationState", 5.98/2.40 "relations": [] 5.98/2.40 }, 5.98/2.40 "ground": [], 5.98/2.40 "free": [], 5.98/2.40 "exprvars": [] 5.98/2.40 } 5.98/2.40 }, 5.98/2.40 "183": { 5.98/2.40 "goal": [], 5.98/2.40 "kb": { 5.98/2.40 "nonunifying": [], 5.98/2.40 "intvars": {}, 5.98/2.40 "arithmetic": { 5.98/2.40 "type": "PlainIntegerRelationState", 5.98/2.40 "relations": [] 5.98/2.40 }, 5.98/2.40 "ground": [], 5.98/2.40 "free": [], 5.98/2.40 "exprvars": [] 5.98/2.40 } 5.98/2.40 }, 5.98/2.40 "173": { 5.98/2.40 "goal": [], 5.98/2.40 "kb": { 5.98/2.40 "nonunifying": [], 5.98/2.40 "intvars": {}, 5.98/2.40 "arithmetic": { 5.98/2.40 "type": "PlainIntegerRelationState", 5.98/2.40 "relations": [] 5.98/2.40 }, 5.98/2.40 "ground": [], 5.98/2.40 "free": [], 5.98/2.40 "exprvars": [] 5.98/2.40 } 5.98/2.40 }, 5.98/2.40 "184": { 5.98/2.40 "goal": [], 5.98/2.40 "kb": { 5.98/2.40 "nonunifying": [], 5.98/2.40 "intvars": {}, 5.98/2.40 "arithmetic": { 5.98/2.40 "type": "PlainIntegerRelationState", 5.98/2.40 "relations": [] 5.98/2.40 }, 5.98/2.40 "ground": [], 5.98/2.40 "free": [], 5.98/2.40 "exprvars": [] 5.98/2.40 } 5.98/2.40 }, 5.98/2.40 "174": { 5.98/2.40 "goal": [{ 5.98/2.40 "clause": 2, 5.98/2.40 "scope": 3, 5.98/2.40 "term": "(',' (r T14) (l T15))" 5.98/2.40 }], 5.98/2.40 "kb": { 5.98/2.40 "nonunifying": [], 5.98/2.40 "intvars": {}, 5.98/2.40 "arithmetic": { 5.98/2.40 "type": "PlainIntegerRelationState", 5.98/2.40 "relations": [] 5.98/2.40 }, 5.98/2.40 "ground": [], 5.98/2.40 "free": [], 5.98/2.40 "exprvars": [] 5.98/2.40 } 5.98/2.40 }, 5.98/2.40 "175": { 5.98/2.40 "goal": [{ 5.98/2.40 "clause": -1, 5.98/2.40 "scope": -1, 5.98/2.40 "term": "(l T16)" 5.98/2.40 }], 5.98/2.40 "kb": { 5.98/2.40 "nonunifying": [], 5.98/2.40 "intvars": {}, 5.98/2.40 "arithmetic": { 5.98/2.40 "type": "PlainIntegerRelationState", 5.98/2.40 "relations": [] 5.98/2.40 }, 5.98/2.40 "ground": [], 5.98/2.40 "free": [], 5.98/2.40 "exprvars": [] 5.98/2.40 } 5.98/2.40 }, 5.98/2.40 "110": { 5.98/2.40 "goal": [{ 5.98/2.40 "clause": -1, 5.98/2.40 "scope": -1, 5.98/2.40 "term": "(q T7)" 5.98/2.40 }], 5.98/2.40 "kb": { 5.98/2.40 "nonunifying": [], 5.98/2.40 "intvars": {}, 5.98/2.40 "arithmetic": { 5.98/2.40 "type": "PlainIntegerRelationState", 5.98/2.40 "relations": [] 5.98/2.40 }, 5.98/2.40 "ground": ["T7"], 5.98/2.40 "free": [], 5.98/2.40 "exprvars": [] 5.98/2.40 } 5.98/2.40 }, 5.98/2.40 "177": { 5.98/2.40 "goal": [], 5.98/2.40 "kb": { 5.98/2.40 "nonunifying": [], 5.98/2.40 "intvars": {}, 5.98/2.40 "arithmetic": { 5.98/2.40 "type": "PlainIntegerRelationState", 5.98/2.40 "relations": [] 5.98/2.40 }, 5.98/2.40 "ground": [], 5.98/2.40 "free": [], 5.98/2.40 "exprvars": [] 5.98/2.40 } 5.98/2.40 }, 5.98/2.40 "167": { 5.98/2.40 "goal": [{ 5.98/2.40 "clause": 3, 5.98/2.40 "scope": 2, 5.98/2.40 "term": "(l T6)" 5.98/2.40 }], 5.98/2.40 "kb": { 5.98/2.40 "nonunifying": [], 5.98/2.40 "intvars": {}, 5.98/2.40 "arithmetic": { 5.98/2.40 "type": "PlainIntegerRelationState", 5.98/2.40 "relations": [] 5.98/2.40 }, 5.98/2.40 "ground": [], 5.98/2.40 "free": [], 5.98/2.40 "exprvars": [] 5.98/2.40 } 5.98/2.40 }, 5.98/2.40 "178": { 5.98/2.40 "goal": [{ 5.98/2.40 "clause": 1, 5.98/2.40 "scope": 4, 5.98/2.40 "term": "(q T7)" 5.98/2.40 }], 5.98/2.40 "kb": { 5.98/2.40 "nonunifying": [], 5.98/2.40 "intvars": {}, 5.98/2.40 "arithmetic": { 5.98/2.40 "type": "PlainIntegerRelationState", 5.98/2.40 "relations": [] 5.98/2.40 }, 5.98/2.40 "ground": ["T7"], 5.98/2.40 "free": [], 5.98/2.40 "exprvars": [] 5.98/2.40 } 5.98/2.40 }, 5.98/2.40 "168": { 5.98/2.40 "goal": [{ 5.98/2.40 "clause": 4, 5.98/2.40 "scope": 2, 5.98/2.40 "term": "(l T6)" 5.98/2.40 }], 5.98/2.40 "kb": { 5.98/2.40 "nonunifying": [], 5.98/2.40 "intvars": {}, 5.98/2.40 "arithmetic": { 5.98/2.40 "type": "PlainIntegerRelationState", 5.98/2.40 "relations": [] 5.98/2.40 }, 5.98/2.40 "ground": [], 5.98/2.40 "free": [], 5.98/2.40 "exprvars": [] 5.98/2.40 } 5.98/2.40 }, 5.98/2.40 "114": { 5.98/2.40 "goal": [ 5.98/2.40 { 5.98/2.40 "clause": 3, 5.98/2.40 "scope": 2, 5.98/2.40 "term": "(l T6)" 5.98/2.40 }, 5.98/2.40 { 5.98/2.40 "clause": 4, 5.98/2.40 "scope": 2, 5.98/2.40 "term": "(l T6)" 5.98/2.40 } 5.98/2.40 ], 5.98/2.40 "kb": { 5.98/2.40 "nonunifying": [], 5.98/2.40 "intvars": {}, 5.98/2.40 "arithmetic": { 5.98/2.40 "type": "PlainIntegerRelationState", 5.98/2.40 "relations": [] 5.98/2.40 }, 5.98/2.40 "ground": [], 5.98/2.40 "free": [], 5.98/2.40 "exprvars": [] 5.98/2.40 } 5.98/2.40 }, 5.98/2.40 "169": { 5.98/2.40 "goal": [{ 5.98/2.40 "clause": -1, 5.98/2.40 "scope": -1, 5.98/2.40 "term": "(true)" 5.98/2.40 }], 5.98/2.40 "kb": { 5.98/2.40 "nonunifying": [], 5.98/2.40 "intvars": {}, 5.98/2.40 "arithmetic": { 5.98/2.40 "type": "PlainIntegerRelationState", 5.98/2.40 "relations": [] 5.98/2.40 }, 5.98/2.40 "ground": [], 5.98/2.40 "free": [], 5.98/2.40 "exprvars": [] 5.98/2.40 } 5.98/2.40 }, 5.98/2.40 "9": { 5.98/2.40 "goal": [{ 5.98/2.40 "clause": -1, 5.98/2.40 "scope": -1, 5.98/2.40 "term": "(p T1)" 5.98/2.40 }], 5.98/2.40 "kb": { 5.98/2.40 "nonunifying": [], 5.98/2.40 "intvars": {}, 5.98/2.40 "arithmetic": { 5.98/2.40 "type": "PlainIntegerRelationState", 5.98/2.40 "relations": [] 5.98/2.40 }, 5.98/2.40 "ground": [], 5.98/2.40 "free": [], 5.98/2.40 "exprvars": [] 5.98/2.40 } 5.98/2.40 }, 5.98/2.40 "109": { 5.98/2.40 "goal": [{ 5.98/2.40 "clause": -1, 5.98/2.40 "scope": -1, 5.98/2.40 "term": "(l T6)" 5.98/2.40 }], 5.98/2.40 "kb": { 5.98/2.40 "nonunifying": [], 5.98/2.40 "intvars": {}, 5.98/2.40 "arithmetic": { 5.98/2.40 "type": "PlainIntegerRelationState", 5.98/2.40 "relations": [] 5.98/2.40 }, 5.98/2.40 "ground": [], 5.98/2.40 "free": [], 5.98/2.40 "exprvars": [] 5.98/2.40 } 5.98/2.40 } 5.98/2.40 }, 5.98/2.40 "edges": [ 5.98/2.40 { 5.98/2.40 "from": 9, 5.98/2.40 "to": 26, 5.98/2.40 "label": "CASE" 5.98/2.40 }, 5.98/2.40 { 5.98/2.40 "from": 26, 5.98/2.40 "to": 28, 5.98/2.40 "label": "ONLY EVAL with clause\np(X3) :- ','(l(X3), q(X3)).\nand substitutionT1 -> T6,\nX3 -> T6,\nT5 -> T6" 5.98/2.40 }, 5.98/2.40 { 5.98/2.40 "from": 28, 5.98/2.40 "to": 109, 5.98/2.40 "label": "SPLIT 1" 5.98/2.40 }, 5.98/2.40 { 5.98/2.40 "from": 28, 5.98/2.40 "to": 110, 5.98/2.40 "label": "SPLIT 2\nnew knowledge:\nT7 is ground\nreplacements:T6 -> T7" 5.98/2.40 }, 5.98/2.40 { 5.98/2.40 "from": 109, 5.98/2.40 "to": 114, 5.98/2.40 "label": "CASE" 5.98/2.40 }, 5.98/2.40 { 5.98/2.40 "from": 110, 5.98/2.40 "to": 178, 5.98/2.40 "label": "CASE" 5.98/2.40 }, 5.98/2.40 { 5.98/2.40 "from": 114, 5.98/2.40 "to": 167, 5.98/2.40 "label": "PARALLEL" 5.98/2.40 }, 5.98/2.40 { 5.98/2.40 "from": 114, 5.98/2.40 "to": 168, 5.98/2.40 "label": "PARALLEL" 5.98/2.40 }, 5.98/2.40 { 5.98/2.40 "from": 167, 5.98/2.40 "to": 169, 5.98/2.40 "label": "EVAL with clause\nl([]).\nand substitutionT6 -> []" 5.98/2.40 }, 5.98/2.40 { 5.98/2.40 "from": 167, 5.98/2.40 "to": 170, 5.98/2.40 "label": "EVAL-BACKTRACK" 5.98/2.40 }, 5.98/2.40 { 5.98/2.40 "from": 168, 5.98/2.40 "to": 172, 5.98/2.40 "label": "EVAL with clause\nl(.(X8, X9)) :- ','(r(X8), l(X9)).\nand substitutionX8 -> T14,\nX9 -> T15,\nT6 -> .(T14, T15),\nT12 -> T14,\nT13 -> T15" 5.98/2.40 }, 5.98/2.40 { 5.98/2.40 "from": 168, 5.98/2.40 "to": 173, 5.98/2.40 "label": "EVAL-BACKTRACK" 5.98/2.40 }, 5.98/2.40 { 5.98/2.40 "from": 169, 5.98/2.40 "to": 171, 5.98/2.40 "label": "SUCCESS" 5.98/2.40 }, 5.98/2.40 { 5.98/2.40 "from": 172, 5.98/2.40 "to": 174, 5.98/2.40 "label": "CASE" 5.98/2.40 }, 5.98/2.40 { 5.98/2.40 "from": 174, 5.98/2.40 "to": 175, 5.98/2.40 "label": "EVAL with clause\nr(1).\nand substitutionT14 -> 1,\nT15 -> T16" 5.98/2.40 }, 5.98/2.40 { 5.98/2.40 "from": 174, 5.98/2.40 "to": 177, 5.98/2.40 "label": "EVAL-BACKTRACK" 5.98/2.40 }, 5.98/2.40 { 5.98/2.40 "from": 175, 5.98/2.40 "to": 109, 5.98/2.40 "label": "INSTANCE with matching:\nT6 -> T16" 5.98/2.40 }, 5.98/2.40 { 5.98/2.40 "from": 178, 5.98/2.40 "to": 182, 5.98/2.40 "label": "EVAL with clause\nq(.(X12, [])).\nand substitutionX12 -> T19,\nT7 -> .(T19, [])" 5.98/2.40 }, 5.98/2.40 { 5.98/2.40 "from": 178, 5.98/2.40 "to": 183, 5.98/2.40 "label": "EVAL-BACKTRACK" 5.98/2.40 }, 5.98/2.40 { 5.98/2.40 "from": 182, 5.98/2.40 "to": 184, 5.98/2.40 "label": "SUCCESS" 5.98/2.40 } 5.98/2.40 ], 5.98/2.40 "type": "Graph" 5.98/2.40 } 5.98/2.40 } 5.98/2.40 5.98/2.40 ---------------------------------------- 5.98/2.40 5.98/2.40 (44) 5.98/2.40 Obligation: 5.98/2.40 Rules: 5.98/2.40 f168_in -> f172_in :|: TRUE 5.98/2.40 f172_out -> f168_out :|: TRUE 5.98/2.40 f168_in -> f173_in :|: TRUE 5.98/2.40 f173_out -> f168_out :|: TRUE 5.98/2.40 f172_in -> f174_in :|: TRUE 5.98/2.40 f174_out -> f172_out :|: TRUE 5.98/2.40 f114_in -> f167_in :|: TRUE 5.98/2.40 f168_out -> f114_out :|: TRUE 5.98/2.40 f167_out -> f114_out :|: TRUE 5.98/2.40 f114_in -> f168_in :|: TRUE 5.98/2.40 f114_out -> f109_out :|: TRUE 5.98/2.40 f109_in -> f114_in :|: TRUE 5.98/2.40 f175_in -> f109_in :|: TRUE 5.98/2.40 f109_out -> f175_out :|: TRUE 5.98/2.40 f174_in -> f175_in :|: TRUE 5.98/2.40 f174_in -> f177_in :|: TRUE 5.98/2.40 f177_out -> f174_out :|: TRUE 5.98/2.40 f175_out -> f174_out :|: TRUE 5.98/2.40 f26_out -> f9_out :|: TRUE 5.98/2.40 f9_in -> f26_in :|: TRUE 5.98/2.40 f26_in -> f28_in :|: TRUE 5.98/2.40 f28_out -> f26_out :|: TRUE 5.98/2.40 f28_in -> f109_in :|: TRUE 5.98/2.40 f109_out -> f110_in(T7) :|: TRUE 5.98/2.40 f110_out(x) -> f28_out :|: TRUE 5.98/2.40 Start term: f9_in 5.98/2.40 5.98/2.40 ---------------------------------------- 5.98/2.40 5.98/2.40 (45) IRSwTSimpleDependencyGraphProof (EQUIVALENT) 5.98/2.40 Constructed simple dependency graph. 5.98/2.40 5.98/2.40 Simplified to the following IRSwTs: 5.98/2.40 5.98/2.40 intTRSProblem: 5.98/2.40 f168_in -> f172_in :|: TRUE 5.98/2.40 f172_in -> f174_in :|: TRUE 5.98/2.40 f114_in -> f168_in :|: TRUE 5.98/2.40 f109_in -> f114_in :|: TRUE 5.98/2.40 f175_in -> f109_in :|: TRUE 5.98/2.40 f174_in -> f175_in :|: TRUE 5.98/2.40 5.98/2.40 5.98/2.40 ---------------------------------------- 5.98/2.40 5.98/2.40 (46) 5.98/2.40 Obligation: 5.98/2.40 Rules: 5.98/2.40 f168_in -> f172_in :|: TRUE 5.98/2.40 f172_in -> f174_in :|: TRUE 5.98/2.40 f114_in -> f168_in :|: TRUE 5.98/2.40 f109_in -> f114_in :|: TRUE 5.98/2.40 f175_in -> f109_in :|: TRUE 5.98/2.40 f174_in -> f175_in :|: TRUE 5.98/2.40 5.98/2.40 ---------------------------------------- 5.98/2.40 5.98/2.40 (47) IntTRSCompressionProof (EQUIVALENT) 5.98/2.40 Compressed rules. 5.98/2.40 ---------------------------------------- 5.98/2.40 5.98/2.40 (48) 5.98/2.40 Obligation: 5.98/2.40 Rules: 5.98/2.40 f175_in -> f175_in :|: TRUE 5.98/2.40 5.98/2.40 ---------------------------------------- 5.98/2.40 5.98/2.40 (49) IRSFormatTransformerProof (EQUIVALENT) 5.98/2.40 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 5.98/2.40 ---------------------------------------- 5.98/2.40 5.98/2.40 (50) 5.98/2.40 Obligation: 5.98/2.40 Rules: 5.98/2.40 f175_in -> f175_in :|: TRUE 5.98/2.40 5.98/2.40 ---------------------------------------- 5.98/2.40 5.98/2.40 (51) IRSwTTerminationDigraphProof (EQUIVALENT) 5.98/2.40 Constructed termination digraph! 5.98/2.40 Nodes: 5.98/2.40 (1) f175_in -> f175_in :|: TRUE 5.98/2.40 5.98/2.40 Arcs: 5.98/2.40 (1) -> (1) 5.98/2.40 5.98/2.40 This digraph is fully evaluated! 5.98/2.40 ---------------------------------------- 5.98/2.40 5.98/2.40 (52) 5.98/2.40 Obligation: 5.98/2.40 5.98/2.40 Termination digraph: 5.98/2.40 Nodes: 5.98/2.40 (1) f175_in -> f175_in :|: TRUE 5.98/2.40 5.98/2.40 Arcs: 5.98/2.40 (1) -> (1) 5.98/2.40 5.98/2.40 This digraph is fully evaluated! 5.98/2.40 5.98/2.40 ---------------------------------------- 5.98/2.40 5.98/2.40 (53) FilterProof (EQUIVALENT) 5.98/2.40 Used the following sort dictionary for filtering: 5.98/2.40 f175_in() 5.98/2.40 Replaced non-predefined constructor symbols by 0. 5.98/2.40 ---------------------------------------- 5.98/2.40 5.98/2.40 (54) 5.98/2.40 Obligation: 5.98/2.40 Rules: 5.98/2.40 f175_in -> f175_in :|: TRUE 5.98/2.40 5.98/2.40 ---------------------------------------- 5.98/2.40 5.98/2.40 (55) IntTRSNonPeriodicNontermProof (COMPLETE) 5.98/2.40 Normalized system to the following form: 5.98/2.40 f(pc) -> f(1) :|: pc = 1 && TRUE 5.98/2.40 Proved unsatisfiability of the following formula, indicating that the system is never left after entering: 5.98/2.40 ((run2_0 = ((1 * 1)) and (((run1_0 * 1)) = ((1 * 1)) and T)) and !(((run2_0 * 1)) = ((1 * 1)) and T)) 5.98/2.40 Proved satisfiability of the following formula, indicating that the system is entered at least once: 5.98/2.40 (run2_0 = ((1 * 1)) and (((run1_0 * 1)) = ((1 * 1)) and T)) 5.98/2.40 5.98/2.40 ---------------------------------------- 5.98/2.40 5.98/2.40 (56) 5.98/2.40 NO 5.98/2.42 EOF