23.42/7.57	WORST_CASE(Omega(n^1), O(n^1))
23.42/7.58	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
23.42/7.58	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
23.42/7.58	
23.42/7.58	
23.42/7.58	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
23.42/7.58	
23.42/7.58	(0) CpxTRS
23.42/7.58	(1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms]
23.42/7.58	(2) CpxTRS
23.42/7.58	    (3) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms]
23.42/7.58	    (4) CpxTRS
23.42/7.58	    (5) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
23.42/7.58	    (6) CdtProblem
23.42/7.58	    (7) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
23.42/7.58	    (8) CdtProblem
23.42/7.58	    (9) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms]
23.42/7.58	    (10) CdtProblem
23.42/7.58	    (11) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
23.42/7.58	    (12) CdtProblem
23.42/7.58	    (13) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 75 ms]
23.42/7.58	    (14) CdtProblem
23.42/7.58	    (15) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
23.42/7.58	    (16) BOUNDS(1, 1)
23.42/7.58	(17) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
23.42/7.58	(18) TRS for Loop Detection
23.42/7.58	    (19) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
23.42/7.58	    (20) BEST
23.42/7.58	        (21) proven lower bound
23.42/7.58	            (22) LowerBoundPropagationProof [FINISHED, 0 ms]
23.42/7.58	            (23) BOUNDS(n^1, INF)
23.42/7.58	        (24) TRS for Loop Detection
23.42/7.58	
23.42/7.58	
23.42/7.58	----------------------------------------
23.42/7.58	
23.42/7.58	(0)
23.42/7.58	Obligation:
23.42/7.58	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
23.42/7.58	
23.42/7.58	
23.42/7.58	The TRS R consists of the following rules:
23.42/7.58	
23.42/7.58	   circ(cons(a, s), t) -> cons(msubst(a, t), circ(s, t))
23.42/7.58	   circ(cons(lift, s), cons(a, t)) -> cons(a, circ(s, t))
23.42/7.58	   circ(cons(lift, s), cons(lift, t)) -> cons(lift, circ(s, t))
23.42/7.58	   circ(circ(s, t), u) -> circ(s, circ(t, u))
23.42/7.58	   circ(s, id) -> s
23.42/7.58	   circ(id, s) -> s
23.42/7.58	   circ(cons(lift, s), circ(cons(lift, t), u)) -> circ(cons(lift, circ(s, t)), u)
23.42/7.58	   subst(a, id) -> a
23.42/7.58	   msubst(a, id) -> a
23.42/7.58	   msubst(msubst(a, s), t) -> msubst(a, circ(s, t))
23.42/7.58	
23.42/7.58	S is empty.
23.42/7.58	Rewrite Strategy: FULL
23.42/7.58	----------------------------------------
23.42/7.58	
23.42/7.58	(1) NestedDefinedSymbolProof (UPPER BOUND(ID))
23.42/7.58	The TRS does not nest defined symbols.
23.42/7.58	Hence, the left-hand sides of the following rules are not basic-reachable and can be removed:
23.42/7.58	circ(circ(s, t), u) -> circ(s, circ(t, u))
23.42/7.58	circ(cons(lift, s), circ(cons(lift, t), u)) -> circ(cons(lift, circ(s, t)), u)
23.42/7.58	msubst(msubst(a, s), t) -> msubst(a, circ(s, t))
23.42/7.58	
23.42/7.58	----------------------------------------
23.42/7.58	
23.42/7.58	(2)
23.42/7.58	Obligation:
23.42/7.58	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
23.42/7.58	
23.42/7.58	
23.42/7.58	The TRS R consists of the following rules:
23.42/7.58	
23.42/7.58	   circ(cons(a, s), t) -> cons(msubst(a, t), circ(s, t))
23.42/7.58	   circ(cons(lift, s), cons(a, t)) -> cons(a, circ(s, t))
23.42/7.58	   circ(cons(lift, s), cons(lift, t)) -> cons(lift, circ(s, t))
23.42/7.58	   circ(s, id) -> s
23.42/7.58	   circ(id, s) -> s
23.42/7.58	   subst(a, id) -> a
23.42/7.58	   msubst(a, id) -> a
23.42/7.58	
23.42/7.58	S is empty.
23.42/7.58	Rewrite Strategy: FULL
23.42/7.58	----------------------------------------
23.42/7.58	
23.42/7.58	(3) RcToIrcProof (BOTH BOUNDS(ID, ID))
23.42/7.58	Converted rc-obligation to irc-obligation.
23.42/7.58	
23.42/7.58	As the TRS does not nest defined symbols, we have rc = irc.
23.42/7.58	----------------------------------------
23.42/7.58	
23.42/7.58	(4)
23.42/7.58	Obligation:
23.42/7.58	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
23.42/7.58	
23.42/7.58	
23.42/7.58	The TRS R consists of the following rules:
23.42/7.58	
23.42/7.58	   circ(cons(a, s), t) -> cons(msubst(a, t), circ(s, t))
23.42/7.58	   circ(cons(lift, s), cons(a, t)) -> cons(a, circ(s, t))
23.42/7.58	   circ(cons(lift, s), cons(lift, t)) -> cons(lift, circ(s, t))
23.42/7.58	   circ(s, id) -> s
23.42/7.58	   circ(id, s) -> s
23.42/7.58	   subst(a, id) -> a
23.42/7.58	   msubst(a, id) -> a
23.42/7.58	
23.42/7.58	S is empty.
23.42/7.58	Rewrite Strategy: INNERMOST
23.42/7.58	----------------------------------------
23.42/7.58	
23.42/7.58	(5) CpxTrsToCdtProof (UPPER BOUND(ID))
23.42/7.58	Converted Cpx (relative) TRS to CDT
23.42/7.58	----------------------------------------
23.42/7.58	
23.42/7.58	(6)
23.42/7.58	Obligation:
23.42/7.58	Complexity Dependency Tuples Problem
23.42/7.58	
23.42/7.58	Rules:
23.42/7.58	   circ(cons(z0, z1), z2) -> cons(msubst(z0, z2), circ(z1, z2))
23.42/7.58	   circ(cons(lift, z0), cons(z1, z2)) -> cons(z1, circ(z0, z2))
23.42/7.58	   circ(cons(lift, z0), cons(lift, z1)) -> cons(lift, circ(z0, z1))
23.42/7.58	   circ(z0, id) -> z0
23.42/7.58	   circ(id, z0) -> z0
23.42/7.58	   subst(z0, id) -> z0
23.42/7.58	   msubst(z0, id) -> z0
23.42/7.58	Tuples:
23.42/7.58	   CIRC(cons(z0, z1), z2) -> c(MSUBST(z0, z2), CIRC(z1, z2))
23.42/7.58	   CIRC(cons(lift, z0), cons(z1, z2)) -> c1(CIRC(z0, z2))
23.42/7.58	   CIRC(cons(lift, z0), cons(lift, z1)) -> c2(CIRC(z0, z1))
23.42/7.58	   CIRC(z0, id) -> c3
23.42/7.58	   CIRC(id, z0) -> c4
23.42/7.58	   SUBST(z0, id) -> c5
23.42/7.58	   MSUBST(z0, id) -> c6
23.42/7.58	S tuples:
23.42/7.58	   CIRC(cons(z0, z1), z2) -> c(MSUBST(z0, z2), CIRC(z1, z2))
23.42/7.58	   CIRC(cons(lift, z0), cons(z1, z2)) -> c1(CIRC(z0, z2))
23.42/7.58	   CIRC(cons(lift, z0), cons(lift, z1)) -> c2(CIRC(z0, z1))
23.42/7.58	   CIRC(z0, id) -> c3
23.42/7.58	   CIRC(id, z0) -> c4
23.42/7.58	   SUBST(z0, id) -> c5
23.42/7.58	   MSUBST(z0, id) -> c6
23.42/7.58	K tuples:none
23.42/7.58	Defined Rule Symbols:   circ_2, subst_2, msubst_2
23.42/7.58	
23.42/7.58	Defined Pair Symbols:   CIRC_2, SUBST_2, MSUBST_2
23.42/7.58	
23.42/7.58	Compound Symbols:   c_2, c1_1, c2_1, c3, c4, c5, c6
23.42/7.58	
23.42/7.58	
23.42/7.58	----------------------------------------
23.42/7.58	
23.42/7.58	(7) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID))
23.42/7.58	Removed 4 trailing nodes:
23.42/7.58	   CIRC(id, z0) -> c4
23.42/7.58	   CIRC(z0, id) -> c3
23.42/7.58	   SUBST(z0, id) -> c5
23.42/7.58	   MSUBST(z0, id) -> c6
23.42/7.58	
23.42/7.58	----------------------------------------
23.42/7.58	
23.42/7.58	(8)
23.42/7.58	Obligation:
23.42/7.58	Complexity Dependency Tuples Problem
23.42/7.58	
23.42/7.58	Rules:
23.42/7.58	   circ(cons(z0, z1), z2) -> cons(msubst(z0, z2), circ(z1, z2))
23.42/7.58	   circ(cons(lift, z0), cons(z1, z2)) -> cons(z1, circ(z0, z2))
23.42/7.58	   circ(cons(lift, z0), cons(lift, z1)) -> cons(lift, circ(z0, z1))
23.42/7.58	   circ(z0, id) -> z0
23.42/7.58	   circ(id, z0) -> z0
23.42/7.58	   subst(z0, id) -> z0
23.42/7.58	   msubst(z0, id) -> z0
23.42/7.58	Tuples:
23.42/7.58	   CIRC(cons(z0, z1), z2) -> c(MSUBST(z0, z2), CIRC(z1, z2))
23.42/7.58	   CIRC(cons(lift, z0), cons(z1, z2)) -> c1(CIRC(z0, z2))
23.42/7.58	   CIRC(cons(lift, z0), cons(lift, z1)) -> c2(CIRC(z0, z1))
23.42/7.58	S tuples:
23.42/7.58	   CIRC(cons(z0, z1), z2) -> c(MSUBST(z0, z2), CIRC(z1, z2))
23.42/7.58	   CIRC(cons(lift, z0), cons(z1, z2)) -> c1(CIRC(z0, z2))
23.42/7.58	   CIRC(cons(lift, z0), cons(lift, z1)) -> c2(CIRC(z0, z1))
23.42/7.58	K tuples:none
23.42/7.58	Defined Rule Symbols:   circ_2, subst_2, msubst_2
23.42/7.58	
23.42/7.58	Defined Pair Symbols:   CIRC_2
23.42/7.58	
23.42/7.58	Compound Symbols:   c_2, c1_1, c2_1
23.42/7.58	
23.42/7.58	
23.42/7.58	----------------------------------------
23.42/7.58	
23.42/7.58	(9) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID))
23.42/7.58	Removed 1 trailing tuple parts
23.42/7.58	----------------------------------------
23.42/7.58	
23.42/7.58	(10)
23.42/7.58	Obligation:
23.42/7.58	Complexity Dependency Tuples Problem
23.42/7.58	
23.42/7.58	Rules:
23.42/7.58	   circ(cons(z0, z1), z2) -> cons(msubst(z0, z2), circ(z1, z2))
23.42/7.58	   circ(cons(lift, z0), cons(z1, z2)) -> cons(z1, circ(z0, z2))
23.42/7.58	   circ(cons(lift, z0), cons(lift, z1)) -> cons(lift, circ(z0, z1))
23.42/7.58	   circ(z0, id) -> z0
23.42/7.58	   circ(id, z0) -> z0
23.42/7.58	   subst(z0, id) -> z0
23.42/7.58	   msubst(z0, id) -> z0
23.42/7.58	Tuples:
23.42/7.58	   CIRC(cons(lift, z0), cons(z1, z2)) -> c1(CIRC(z0, z2))
23.42/7.58	   CIRC(cons(lift, z0), cons(lift, z1)) -> c2(CIRC(z0, z1))
23.42/7.58	   CIRC(cons(z0, z1), z2) -> c(CIRC(z1, z2))
23.42/7.58	S tuples:
23.42/7.58	   CIRC(cons(lift, z0), cons(z1, z2)) -> c1(CIRC(z0, z2))
23.42/7.58	   CIRC(cons(lift, z0), cons(lift, z1)) -> c2(CIRC(z0, z1))
23.42/7.58	   CIRC(cons(z0, z1), z2) -> c(CIRC(z1, z2))
23.42/7.58	K tuples:none
23.42/7.58	Defined Rule Symbols:   circ_2, subst_2, msubst_2
23.42/7.58	
23.42/7.58	Defined Pair Symbols:   CIRC_2
23.42/7.58	
23.42/7.58	Compound Symbols:   c1_1, c2_1, c_1
23.42/7.58	
23.42/7.58	
23.42/7.58	----------------------------------------
23.42/7.58	
23.42/7.58	(11) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
23.42/7.58	The following rules are not usable and were removed:
23.42/7.58	   circ(cons(z0, z1), z2) -> cons(msubst(z0, z2), circ(z1, z2))
23.42/7.58	   circ(cons(lift, z0), cons(z1, z2)) -> cons(z1, circ(z0, z2))
23.42/7.58	   circ(cons(lift, z0), cons(lift, z1)) -> cons(lift, circ(z0, z1))
23.42/7.58	   circ(z0, id) -> z0
23.42/7.58	   circ(id, z0) -> z0
23.42/7.58	   subst(z0, id) -> z0
23.42/7.58	   msubst(z0, id) -> z0
23.42/7.58	
23.42/7.58	----------------------------------------
23.42/7.58	
23.42/7.58	(12)
23.42/7.58	Obligation:
23.42/7.58	Complexity Dependency Tuples Problem
23.42/7.58	
23.42/7.58	Rules:none
23.42/7.58	Tuples:
23.42/7.58	   CIRC(cons(lift, z0), cons(z1, z2)) -> c1(CIRC(z0, z2))
23.42/7.58	   CIRC(cons(lift, z0), cons(lift, z1)) -> c2(CIRC(z0, z1))
23.42/7.58	   CIRC(cons(z0, z1), z2) -> c(CIRC(z1, z2))
23.42/7.58	S tuples:
23.42/7.58	   CIRC(cons(lift, z0), cons(z1, z2)) -> c1(CIRC(z0, z2))
23.42/7.58	   CIRC(cons(lift, z0), cons(lift, z1)) -> c2(CIRC(z0, z1))
23.42/7.58	   CIRC(cons(z0, z1), z2) -> c(CIRC(z1, z2))
23.42/7.58	K tuples:none
23.42/7.58	Defined Rule Symbols:none
23.42/7.58	
23.42/7.58	Defined Pair Symbols:   CIRC_2
23.42/7.58	
23.42/7.58	Compound Symbols:   c1_1, c2_1, c_1
23.42/7.58	
23.42/7.58	
23.42/7.58	----------------------------------------
23.42/7.58	
23.42/7.58	(13) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
23.42/7.58	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
23.42/7.58	   CIRC(cons(lift, z0), cons(z1, z2)) -> c1(CIRC(z0, z2))
23.42/7.58	   CIRC(cons(lift, z0), cons(lift, z1)) -> c2(CIRC(z0, z1))
23.42/7.58	   CIRC(cons(z0, z1), z2) -> c(CIRC(z1, z2))
23.42/7.58	We considered the (Usable) Rules:none
23.42/7.58	And the Tuples:
23.42/7.58	   CIRC(cons(lift, z0), cons(z1, z2)) -> c1(CIRC(z0, z2))
23.42/7.58	   CIRC(cons(lift, z0), cons(lift, z1)) -> c2(CIRC(z0, z1))
23.42/7.58	   CIRC(cons(z0, z1), z2) -> c(CIRC(z1, z2))
23.42/7.58	The order we found is given by the following interpretation:
23.42/7.58	
23.42/7.58	Polynomial interpretation :
23.42/7.58	
23.42/7.58	   POL(CIRC(x_1, x_2)) = x_1 + x_2
23.42/7.58	   POL(c(x_1)) = x_1
23.42/7.58	   POL(c1(x_1)) = x_1
23.42/7.58	   POL(c2(x_1)) = x_1
23.42/7.58	   POL(cons(x_1, x_2)) = [1] + x_1 + x_2
23.42/7.58	   POL(lift) = [1]
23.42/7.58	
23.42/7.58	----------------------------------------
23.42/7.58	
23.42/7.58	(14)
23.42/7.58	Obligation:
23.42/7.58	Complexity Dependency Tuples Problem
23.42/7.58	
23.42/7.58	Rules:none
23.42/7.58	Tuples:
23.42/7.58	   CIRC(cons(lift, z0), cons(z1, z2)) -> c1(CIRC(z0, z2))
23.42/7.58	   CIRC(cons(lift, z0), cons(lift, z1)) -> c2(CIRC(z0, z1))
23.42/7.58	   CIRC(cons(z0, z1), z2) -> c(CIRC(z1, z2))
23.42/7.58	S tuples:none
23.42/7.58	K tuples:
23.42/7.58	   CIRC(cons(lift, z0), cons(z1, z2)) -> c1(CIRC(z0, z2))
23.42/7.58	   CIRC(cons(lift, z0), cons(lift, z1)) -> c2(CIRC(z0, z1))
23.42/7.58	   CIRC(cons(z0, z1), z2) -> c(CIRC(z1, z2))
23.42/7.58	Defined Rule Symbols:none
23.42/7.58	
23.42/7.58	Defined Pair Symbols:   CIRC_2
23.42/7.58	
23.42/7.58	Compound Symbols:   c1_1, c2_1, c_1
23.42/7.58	
23.42/7.58	
23.42/7.58	----------------------------------------
23.42/7.58	
23.42/7.58	(15) SIsEmptyProof (BOTH BOUNDS(ID, ID))
23.42/7.58	The set S is empty
23.42/7.58	----------------------------------------
23.42/7.58	
23.42/7.58	(16)
23.42/7.58	BOUNDS(1, 1)
23.42/7.58	
23.42/7.58	----------------------------------------
23.42/7.58	
23.42/7.58	(17) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
23.42/7.58	Transformed a relative TRS into a decreasing-loop problem.
23.42/7.58	----------------------------------------
23.42/7.58	
23.42/7.58	(18)
23.42/7.58	Obligation:
23.42/7.58	Analyzing the following TRS for decreasing loops:
23.42/7.58	
23.42/7.58	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
23.42/7.58	
23.42/7.58	
23.42/7.58	The TRS R consists of the following rules:
23.42/7.58	
23.42/7.58	   circ(cons(a, s), t) -> cons(msubst(a, t), circ(s, t))
23.42/7.58	   circ(cons(lift, s), cons(a, t)) -> cons(a, circ(s, t))
23.42/7.58	   circ(cons(lift, s), cons(lift, t)) -> cons(lift, circ(s, t))
23.42/7.58	   circ(circ(s, t), u) -> circ(s, circ(t, u))
23.42/7.58	   circ(s, id) -> s
23.42/7.58	   circ(id, s) -> s
23.42/7.58	   circ(cons(lift, s), circ(cons(lift, t), u)) -> circ(cons(lift, circ(s, t)), u)
23.42/7.58	   subst(a, id) -> a
23.42/7.58	   msubst(a, id) -> a
23.42/7.58	   msubst(msubst(a, s), t) -> msubst(a, circ(s, t))
23.42/7.58	
23.42/7.58	S is empty.
23.42/7.58	Rewrite Strategy: FULL
23.42/7.58	----------------------------------------
23.42/7.58	
23.42/7.58	(19) DecreasingLoopProof (LOWER BOUND(ID))
23.42/7.58	The following loop(s) give(s) rise to the lower bound Omega(n^1):
23.42/7.58	
23.42/7.58	The rewrite sequence
23.42/7.58	
23.42/7.58	circ(cons(lift, s), cons(lift, t)) ->^+ cons(lift, circ(s, t))
23.42/7.58	
23.42/7.58	gives rise to a decreasing loop by considering the right hand sides subterm at position [1].
23.42/7.58	
23.42/7.58	The pumping substitution is [s / cons(lift, s), t / cons(lift, t)].
23.42/7.58	
23.42/7.58	The result substitution is [ ].
23.42/7.58	
23.42/7.58	
23.42/7.58	
23.42/7.58	
23.42/7.58	----------------------------------------
23.42/7.58	
23.42/7.58	(20)
23.42/7.58	Complex Obligation (BEST)
23.42/7.58	
23.42/7.58	----------------------------------------
23.42/7.58	
23.42/7.58	(21)
23.42/7.58	Obligation:
23.42/7.58	Proved the lower bound n^1 for the following obligation:
23.42/7.58	
23.42/7.58	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
23.42/7.58	
23.42/7.58	
23.42/7.58	The TRS R consists of the following rules:
23.42/7.58	
23.42/7.58	   circ(cons(a, s), t) -> cons(msubst(a, t), circ(s, t))
23.42/7.58	   circ(cons(lift, s), cons(a, t)) -> cons(a, circ(s, t))
23.42/7.58	   circ(cons(lift, s), cons(lift, t)) -> cons(lift, circ(s, t))
23.42/7.58	   circ(circ(s, t), u) -> circ(s, circ(t, u))
23.42/7.58	   circ(s, id) -> s
23.42/7.58	   circ(id, s) -> s
23.42/7.58	   circ(cons(lift, s), circ(cons(lift, t), u)) -> circ(cons(lift, circ(s, t)), u)
23.42/7.58	   subst(a, id) -> a
23.42/7.58	   msubst(a, id) -> a
23.42/7.58	   msubst(msubst(a, s), t) -> msubst(a, circ(s, t))
23.42/7.58	
23.42/7.58	S is empty.
23.42/7.58	Rewrite Strategy: FULL
23.42/7.58	----------------------------------------
23.42/7.58	
23.42/7.58	(22) LowerBoundPropagationProof (FINISHED)
23.42/7.58	Propagated lower bound.
23.42/7.58	----------------------------------------
23.42/7.58	
23.42/7.58	(23)
23.42/7.58	BOUNDS(n^1, INF)
23.42/7.58	
23.42/7.58	----------------------------------------
23.42/7.58	
23.42/7.58	(24)
23.42/7.58	Obligation:
23.42/7.58	Analyzing the following TRS for decreasing loops:
23.42/7.58	
23.42/7.58	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
23.42/7.58	
23.42/7.58	
23.42/7.58	The TRS R consists of the following rules:
23.42/7.58	
23.42/7.58	   circ(cons(a, s), t) -> cons(msubst(a, t), circ(s, t))
23.42/7.58	   circ(cons(lift, s), cons(a, t)) -> cons(a, circ(s, t))
23.42/7.58	   circ(cons(lift, s), cons(lift, t)) -> cons(lift, circ(s, t))
23.42/7.58	   circ(circ(s, t), u) -> circ(s, circ(t, u))
23.42/7.58	   circ(s, id) -> s
23.42/7.58	   circ(id, s) -> s
23.42/7.58	   circ(cons(lift, s), circ(cons(lift, t), u)) -> circ(cons(lift, circ(s, t)), u)
23.42/7.58	   subst(a, id) -> a
23.42/7.58	   msubst(a, id) -> a
23.42/7.58	   msubst(msubst(a, s), t) -> msubst(a, circ(s, t))
23.42/7.58	
23.42/7.58	S is empty.
23.42/7.58	Rewrite Strategy: FULL
23.73/7.62	EOF