4.43/2.11 YES 4.43/2.12 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 4.43/2.12 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.43/2.12 4.43/2.12 4.43/2.12 Termination w.r.t. Q of the given QTRS could be proven: 4.43/2.12 4.43/2.12 (0) QTRS 4.43/2.12 (1) QTRSToCSRProof [SOUND, 0 ms] 4.43/2.12 (2) CSR 4.43/2.12 (3) CSDependencyPairsProof [EQUIVALENT, 1 ms] 4.43/2.12 (4) QCSDP 4.43/2.12 (5) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 4.43/2.12 (6) AND 4.43/2.12 (7) QCSDP 4.43/2.12 (8) QCSDPSubtermProof [EQUIVALENT, 0 ms] 4.43/2.12 (9) QCSDP 4.43/2.12 (10) PIsEmptyProof [EQUIVALENT, 0 ms] 4.43/2.12 (11) YES 4.43/2.12 (12) QCSDP 4.43/2.12 (13) QCSDPReductionPairProof [EQUIVALENT, 10 ms] 4.43/2.12 (14) QCSDP 4.43/2.12 (15) PIsEmptyProof [EQUIVALENT, 0 ms] 4.43/2.12 (16) YES 4.43/2.12 (17) QCSDP 4.43/2.12 (18) QCSDPSubtermProof [EQUIVALENT, 0 ms] 4.43/2.12 (19) QCSDP 4.43/2.12 (20) PIsEmptyProof [EQUIVALENT, 0 ms] 4.43/2.12 (21) YES 4.43/2.12 (22) QCSDP 4.43/2.12 (23) QCSDPSubtermProof [EQUIVALENT, 0 ms] 4.43/2.12 (24) QCSDP 4.43/2.12 (25) PIsEmptyProof [EQUIVALENT, 0 ms] 4.43/2.12 (26) YES 4.43/2.12 4.43/2.12 4.43/2.12 ---------------------------------------- 4.43/2.12 4.43/2.12 (0) 4.43/2.12 Obligation: 4.43/2.12 Q restricted rewrite system: 4.43/2.12 The TRS R consists of the following rules: 4.43/2.12 4.43/2.12 active(from(X)) -> mark(cons(X, from(s(X)))) 4.43/2.12 active(sel(0, cons(X, XS))) -> mark(X) 4.43/2.12 active(sel(s(N), cons(X, XS))) -> mark(sel(N, XS)) 4.43/2.12 active(minus(X, 0)) -> mark(0) 4.43/2.12 active(minus(s(X), s(Y))) -> mark(minus(X, Y)) 4.43/2.12 active(quot(0, s(Y))) -> mark(0) 4.43/2.12 active(quot(s(X), s(Y))) -> mark(s(quot(minus(X, Y), s(Y)))) 4.43/2.12 active(zWquot(XS, nil)) -> mark(nil) 4.43/2.12 active(zWquot(nil, XS)) -> mark(nil) 4.43/2.12 active(zWquot(cons(X, XS), cons(Y, YS))) -> mark(cons(quot(X, Y), zWquot(XS, YS))) 4.43/2.12 active(from(X)) -> from(active(X)) 4.43/2.12 active(cons(X1, X2)) -> cons(active(X1), X2) 4.43/2.12 active(s(X)) -> s(active(X)) 4.43/2.12 active(sel(X1, X2)) -> sel(active(X1), X2) 4.43/2.12 active(sel(X1, X2)) -> sel(X1, active(X2)) 4.43/2.12 active(minus(X1, X2)) -> minus(active(X1), X2) 4.43/2.12 active(minus(X1, X2)) -> minus(X1, active(X2)) 4.43/2.12 active(quot(X1, X2)) -> quot(active(X1), X2) 4.43/2.12 active(quot(X1, X2)) -> quot(X1, active(X2)) 4.43/2.12 active(zWquot(X1, X2)) -> zWquot(active(X1), X2) 4.43/2.12 active(zWquot(X1, X2)) -> zWquot(X1, active(X2)) 4.43/2.12 from(mark(X)) -> mark(from(X)) 4.43/2.12 cons(mark(X1), X2) -> mark(cons(X1, X2)) 4.43/2.12 s(mark(X)) -> mark(s(X)) 4.43/2.12 sel(mark(X1), X2) -> mark(sel(X1, X2)) 4.43/2.12 sel(X1, mark(X2)) -> mark(sel(X1, X2)) 4.43/2.12 minus(mark(X1), X2) -> mark(minus(X1, X2)) 4.43/2.12 minus(X1, mark(X2)) -> mark(minus(X1, X2)) 4.43/2.12 quot(mark(X1), X2) -> mark(quot(X1, X2)) 4.43/2.12 quot(X1, mark(X2)) -> mark(quot(X1, X2)) 4.43/2.12 zWquot(mark(X1), X2) -> mark(zWquot(X1, X2)) 4.43/2.12 zWquot(X1, mark(X2)) -> mark(zWquot(X1, X2)) 4.43/2.12 proper(from(X)) -> from(proper(X)) 4.43/2.12 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 4.43/2.12 proper(s(X)) -> s(proper(X)) 4.43/2.12 proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) 4.43/2.12 proper(0) -> ok(0) 4.43/2.12 proper(minus(X1, X2)) -> minus(proper(X1), proper(X2)) 4.43/2.12 proper(quot(X1, X2)) -> quot(proper(X1), proper(X2)) 4.43/2.12 proper(zWquot(X1, X2)) -> zWquot(proper(X1), proper(X2)) 4.43/2.12 proper(nil) -> ok(nil) 4.43/2.12 from(ok(X)) -> ok(from(X)) 4.43/2.12 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 4.43/2.12 s(ok(X)) -> ok(s(X)) 4.43/2.12 sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) 4.43/2.12 minus(ok(X1), ok(X2)) -> ok(minus(X1, X2)) 4.43/2.12 quot(ok(X1), ok(X2)) -> ok(quot(X1, X2)) 4.43/2.12 zWquot(ok(X1), ok(X2)) -> ok(zWquot(X1, X2)) 4.43/2.12 top(mark(X)) -> top(proper(X)) 4.43/2.12 top(ok(X)) -> top(active(X)) 4.43/2.12 4.43/2.12 The set Q consists of the following terms: 4.43/2.12 4.43/2.12 active(from(x0)) 4.43/2.12 active(cons(x0, x1)) 4.43/2.12 active(s(x0)) 4.43/2.12 active(sel(x0, x1)) 4.43/2.12 active(minus(x0, x1)) 4.43/2.12 active(quot(x0, x1)) 4.43/2.12 active(zWquot(x0, x1)) 4.43/2.12 from(mark(x0)) 4.43/2.12 cons(mark(x0), x1) 4.43/2.12 s(mark(x0)) 4.43/2.12 sel(mark(x0), x1) 4.43/2.12 sel(x0, mark(x1)) 4.43/2.12 minus(mark(x0), x1) 4.43/2.12 minus(x0, mark(x1)) 4.43/2.12 quot(mark(x0), x1) 4.43/2.12 quot(x0, mark(x1)) 4.43/2.12 zWquot(mark(x0), x1) 4.43/2.12 zWquot(x0, mark(x1)) 4.43/2.12 proper(from(x0)) 4.43/2.12 proper(cons(x0, x1)) 4.43/2.12 proper(s(x0)) 4.43/2.12 proper(sel(x0, x1)) 4.43/2.12 proper(0) 4.43/2.12 proper(minus(x0, x1)) 4.43/2.12 proper(quot(x0, x1)) 4.43/2.12 proper(zWquot(x0, x1)) 4.43/2.12 proper(nil) 4.43/2.12 from(ok(x0)) 4.43/2.12 cons(ok(x0), ok(x1)) 4.43/2.12 s(ok(x0)) 4.43/2.12 sel(ok(x0), ok(x1)) 4.43/2.12 minus(ok(x0), ok(x1)) 4.43/2.12 quot(ok(x0), ok(x1)) 4.43/2.12 zWquot(ok(x0), ok(x1)) 4.43/2.12 top(mark(x0)) 4.43/2.12 top(ok(x0)) 4.43/2.12 4.43/2.12 4.43/2.12 ---------------------------------------- 4.43/2.12 4.43/2.12 (1) QTRSToCSRProof (SOUND) 4.43/2.12 The following Q TRS is given: Q restricted rewrite system: 4.43/2.12 The TRS R consists of the following rules: 4.43/2.12 4.43/2.12 active(from(X)) -> mark(cons(X, from(s(X)))) 4.43/2.12 active(sel(0, cons(X, XS))) -> mark(X) 4.43/2.12 active(sel(s(N), cons(X, XS))) -> mark(sel(N, XS)) 4.43/2.12 active(minus(X, 0)) -> mark(0) 4.43/2.12 active(minus(s(X), s(Y))) -> mark(minus(X, Y)) 4.43/2.12 active(quot(0, s(Y))) -> mark(0) 4.43/2.12 active(quot(s(X), s(Y))) -> mark(s(quot(minus(X, Y), s(Y)))) 4.43/2.12 active(zWquot(XS, nil)) -> mark(nil) 4.43/2.12 active(zWquot(nil, XS)) -> mark(nil) 4.43/2.12 active(zWquot(cons(X, XS), cons(Y, YS))) -> mark(cons(quot(X, Y), zWquot(XS, YS))) 4.43/2.12 active(from(X)) -> from(active(X)) 4.43/2.12 active(cons(X1, X2)) -> cons(active(X1), X2) 4.43/2.12 active(s(X)) -> s(active(X)) 4.43/2.12 active(sel(X1, X2)) -> sel(active(X1), X2) 4.43/2.12 active(sel(X1, X2)) -> sel(X1, active(X2)) 4.43/2.12 active(minus(X1, X2)) -> minus(active(X1), X2) 4.43/2.12 active(minus(X1, X2)) -> minus(X1, active(X2)) 4.43/2.12 active(quot(X1, X2)) -> quot(active(X1), X2) 4.43/2.12 active(quot(X1, X2)) -> quot(X1, active(X2)) 4.43/2.12 active(zWquot(X1, X2)) -> zWquot(active(X1), X2) 4.43/2.12 active(zWquot(X1, X2)) -> zWquot(X1, active(X2)) 4.43/2.12 from(mark(X)) -> mark(from(X)) 4.43/2.12 cons(mark(X1), X2) -> mark(cons(X1, X2)) 4.43/2.12 s(mark(X)) -> mark(s(X)) 4.43/2.12 sel(mark(X1), X2) -> mark(sel(X1, X2)) 4.43/2.12 sel(X1, mark(X2)) -> mark(sel(X1, X2)) 4.43/2.12 minus(mark(X1), X2) -> mark(minus(X1, X2)) 4.43/2.12 minus(X1, mark(X2)) -> mark(minus(X1, X2)) 4.43/2.12 quot(mark(X1), X2) -> mark(quot(X1, X2)) 4.43/2.12 quot(X1, mark(X2)) -> mark(quot(X1, X2)) 4.43/2.12 zWquot(mark(X1), X2) -> mark(zWquot(X1, X2)) 4.43/2.12 zWquot(X1, mark(X2)) -> mark(zWquot(X1, X2)) 4.43/2.12 proper(from(X)) -> from(proper(X)) 4.43/2.12 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 4.43/2.12 proper(s(X)) -> s(proper(X)) 4.43/2.12 proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) 4.43/2.12 proper(0) -> ok(0) 4.43/2.12 proper(minus(X1, X2)) -> minus(proper(X1), proper(X2)) 4.43/2.12 proper(quot(X1, X2)) -> quot(proper(X1), proper(X2)) 4.43/2.12 proper(zWquot(X1, X2)) -> zWquot(proper(X1), proper(X2)) 4.43/2.12 proper(nil) -> ok(nil) 4.43/2.12 from(ok(X)) -> ok(from(X)) 4.43/2.12 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 4.43/2.12 s(ok(X)) -> ok(s(X)) 4.43/2.12 sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) 4.43/2.12 minus(ok(X1), ok(X2)) -> ok(minus(X1, X2)) 4.43/2.12 quot(ok(X1), ok(X2)) -> ok(quot(X1, X2)) 4.43/2.12 zWquot(ok(X1), ok(X2)) -> ok(zWquot(X1, X2)) 4.43/2.12 top(mark(X)) -> top(proper(X)) 4.43/2.12 top(ok(X)) -> top(active(X)) 4.43/2.12 4.43/2.12 The set Q consists of the following terms: 4.43/2.12 4.43/2.12 active(from(x0)) 4.43/2.12 active(cons(x0, x1)) 4.43/2.12 active(s(x0)) 4.43/2.12 active(sel(x0, x1)) 4.43/2.12 active(minus(x0, x1)) 4.43/2.12 active(quot(x0, x1)) 4.43/2.12 active(zWquot(x0, x1)) 4.43/2.12 from(mark(x0)) 4.43/2.12 cons(mark(x0), x1) 4.43/2.12 s(mark(x0)) 4.43/2.12 sel(mark(x0), x1) 4.43/2.12 sel(x0, mark(x1)) 4.43/2.12 minus(mark(x0), x1) 4.43/2.12 minus(x0, mark(x1)) 4.43/2.12 quot(mark(x0), x1) 4.43/2.12 quot(x0, mark(x1)) 4.43/2.12 zWquot(mark(x0), x1) 4.43/2.12 zWquot(x0, mark(x1)) 4.43/2.12 proper(from(x0)) 4.43/2.12 proper(cons(x0, x1)) 4.43/2.12 proper(s(x0)) 4.43/2.12 proper(sel(x0, x1)) 4.43/2.12 proper(0) 4.43/2.12 proper(minus(x0, x1)) 4.43/2.12 proper(quot(x0, x1)) 4.43/2.12 proper(zWquot(x0, x1)) 4.43/2.12 proper(nil) 4.43/2.12 from(ok(x0)) 4.43/2.12 cons(ok(x0), ok(x1)) 4.43/2.12 s(ok(x0)) 4.43/2.12 sel(ok(x0), ok(x1)) 4.43/2.12 minus(ok(x0), ok(x1)) 4.43/2.12 quot(ok(x0), ok(x1)) 4.43/2.12 zWquot(ok(x0), ok(x1)) 4.43/2.12 top(mark(x0)) 4.43/2.12 top(ok(x0)) 4.43/2.12 4.43/2.12 Special symbols used for the transformation (see [GM04]): 4.43/2.12 top: top_1, active: active_1, mark: mark_1, ok: ok_1, proper: proper_1 4.43/2.12 The replacement map contains the following entries: 4.43/2.12 4.43/2.12 from: {1} 4.43/2.12 cons: {1} 4.43/2.12 s: {1} 4.43/2.12 sel: {1, 2} 4.43/2.12 0: empty set 4.43/2.12 minus: {1, 2} 4.43/2.12 quot: {1, 2} 4.43/2.12 zWquot: {1, 2} 4.43/2.12 nil: empty set 4.43/2.12 The QTRS contained just a subset of rules created by the complete Giesl-Middeldorp transformation. Therefore, the inverse transformation is sound, but not necessarily complete. 4.43/2.12 ---------------------------------------- 4.43/2.12 4.43/2.12 (2) 4.43/2.12 Obligation: 4.43/2.12 Context-sensitive rewrite system: 4.43/2.12 The TRS R consists of the following rules: 4.43/2.12 4.43/2.12 from(X) -> cons(X, from(s(X))) 4.43/2.12 sel(0, cons(X, XS)) -> X 4.43/2.12 sel(s(N), cons(X, XS)) -> sel(N, XS) 4.43/2.12 minus(X, 0) -> 0 4.43/2.12 minus(s(X), s(Y)) -> minus(X, Y) 4.43/2.12 quot(0, s(Y)) -> 0 4.43/2.12 quot(s(X), s(Y)) -> s(quot(minus(X, Y), s(Y))) 4.43/2.12 zWquot(XS, nil) -> nil 4.43/2.12 zWquot(nil, XS) -> nil 4.43/2.12 zWquot(cons(X, XS), cons(Y, YS)) -> cons(quot(X, Y), zWquot(XS, YS)) 4.43/2.12 4.43/2.12 The replacement map contains the following entries: 4.43/2.12 4.43/2.12 from: {1} 4.43/2.12 cons: {1} 4.43/2.12 s: {1} 4.43/2.12 sel: {1, 2} 4.43/2.12 0: empty set 4.43/2.12 minus: {1, 2} 4.43/2.12 quot: {1, 2} 4.43/2.12 zWquot: {1, 2} 4.43/2.12 nil: empty set 4.43/2.12 4.43/2.12 ---------------------------------------- 4.43/2.12 4.43/2.12 (3) CSDependencyPairsProof (EQUIVALENT) 4.43/2.12 Using Improved CS-DPs [LPAR08] we result in the following initial Q-CSDP problem. 4.43/2.12 ---------------------------------------- 4.43/2.12 4.43/2.12 (4) 4.43/2.12 Obligation: 4.43/2.12 Q-restricted context-sensitive dependency pair problem: 4.43/2.12 The symbols in {from_1, s_1, sel_2, minus_2, quot_2, zWquot_2, SEL_2, MINUS_2, QUOT_2, ZWQUOT_2, FROM_1} are replacing on all positions. 4.43/2.12 For all symbols f in {cons_2} we have mu(f) = {1}. 4.43/2.12 The symbols in {U_1} are not replacing on any position. 4.43/2.12 4.43/2.12 The ordinary context-sensitive dependency pairs DP_o are: 4.43/2.12 SEL(s(N), cons(X, XS)) -> SEL(N, XS) 4.43/2.12 MINUS(s(X), s(Y)) -> MINUS(X, Y) 4.43/2.12 QUOT(s(X), s(Y)) -> QUOT(minus(X, Y), s(Y)) 4.43/2.12 QUOT(s(X), s(Y)) -> MINUS(X, Y) 4.43/2.12 ZWQUOT(cons(X, XS), cons(Y, YS)) -> QUOT(X, Y) 4.43/2.12 4.43/2.12 The collapsing dependency pairs are DP_c: 4.43/2.12 SEL(s(N), cons(X, XS)) -> XS 4.43/2.12 4.43/2.12 4.43/2.12 The hidden terms of R are: 4.43/2.12 4.43/2.12 from(s(x0)) 4.43/2.12 zWquot(x0, x1) 4.43/2.12 4.43/2.12 Every hiding context is built from: 4.43/2.12 aprove.DPFramework.CSDPProblem.QCSDPProblem$1@21f59b5d 4.43/2.12 aprove.DPFramework.CSDPProblem.QCSDPProblem$1@76cecf5d 4.43/2.12 aprove.DPFramework.CSDPProblem.QCSDPProblem$1@a33e84a 4.43/2.12 4.43/2.12 Hence, the new unhiding pairs DP_u are : 4.43/2.12 SEL(s(N), cons(X, XS)) -> U(XS) 4.43/2.12 U(s(x_0)) -> U(x_0) 4.43/2.12 U(from(x_0)) -> U(x_0) 4.43/2.12 U(zWquot(x_0, x_1)) -> U(x_0) 4.43/2.12 U(zWquot(x_0, x_1)) -> U(x_1) 4.43/2.12 U(from(s(x0))) -> FROM(s(x0)) 4.43/2.12 U(zWquot(x0, x1)) -> ZWQUOT(x0, x1) 4.43/2.12 4.43/2.12 The TRS R consists of the following rules: 4.43/2.12 4.43/2.12 from(X) -> cons(X, from(s(X))) 4.43/2.12 sel(0, cons(X, XS)) -> X 4.43/2.12 sel(s(N), cons(X, XS)) -> sel(N, XS) 4.43/2.12 minus(X, 0) -> 0 4.43/2.12 minus(s(X), s(Y)) -> minus(X, Y) 4.43/2.12 quot(0, s(Y)) -> 0 4.43/2.12 quot(s(X), s(Y)) -> s(quot(minus(X, Y), s(Y))) 4.43/2.12 zWquot(XS, nil) -> nil 4.43/2.12 zWquot(nil, XS) -> nil 4.43/2.12 zWquot(cons(X, XS), cons(Y, YS)) -> cons(quot(X, Y), zWquot(XS, YS)) 4.43/2.12 4.43/2.12 Q is empty. 4.43/2.12 4.43/2.12 ---------------------------------------- 4.43/2.12 4.43/2.12 (5) QCSDependencyGraphProof (EQUIVALENT) 4.43/2.12 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 4 SCCs with 5 less nodes. 4.43/2.12 4.43/2.12 ---------------------------------------- 4.43/2.12 4.43/2.12 (6) 4.43/2.12 Complex Obligation (AND) 4.43/2.12 4.43/2.12 ---------------------------------------- 4.43/2.12 4.43/2.12 (7) 4.43/2.12 Obligation: 4.43/2.12 Q-restricted context-sensitive dependency pair problem: 4.43/2.12 The symbols in {from_1, s_1, sel_2, minus_2, quot_2, zWquot_2, MINUS_2} are replacing on all positions. 4.43/2.12 For all symbols f in {cons_2} we have mu(f) = {1}. 4.43/2.12 4.43/2.12 The TRS P consists of the following rules: 4.43/2.12 4.43/2.12 MINUS(s(X), s(Y)) -> MINUS(X, Y) 4.43/2.12 4.43/2.12 The TRS R consists of the following rules: 4.43/2.12 4.43/2.12 from(X) -> cons(X, from(s(X))) 4.43/2.12 sel(0, cons(X, XS)) -> X 4.43/2.12 sel(s(N), cons(X, XS)) -> sel(N, XS) 4.43/2.12 minus(X, 0) -> 0 4.43/2.12 minus(s(X), s(Y)) -> minus(X, Y) 4.43/2.12 quot(0, s(Y)) -> 0 4.43/2.12 quot(s(X), s(Y)) -> s(quot(minus(X, Y), s(Y))) 4.43/2.12 zWquot(XS, nil) -> nil 4.43/2.12 zWquot(nil, XS) -> nil 4.43/2.12 zWquot(cons(X, XS), cons(Y, YS)) -> cons(quot(X, Y), zWquot(XS, YS)) 4.43/2.12 4.43/2.12 Q is empty. 4.43/2.12 4.43/2.12 ---------------------------------------- 4.43/2.12 4.43/2.12 (8) QCSDPSubtermProof (EQUIVALENT) 4.43/2.12 We use the subterm processor [DA_EMMES]. 4.43/2.12 4.43/2.12 4.43/2.12 The following pairs can be oriented strictly and are deleted. 4.43/2.12 4.43/2.12 MINUS(s(X), s(Y)) -> MINUS(X, Y) 4.43/2.12 The remaining pairs can at least be oriented weakly. 4.43/2.12 none 4.43/2.12 Used ordering: Combined order from the following AFS and order. 4.43/2.12 MINUS(x1, x2) = x1 4.43/2.12 4.43/2.12 4.43/2.12 Subterm Order 4.43/2.12 4.43/2.12 ---------------------------------------- 4.43/2.12 4.43/2.12 (9) 4.43/2.12 Obligation: 4.43/2.12 Q-restricted context-sensitive dependency pair problem: 4.43/2.12 The symbols in {from_1, s_1, sel_2, minus_2, quot_2, zWquot_2} are replacing on all positions. 4.43/2.12 For all symbols f in {cons_2} we have mu(f) = {1}. 4.43/2.12 4.43/2.12 The TRS P consists of the following rules: 4.43/2.12 none 4.43/2.12 4.43/2.12 The TRS R consists of the following rules: 4.43/2.12 4.43/2.12 from(X) -> cons(X, from(s(X))) 4.43/2.12 sel(0, cons(X, XS)) -> X 4.43/2.12 sel(s(N), cons(X, XS)) -> sel(N, XS) 4.43/2.12 minus(X, 0) -> 0 4.43/2.12 minus(s(X), s(Y)) -> minus(X, Y) 4.43/2.12 quot(0, s(Y)) -> 0 4.43/2.12 quot(s(X), s(Y)) -> s(quot(minus(X, Y), s(Y))) 4.43/2.12 zWquot(XS, nil) -> nil 4.43/2.12 zWquot(nil, XS) -> nil 4.43/2.12 zWquot(cons(X, XS), cons(Y, YS)) -> cons(quot(X, Y), zWquot(XS, YS)) 4.43/2.12 4.43/2.12 Q is empty. 4.43/2.12 4.43/2.12 ---------------------------------------- 4.43/2.12 4.43/2.12 (10) PIsEmptyProof (EQUIVALENT) 4.43/2.12 The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain. 4.43/2.12 ---------------------------------------- 4.43/2.12 4.43/2.12 (11) 4.43/2.12 YES 4.43/2.12 4.43/2.12 ---------------------------------------- 4.43/2.12 4.43/2.12 (12) 4.43/2.12 Obligation: 4.43/2.12 Q-restricted context-sensitive dependency pair problem: 4.43/2.12 The symbols in {from_1, s_1, sel_2, minus_2, quot_2, zWquot_2, QUOT_2} are replacing on all positions. 4.43/2.12 For all symbols f in {cons_2} we have mu(f) = {1}. 4.43/2.12 4.43/2.12 The TRS P consists of the following rules: 4.43/2.12 4.43/2.12 QUOT(s(X), s(Y)) -> QUOT(minus(X, Y), s(Y)) 4.43/2.12 4.43/2.12 The TRS R consists of the following rules: 4.43/2.12 4.43/2.12 from(X) -> cons(X, from(s(X))) 4.43/2.12 sel(0, cons(X, XS)) -> X 4.43/2.12 sel(s(N), cons(X, XS)) -> sel(N, XS) 4.43/2.12 minus(X, 0) -> 0 4.43/2.12 minus(s(X), s(Y)) -> minus(X, Y) 4.43/2.12 quot(0, s(Y)) -> 0 4.43/2.12 quot(s(X), s(Y)) -> s(quot(minus(X, Y), s(Y))) 4.43/2.12 zWquot(XS, nil) -> nil 4.43/2.12 zWquot(nil, XS) -> nil 4.43/2.12 zWquot(cons(X, XS), cons(Y, YS)) -> cons(quot(X, Y), zWquot(XS, YS)) 4.43/2.12 4.43/2.12 Q is empty. 4.43/2.12 4.43/2.12 ---------------------------------------- 4.43/2.12 4.43/2.12 (13) QCSDPReductionPairProof (EQUIVALENT) 4.43/2.12 Using the order 4.43/2.12 4.43/2.12 Polynomial interpretation with max and min functions [POLO,MAXPOLO]: 4.43/2.12 4.43/2.12 POL(0) = 0 4.43/2.12 POL(QUOT(x_1, x_2)) = x_1 4.43/2.12 POL(cons(x_1, x_2)) = 1 + x_1 4.43/2.12 POL(from(x_1)) = 1 + x_1 4.43/2.12 POL(minus(x_1, x_2)) = 0 4.43/2.12 POL(nil) = 1 4.43/2.12 POL(quot(x_1, x_2)) = 1 + x_1 4.43/2.12 POL(s(x_1)) = 1 + x_1 4.43/2.12 POL(zWquot(x_1, x_2)) = 1 + x_1 4.43/2.12 4.43/2.12 4.43/2.12 the following usable rules 4.43/2.12 4.43/2.12 4.43/2.12 minus(X, 0) -> 0 4.43/2.12 minus(s(X), s(Y)) -> minus(X, Y) 4.43/2.12 quot(0, s(Y)) -> 0 4.43/2.12 quot(s(X), s(Y)) -> s(quot(minus(X, Y), s(Y))) 4.43/2.12 from(X) -> cons(X, from(s(X))) 4.43/2.12 zWquot(XS, nil) -> nil 4.43/2.12 zWquot(nil, XS) -> nil 4.43/2.12 zWquot(cons(X, XS), cons(Y, YS)) -> cons(quot(X, Y), zWquot(XS, YS)) 4.43/2.12 4.43/2.12 4.43/2.12 could all be oriented weakly. 4.43/2.12 4.43/2.12 Furthermore, the pairs 4.43/2.12 4.43/2.12 4.43/2.12 QUOT(s(X), s(Y)) -> QUOT(minus(X, Y), s(Y)) 4.43/2.12 4.43/2.12 4.43/2.12 could be oriented strictly and thus removed by the CS-Reduction Pair Processor [LPAR08,DA_EMMES]. 4.43/2.12 4.43/2.12 4.43/2.12 ---------------------------------------- 4.43/2.12 4.43/2.12 (14) 4.43/2.12 Obligation: 4.43/2.12 Q-restricted context-sensitive dependency pair problem: 4.43/2.12 The symbols in {from_1, s_1, sel_2, minus_2, quot_2, zWquot_2} are replacing on all positions. 4.43/2.12 For all symbols f in {cons_2} we have mu(f) = {1}. 4.43/2.12 4.43/2.12 The TRS P consists of the following rules: 4.43/2.12 none 4.43/2.12 4.43/2.12 The TRS R consists of the following rules: 4.43/2.12 4.43/2.12 from(X) -> cons(X, from(s(X))) 4.43/2.12 sel(0, cons(X, XS)) -> X 4.43/2.12 sel(s(N), cons(X, XS)) -> sel(N, XS) 4.43/2.12 minus(X, 0) -> 0 4.43/2.12 minus(s(X), s(Y)) -> minus(X, Y) 4.43/2.12 quot(0, s(Y)) -> 0 4.43/2.12 quot(s(X), s(Y)) -> s(quot(minus(X, Y), s(Y))) 4.43/2.12 zWquot(XS, nil) -> nil 4.43/2.12 zWquot(nil, XS) -> nil 4.43/2.12 zWquot(cons(X, XS), cons(Y, YS)) -> cons(quot(X, Y), zWquot(XS, YS)) 4.43/2.12 4.43/2.12 Q is empty. 4.43/2.12 4.43/2.12 ---------------------------------------- 4.43/2.12 4.43/2.12 (15) PIsEmptyProof (EQUIVALENT) 4.43/2.12 The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain. 4.43/2.12 ---------------------------------------- 4.43/2.12 4.43/2.12 (16) 4.43/2.12 YES 4.43/2.12 4.43/2.12 ---------------------------------------- 4.43/2.12 4.43/2.12 (17) 4.43/2.12 Obligation: 4.43/2.12 Q-restricted context-sensitive dependency pair problem: 4.43/2.12 The symbols in {from_1, s_1, sel_2, minus_2, quot_2, zWquot_2} are replacing on all positions. 4.43/2.12 For all symbols f in {cons_2} we have mu(f) = {1}. 4.43/2.12 The symbols in {U_1} are not replacing on any position. 4.43/2.12 4.43/2.12 The TRS P consists of the following rules: 4.43/2.12 4.43/2.12 U(s(x_0)) -> U(x_0) 4.43/2.12 U(from(x_0)) -> U(x_0) 4.43/2.12 U(zWquot(x_0, x_1)) -> U(x_0) 4.43/2.12 U(zWquot(x_0, x_1)) -> U(x_1) 4.43/2.12 4.43/2.12 The TRS R consists of the following rules: 4.43/2.12 4.43/2.12 from(X) -> cons(X, from(s(X))) 4.43/2.12 sel(0, cons(X, XS)) -> X 4.43/2.12 sel(s(N), cons(X, XS)) -> sel(N, XS) 4.43/2.12 minus(X, 0) -> 0 4.43/2.12 minus(s(X), s(Y)) -> minus(X, Y) 4.43/2.12 quot(0, s(Y)) -> 0 4.43/2.12 quot(s(X), s(Y)) -> s(quot(minus(X, Y), s(Y))) 4.43/2.12 zWquot(XS, nil) -> nil 4.43/2.12 zWquot(nil, XS) -> nil 4.43/2.12 zWquot(cons(X, XS), cons(Y, YS)) -> cons(quot(X, Y), zWquot(XS, YS)) 4.43/2.12 4.43/2.12 Q is empty. 4.43/2.12 4.43/2.12 ---------------------------------------- 4.43/2.12 4.43/2.12 (18) QCSDPSubtermProof (EQUIVALENT) 4.43/2.12 We use the subterm processor [DA_EMMES]. 4.43/2.12 4.43/2.12 4.43/2.12 The following pairs can be oriented strictly and are deleted. 4.43/2.12 4.43/2.12 U(s(x_0)) -> U(x_0) 4.43/2.12 U(from(x_0)) -> U(x_0) 4.43/2.12 U(zWquot(x_0, x_1)) -> U(x_0) 4.43/2.12 U(zWquot(x_0, x_1)) -> U(x_1) 4.43/2.12 The remaining pairs can at least be oriented weakly. 4.43/2.12 none 4.43/2.12 Used ordering: Combined order from the following AFS and order. 4.43/2.12 U(x1) = x1 4.43/2.12 4.43/2.12 4.43/2.12 Subterm Order 4.43/2.12 4.43/2.12 ---------------------------------------- 4.43/2.12 4.43/2.12 (19) 4.43/2.12 Obligation: 4.43/2.12 Q-restricted context-sensitive dependency pair problem: 4.43/2.12 The symbols in {from_1, s_1, sel_2, minus_2, quot_2, zWquot_2} are replacing on all positions. 4.43/2.12 For all symbols f in {cons_2} we have mu(f) = {1}. 4.43/2.12 4.43/2.12 The TRS P consists of the following rules: 4.43/2.12 none 4.43/2.12 4.43/2.12 The TRS R consists of the following rules: 4.43/2.12 4.43/2.12 from(X) -> cons(X, from(s(X))) 4.43/2.12 sel(0, cons(X, XS)) -> X 4.43/2.12 sel(s(N), cons(X, XS)) -> sel(N, XS) 4.43/2.12 minus(X, 0) -> 0 4.43/2.12 minus(s(X), s(Y)) -> minus(X, Y) 4.43/2.12 quot(0, s(Y)) -> 0 4.43/2.12 quot(s(X), s(Y)) -> s(quot(minus(X, Y), s(Y))) 4.43/2.12 zWquot(XS, nil) -> nil 4.43/2.12 zWquot(nil, XS) -> nil 4.43/2.12 zWquot(cons(X, XS), cons(Y, YS)) -> cons(quot(X, Y), zWquot(XS, YS)) 4.43/2.12 4.43/2.12 Q is empty. 4.43/2.12 4.43/2.12 ---------------------------------------- 4.43/2.12 4.43/2.12 (20) PIsEmptyProof (EQUIVALENT) 4.43/2.12 The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain. 4.43/2.12 ---------------------------------------- 4.43/2.12 4.43/2.12 (21) 4.43/2.12 YES 4.43/2.12 4.43/2.12 ---------------------------------------- 4.43/2.12 4.43/2.12 (22) 4.43/2.12 Obligation: 4.43/2.12 Q-restricted context-sensitive dependency pair problem: 4.43/2.12 The symbols in {from_1, s_1, sel_2, minus_2, quot_2, zWquot_2, SEL_2} are replacing on all positions. 4.43/2.12 For all symbols f in {cons_2} we have mu(f) = {1}. 4.43/2.12 4.43/2.12 The TRS P consists of the following rules: 4.43/2.12 4.43/2.12 SEL(s(N), cons(X, XS)) -> SEL(N, XS) 4.43/2.12 4.43/2.12 The TRS R consists of the following rules: 4.43/2.12 4.43/2.12 from(X) -> cons(X, from(s(X))) 4.43/2.12 sel(0, cons(X, XS)) -> X 4.43/2.12 sel(s(N), cons(X, XS)) -> sel(N, XS) 4.43/2.12 minus(X, 0) -> 0 4.43/2.12 minus(s(X), s(Y)) -> minus(X, Y) 4.43/2.12 quot(0, s(Y)) -> 0 4.43/2.12 quot(s(X), s(Y)) -> s(quot(minus(X, Y), s(Y))) 4.43/2.12 zWquot(XS, nil) -> nil 4.43/2.12 zWquot(nil, XS) -> nil 4.43/2.12 zWquot(cons(X, XS), cons(Y, YS)) -> cons(quot(X, Y), zWquot(XS, YS)) 4.43/2.12 4.43/2.12 Q is empty. 4.43/2.12 4.43/2.12 ---------------------------------------- 4.43/2.12 4.43/2.12 (23) QCSDPSubtermProof (EQUIVALENT) 4.43/2.12 We use the subterm processor [DA_EMMES]. 4.43/2.12 4.43/2.12 4.43/2.12 The following pairs can be oriented strictly and are deleted. 4.43/2.12 4.43/2.12 SEL(s(N), cons(X, XS)) -> SEL(N, XS) 4.43/2.12 The remaining pairs can at least be oriented weakly. 4.43/2.12 none 4.43/2.12 Used ordering: Combined order from the following AFS and order. 4.43/2.12 SEL(x1, x2) = x1 4.43/2.12 4.43/2.12 4.43/2.12 Subterm Order 4.43/2.12 4.43/2.12 ---------------------------------------- 4.43/2.12 4.43/2.12 (24) 4.43/2.12 Obligation: 4.43/2.12 Q-restricted context-sensitive dependency pair problem: 4.43/2.12 The symbols in {from_1, s_1, sel_2, minus_2, quot_2, zWquot_2} are replacing on all positions. 4.43/2.12 For all symbols f in {cons_2} we have mu(f) = {1}. 4.43/2.12 4.43/2.12 The TRS P consists of the following rules: 4.43/2.12 none 4.43/2.12 4.43/2.12 The TRS R consists of the following rules: 4.43/2.12 4.43/2.12 from(X) -> cons(X, from(s(X))) 4.43/2.12 sel(0, cons(X, XS)) -> X 4.43/2.12 sel(s(N), cons(X, XS)) -> sel(N, XS) 4.43/2.12 minus(X, 0) -> 0 4.43/2.12 minus(s(X), s(Y)) -> minus(X, Y) 4.43/2.12 quot(0, s(Y)) -> 0 4.43/2.12 quot(s(X), s(Y)) -> s(quot(minus(X, Y), s(Y))) 4.43/2.12 zWquot(XS, nil) -> nil 4.43/2.12 zWquot(nil, XS) -> nil 4.43/2.12 zWquot(cons(X, XS), cons(Y, YS)) -> cons(quot(X, Y), zWquot(XS, YS)) 4.43/2.12 4.43/2.12 Q is empty. 4.43/2.12 4.43/2.12 ---------------------------------------- 4.43/2.12 4.43/2.12 (25) PIsEmptyProof (EQUIVALENT) 4.43/2.12 The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain. 4.43/2.12 ---------------------------------------- 4.43/2.12 4.43/2.12 (26) 4.43/2.12 YES 4.79/2.15 EOF