17.34/5.32	WORST_CASE(Omega(n^1), O(n^1))
17.53/5.34	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
17.53/5.34	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
17.53/5.34	
17.53/5.34	
17.53/5.34	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
17.53/5.34	
17.53/5.34	(0) CpxTRS
17.53/5.34	(1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms]
17.53/5.34	(2) CpxTRS
17.53/5.34	    (3) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms]
17.53/5.34	    (4) CpxTRS
17.53/5.34	    (5) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
17.53/5.34	    (6) CpxWeightedTrs
17.53/5.34	    (7) CpxWeightedTrsRenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
17.53/5.34	    (8) CpxWeightedTrs
17.53/5.34	    (9) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
17.53/5.34	    (10) CpxTypedWeightedTrs
17.53/5.34	    (11) CompletionProof [UPPER BOUND(ID), 0 ms]
17.53/5.34	    (12) CpxTypedWeightedCompleteTrs
17.53/5.34	    (13) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
17.53/5.34	    (14) CpxTypedWeightedCompleteTrs
17.53/5.34	    (15) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
17.53/5.34	    (16) CpxRNTS
17.53/5.34	    (17) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms]
17.53/5.34	    (18) CpxRNTS
17.53/5.34	    (19) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms]
17.53/5.34	    (20) CpxRNTS
17.53/5.34	    (21) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
17.53/5.34	    (22) CpxRNTS
17.53/5.34	    (23) IntTrsBoundProof [UPPER BOUND(ID), 240 ms]
17.53/5.34	    (24) CpxRNTS
17.53/5.34	    (25) IntTrsBoundProof [UPPER BOUND(ID), 86 ms]
17.53/5.34	    (26) CpxRNTS
17.53/5.34	    (27) FinalProof [FINISHED, 0 ms]
17.53/5.34	    (28) BOUNDS(1, n^1)
17.53/5.34	(29) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
17.53/5.34	(30) TRS for Loop Detection
17.53/5.34	    (31) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
17.53/5.34	    (32) BEST
17.53/5.34	        (33) proven lower bound
17.53/5.34	            (34) LowerBoundPropagationProof [FINISHED, 0 ms]
17.53/5.34	            (35) BOUNDS(n^1, INF)
17.53/5.34	        (36) TRS for Loop Detection
17.53/5.34	
17.53/5.34	
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(0)
17.53/5.34	Obligation:
17.53/5.34	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
17.53/5.34	
17.53/5.34	
17.53/5.34	The TRS R consists of the following rules:
17.53/5.34	
17.53/5.34	   +(*(x, y), *(x, z)) -> *(x, +(y, z))
17.53/5.34	   +(+(x, y), z) -> +(x, +(y, z))
17.53/5.34	   +(*(x, y), +(*(x, z), u)) -> +(*(x, +(y, z)), u)
17.53/5.34	
17.53/5.34	S is empty.
17.53/5.34	Rewrite Strategy: FULL
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(1) NestedDefinedSymbolProof (UPPER BOUND(ID))
17.53/5.34	The TRS does not nest defined symbols.
17.53/5.34	Hence, the left-hand sides of the following rules are not basic-reachable and can be removed:
17.53/5.34	+(+(x, y), z) -> +(x, +(y, z))
17.53/5.34	+(*(x, y), +(*(x, z), u)) -> +(*(x, +(y, z)), u)
17.53/5.34	
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(2)
17.53/5.34	Obligation:
17.53/5.34	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
17.53/5.34	
17.53/5.34	
17.53/5.34	The TRS R consists of the following rules:
17.53/5.34	
17.53/5.34	   +(*(x, y), *(x, z)) -> *(x, +(y, z))
17.53/5.34	
17.53/5.34	S is empty.
17.53/5.34	Rewrite Strategy: FULL
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(3) RcToIrcProof (BOTH BOUNDS(ID, ID))
17.53/5.34	Converted rc-obligation to irc-obligation.
17.53/5.34	
17.53/5.34	As the TRS does not nest defined symbols, we have rc = irc.
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(4)
17.53/5.34	Obligation:
17.53/5.34	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
17.53/5.34	
17.53/5.34	
17.53/5.34	The TRS R consists of the following rules:
17.53/5.34	
17.53/5.34	   +(*(x, y), *(x, z)) -> *(x, +(y, z))
17.53/5.34	
17.53/5.34	S is empty.
17.53/5.34	Rewrite Strategy: INNERMOST
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(5) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
17.53/5.34	Transformed relative TRS to weighted TRS
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(6)
17.53/5.34	Obligation:
17.53/5.34	The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1).
17.53/5.34	
17.53/5.34	
17.53/5.34	The TRS R consists of the following rules:
17.53/5.34	
17.53/5.34	   +(*(x, y), *(x, z)) -> *(x, +(y, z)) [1]
17.53/5.34	
17.53/5.34	Rewrite Strategy: INNERMOST
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(7) CpxWeightedTrsRenamingProof (BOTH BOUNDS(ID, ID))
17.53/5.34	Renamed defined symbols to avoid conflicts with arithmetic symbols:
17.53/5.34	
17.53/5.34	+ => plus
17.53/5.34	
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(8)
17.53/5.34	Obligation:
17.53/5.34	The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1).
17.53/5.34	
17.53/5.34	
17.53/5.34	The TRS R consists of the following rules:
17.53/5.34	
17.53/5.34	   plus(*(x, y), *(x, z)) -> *(x, plus(y, z)) [1]
17.53/5.34	
17.53/5.34	Rewrite Strategy: INNERMOST
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(9) TypeInferenceProof (BOTH BOUNDS(ID, ID))
17.53/5.34	Infered types.
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(10)
17.53/5.34	Obligation:
17.53/5.34	Runtime Complexity Weighted TRS with Types.
17.53/5.34	The TRS R consists of the following rules:
17.53/5.34	
17.53/5.34	   plus(*(x, y), *(x, z)) -> *(x, plus(y, z)) [1]
17.53/5.34	
17.53/5.34	The TRS has the following type information:
17.53/5.34	plus :: * -> * -> *
17.53/5.34	* :: a -> * -> *
17.53/5.34	
17.53/5.34	Rewrite Strategy: INNERMOST
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(11) CompletionProof (UPPER BOUND(ID))
17.53/5.34	The transformation into a RNTS is sound, since:
17.53/5.34	
17.53/5.34	(a) The obligation is a constructor system where every type has a constant constructor,
17.53/5.34	
17.53/5.34	(b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols:
17.53/5.34	
17.53/5.34	   plus_2
17.53/5.34	
17.53/5.34	(c) The following functions are completely defined:
17.53/5.34	none
17.53/5.34	
17.53/5.34	Due to the following rules being added:
17.53/5.34	none
17.53/5.34	
17.53/5.34	And the following fresh constants:    const, const1
17.53/5.34	
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(12)
17.53/5.34	Obligation:
17.53/5.34	Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is:
17.53/5.34	
17.53/5.34	Runtime Complexity Weighted TRS with Types.
17.53/5.34	The TRS R consists of the following rules:
17.53/5.34	
17.53/5.34	   plus(*(x, y), *(x, z)) -> *(x, plus(y, z)) [1]
17.53/5.34	
17.53/5.34	The TRS has the following type information:
17.53/5.34	plus :: * -> * -> *
17.53/5.34	* :: a -> * -> *
17.53/5.34	const :: *
17.53/5.34	const1 :: a
17.53/5.34	
17.53/5.34	Rewrite Strategy: INNERMOST
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(13) NarrowingProof (BOTH BOUNDS(ID, ID))
17.53/5.34	Narrowed the inner basic terms of all right-hand sides by a single narrowing step.
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(14)
17.53/5.34	Obligation:
17.53/5.34	Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is:
17.53/5.34	
17.53/5.34	Runtime Complexity Weighted TRS with Types.
17.53/5.34	The TRS R consists of the following rules:
17.53/5.34	
17.53/5.34	   plus(*(x, y), *(x, z)) -> *(x, plus(y, z)) [1]
17.53/5.34	
17.53/5.34	The TRS has the following type information:
17.53/5.34	plus :: * -> * -> *
17.53/5.34	* :: a -> * -> *
17.53/5.34	const :: *
17.53/5.34	const1 :: a
17.53/5.34	
17.53/5.34	Rewrite Strategy: INNERMOST
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(15) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID))
17.53/5.34	Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction.
17.53/5.34	The constant constructors are abstracted as follows:
17.53/5.34	
17.53/5.34	   const => 0
17.53/5.34	   const1 => 0
17.53/5.34	
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(16)
17.53/5.34	Obligation:
17.53/5.34	Complexity RNTS consisting of the following rules:
17.53/5.34	
17.53/5.34	   plus(z', z'') -{ 1 }-> 1 + x + plus(y, z) :|: z >= 0, z' = 1 + x + y, z'' = 1 + x + z, x >= 0, y >= 0
17.53/5.34	
17.53/5.34	
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(17) SimplificationProof (BOTH BOUNDS(ID, ID))
17.53/5.34	Simplified the RNTS by moving equalities from the constraints into the right-hand sides.
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(18)
17.53/5.34	Obligation:
17.53/5.34	Complexity RNTS consisting of the following rules:
17.53/5.34	
17.53/5.34	   plus(z', z'') -{ 1 }-> 1 + x + plus(y, z) :|: z >= 0, z' = 1 + x + y, z'' = 1 + x + z, x >= 0, y >= 0
17.53/5.34	
17.53/5.34	
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(19) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID))
17.53/5.34	Found the following analysis order by SCC decomposition:
17.53/5.34	
17.53/5.34	   { plus }
17.53/5.34	
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(20)
17.53/5.34	Obligation:
17.53/5.34	Complexity RNTS consisting of the following rules:
17.53/5.34	
17.53/5.34	   plus(z', z'') -{ 1 }-> 1 + x + plus(y, z) :|: z >= 0, z' = 1 + x + y, z'' = 1 + x + z, x >= 0, y >= 0
17.53/5.34	
17.53/5.34	Function symbols to be analyzed: {plus}
17.53/5.34	
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(21) ResultPropagationProof (UPPER BOUND(ID))
17.53/5.34	Applied inner abstraction using the recently inferred runtime/size bounds where possible.
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(22)
17.53/5.34	Obligation:
17.53/5.34	Complexity RNTS consisting of the following rules:
17.53/5.34	
17.53/5.34	   plus(z', z'') -{ 1 }-> 1 + x + plus(y, z) :|: z >= 0, z' = 1 + x + y, z'' = 1 + x + z, x >= 0, y >= 0
17.53/5.34	
17.53/5.34	Function symbols to be analyzed: {plus}
17.53/5.34	
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(23) IntTrsBoundProof (UPPER BOUND(ID))
17.53/5.34	
17.53/5.34	Computed SIZE bound using CoFloCo for: plus
17.53/5.34	after applying outer abstraction to obtain an ITS,
17.53/5.34	resulting in: O(1) with polynomial bound: 0
17.53/5.34	
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(24)
17.53/5.34	Obligation:
17.53/5.34	Complexity RNTS consisting of the following rules:
17.53/5.34	
17.53/5.34	   plus(z', z'') -{ 1 }-> 1 + x + plus(y, z) :|: z >= 0, z' = 1 + x + y, z'' = 1 + x + z, x >= 0, y >= 0
17.53/5.34	
17.53/5.34	Function symbols to be analyzed: {plus}
17.53/5.34	Previous analysis results are:
17.53/5.34	  plus: runtime: ?, size: O(1) [0]
17.53/5.34	
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(25) IntTrsBoundProof (UPPER BOUND(ID))
17.53/5.34	
17.53/5.34	Computed RUNTIME bound using CoFloCo for: plus
17.53/5.34	after applying outer abstraction to obtain an ITS,
17.53/5.34	resulting in: O(n^1) with polynomial bound: z''
17.53/5.34	
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(26)
17.53/5.34	Obligation:
17.53/5.34	Complexity RNTS consisting of the following rules:
17.53/5.34	
17.53/5.34	   plus(z', z'') -{ 1 }-> 1 + x + plus(y, z) :|: z >= 0, z' = 1 + x + y, z'' = 1 + x + z, x >= 0, y >= 0
17.53/5.34	
17.53/5.34	Function symbols to be analyzed: 
17.53/5.34	Previous analysis results are:
17.53/5.34	  plus: runtime: O(n^1) [z''], size: O(1) [0]
17.53/5.34	
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(27) FinalProof (FINISHED)
17.53/5.34	Computed overall runtime complexity
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(28)
17.53/5.34	BOUNDS(1, n^1)
17.53/5.34	
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(29) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
17.53/5.34	Transformed a relative TRS into a decreasing-loop problem.
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(30)
17.53/5.34	Obligation:
17.53/5.34	Analyzing the following TRS for decreasing loops:
17.53/5.34	
17.53/5.34	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
17.53/5.34	
17.53/5.34	
17.53/5.34	The TRS R consists of the following rules:
17.53/5.34	
17.53/5.34	   +(*(x, y), *(x, z)) -> *(x, +(y, z))
17.53/5.34	   +(+(x, y), z) -> +(x, +(y, z))
17.53/5.34	   +(*(x, y), +(*(x, z), u)) -> +(*(x, +(y, z)), u)
17.53/5.34	
17.53/5.34	S is empty.
17.53/5.34	Rewrite Strategy: FULL
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(31) DecreasingLoopProof (LOWER BOUND(ID))
17.53/5.34	The following loop(s) give(s) rise to the lower bound Omega(n^1):
17.53/5.34	
17.53/5.34	The rewrite sequence
17.53/5.34	
17.53/5.34	+(*(x1_0, y), *(x1_0, z)) ->^+ *(x1_0, +(y, z))
17.53/5.34	
17.53/5.34	gives rise to a decreasing loop by considering the right hand sides subterm at position [1].
17.53/5.34	
17.53/5.34	The pumping substitution is [y / *(x1_0, y), z / *(x1_0, z)].
17.53/5.34	
17.53/5.34	The result substitution is [ ].
17.53/5.34	
17.53/5.34	
17.53/5.34	
17.53/5.34	
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(32)
17.53/5.34	Complex Obligation (BEST)
17.53/5.34	
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(33)
17.53/5.34	Obligation:
17.53/5.34	Proved the lower bound n^1 for the following obligation:
17.53/5.34	
17.53/5.34	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
17.53/5.34	
17.53/5.34	
17.53/5.34	The TRS R consists of the following rules:
17.53/5.34	
17.53/5.34	   +(*(x, y), *(x, z)) -> *(x, +(y, z))
17.53/5.34	   +(+(x, y), z) -> +(x, +(y, z))
17.53/5.34	   +(*(x, y), +(*(x, z), u)) -> +(*(x, +(y, z)), u)
17.53/5.34	
17.53/5.34	S is empty.
17.53/5.34	Rewrite Strategy: FULL
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(34) LowerBoundPropagationProof (FINISHED)
17.53/5.34	Propagated lower bound.
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(35)
17.53/5.34	BOUNDS(n^1, INF)
17.53/5.34	
17.53/5.34	----------------------------------------
17.53/5.34	
17.53/5.34	(36)
17.53/5.34	Obligation:
17.53/5.34	Analyzing the following TRS for decreasing loops:
17.53/5.34	
17.53/5.34	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
17.53/5.34	
17.53/5.34	
17.53/5.34	The TRS R consists of the following rules:
17.53/5.34	
17.53/5.34	   +(*(x, y), *(x, z)) -> *(x, +(y, z))
17.53/5.34	   +(+(x, y), z) -> +(x, +(y, z))
17.53/5.34	   +(*(x, y), +(*(x, z), u)) -> +(*(x, +(y, z)), u)
17.53/5.34	
17.53/5.34	S is empty.
17.53/5.34	Rewrite Strategy: FULL
17.56/5.38	EOF