569.82/291.54	WORST_CASE(Omega(n^1), O(n^2))
569.82/291.55	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
569.82/291.55	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
569.82/291.55	
569.82/291.55	
569.82/291.55	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2).
569.82/291.55	
569.82/291.55	(0) CpxRelTRS
569.82/291.55	(1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 292 ms]
569.82/291.55	(2) CpxRelTRS
569.82/291.55	(3) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
569.82/291.55	(4) CdtProblem
569.82/291.55	    (5) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms]
569.82/291.55	    (6) CdtProblem
569.82/291.55	    (7) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms]
569.82/291.55	    (8) CdtProblem
569.82/291.55	    (9) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
569.82/291.55	    (10) CdtProblem
569.82/291.55	    (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 62 ms]
569.82/291.55	    (12) CdtProblem
569.82/291.55	    (13) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 28 ms]
569.82/291.55	    (14) CdtProblem
569.82/291.55	    (15) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 22 ms]
569.82/291.55	    (16) CdtProblem
569.82/291.55	    (17) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 25 ms]
569.82/291.55	    (18) CdtProblem
569.82/291.55	    (19) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 23 ms]
569.82/291.55	    (20) CdtProblem
569.82/291.55	    (21) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 218 ms]
569.82/291.55	    (22) CdtProblem
569.82/291.55	    (23) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
569.82/291.55	    (24) BOUNDS(1, 1)
569.82/291.55	(25) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
569.82/291.55	(26) TRS for Loop Detection
569.82/291.55	    (27) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
569.82/291.55	    (28) BEST
569.82/291.55	        (29) proven lower bound
569.82/291.55	            (30) LowerBoundPropagationProof [FINISHED, 0 ms]
569.82/291.55	            (31) BOUNDS(n^1, INF)
569.82/291.55	        (32) TRS for Loop Detection
569.82/291.55	
569.82/291.55	
569.82/291.55	----------------------------------------
569.82/291.55	
569.82/291.55	(0)
569.82/291.55	Obligation:
569.82/291.55	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2).
569.82/291.55	
569.82/291.55	
569.82/291.55	The TRS R consists of the following rules:
569.82/291.55	
569.82/291.55	   prefix(Cons(x', xs'), Cons(x, xs)) -> and(!EQ(x', x), prefix(xs', xs))
569.82/291.55	   domatch(Cons(x, xs), Nil, n) -> Nil
569.82/291.55	   domatch(Nil, Nil, n) -> Cons(n, Nil)
569.82/291.55	   prefix(Cons(x, xs), Nil) -> False
569.82/291.55	   prefix(Nil, cs) -> True
569.82/291.55	   domatch(patcs, Cons(x, xs), n) -> domatch[Ite](prefix(patcs, Cons(x, xs)), patcs, Cons(x, xs), n)
569.82/291.56	   eqNatList(Cons(x, xs), Cons(y, ys)) -> eqNatList[Ite](!EQ(x, y), y, ys, x, xs)
569.82/291.56	   eqNatList(Cons(x, xs), Nil) -> False
569.82/291.56	   eqNatList(Nil, Cons(y, ys)) -> False
569.82/291.56	   eqNatList(Nil, Nil) -> True
569.82/291.56	   notEmpty(Cons(x, xs)) -> True
569.82/291.56	   notEmpty(Nil) -> False
569.82/291.56	   strmatch(patstr, str) -> domatch(patstr, str, Nil)
569.82/291.56	
569.82/291.56	The (relative) TRS S consists of the following rules:
569.82/291.56	
569.82/291.56	   and(False, False) -> False
569.82/291.56	   and(True, False) -> False
569.82/291.56	   and(False, True) -> False
569.82/291.56	   and(True, True) -> True
569.82/291.56	   !EQ(S(x), S(y)) -> !EQ(x, y)
569.82/291.56	   !EQ(0, S(y)) -> False
569.82/291.56	   !EQ(S(x), 0) -> False
569.82/291.56	   !EQ(0, 0) -> True
569.82/291.56	   domatch[Ite](False, patcs, Cons(x, xs), n) -> domatch(patcs, xs, Cons(n, Cons(Nil, Nil)))
569.82/291.56	   domatch[Ite](True, patcs, Cons(x, xs), n) -> Cons(n, domatch(patcs, xs, Cons(n, Cons(Nil, Nil))))
569.82/291.56	   eqNatList[Ite](False, y, ys, x, xs) -> False
569.82/291.56	   eqNatList[Ite](True, y, ys, x, xs) -> eqNatList(xs, ys)
569.82/291.56	
569.82/291.56	Rewrite Strategy: INNERMOST
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID))
569.82/291.56	proved termination of relative rules
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(2)
569.82/291.56	Obligation:
569.82/291.56	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2).
569.82/291.56	
569.82/291.56	
569.82/291.56	The TRS R consists of the following rules:
569.82/291.56	
569.82/291.56	   prefix(Cons(x', xs'), Cons(x, xs)) -> and(!EQ(x', x), prefix(xs', xs))
569.82/291.56	   domatch(Cons(x, xs), Nil, n) -> Nil
569.82/291.56	   domatch(Nil, Nil, n) -> Cons(n, Nil)
569.82/291.56	   prefix(Cons(x, xs), Nil) -> False
569.82/291.56	   prefix(Nil, cs) -> True
569.82/291.56	   domatch(patcs, Cons(x, xs), n) -> domatch[Ite](prefix(patcs, Cons(x, xs)), patcs, Cons(x, xs), n)
569.82/291.56	   eqNatList(Cons(x, xs), Cons(y, ys)) -> eqNatList[Ite](!EQ(x, y), y, ys, x, xs)
569.82/291.56	   eqNatList(Cons(x, xs), Nil) -> False
569.82/291.56	   eqNatList(Nil, Cons(y, ys)) -> False
569.82/291.56	   eqNatList(Nil, Nil) -> True
569.82/291.56	   notEmpty(Cons(x, xs)) -> True
569.82/291.56	   notEmpty(Nil) -> False
569.82/291.56	   strmatch(patstr, str) -> domatch(patstr, str, Nil)
569.82/291.56	
569.82/291.56	The (relative) TRS S consists of the following rules:
569.82/291.56	
569.82/291.56	   and(False, False) -> False
569.82/291.56	   and(True, False) -> False
569.82/291.56	   and(False, True) -> False
569.82/291.56	   and(True, True) -> True
569.82/291.56	   !EQ(S(x), S(y)) -> !EQ(x, y)
569.82/291.56	   !EQ(0, S(y)) -> False
569.82/291.56	   !EQ(S(x), 0) -> False
569.82/291.56	   !EQ(0, 0) -> True
569.82/291.56	   domatch[Ite](False, patcs, Cons(x, xs), n) -> domatch(patcs, xs, Cons(n, Cons(Nil, Nil)))
569.82/291.56	   domatch[Ite](True, patcs, Cons(x, xs), n) -> Cons(n, domatch(patcs, xs, Cons(n, Cons(Nil, Nil))))
569.82/291.56	   eqNatList[Ite](False, y, ys, x, xs) -> False
569.82/291.56	   eqNatList[Ite](True, y, ys, x, xs) -> eqNatList(xs, ys)
569.82/291.56	
569.82/291.56	Rewrite Strategy: INNERMOST
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(3) CpxTrsToCdtProof (UPPER BOUND(ID))
569.82/291.56	Converted Cpx (relative) TRS to CDT
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(4)
569.82/291.56	Obligation:
569.82/291.56	Complexity Dependency Tuples Problem
569.82/291.56	
569.82/291.56	Rules:
569.82/291.56	   and(False, False) -> False
569.82/291.56	   and(True, False) -> False
569.82/291.56	   and(False, True) -> False
569.82/291.56	   and(True, True) -> True
569.82/291.56	   !EQ(S(z0), S(z1)) -> !EQ(z0, z1)
569.82/291.56	   !EQ(0, S(z0)) -> False
569.82/291.56	   !EQ(S(z0), 0) -> False
569.82/291.56	   !EQ(0, 0) -> True
569.82/291.56	   domatch[Ite](False, z0, Cons(z1, z2), z3) -> domatch(z0, z2, Cons(z3, Cons(Nil, Nil)))
569.82/291.56	   domatch[Ite](True, z0, Cons(z1, z2), z3) -> Cons(z3, domatch(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   eqNatList[Ite](False, z0, z1, z2, z3) -> False
569.82/291.56	   eqNatList[Ite](True, z0, z1, z2, z3) -> eqNatList(z3, z1)
569.82/291.56	   prefix(Cons(z0, z1), Cons(z2, z3)) -> and(!EQ(z0, z2), prefix(z1, z3))
569.82/291.56	   prefix(Cons(z0, z1), Nil) -> False
569.82/291.56	   prefix(Nil, z0) -> True
569.82/291.56	   domatch(Cons(z0, z1), Nil, z2) -> Nil
569.82/291.56	   domatch(Nil, Nil, z0) -> Cons(z0, Nil)
569.82/291.56	   domatch(z0, Cons(z1, z2), z3) -> domatch[Ite](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3)
569.82/291.56	   eqNatList(Cons(z0, z1), Cons(z2, z3)) -> eqNatList[Ite](!EQ(z0, z2), z2, z3, z0, z1)
569.82/291.56	   eqNatList(Cons(z0, z1), Nil) -> False
569.82/291.56	   eqNatList(Nil, Cons(z0, z1)) -> False
569.82/291.56	   eqNatList(Nil, Nil) -> True
569.82/291.56	   notEmpty(Cons(z0, z1)) -> True
569.82/291.56	   notEmpty(Nil) -> False
569.82/291.56	   strmatch(z0, z1) -> domatch(z0, z1, Nil)
569.82/291.56	Tuples:
569.82/291.56	   AND(False, False) -> c
569.82/291.56	   AND(True, False) -> c1
569.82/291.56	   AND(False, True) -> c2
569.82/291.56	   AND(True, True) -> c3
569.82/291.56	   !EQ'(S(z0), S(z1)) -> c4(!EQ'(z0, z1))
569.82/291.56	   !EQ'(0, S(z0)) -> c5
569.82/291.56	   !EQ'(S(z0), 0) -> c6
569.82/291.56	   !EQ'(0, 0) -> c7
569.82/291.56	   DOMATCH[ITE](False, z0, Cons(z1, z2), z3) -> c8(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   DOMATCH[ITE](True, z0, Cons(z1, z2), z3) -> c9(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   EQNATLIST[ITE](False, z0, z1, z2, z3) -> c10
569.82/291.56	   EQNATLIST[ITE](True, z0, z1, z2, z3) -> c11(EQNATLIST(z3, z1))
569.82/291.56	   PREFIX(Cons(z0, z1), Cons(z2, z3)) -> c12(AND(!EQ(z0, z2), prefix(z1, z3)), !EQ'(z0, z2), PREFIX(z1, z3))
569.82/291.56	   PREFIX(Cons(z0, z1), Nil) -> c13
569.82/291.56	   PREFIX(Nil, z0) -> c14
569.82/291.56	   DOMATCH(Cons(z0, z1), Nil, z2) -> c15
569.82/291.56	   DOMATCH(Nil, Nil, z0) -> c16
569.82/291.56	   DOMATCH(z0, Cons(z1, z2), z3) -> c17(DOMATCH[ITE](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3), PREFIX(z0, Cons(z1, z2)))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Cons(z2, z3)) -> c18(EQNATLIST[ITE](!EQ(z0, z2), z2, z3, z0, z1), !EQ'(z0, z2))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Nil) -> c19
569.82/291.56	   EQNATLIST(Nil, Cons(z0, z1)) -> c20
569.82/291.56	   EQNATLIST(Nil, Nil) -> c21
569.82/291.56	   NOTEMPTY(Cons(z0, z1)) -> c22
569.82/291.56	   NOTEMPTY(Nil) -> c23
569.82/291.56	   STRMATCH(z0, z1) -> c24(DOMATCH(z0, z1, Nil))
569.82/291.56	S tuples:
569.82/291.56	   PREFIX(Cons(z0, z1), Cons(z2, z3)) -> c12(AND(!EQ(z0, z2), prefix(z1, z3)), !EQ'(z0, z2), PREFIX(z1, z3))
569.82/291.56	   PREFIX(Cons(z0, z1), Nil) -> c13
569.82/291.56	   PREFIX(Nil, z0) -> c14
569.82/291.56	   DOMATCH(Cons(z0, z1), Nil, z2) -> c15
569.82/291.56	   DOMATCH(Nil, Nil, z0) -> c16
569.82/291.56	   DOMATCH(z0, Cons(z1, z2), z3) -> c17(DOMATCH[ITE](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3), PREFIX(z0, Cons(z1, z2)))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Cons(z2, z3)) -> c18(EQNATLIST[ITE](!EQ(z0, z2), z2, z3, z0, z1), !EQ'(z0, z2))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Nil) -> c19
569.82/291.56	   EQNATLIST(Nil, Cons(z0, z1)) -> c20
569.82/291.56	   EQNATLIST(Nil, Nil) -> c21
569.82/291.56	   NOTEMPTY(Cons(z0, z1)) -> c22
569.82/291.56	   NOTEMPTY(Nil) -> c23
569.82/291.56	   STRMATCH(z0, z1) -> c24(DOMATCH(z0, z1, Nil))
569.82/291.56	K tuples:none
569.82/291.56	Defined Rule Symbols:   prefix_2, domatch_3, eqNatList_2, notEmpty_1, strmatch_2, and_2, !EQ_2, domatch[Ite]_4, eqNatList[Ite]_5
569.82/291.56	
569.82/291.56	Defined Pair Symbols:   AND_2, !EQ'_2, DOMATCH[ITE]_4, EQNATLIST[ITE]_5, PREFIX_2, DOMATCH_3, EQNATLIST_2, NOTEMPTY_1, STRMATCH_2
569.82/291.56	
569.82/291.56	Compound Symbols:   c, c1, c2, c3, c4_1, c5, c6, c7, c8_1, c9_1, c10, c11_1, c12_3, c13, c14, c15, c16, c17_2, c18_2, c19, c20, c21, c22, c23, c24_1
569.82/291.56	
569.82/291.56	
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(5) CdtLeafRemovalProof (ComplexityIfPolyImplication)
569.82/291.56	Removed 1 leading nodes:
569.82/291.56	   STRMATCH(z0, z1) -> c24(DOMATCH(z0, z1, Nil))
569.82/291.56	Removed 12 trailing nodes:
569.82/291.56	   PREFIX(Cons(z0, z1), Nil) -> c13
569.82/291.56	   AND(False, False) -> c
569.82/291.56	   !EQ'(S(z0), 0) -> c6
569.82/291.56	   EQNATLIST[ITE](False, z0, z1, z2, z3) -> c10
569.82/291.56	   AND(True, True) -> c3
569.82/291.56	   PREFIX(Nil, z0) -> c14
569.82/291.56	   !EQ'(0, 0) -> c7
569.82/291.56	   AND(False, True) -> c2
569.82/291.56	   !EQ'(0, S(z0)) -> c5
569.82/291.56	   AND(True, False) -> c1
569.82/291.56	   NOTEMPTY(Nil) -> c23
569.82/291.56	   NOTEMPTY(Cons(z0, z1)) -> c22
569.82/291.56	
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(6)
569.82/291.56	Obligation:
569.82/291.56	Complexity Dependency Tuples Problem
569.82/291.56	
569.82/291.56	Rules:
569.82/291.56	   and(False, False) -> False
569.82/291.56	   and(True, False) -> False
569.82/291.56	   and(False, True) -> False
569.82/291.56	   and(True, True) -> True
569.82/291.56	   !EQ(S(z0), S(z1)) -> !EQ(z0, z1)
569.82/291.56	   !EQ(0, S(z0)) -> False
569.82/291.56	   !EQ(S(z0), 0) -> False
569.82/291.56	   !EQ(0, 0) -> True
569.82/291.56	   domatch[Ite](False, z0, Cons(z1, z2), z3) -> domatch(z0, z2, Cons(z3, Cons(Nil, Nil)))
569.82/291.56	   domatch[Ite](True, z0, Cons(z1, z2), z3) -> Cons(z3, domatch(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   eqNatList[Ite](False, z0, z1, z2, z3) -> False
569.82/291.56	   eqNatList[Ite](True, z0, z1, z2, z3) -> eqNatList(z3, z1)
569.82/291.56	   prefix(Cons(z0, z1), Cons(z2, z3)) -> and(!EQ(z0, z2), prefix(z1, z3))
569.82/291.56	   prefix(Cons(z0, z1), Nil) -> False
569.82/291.56	   prefix(Nil, z0) -> True
569.82/291.56	   domatch(Cons(z0, z1), Nil, z2) -> Nil
569.82/291.56	   domatch(Nil, Nil, z0) -> Cons(z0, Nil)
569.82/291.56	   domatch(z0, Cons(z1, z2), z3) -> domatch[Ite](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3)
569.82/291.56	   eqNatList(Cons(z0, z1), Cons(z2, z3)) -> eqNatList[Ite](!EQ(z0, z2), z2, z3, z0, z1)
569.82/291.56	   eqNatList(Cons(z0, z1), Nil) -> False
569.82/291.56	   eqNatList(Nil, Cons(z0, z1)) -> False
569.82/291.56	   eqNatList(Nil, Nil) -> True
569.82/291.56	   notEmpty(Cons(z0, z1)) -> True
569.82/291.56	   notEmpty(Nil) -> False
569.82/291.56	   strmatch(z0, z1) -> domatch(z0, z1, Nil)
569.82/291.56	Tuples:
569.82/291.56	   !EQ'(S(z0), S(z1)) -> c4(!EQ'(z0, z1))
569.82/291.56	   DOMATCH[ITE](False, z0, Cons(z1, z2), z3) -> c8(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   DOMATCH[ITE](True, z0, Cons(z1, z2), z3) -> c9(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   EQNATLIST[ITE](True, z0, z1, z2, z3) -> c11(EQNATLIST(z3, z1))
569.82/291.56	   PREFIX(Cons(z0, z1), Cons(z2, z3)) -> c12(AND(!EQ(z0, z2), prefix(z1, z3)), !EQ'(z0, z2), PREFIX(z1, z3))
569.82/291.56	   DOMATCH(Cons(z0, z1), Nil, z2) -> c15
569.82/291.56	   DOMATCH(Nil, Nil, z0) -> c16
569.82/291.56	   DOMATCH(z0, Cons(z1, z2), z3) -> c17(DOMATCH[ITE](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3), PREFIX(z0, Cons(z1, z2)))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Cons(z2, z3)) -> c18(EQNATLIST[ITE](!EQ(z0, z2), z2, z3, z0, z1), !EQ'(z0, z2))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Nil) -> c19
569.82/291.56	   EQNATLIST(Nil, Cons(z0, z1)) -> c20
569.82/291.56	   EQNATLIST(Nil, Nil) -> c21
569.82/291.56	S tuples:
569.82/291.56	   PREFIX(Cons(z0, z1), Cons(z2, z3)) -> c12(AND(!EQ(z0, z2), prefix(z1, z3)), !EQ'(z0, z2), PREFIX(z1, z3))
569.82/291.56	   DOMATCH(Cons(z0, z1), Nil, z2) -> c15
569.82/291.56	   DOMATCH(Nil, Nil, z0) -> c16
569.82/291.56	   DOMATCH(z0, Cons(z1, z2), z3) -> c17(DOMATCH[ITE](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3), PREFIX(z0, Cons(z1, z2)))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Cons(z2, z3)) -> c18(EQNATLIST[ITE](!EQ(z0, z2), z2, z3, z0, z1), !EQ'(z0, z2))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Nil) -> c19
569.82/291.56	   EQNATLIST(Nil, Cons(z0, z1)) -> c20
569.82/291.56	   EQNATLIST(Nil, Nil) -> c21
569.82/291.56	K tuples:none
569.82/291.56	Defined Rule Symbols:   prefix_2, domatch_3, eqNatList_2, notEmpty_1, strmatch_2, and_2, !EQ_2, domatch[Ite]_4, eqNatList[Ite]_5
569.82/291.56	
569.82/291.56	Defined Pair Symbols:   !EQ'_2, DOMATCH[ITE]_4, EQNATLIST[ITE]_5, PREFIX_2, DOMATCH_3, EQNATLIST_2
569.82/291.56	
569.82/291.56	Compound Symbols:   c4_1, c8_1, c9_1, c11_1, c12_3, c15, c16, c17_2, c18_2, c19, c20, c21
569.82/291.56	
569.82/291.56	
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(7) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID))
569.82/291.56	Removed 1 trailing tuple parts
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(8)
569.82/291.56	Obligation:
569.82/291.56	Complexity Dependency Tuples Problem
569.82/291.56	
569.82/291.56	Rules:
569.82/291.56	   and(False, False) -> False
569.82/291.56	   and(True, False) -> False
569.82/291.56	   and(False, True) -> False
569.82/291.56	   and(True, True) -> True
569.82/291.56	   !EQ(S(z0), S(z1)) -> !EQ(z0, z1)
569.82/291.56	   !EQ(0, S(z0)) -> False
569.82/291.56	   !EQ(S(z0), 0) -> False
569.82/291.56	   !EQ(0, 0) -> True
569.82/291.56	   domatch[Ite](False, z0, Cons(z1, z2), z3) -> domatch(z0, z2, Cons(z3, Cons(Nil, Nil)))
569.82/291.56	   domatch[Ite](True, z0, Cons(z1, z2), z3) -> Cons(z3, domatch(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   eqNatList[Ite](False, z0, z1, z2, z3) -> False
569.82/291.56	   eqNatList[Ite](True, z0, z1, z2, z3) -> eqNatList(z3, z1)
569.82/291.56	   prefix(Cons(z0, z1), Cons(z2, z3)) -> and(!EQ(z0, z2), prefix(z1, z3))
569.82/291.56	   prefix(Cons(z0, z1), Nil) -> False
569.82/291.56	   prefix(Nil, z0) -> True
569.82/291.56	   domatch(Cons(z0, z1), Nil, z2) -> Nil
569.82/291.56	   domatch(Nil, Nil, z0) -> Cons(z0, Nil)
569.82/291.56	   domatch(z0, Cons(z1, z2), z3) -> domatch[Ite](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3)
569.82/291.56	   eqNatList(Cons(z0, z1), Cons(z2, z3)) -> eqNatList[Ite](!EQ(z0, z2), z2, z3, z0, z1)
569.82/291.56	   eqNatList(Cons(z0, z1), Nil) -> False
569.82/291.56	   eqNatList(Nil, Cons(z0, z1)) -> False
569.82/291.56	   eqNatList(Nil, Nil) -> True
569.82/291.56	   notEmpty(Cons(z0, z1)) -> True
569.82/291.56	   notEmpty(Nil) -> False
569.82/291.56	   strmatch(z0, z1) -> domatch(z0, z1, Nil)
569.82/291.56	Tuples:
569.82/291.56	   !EQ'(S(z0), S(z1)) -> c4(!EQ'(z0, z1))
569.82/291.56	   DOMATCH[ITE](False, z0, Cons(z1, z2), z3) -> c8(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   DOMATCH[ITE](True, z0, Cons(z1, z2), z3) -> c9(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   EQNATLIST[ITE](True, z0, z1, z2, z3) -> c11(EQNATLIST(z3, z1))
569.82/291.56	   DOMATCH(Cons(z0, z1), Nil, z2) -> c15
569.82/291.56	   DOMATCH(Nil, Nil, z0) -> c16
569.82/291.56	   DOMATCH(z0, Cons(z1, z2), z3) -> c17(DOMATCH[ITE](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3), PREFIX(z0, Cons(z1, z2)))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Cons(z2, z3)) -> c18(EQNATLIST[ITE](!EQ(z0, z2), z2, z3, z0, z1), !EQ'(z0, z2))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Nil) -> c19
569.82/291.56	   EQNATLIST(Nil, Cons(z0, z1)) -> c20
569.82/291.56	   EQNATLIST(Nil, Nil) -> c21
569.82/291.56	   PREFIX(Cons(z0, z1), Cons(z2, z3)) -> c12(!EQ'(z0, z2), PREFIX(z1, z3))
569.82/291.56	S tuples:
569.82/291.56	   DOMATCH(Cons(z0, z1), Nil, z2) -> c15
569.82/291.56	   DOMATCH(Nil, Nil, z0) -> c16
569.82/291.56	   DOMATCH(z0, Cons(z1, z2), z3) -> c17(DOMATCH[ITE](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3), PREFIX(z0, Cons(z1, z2)))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Cons(z2, z3)) -> c18(EQNATLIST[ITE](!EQ(z0, z2), z2, z3, z0, z1), !EQ'(z0, z2))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Nil) -> c19
569.82/291.56	   EQNATLIST(Nil, Cons(z0, z1)) -> c20
569.82/291.56	   EQNATLIST(Nil, Nil) -> c21
569.82/291.56	   PREFIX(Cons(z0, z1), Cons(z2, z3)) -> c12(!EQ'(z0, z2), PREFIX(z1, z3))
569.82/291.56	K tuples:none
569.82/291.56	Defined Rule Symbols:   prefix_2, domatch_3, eqNatList_2, notEmpty_1, strmatch_2, and_2, !EQ_2, domatch[Ite]_4, eqNatList[Ite]_5
569.82/291.56	
569.82/291.56	Defined Pair Symbols:   !EQ'_2, DOMATCH[ITE]_4, EQNATLIST[ITE]_5, DOMATCH_3, EQNATLIST_2, PREFIX_2
569.82/291.56	
569.82/291.56	Compound Symbols:   c4_1, c8_1, c9_1, c11_1, c15, c16, c17_2, c18_2, c19, c20, c21, c12_2
569.82/291.56	
569.82/291.56	
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(9) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
569.82/291.56	The following rules are not usable and were removed:
569.82/291.56	   domatch[Ite](False, z0, Cons(z1, z2), z3) -> domatch(z0, z2, Cons(z3, Cons(Nil, Nil)))
569.82/291.56	   domatch[Ite](True, z0, Cons(z1, z2), z3) -> Cons(z3, domatch(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   eqNatList[Ite](False, z0, z1, z2, z3) -> False
569.82/291.56	   eqNatList[Ite](True, z0, z1, z2, z3) -> eqNatList(z3, z1)
569.82/291.56	   domatch(Cons(z0, z1), Nil, z2) -> Nil
569.82/291.56	   domatch(Nil, Nil, z0) -> Cons(z0, Nil)
569.82/291.56	   domatch(z0, Cons(z1, z2), z3) -> domatch[Ite](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3)
569.82/291.56	   eqNatList(Cons(z0, z1), Cons(z2, z3)) -> eqNatList[Ite](!EQ(z0, z2), z2, z3, z0, z1)
569.82/291.56	   eqNatList(Cons(z0, z1), Nil) -> False
569.82/291.56	   eqNatList(Nil, Cons(z0, z1)) -> False
569.82/291.56	   eqNatList(Nil, Nil) -> True
569.82/291.56	   notEmpty(Cons(z0, z1)) -> True
569.82/291.56	   notEmpty(Nil) -> False
569.82/291.56	   strmatch(z0, z1) -> domatch(z0, z1, Nil)
569.82/291.56	
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(10)
569.82/291.56	Obligation:
569.82/291.56	Complexity Dependency Tuples Problem
569.82/291.56	
569.82/291.56	Rules:
569.82/291.56	   prefix(Cons(z0, z1), Cons(z2, z3)) -> and(!EQ(z0, z2), prefix(z1, z3))
569.82/291.56	   prefix(Nil, z0) -> True
569.82/291.56	   prefix(Cons(z0, z1), Nil) -> False
569.82/291.56	   and(False, False) -> False
569.82/291.56	   and(True, False) -> False
569.82/291.56	   and(False, True) -> False
569.82/291.56	   and(True, True) -> True
569.82/291.56	   !EQ(S(z0), S(z1)) -> !EQ(z0, z1)
569.82/291.56	   !EQ(0, S(z0)) -> False
569.82/291.56	   !EQ(S(z0), 0) -> False
569.82/291.56	   !EQ(0, 0) -> True
569.82/291.56	Tuples:
569.82/291.56	   !EQ'(S(z0), S(z1)) -> c4(!EQ'(z0, z1))
569.82/291.56	   DOMATCH[ITE](False, z0, Cons(z1, z2), z3) -> c8(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   DOMATCH[ITE](True, z0, Cons(z1, z2), z3) -> c9(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   EQNATLIST[ITE](True, z0, z1, z2, z3) -> c11(EQNATLIST(z3, z1))
569.82/291.56	   DOMATCH(Cons(z0, z1), Nil, z2) -> c15
569.82/291.56	   DOMATCH(Nil, Nil, z0) -> c16
569.82/291.56	   DOMATCH(z0, Cons(z1, z2), z3) -> c17(DOMATCH[ITE](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3), PREFIX(z0, Cons(z1, z2)))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Cons(z2, z3)) -> c18(EQNATLIST[ITE](!EQ(z0, z2), z2, z3, z0, z1), !EQ'(z0, z2))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Nil) -> c19
569.82/291.56	   EQNATLIST(Nil, Cons(z0, z1)) -> c20
569.82/291.56	   EQNATLIST(Nil, Nil) -> c21
569.82/291.56	   PREFIX(Cons(z0, z1), Cons(z2, z3)) -> c12(!EQ'(z0, z2), PREFIX(z1, z3))
569.82/291.56	S tuples:
569.82/291.56	   DOMATCH(Cons(z0, z1), Nil, z2) -> c15
569.82/291.56	   DOMATCH(Nil, Nil, z0) -> c16
569.82/291.56	   DOMATCH(z0, Cons(z1, z2), z3) -> c17(DOMATCH[ITE](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3), PREFIX(z0, Cons(z1, z2)))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Cons(z2, z3)) -> c18(EQNATLIST[ITE](!EQ(z0, z2), z2, z3, z0, z1), !EQ'(z0, z2))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Nil) -> c19
569.82/291.56	   EQNATLIST(Nil, Cons(z0, z1)) -> c20
569.82/291.56	   EQNATLIST(Nil, Nil) -> c21
569.82/291.56	   PREFIX(Cons(z0, z1), Cons(z2, z3)) -> c12(!EQ'(z0, z2), PREFIX(z1, z3))
569.82/291.56	K tuples:none
569.82/291.56	Defined Rule Symbols:   prefix_2, and_2, !EQ_2
569.82/291.56	
569.82/291.56	Defined Pair Symbols:   !EQ'_2, DOMATCH[ITE]_4, EQNATLIST[ITE]_5, DOMATCH_3, EQNATLIST_2, PREFIX_2
569.82/291.56	
569.82/291.56	Compound Symbols:   c4_1, c8_1, c9_1, c11_1, c15, c16, c17_2, c18_2, c19, c20, c21, c12_2
569.82/291.56	
569.82/291.56	
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
569.82/291.56	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
569.82/291.56	   EQNATLIST(Cons(z0, z1), Nil) -> c19
569.82/291.56	   EQNATLIST(Nil, Cons(z0, z1)) -> c20
569.82/291.56	   EQNATLIST(Nil, Nil) -> c21
569.82/291.56	We considered the (Usable) Rules:none
569.82/291.56	And the Tuples:
569.82/291.56	   !EQ'(S(z0), S(z1)) -> c4(!EQ'(z0, z1))
569.82/291.56	   DOMATCH[ITE](False, z0, Cons(z1, z2), z3) -> c8(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   DOMATCH[ITE](True, z0, Cons(z1, z2), z3) -> c9(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   EQNATLIST[ITE](True, z0, z1, z2, z3) -> c11(EQNATLIST(z3, z1))
569.82/291.56	   DOMATCH(Cons(z0, z1), Nil, z2) -> c15
569.82/291.56	   DOMATCH(Nil, Nil, z0) -> c16
569.82/291.56	   DOMATCH(z0, Cons(z1, z2), z3) -> c17(DOMATCH[ITE](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3), PREFIX(z0, Cons(z1, z2)))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Cons(z2, z3)) -> c18(EQNATLIST[ITE](!EQ(z0, z2), z2, z3, z0, z1), !EQ'(z0, z2))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Nil) -> c19
569.82/291.56	   EQNATLIST(Nil, Cons(z0, z1)) -> c20
569.82/291.56	   EQNATLIST(Nil, Nil) -> c21
569.82/291.56	   PREFIX(Cons(z0, z1), Cons(z2, z3)) -> c12(!EQ'(z0, z2), PREFIX(z1, z3))
569.82/291.56	The order we found is given by the following interpretation:
569.82/291.56	
569.82/291.56	Polynomial interpretation :
569.82/291.56	
569.82/291.56	   POL(!EQ(x_1, x_2)) = [1] + x_2
569.82/291.56	   POL(!EQ'(x_1, x_2)) = 0
569.82/291.56	   POL(0) = [1]
569.82/291.56	   POL(Cons(x_1, x_2)) = 0
569.82/291.56	   POL(DOMATCH(x_1, x_2, x_3)) = x_1 + x_3
569.82/291.56	   POL(DOMATCH[ITE](x_1, x_2, x_3, x_4)) = x_2 + x_3 + x_4
569.82/291.56	   POL(EQNATLIST(x_1, x_2)) = [1]
569.82/291.56	   POL(EQNATLIST[ITE](x_1, x_2, x_3, x_4, x_5)) = [1]
569.82/291.56	   POL(False) = [1]
569.82/291.56	   POL(Nil) = 0
569.82/291.56	   POL(PREFIX(x_1, x_2)) = 0
569.82/291.56	   POL(S(x_1)) = [1] + x_1
569.82/291.56	   POL(True) = [1]
569.82/291.56	   POL(and(x_1, x_2)) = [1] + x_1
569.82/291.56	   POL(c11(x_1)) = x_1
569.82/291.56	   POL(c12(x_1, x_2)) = x_1 + x_2
569.82/291.56	   POL(c15) = 0
569.82/291.56	   POL(c16) = 0
569.82/291.56	   POL(c17(x_1, x_2)) = x_1 + x_2
569.82/291.56	   POL(c18(x_1, x_2)) = x_1 + x_2
569.82/291.56	   POL(c19) = 0
569.82/291.56	   POL(c20) = 0
569.82/291.56	   POL(c21) = 0
569.82/291.56	   POL(c4(x_1)) = x_1
569.82/291.56	   POL(c8(x_1)) = x_1
569.82/291.56	   POL(c9(x_1)) = x_1
569.82/291.56	   POL(prefix(x_1, x_2)) = [1] + x_1 + x_2
569.82/291.56	
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(12)
569.82/291.56	Obligation:
569.82/291.56	Complexity Dependency Tuples Problem
569.82/291.56	
569.82/291.56	Rules:
569.82/291.56	   prefix(Cons(z0, z1), Cons(z2, z3)) -> and(!EQ(z0, z2), prefix(z1, z3))
569.82/291.56	   prefix(Nil, z0) -> True
569.82/291.56	   prefix(Cons(z0, z1), Nil) -> False
569.82/291.56	   and(False, False) -> False
569.82/291.56	   and(True, False) -> False
569.82/291.56	   and(False, True) -> False
569.82/291.56	   and(True, True) -> True
569.82/291.56	   !EQ(S(z0), S(z1)) -> !EQ(z0, z1)
569.82/291.56	   !EQ(0, S(z0)) -> False
569.82/291.56	   !EQ(S(z0), 0) -> False
569.82/291.56	   !EQ(0, 0) -> True
569.82/291.56	Tuples:
569.82/291.56	   !EQ'(S(z0), S(z1)) -> c4(!EQ'(z0, z1))
569.82/291.56	   DOMATCH[ITE](False, z0, Cons(z1, z2), z3) -> c8(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   DOMATCH[ITE](True, z0, Cons(z1, z2), z3) -> c9(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   EQNATLIST[ITE](True, z0, z1, z2, z3) -> c11(EQNATLIST(z3, z1))
569.82/291.56	   DOMATCH(Cons(z0, z1), Nil, z2) -> c15
569.82/291.56	   DOMATCH(Nil, Nil, z0) -> c16
569.82/291.56	   DOMATCH(z0, Cons(z1, z2), z3) -> c17(DOMATCH[ITE](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3), PREFIX(z0, Cons(z1, z2)))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Cons(z2, z3)) -> c18(EQNATLIST[ITE](!EQ(z0, z2), z2, z3, z0, z1), !EQ'(z0, z2))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Nil) -> c19
569.82/291.56	   EQNATLIST(Nil, Cons(z0, z1)) -> c20
569.82/291.56	   EQNATLIST(Nil, Nil) -> c21
569.82/291.56	   PREFIX(Cons(z0, z1), Cons(z2, z3)) -> c12(!EQ'(z0, z2), PREFIX(z1, z3))
569.82/291.56	S tuples:
569.82/291.56	   DOMATCH(Cons(z0, z1), Nil, z2) -> c15
569.82/291.56	   DOMATCH(Nil, Nil, z0) -> c16
569.82/291.56	   DOMATCH(z0, Cons(z1, z2), z3) -> c17(DOMATCH[ITE](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3), PREFIX(z0, Cons(z1, z2)))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Cons(z2, z3)) -> c18(EQNATLIST[ITE](!EQ(z0, z2), z2, z3, z0, z1), !EQ'(z0, z2))
569.82/291.56	   PREFIX(Cons(z0, z1), Cons(z2, z3)) -> c12(!EQ'(z0, z2), PREFIX(z1, z3))
569.82/291.56	K tuples:
569.82/291.56	   EQNATLIST(Cons(z0, z1), Nil) -> c19
569.82/291.56	   EQNATLIST(Nil, Cons(z0, z1)) -> c20
569.82/291.56	   EQNATLIST(Nil, Nil) -> c21
569.82/291.56	Defined Rule Symbols:   prefix_2, and_2, !EQ_2
569.82/291.56	
569.82/291.56	Defined Pair Symbols:   !EQ'_2, DOMATCH[ITE]_4, EQNATLIST[ITE]_5, DOMATCH_3, EQNATLIST_2, PREFIX_2
569.82/291.56	
569.82/291.56	Compound Symbols:   c4_1, c8_1, c9_1, c11_1, c15, c16, c17_2, c18_2, c19, c20, c21, c12_2
569.82/291.56	
569.82/291.56	
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(13) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
569.82/291.56	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
569.82/291.56	   DOMATCH(Cons(z0, z1), Nil, z2) -> c15
569.82/291.56	We considered the (Usable) Rules:none
569.82/291.56	And the Tuples:
569.82/291.56	   !EQ'(S(z0), S(z1)) -> c4(!EQ'(z0, z1))
569.82/291.56	   DOMATCH[ITE](False, z0, Cons(z1, z2), z3) -> c8(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   DOMATCH[ITE](True, z0, Cons(z1, z2), z3) -> c9(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   EQNATLIST[ITE](True, z0, z1, z2, z3) -> c11(EQNATLIST(z3, z1))
569.82/291.56	   DOMATCH(Cons(z0, z1), Nil, z2) -> c15
569.82/291.56	   DOMATCH(Nil, Nil, z0) -> c16
569.82/291.56	   DOMATCH(z0, Cons(z1, z2), z3) -> c17(DOMATCH[ITE](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3), PREFIX(z0, Cons(z1, z2)))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Cons(z2, z3)) -> c18(EQNATLIST[ITE](!EQ(z0, z2), z2, z3, z0, z1), !EQ'(z0, z2))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Nil) -> c19
569.82/291.56	   EQNATLIST(Nil, Cons(z0, z1)) -> c20
569.82/291.56	   EQNATLIST(Nil, Nil) -> c21
569.82/291.56	   PREFIX(Cons(z0, z1), Cons(z2, z3)) -> c12(!EQ'(z0, z2), PREFIX(z1, z3))
569.82/291.56	The order we found is given by the following interpretation:
569.82/291.56	
569.82/291.56	Polynomial interpretation :
569.82/291.56	
569.82/291.56	   POL(!EQ(x_1, x_2)) = [1]
569.82/291.56	   POL(!EQ'(x_1, x_2)) = 0
569.82/291.56	   POL(0) = [1]
569.82/291.56	   POL(Cons(x_1, x_2)) = [1]
569.82/291.56	   POL(DOMATCH(x_1, x_2, x_3)) = x_1
569.82/291.56	   POL(DOMATCH[ITE](x_1, x_2, x_3, x_4)) = x_2
569.82/291.56	   POL(EQNATLIST(x_1, x_2)) = 0
569.82/291.56	   POL(EQNATLIST[ITE](x_1, x_2, x_3, x_4, x_5)) = 0
569.82/291.56	   POL(False) = [1]
569.82/291.56	   POL(Nil) = 0
569.82/291.56	   POL(PREFIX(x_1, x_2)) = 0
569.82/291.56	   POL(S(x_1)) = [1] + x_1
569.82/291.56	   POL(True) = 0
569.82/291.56	   POL(and(x_1, x_2)) = [1] + x_1
569.82/291.56	   POL(c11(x_1)) = x_1
569.82/291.56	   POL(c12(x_1, x_2)) = x_1 + x_2
569.82/291.56	   POL(c15) = 0
569.82/291.56	   POL(c16) = 0
569.82/291.56	   POL(c17(x_1, x_2)) = x_1 + x_2
569.82/291.56	   POL(c18(x_1, x_2)) = x_1 + x_2
569.82/291.56	   POL(c19) = 0
569.82/291.56	   POL(c20) = 0
569.82/291.56	   POL(c21) = 0
569.82/291.56	   POL(c4(x_1)) = x_1
569.82/291.56	   POL(c8(x_1)) = x_1
569.82/291.56	   POL(c9(x_1)) = x_1
569.82/291.56	   POL(prefix(x_1, x_2)) = [1] + x_1 + x_2
569.82/291.56	
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(14)
569.82/291.56	Obligation:
569.82/291.56	Complexity Dependency Tuples Problem
569.82/291.56	
569.82/291.56	Rules:
569.82/291.56	   prefix(Cons(z0, z1), Cons(z2, z3)) -> and(!EQ(z0, z2), prefix(z1, z3))
569.82/291.56	   prefix(Nil, z0) -> True
569.82/291.56	   prefix(Cons(z0, z1), Nil) -> False
569.82/291.56	   and(False, False) -> False
569.82/291.56	   and(True, False) -> False
569.82/291.56	   and(False, True) -> False
569.82/291.56	   and(True, True) -> True
569.82/291.56	   !EQ(S(z0), S(z1)) -> !EQ(z0, z1)
569.82/291.56	   !EQ(0, S(z0)) -> False
569.82/291.56	   !EQ(S(z0), 0) -> False
569.82/291.56	   !EQ(0, 0) -> True
569.82/291.56	Tuples:
569.82/291.56	   !EQ'(S(z0), S(z1)) -> c4(!EQ'(z0, z1))
569.82/291.56	   DOMATCH[ITE](False, z0, Cons(z1, z2), z3) -> c8(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   DOMATCH[ITE](True, z0, Cons(z1, z2), z3) -> c9(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   EQNATLIST[ITE](True, z0, z1, z2, z3) -> c11(EQNATLIST(z3, z1))
569.82/291.56	   DOMATCH(Cons(z0, z1), Nil, z2) -> c15
569.82/291.56	   DOMATCH(Nil, Nil, z0) -> c16
569.82/291.56	   DOMATCH(z0, Cons(z1, z2), z3) -> c17(DOMATCH[ITE](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3), PREFIX(z0, Cons(z1, z2)))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Cons(z2, z3)) -> c18(EQNATLIST[ITE](!EQ(z0, z2), z2, z3, z0, z1), !EQ'(z0, z2))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Nil) -> c19
569.82/291.56	   EQNATLIST(Nil, Cons(z0, z1)) -> c20
569.82/291.56	   EQNATLIST(Nil, Nil) -> c21
569.82/291.56	   PREFIX(Cons(z0, z1), Cons(z2, z3)) -> c12(!EQ'(z0, z2), PREFIX(z1, z3))
569.82/291.56	S tuples:
569.82/291.56	   DOMATCH(Nil, Nil, z0) -> c16
569.82/291.56	   DOMATCH(z0, Cons(z1, z2), z3) -> c17(DOMATCH[ITE](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3), PREFIX(z0, Cons(z1, z2)))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Cons(z2, z3)) -> c18(EQNATLIST[ITE](!EQ(z0, z2), z2, z3, z0, z1), !EQ'(z0, z2))
569.82/291.56	   PREFIX(Cons(z0, z1), Cons(z2, z3)) -> c12(!EQ'(z0, z2), PREFIX(z1, z3))
569.82/291.56	K tuples:
569.82/291.56	   EQNATLIST(Cons(z0, z1), Nil) -> c19
569.82/291.56	   EQNATLIST(Nil, Cons(z0, z1)) -> c20
569.82/291.56	   EQNATLIST(Nil, Nil) -> c21
569.82/291.56	   DOMATCH(Cons(z0, z1), Nil, z2) -> c15
569.82/291.56	Defined Rule Symbols:   prefix_2, and_2, !EQ_2
569.82/291.56	
569.82/291.56	Defined Pair Symbols:   !EQ'_2, DOMATCH[ITE]_4, EQNATLIST[ITE]_5, DOMATCH_3, EQNATLIST_2, PREFIX_2
569.82/291.56	
569.82/291.56	Compound Symbols:   c4_1, c8_1, c9_1, c11_1, c15, c16, c17_2, c18_2, c19, c20, c21, c12_2
569.82/291.56	
569.82/291.56	
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(15) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
569.82/291.56	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
569.82/291.56	   DOMATCH(Nil, Nil, z0) -> c16
569.82/291.56	We considered the (Usable) Rules:none
569.82/291.56	And the Tuples:
569.82/291.56	   !EQ'(S(z0), S(z1)) -> c4(!EQ'(z0, z1))
569.82/291.56	   DOMATCH[ITE](False, z0, Cons(z1, z2), z3) -> c8(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   DOMATCH[ITE](True, z0, Cons(z1, z2), z3) -> c9(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   EQNATLIST[ITE](True, z0, z1, z2, z3) -> c11(EQNATLIST(z3, z1))
569.82/291.56	   DOMATCH(Cons(z0, z1), Nil, z2) -> c15
569.82/291.56	   DOMATCH(Nil, Nil, z0) -> c16
569.82/291.56	   DOMATCH(z0, Cons(z1, z2), z3) -> c17(DOMATCH[ITE](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3), PREFIX(z0, Cons(z1, z2)))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Cons(z2, z3)) -> c18(EQNATLIST[ITE](!EQ(z0, z2), z2, z3, z0, z1), !EQ'(z0, z2))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Nil) -> c19
569.82/291.56	   EQNATLIST(Nil, Cons(z0, z1)) -> c20
569.82/291.56	   EQNATLIST(Nil, Nil) -> c21
569.82/291.56	   PREFIX(Cons(z0, z1), Cons(z2, z3)) -> c12(!EQ'(z0, z2), PREFIX(z1, z3))
569.82/291.56	The order we found is given by the following interpretation:
569.82/291.56	
569.82/291.56	Polynomial interpretation :
569.82/291.56	
569.82/291.56	   POL(!EQ(x_1, x_2)) = [1]
569.82/291.56	   POL(!EQ'(x_1, x_2)) = 0
569.82/291.56	   POL(0) = [1]
569.82/291.56	   POL(Cons(x_1, x_2)) = 0
569.82/291.56	   POL(DOMATCH(x_1, x_2, x_3)) = x_1 + x_3
569.82/291.56	   POL(DOMATCH[ITE](x_1, x_2, x_3, x_4)) = x_2 + x_3 + x_4
569.82/291.56	   POL(EQNATLIST(x_1, x_2)) = 0
569.82/291.56	   POL(EQNATLIST[ITE](x_1, x_2, x_3, x_4, x_5)) = 0
569.82/291.56	   POL(False) = [1]
569.82/291.56	   POL(Nil) = [1]
569.82/291.56	   POL(PREFIX(x_1, x_2)) = 0
569.82/291.56	   POL(S(x_1)) = [1] + x_1
569.82/291.56	   POL(True) = 0
569.82/291.56	   POL(and(x_1, x_2)) = [1] + x_1
569.82/291.56	   POL(c11(x_1)) = x_1
569.82/291.56	   POL(c12(x_1, x_2)) = x_1 + x_2
569.82/291.56	   POL(c15) = 0
569.82/291.56	   POL(c16) = 0
569.82/291.56	   POL(c17(x_1, x_2)) = x_1 + x_2
569.82/291.56	   POL(c18(x_1, x_2)) = x_1 + x_2
569.82/291.56	   POL(c19) = 0
569.82/291.56	   POL(c20) = 0
569.82/291.56	   POL(c21) = 0
569.82/291.56	   POL(c4(x_1)) = x_1
569.82/291.56	   POL(c8(x_1)) = x_1
569.82/291.56	   POL(c9(x_1)) = x_1
569.82/291.56	   POL(prefix(x_1, x_2)) = [1] + x_1
569.82/291.56	
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(16)
569.82/291.56	Obligation:
569.82/291.56	Complexity Dependency Tuples Problem
569.82/291.56	
569.82/291.56	Rules:
569.82/291.56	   prefix(Cons(z0, z1), Cons(z2, z3)) -> and(!EQ(z0, z2), prefix(z1, z3))
569.82/291.56	   prefix(Nil, z0) -> True
569.82/291.56	   prefix(Cons(z0, z1), Nil) -> False
569.82/291.56	   and(False, False) -> False
569.82/291.56	   and(True, False) -> False
569.82/291.56	   and(False, True) -> False
569.82/291.56	   and(True, True) -> True
569.82/291.56	   !EQ(S(z0), S(z1)) -> !EQ(z0, z1)
569.82/291.56	   !EQ(0, S(z0)) -> False
569.82/291.56	   !EQ(S(z0), 0) -> False
569.82/291.56	   !EQ(0, 0) -> True
569.82/291.56	Tuples:
569.82/291.56	   !EQ'(S(z0), S(z1)) -> c4(!EQ'(z0, z1))
569.82/291.56	   DOMATCH[ITE](False, z0, Cons(z1, z2), z3) -> c8(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   DOMATCH[ITE](True, z0, Cons(z1, z2), z3) -> c9(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   EQNATLIST[ITE](True, z0, z1, z2, z3) -> c11(EQNATLIST(z3, z1))
569.82/291.56	   DOMATCH(Cons(z0, z1), Nil, z2) -> c15
569.82/291.56	   DOMATCH(Nil, Nil, z0) -> c16
569.82/291.56	   DOMATCH(z0, Cons(z1, z2), z3) -> c17(DOMATCH[ITE](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3), PREFIX(z0, Cons(z1, z2)))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Cons(z2, z3)) -> c18(EQNATLIST[ITE](!EQ(z0, z2), z2, z3, z0, z1), !EQ'(z0, z2))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Nil) -> c19
569.82/291.56	   EQNATLIST(Nil, Cons(z0, z1)) -> c20
569.82/291.56	   EQNATLIST(Nil, Nil) -> c21
569.82/291.56	   PREFIX(Cons(z0, z1), Cons(z2, z3)) -> c12(!EQ'(z0, z2), PREFIX(z1, z3))
569.82/291.56	S tuples:
569.82/291.56	   DOMATCH(z0, Cons(z1, z2), z3) -> c17(DOMATCH[ITE](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3), PREFIX(z0, Cons(z1, z2)))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Cons(z2, z3)) -> c18(EQNATLIST[ITE](!EQ(z0, z2), z2, z3, z0, z1), !EQ'(z0, z2))
569.82/291.56	   PREFIX(Cons(z0, z1), Cons(z2, z3)) -> c12(!EQ'(z0, z2), PREFIX(z1, z3))
569.82/291.56	K tuples:
569.82/291.56	   EQNATLIST(Cons(z0, z1), Nil) -> c19
569.82/291.56	   EQNATLIST(Nil, Cons(z0, z1)) -> c20
569.82/291.56	   EQNATLIST(Nil, Nil) -> c21
569.82/291.56	   DOMATCH(Cons(z0, z1), Nil, z2) -> c15
569.82/291.56	   DOMATCH(Nil, Nil, z0) -> c16
569.82/291.56	Defined Rule Symbols:   prefix_2, and_2, !EQ_2
569.82/291.56	
569.82/291.56	Defined Pair Symbols:   !EQ'_2, DOMATCH[ITE]_4, EQNATLIST[ITE]_5, DOMATCH_3, EQNATLIST_2, PREFIX_2
569.82/291.56	
569.82/291.56	Compound Symbols:   c4_1, c8_1, c9_1, c11_1, c15, c16, c17_2, c18_2, c19, c20, c21, c12_2
569.82/291.56	
569.82/291.56	
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(17) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
569.82/291.56	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
569.82/291.56	   EQNATLIST(Cons(z0, z1), Cons(z2, z3)) -> c18(EQNATLIST[ITE](!EQ(z0, z2), z2, z3, z0, z1), !EQ'(z0, z2))
569.82/291.56	We considered the (Usable) Rules:none
569.82/291.56	And the Tuples:
569.82/291.56	   !EQ'(S(z0), S(z1)) -> c4(!EQ'(z0, z1))
569.82/291.56	   DOMATCH[ITE](False, z0, Cons(z1, z2), z3) -> c8(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   DOMATCH[ITE](True, z0, Cons(z1, z2), z3) -> c9(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   EQNATLIST[ITE](True, z0, z1, z2, z3) -> c11(EQNATLIST(z3, z1))
569.82/291.56	   DOMATCH(Cons(z0, z1), Nil, z2) -> c15
569.82/291.56	   DOMATCH(Nil, Nil, z0) -> c16
569.82/291.56	   DOMATCH(z0, Cons(z1, z2), z3) -> c17(DOMATCH[ITE](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3), PREFIX(z0, Cons(z1, z2)))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Cons(z2, z3)) -> c18(EQNATLIST[ITE](!EQ(z0, z2), z2, z3, z0, z1), !EQ'(z0, z2))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Nil) -> c19
569.82/291.56	   EQNATLIST(Nil, Cons(z0, z1)) -> c20
569.82/291.56	   EQNATLIST(Nil, Nil) -> c21
569.82/291.56	   PREFIX(Cons(z0, z1), Cons(z2, z3)) -> c12(!EQ'(z0, z2), PREFIX(z1, z3))
569.82/291.56	The order we found is given by the following interpretation:
569.82/291.56	
569.82/291.56	Polynomial interpretation :
569.82/291.56	
569.82/291.56	   POL(!EQ(x_1, x_2)) = [1]
569.82/291.56	   POL(!EQ'(x_1, x_2)) = 0
569.82/291.56	   POL(0) = [1]
569.82/291.56	   POL(Cons(x_1, x_2)) = [1] + x_2
569.82/291.56	   POL(DOMATCH(x_1, x_2, x_3)) = x_1
569.82/291.56	   POL(DOMATCH[ITE](x_1, x_2, x_3, x_4)) = x_2
569.82/291.56	   POL(EQNATLIST(x_1, x_2)) = x_2
569.82/291.56	   POL(EQNATLIST[ITE](x_1, x_2, x_3, x_4, x_5)) = x_3
569.82/291.56	   POL(False) = [1]
569.82/291.56	   POL(Nil) = 0
569.82/291.56	   POL(PREFIX(x_1, x_2)) = 0
569.82/291.56	   POL(S(x_1)) = [1] + x_1
569.82/291.56	   POL(True) = 0
569.82/291.56	   POL(and(x_1, x_2)) = [1] + x_1
569.82/291.56	   POL(c11(x_1)) = x_1
569.82/291.56	   POL(c12(x_1, x_2)) = x_1 + x_2
569.82/291.56	   POL(c15) = 0
569.82/291.56	   POL(c16) = 0
569.82/291.56	   POL(c17(x_1, x_2)) = x_1 + x_2
569.82/291.56	   POL(c18(x_1, x_2)) = x_1 + x_2
569.82/291.56	   POL(c19) = 0
569.82/291.56	   POL(c20) = 0
569.82/291.56	   POL(c21) = 0
569.82/291.56	   POL(c4(x_1)) = x_1
569.82/291.56	   POL(c8(x_1)) = x_1
569.82/291.56	   POL(c9(x_1)) = x_1
569.82/291.56	   POL(prefix(x_1, x_2)) = [1] + x_1 + x_2
569.82/291.56	
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(18)
569.82/291.56	Obligation:
569.82/291.56	Complexity Dependency Tuples Problem
569.82/291.56	
569.82/291.56	Rules:
569.82/291.56	   prefix(Cons(z0, z1), Cons(z2, z3)) -> and(!EQ(z0, z2), prefix(z1, z3))
569.82/291.56	   prefix(Nil, z0) -> True
569.82/291.56	   prefix(Cons(z0, z1), Nil) -> False
569.82/291.56	   and(False, False) -> False
569.82/291.56	   and(True, False) -> False
569.82/291.56	   and(False, True) -> False
569.82/291.56	   and(True, True) -> True
569.82/291.56	   !EQ(S(z0), S(z1)) -> !EQ(z0, z1)
569.82/291.56	   !EQ(0, S(z0)) -> False
569.82/291.56	   !EQ(S(z0), 0) -> False
569.82/291.56	   !EQ(0, 0) -> True
569.82/291.56	Tuples:
569.82/291.56	   !EQ'(S(z0), S(z1)) -> c4(!EQ'(z0, z1))
569.82/291.56	   DOMATCH[ITE](False, z0, Cons(z1, z2), z3) -> c8(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   DOMATCH[ITE](True, z0, Cons(z1, z2), z3) -> c9(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   EQNATLIST[ITE](True, z0, z1, z2, z3) -> c11(EQNATLIST(z3, z1))
569.82/291.56	   DOMATCH(Cons(z0, z1), Nil, z2) -> c15
569.82/291.56	   DOMATCH(Nil, Nil, z0) -> c16
569.82/291.56	   DOMATCH(z0, Cons(z1, z2), z3) -> c17(DOMATCH[ITE](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3), PREFIX(z0, Cons(z1, z2)))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Cons(z2, z3)) -> c18(EQNATLIST[ITE](!EQ(z0, z2), z2, z3, z0, z1), !EQ'(z0, z2))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Nil) -> c19
569.82/291.56	   EQNATLIST(Nil, Cons(z0, z1)) -> c20
569.82/291.56	   EQNATLIST(Nil, Nil) -> c21
569.82/291.56	   PREFIX(Cons(z0, z1), Cons(z2, z3)) -> c12(!EQ'(z0, z2), PREFIX(z1, z3))
569.82/291.56	S tuples:
569.82/291.56	   DOMATCH(z0, Cons(z1, z2), z3) -> c17(DOMATCH[ITE](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3), PREFIX(z0, Cons(z1, z2)))
569.82/291.56	   PREFIX(Cons(z0, z1), Cons(z2, z3)) -> c12(!EQ'(z0, z2), PREFIX(z1, z3))
569.82/291.56	K tuples:
569.82/291.56	   EQNATLIST(Cons(z0, z1), Nil) -> c19
569.82/291.56	   EQNATLIST(Nil, Cons(z0, z1)) -> c20
569.82/291.56	   EQNATLIST(Nil, Nil) -> c21
569.82/291.56	   DOMATCH(Cons(z0, z1), Nil, z2) -> c15
569.82/291.56	   DOMATCH(Nil, Nil, z0) -> c16
569.82/291.56	   EQNATLIST(Cons(z0, z1), Cons(z2, z3)) -> c18(EQNATLIST[ITE](!EQ(z0, z2), z2, z3, z0, z1), !EQ'(z0, z2))
569.82/291.56	Defined Rule Symbols:   prefix_2, and_2, !EQ_2
569.82/291.56	
569.82/291.56	Defined Pair Symbols:   !EQ'_2, DOMATCH[ITE]_4, EQNATLIST[ITE]_5, DOMATCH_3, EQNATLIST_2, PREFIX_2
569.82/291.56	
569.82/291.56	Compound Symbols:   c4_1, c8_1, c9_1, c11_1, c15, c16, c17_2, c18_2, c19, c20, c21, c12_2
569.82/291.56	
569.82/291.56	
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(19) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
569.82/291.56	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
569.82/291.56	   DOMATCH(z0, Cons(z1, z2), z3) -> c17(DOMATCH[ITE](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3), PREFIX(z0, Cons(z1, z2)))
569.82/291.56	We considered the (Usable) Rules:none
569.82/291.56	And the Tuples:
569.82/291.56	   !EQ'(S(z0), S(z1)) -> c4(!EQ'(z0, z1))
569.82/291.56	   DOMATCH[ITE](False, z0, Cons(z1, z2), z3) -> c8(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   DOMATCH[ITE](True, z0, Cons(z1, z2), z3) -> c9(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   EQNATLIST[ITE](True, z0, z1, z2, z3) -> c11(EQNATLIST(z3, z1))
569.82/291.56	   DOMATCH(Cons(z0, z1), Nil, z2) -> c15
569.82/291.56	   DOMATCH(Nil, Nil, z0) -> c16
569.82/291.56	   DOMATCH(z0, Cons(z1, z2), z3) -> c17(DOMATCH[ITE](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3), PREFIX(z0, Cons(z1, z2)))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Cons(z2, z3)) -> c18(EQNATLIST[ITE](!EQ(z0, z2), z2, z3, z0, z1), !EQ'(z0, z2))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Nil) -> c19
569.82/291.56	   EQNATLIST(Nil, Cons(z0, z1)) -> c20
569.82/291.56	   EQNATLIST(Nil, Nil) -> c21
569.82/291.56	   PREFIX(Cons(z0, z1), Cons(z2, z3)) -> c12(!EQ'(z0, z2), PREFIX(z1, z3))
569.82/291.56	The order we found is given by the following interpretation:
569.82/291.56	
569.82/291.56	Polynomial interpretation :
569.82/291.56	
569.82/291.56	   POL(!EQ(x_1, x_2)) = [1]
569.82/291.56	   POL(!EQ'(x_1, x_2)) = 0
569.82/291.56	   POL(0) = [1]
569.82/291.56	   POL(Cons(x_1, x_2)) = [1] + x_2
569.82/291.56	   POL(DOMATCH(x_1, x_2, x_3)) = [1] + x_1 + x_2
569.82/291.56	   POL(DOMATCH[ITE](x_1, x_2, x_3, x_4)) = x_2 + x_3
569.82/291.56	   POL(EQNATLIST(x_1, x_2)) = 0
569.82/291.56	   POL(EQNATLIST[ITE](x_1, x_2, x_3, x_4, x_5)) = 0
569.82/291.56	   POL(False) = [1]
569.82/291.56	   POL(Nil) = 0
569.82/291.56	   POL(PREFIX(x_1, x_2)) = 0
569.82/291.56	   POL(S(x_1)) = [1] + x_1
569.82/291.56	   POL(True) = 0
569.82/291.56	   POL(and(x_1, x_2)) = [1] + x_1
569.82/291.56	   POL(c11(x_1)) = x_1
569.82/291.56	   POL(c12(x_1, x_2)) = x_1 + x_2
569.82/291.56	   POL(c15) = 0
569.82/291.56	   POL(c16) = 0
569.82/291.56	   POL(c17(x_1, x_2)) = x_1 + x_2
569.82/291.56	   POL(c18(x_1, x_2)) = x_1 + x_2
569.82/291.56	   POL(c19) = 0
569.82/291.56	   POL(c20) = 0
569.82/291.56	   POL(c21) = 0
569.82/291.56	   POL(c4(x_1)) = x_1
569.82/291.56	   POL(c8(x_1)) = x_1
569.82/291.56	   POL(c9(x_1)) = x_1
569.82/291.56	   POL(prefix(x_1, x_2)) = [1] + x_1 + x_2
569.82/291.56	
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(20)
569.82/291.56	Obligation:
569.82/291.56	Complexity Dependency Tuples Problem
569.82/291.56	
569.82/291.56	Rules:
569.82/291.56	   prefix(Cons(z0, z1), Cons(z2, z3)) -> and(!EQ(z0, z2), prefix(z1, z3))
569.82/291.56	   prefix(Nil, z0) -> True
569.82/291.56	   prefix(Cons(z0, z1), Nil) -> False
569.82/291.56	   and(False, False) -> False
569.82/291.56	   and(True, False) -> False
569.82/291.56	   and(False, True) -> False
569.82/291.56	   and(True, True) -> True
569.82/291.56	   !EQ(S(z0), S(z1)) -> !EQ(z0, z1)
569.82/291.56	   !EQ(0, S(z0)) -> False
569.82/291.56	   !EQ(S(z0), 0) -> False
569.82/291.56	   !EQ(0, 0) -> True
569.82/291.56	Tuples:
569.82/291.56	   !EQ'(S(z0), S(z1)) -> c4(!EQ'(z0, z1))
569.82/291.56	   DOMATCH[ITE](False, z0, Cons(z1, z2), z3) -> c8(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   DOMATCH[ITE](True, z0, Cons(z1, z2), z3) -> c9(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   EQNATLIST[ITE](True, z0, z1, z2, z3) -> c11(EQNATLIST(z3, z1))
569.82/291.56	   DOMATCH(Cons(z0, z1), Nil, z2) -> c15
569.82/291.56	   DOMATCH(Nil, Nil, z0) -> c16
569.82/291.56	   DOMATCH(z0, Cons(z1, z2), z3) -> c17(DOMATCH[ITE](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3), PREFIX(z0, Cons(z1, z2)))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Cons(z2, z3)) -> c18(EQNATLIST[ITE](!EQ(z0, z2), z2, z3, z0, z1), !EQ'(z0, z2))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Nil) -> c19
569.82/291.56	   EQNATLIST(Nil, Cons(z0, z1)) -> c20
569.82/291.56	   EQNATLIST(Nil, Nil) -> c21
569.82/291.56	   PREFIX(Cons(z0, z1), Cons(z2, z3)) -> c12(!EQ'(z0, z2), PREFIX(z1, z3))
569.82/291.56	S tuples:
569.82/291.56	   PREFIX(Cons(z0, z1), Cons(z2, z3)) -> c12(!EQ'(z0, z2), PREFIX(z1, z3))
569.82/291.56	K tuples:
569.82/291.56	   EQNATLIST(Cons(z0, z1), Nil) -> c19
569.82/291.56	   EQNATLIST(Nil, Cons(z0, z1)) -> c20
569.82/291.56	   EQNATLIST(Nil, Nil) -> c21
569.82/291.56	   DOMATCH(Cons(z0, z1), Nil, z2) -> c15
569.82/291.56	   DOMATCH(Nil, Nil, z0) -> c16
569.82/291.56	   EQNATLIST(Cons(z0, z1), Cons(z2, z3)) -> c18(EQNATLIST[ITE](!EQ(z0, z2), z2, z3, z0, z1), !EQ'(z0, z2))
569.82/291.56	   DOMATCH(z0, Cons(z1, z2), z3) -> c17(DOMATCH[ITE](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3), PREFIX(z0, Cons(z1, z2)))
569.82/291.56	Defined Rule Symbols:   prefix_2, and_2, !EQ_2
569.82/291.56	
569.82/291.56	Defined Pair Symbols:   !EQ'_2, DOMATCH[ITE]_4, EQNATLIST[ITE]_5, DOMATCH_3, EQNATLIST_2, PREFIX_2
569.82/291.56	
569.82/291.56	Compound Symbols:   c4_1, c8_1, c9_1, c11_1, c15, c16, c17_2, c18_2, c19, c20, c21, c12_2
569.82/291.56	
569.82/291.56	
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(21) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2)))
569.82/291.56	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
569.82/291.56	   PREFIX(Cons(z0, z1), Cons(z2, z3)) -> c12(!EQ'(z0, z2), PREFIX(z1, z3))
569.82/291.56	We considered the (Usable) Rules:none
569.82/291.56	And the Tuples:
569.82/291.56	   !EQ'(S(z0), S(z1)) -> c4(!EQ'(z0, z1))
569.82/291.56	   DOMATCH[ITE](False, z0, Cons(z1, z2), z3) -> c8(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   DOMATCH[ITE](True, z0, Cons(z1, z2), z3) -> c9(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   EQNATLIST[ITE](True, z0, z1, z2, z3) -> c11(EQNATLIST(z3, z1))
569.82/291.56	   DOMATCH(Cons(z0, z1), Nil, z2) -> c15
569.82/291.56	   DOMATCH(Nil, Nil, z0) -> c16
569.82/291.56	   DOMATCH(z0, Cons(z1, z2), z3) -> c17(DOMATCH[ITE](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3), PREFIX(z0, Cons(z1, z2)))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Cons(z2, z3)) -> c18(EQNATLIST[ITE](!EQ(z0, z2), z2, z3, z0, z1), !EQ'(z0, z2))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Nil) -> c19
569.82/291.56	   EQNATLIST(Nil, Cons(z0, z1)) -> c20
569.82/291.56	   EQNATLIST(Nil, Nil) -> c21
569.82/291.56	   PREFIX(Cons(z0, z1), Cons(z2, z3)) -> c12(!EQ'(z0, z2), PREFIX(z1, z3))
569.82/291.56	The order we found is given by the following interpretation:
569.82/291.56	
569.82/291.56	Polynomial interpretation :
569.82/291.56	
569.82/291.56	   POL(!EQ(x_1, x_2)) = 0
569.82/291.56	   POL(!EQ'(x_1, x_2)) = 0
569.82/291.56	   POL(0) = 0
569.82/291.56	   POL(Cons(x_1, x_2)) = [1] + x_2
569.82/291.56	   POL(DOMATCH(x_1, x_2, x_3)) = x_1 + x_1*x_2
569.82/291.56	   POL(DOMATCH[ITE](x_1, x_2, x_3, x_4)) = x_2*x_3
569.82/291.56	   POL(EQNATLIST(x_1, x_2)) = 0
569.82/291.56	   POL(EQNATLIST[ITE](x_1, x_2, x_3, x_4, x_5)) = 0
569.82/291.56	   POL(False) = 0
569.82/291.56	   POL(Nil) = 0
569.82/291.56	   POL(PREFIX(x_1, x_2)) = x_1
569.82/291.56	   POL(S(x_1)) = 0
569.82/291.56	   POL(True) = 0
569.82/291.56	   POL(and(x_1, x_2)) = [1]
569.82/291.56	   POL(c11(x_1)) = x_1
569.82/291.56	   POL(c12(x_1, x_2)) = x_1 + x_2
569.82/291.56	   POL(c15) = 0
569.82/291.56	   POL(c16) = 0
569.82/291.56	   POL(c17(x_1, x_2)) = x_1 + x_2
569.82/291.56	   POL(c18(x_1, x_2)) = x_1 + x_2
569.82/291.56	   POL(c19) = 0
569.82/291.56	   POL(c20) = 0
569.82/291.56	   POL(c21) = 0
569.82/291.56	   POL(c4(x_1)) = x_1
569.82/291.56	   POL(c8(x_1)) = x_1
569.82/291.56	   POL(c9(x_1)) = x_1
569.82/291.56	   POL(prefix(x_1, x_2)) = 0
569.82/291.56	
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(22)
569.82/291.56	Obligation:
569.82/291.56	Complexity Dependency Tuples Problem
569.82/291.56	
569.82/291.56	Rules:
569.82/291.56	   prefix(Cons(z0, z1), Cons(z2, z3)) -> and(!EQ(z0, z2), prefix(z1, z3))
569.82/291.56	   prefix(Nil, z0) -> True
569.82/291.56	   prefix(Cons(z0, z1), Nil) -> False
569.82/291.56	   and(False, False) -> False
569.82/291.56	   and(True, False) -> False
569.82/291.56	   and(False, True) -> False
569.82/291.56	   and(True, True) -> True
569.82/291.56	   !EQ(S(z0), S(z1)) -> !EQ(z0, z1)
569.82/291.56	   !EQ(0, S(z0)) -> False
569.82/291.56	   !EQ(S(z0), 0) -> False
569.82/291.56	   !EQ(0, 0) -> True
569.82/291.56	Tuples:
569.82/291.56	   !EQ'(S(z0), S(z1)) -> c4(!EQ'(z0, z1))
569.82/291.56	   DOMATCH[ITE](False, z0, Cons(z1, z2), z3) -> c8(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   DOMATCH[ITE](True, z0, Cons(z1, z2), z3) -> c9(DOMATCH(z0, z2, Cons(z3, Cons(Nil, Nil))))
569.82/291.56	   EQNATLIST[ITE](True, z0, z1, z2, z3) -> c11(EQNATLIST(z3, z1))
569.82/291.56	   DOMATCH(Cons(z0, z1), Nil, z2) -> c15
569.82/291.56	   DOMATCH(Nil, Nil, z0) -> c16
569.82/291.56	   DOMATCH(z0, Cons(z1, z2), z3) -> c17(DOMATCH[ITE](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3), PREFIX(z0, Cons(z1, z2)))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Cons(z2, z3)) -> c18(EQNATLIST[ITE](!EQ(z0, z2), z2, z3, z0, z1), !EQ'(z0, z2))
569.82/291.56	   EQNATLIST(Cons(z0, z1), Nil) -> c19
569.82/291.56	   EQNATLIST(Nil, Cons(z0, z1)) -> c20
569.82/291.56	   EQNATLIST(Nil, Nil) -> c21
569.82/291.56	   PREFIX(Cons(z0, z1), Cons(z2, z3)) -> c12(!EQ'(z0, z2), PREFIX(z1, z3))
569.82/291.56	S tuples:none
569.82/291.56	K tuples:
569.82/291.56	   EQNATLIST(Cons(z0, z1), Nil) -> c19
569.82/291.56	   EQNATLIST(Nil, Cons(z0, z1)) -> c20
569.82/291.56	   EQNATLIST(Nil, Nil) -> c21
569.82/291.56	   DOMATCH(Cons(z0, z1), Nil, z2) -> c15
569.82/291.56	   DOMATCH(Nil, Nil, z0) -> c16
569.82/291.56	   EQNATLIST(Cons(z0, z1), Cons(z2, z3)) -> c18(EQNATLIST[ITE](!EQ(z0, z2), z2, z3, z0, z1), !EQ'(z0, z2))
569.82/291.56	   DOMATCH(z0, Cons(z1, z2), z3) -> c17(DOMATCH[ITE](prefix(z0, Cons(z1, z2)), z0, Cons(z1, z2), z3), PREFIX(z0, Cons(z1, z2)))
569.82/291.56	   PREFIX(Cons(z0, z1), Cons(z2, z3)) -> c12(!EQ'(z0, z2), PREFIX(z1, z3))
569.82/291.56	Defined Rule Symbols:   prefix_2, and_2, !EQ_2
569.82/291.56	
569.82/291.56	Defined Pair Symbols:   !EQ'_2, DOMATCH[ITE]_4, EQNATLIST[ITE]_5, DOMATCH_3, EQNATLIST_2, PREFIX_2
569.82/291.56	
569.82/291.56	Compound Symbols:   c4_1, c8_1, c9_1, c11_1, c15, c16, c17_2, c18_2, c19, c20, c21, c12_2
569.82/291.56	
569.82/291.56	
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(23) SIsEmptyProof (BOTH BOUNDS(ID, ID))
569.82/291.56	The set S is empty
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(24)
569.82/291.56	BOUNDS(1, 1)
569.82/291.56	
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(25) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
569.82/291.56	Transformed a relative TRS into a decreasing-loop problem.
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(26)
569.82/291.56	Obligation:
569.82/291.56	Analyzing the following TRS for decreasing loops:
569.82/291.56	
569.82/291.56	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2).
569.82/291.56	
569.82/291.56	
569.82/291.56	The TRS R consists of the following rules:
569.82/291.56	
569.82/291.56	   prefix(Cons(x', xs'), Cons(x, xs)) -> and(!EQ(x', x), prefix(xs', xs))
569.82/291.56	   domatch(Cons(x, xs), Nil, n) -> Nil
569.82/291.56	   domatch(Nil, Nil, n) -> Cons(n, Nil)
569.82/291.56	   prefix(Cons(x, xs), Nil) -> False
569.82/291.56	   prefix(Nil, cs) -> True
569.82/291.56	   domatch(patcs, Cons(x, xs), n) -> domatch[Ite](prefix(patcs, Cons(x, xs)), patcs, Cons(x, xs), n)
569.82/291.56	   eqNatList(Cons(x, xs), Cons(y, ys)) -> eqNatList[Ite](!EQ(x, y), y, ys, x, xs)
569.82/291.56	   eqNatList(Cons(x, xs), Nil) -> False
569.82/291.56	   eqNatList(Nil, Cons(y, ys)) -> False
569.82/291.56	   eqNatList(Nil, Nil) -> True
569.82/291.56	   notEmpty(Cons(x, xs)) -> True
569.82/291.56	   notEmpty(Nil) -> False
569.82/291.56	   strmatch(patstr, str) -> domatch(patstr, str, Nil)
569.82/291.56	
569.82/291.56	The (relative) TRS S consists of the following rules:
569.82/291.56	
569.82/291.56	   and(False, False) -> False
569.82/291.56	   and(True, False) -> False
569.82/291.56	   and(False, True) -> False
569.82/291.56	   and(True, True) -> True
569.82/291.56	   !EQ(S(x), S(y)) -> !EQ(x, y)
569.82/291.56	   !EQ(0, S(y)) -> False
569.82/291.56	   !EQ(S(x), 0) -> False
569.82/291.56	   !EQ(0, 0) -> True
569.82/291.56	   domatch[Ite](False, patcs, Cons(x, xs), n) -> domatch(patcs, xs, Cons(n, Cons(Nil, Nil)))
569.82/291.56	   domatch[Ite](True, patcs, Cons(x, xs), n) -> Cons(n, domatch(patcs, xs, Cons(n, Cons(Nil, Nil))))
569.82/291.56	   eqNatList[Ite](False, y, ys, x, xs) -> False
569.82/291.56	   eqNatList[Ite](True, y, ys, x, xs) -> eqNatList(xs, ys)
569.82/291.56	
569.82/291.56	Rewrite Strategy: INNERMOST
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(27) DecreasingLoopProof (LOWER BOUND(ID))
569.82/291.56	The following loop(s) give(s) rise to the lower bound Omega(n^1):
569.82/291.56	
569.82/291.56	The rewrite sequence
569.82/291.56	
569.82/291.56	prefix(Cons(x', xs'), Cons(x, xs)) ->^+ and(!EQ(x', x), prefix(xs', xs))
569.82/291.56	
569.82/291.56	gives rise to a decreasing loop by considering the right hand sides subterm at position [1].
569.82/291.56	
569.82/291.56	The pumping substitution is [xs' / Cons(x', xs'), xs / Cons(x, xs)].
569.82/291.56	
569.82/291.56	The result substitution is [ ].
569.82/291.56	
569.82/291.56	
569.82/291.56	
569.82/291.56	
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(28)
569.82/291.56	Complex Obligation (BEST)
569.82/291.56	
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(29)
569.82/291.56	Obligation:
569.82/291.56	Proved the lower bound n^1 for the following obligation:
569.82/291.56	
569.82/291.56	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2).
569.82/291.56	
569.82/291.56	
569.82/291.56	The TRS R consists of the following rules:
569.82/291.56	
569.82/291.56	   prefix(Cons(x', xs'), Cons(x, xs)) -> and(!EQ(x', x), prefix(xs', xs))
569.82/291.56	   domatch(Cons(x, xs), Nil, n) -> Nil
569.82/291.56	   domatch(Nil, Nil, n) -> Cons(n, Nil)
569.82/291.56	   prefix(Cons(x, xs), Nil) -> False
569.82/291.56	   prefix(Nil, cs) -> True
569.82/291.56	   domatch(patcs, Cons(x, xs), n) -> domatch[Ite](prefix(patcs, Cons(x, xs)), patcs, Cons(x, xs), n)
569.82/291.56	   eqNatList(Cons(x, xs), Cons(y, ys)) -> eqNatList[Ite](!EQ(x, y), y, ys, x, xs)
569.82/291.56	   eqNatList(Cons(x, xs), Nil) -> False
569.82/291.56	   eqNatList(Nil, Cons(y, ys)) -> False
569.82/291.56	   eqNatList(Nil, Nil) -> True
569.82/291.56	   notEmpty(Cons(x, xs)) -> True
569.82/291.56	   notEmpty(Nil) -> False
569.82/291.56	   strmatch(patstr, str) -> domatch(patstr, str, Nil)
569.82/291.56	
569.82/291.56	The (relative) TRS S consists of the following rules:
569.82/291.56	
569.82/291.56	   and(False, False) -> False
569.82/291.56	   and(True, False) -> False
569.82/291.56	   and(False, True) -> False
569.82/291.56	   and(True, True) -> True
569.82/291.56	   !EQ(S(x), S(y)) -> !EQ(x, y)
569.82/291.56	   !EQ(0, S(y)) -> False
569.82/291.56	   !EQ(S(x), 0) -> False
569.82/291.56	   !EQ(0, 0) -> True
569.82/291.56	   domatch[Ite](False, patcs, Cons(x, xs), n) -> domatch(patcs, xs, Cons(n, Cons(Nil, Nil)))
569.82/291.56	   domatch[Ite](True, patcs, Cons(x, xs), n) -> Cons(n, domatch(patcs, xs, Cons(n, Cons(Nil, Nil))))
569.82/291.56	   eqNatList[Ite](False, y, ys, x, xs) -> False
569.82/291.56	   eqNatList[Ite](True, y, ys, x, xs) -> eqNatList(xs, ys)
569.82/291.56	
569.82/291.56	Rewrite Strategy: INNERMOST
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(30) LowerBoundPropagationProof (FINISHED)
569.82/291.56	Propagated lower bound.
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(31)
569.82/291.56	BOUNDS(n^1, INF)
569.82/291.56	
569.82/291.56	----------------------------------------
569.82/291.56	
569.82/291.56	(32)
569.82/291.56	Obligation:
569.82/291.56	Analyzing the following TRS for decreasing loops:
569.82/291.56	
569.82/291.56	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2).
569.82/291.56	
569.82/291.56	
569.82/291.56	The TRS R consists of the following rules:
569.82/291.56	
569.82/291.56	   prefix(Cons(x', xs'), Cons(x, xs)) -> and(!EQ(x', x), prefix(xs', xs))
569.82/291.56	   domatch(Cons(x, xs), Nil, n) -> Nil
569.82/291.56	   domatch(Nil, Nil, n) -> Cons(n, Nil)
569.82/291.56	   prefix(Cons(x, xs), Nil) -> False
569.82/291.56	   prefix(Nil, cs) -> True
569.82/291.56	   domatch(patcs, Cons(x, xs), n) -> domatch[Ite](prefix(patcs, Cons(x, xs)), patcs, Cons(x, xs), n)
569.82/291.56	   eqNatList(Cons(x, xs), Cons(y, ys)) -> eqNatList[Ite](!EQ(x, y), y, ys, x, xs)
569.82/291.56	   eqNatList(Cons(x, xs), Nil) -> False
569.82/291.56	   eqNatList(Nil, Cons(y, ys)) -> False
569.82/291.56	   eqNatList(Nil, Nil) -> True
569.82/291.56	   notEmpty(Cons(x, xs)) -> True
569.82/291.56	   notEmpty(Nil) -> False
569.82/291.56	   strmatch(patstr, str) -> domatch(patstr, str, Nil)
569.82/291.56	
569.82/291.56	The (relative) TRS S consists of the following rules:
569.82/291.56	
569.82/291.56	   and(False, False) -> False
569.82/291.56	   and(True, False) -> False
569.82/291.56	   and(False, True) -> False
569.82/291.56	   and(True, True) -> True
569.82/291.56	   !EQ(S(x), S(y)) -> !EQ(x, y)
569.82/291.56	   !EQ(0, S(y)) -> False
569.82/291.56	   !EQ(S(x), 0) -> False
569.82/291.56	   !EQ(0, 0) -> True
569.82/291.56	   domatch[Ite](False, patcs, Cons(x, xs), n) -> domatch(patcs, xs, Cons(n, Cons(Nil, Nil)))
569.82/291.56	   domatch[Ite](True, patcs, Cons(x, xs), n) -> Cons(n, domatch(patcs, xs, Cons(n, Cons(Nil, Nil))))
569.82/291.56	   eqNatList[Ite](False, y, ys, x, xs) -> False
569.82/291.56	   eqNatList[Ite](True, y, ys, x, xs) -> eqNatList(xs, ys)
569.82/291.56	
569.82/291.56	Rewrite Strategy: INNERMOST
569.98/291.63	EOF