3.78/1.88	WORST_CASE(Omega(n^1), O(n^1))
3.78/1.89	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
3.78/1.89	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.78/1.89	
3.78/1.89	
3.78/1.89	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
3.78/1.89	
3.78/1.89	(0) CpxTRS
3.78/1.89	(1) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms]
3.78/1.89	(2) CpxTRS
3.78/1.89	    (3) CpxTrsMatchBoundsTAProof [FINISHED, 132 ms]
3.78/1.89	    (4) BOUNDS(1, n^1)
3.78/1.89	(5) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
3.78/1.89	(6) TRS for Loop Detection
3.78/1.89	    (7) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
3.78/1.89	    (8) BEST
3.78/1.89	        (9) proven lower bound
3.78/1.89	            (10) LowerBoundPropagationProof [FINISHED, 0 ms]
3.78/1.89	            (11) BOUNDS(n^1, INF)
3.78/1.89	        (12) TRS for Loop Detection
3.78/1.89	
3.78/1.89	
3.78/1.89	----------------------------------------
3.78/1.89	
3.78/1.89	(0)
3.78/1.89	Obligation:
3.78/1.89	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
3.78/1.89	
3.78/1.89	
3.78/1.89	The TRS R consists of the following rules:
3.78/1.89	
3.78/1.89	   @(Cons(x, xs), ys) -> Cons(x, @(xs, ys))
3.78/1.89	   @(Nil, ys) -> ys
3.78/1.89	   game(p1, Cons(x', xs'), Cons(Capture, xs)) -> game(Cons(x', p1), xs', xs)
3.78/1.89	   game(p1, p2, Cons(Swap, xs)) -> game(p2, p1, xs)
3.78/1.89	   equal(Capture, Capture) -> True
3.78/1.89	   equal(Capture, Swap) -> False
3.78/1.89	   equal(Swap, Capture) -> False
3.78/1.89	   equal(Swap, Swap) -> True
3.78/1.89	   game(p1, p2, Nil) -> @(p1, p2)
3.78/1.89	   goal(p1, p2, moves) -> game(p1, p2, moves)
3.78/1.89	
3.78/1.89	S is empty.
3.78/1.89	Rewrite Strategy: INNERMOST
3.78/1.89	----------------------------------------
3.78/1.89	
3.78/1.89	(1) RelTrsToTrsProof (UPPER BOUND(ID))
3.78/1.89	transformed relative TRS to TRS
3.78/1.89	----------------------------------------
3.78/1.89	
3.78/1.89	(2)
3.78/1.89	Obligation:
3.78/1.89	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
3.78/1.89	
3.78/1.89	
3.78/1.89	The TRS R consists of the following rules:
3.78/1.89	
3.78/1.89	   @(Cons(x, xs), ys) -> Cons(x, @(xs, ys))
3.78/1.89	   @(Nil, ys) -> ys
3.78/1.89	   game(p1, Cons(x', xs'), Cons(Capture, xs)) -> game(Cons(x', p1), xs', xs)
3.78/1.89	   game(p1, p2, Cons(Swap, xs)) -> game(p2, p1, xs)
3.78/1.89	   equal(Capture, Capture) -> True
3.78/1.89	   equal(Capture, Swap) -> False
3.78/1.89	   equal(Swap, Capture) -> False
3.78/1.89	   equal(Swap, Swap) -> True
3.78/1.89	   game(p1, p2, Nil) -> @(p1, p2)
3.78/1.89	   goal(p1, p2, moves) -> game(p1, p2, moves)
3.78/1.89	
3.78/1.89	S is empty.
3.78/1.89	Rewrite Strategy: INNERMOST
3.78/1.89	----------------------------------------
3.78/1.89	
3.78/1.89	(3) CpxTrsMatchBoundsTAProof (FINISHED)
3.78/1.89	A linear upper bound on the runtime complexity of the TRS R could be shown with a Match-Bound[TAB_LEFTLINEAR,TAB_NONLEFTLINEAR] (for contructor-based start-terms) of 2. 
3.78/1.89	
3.78/1.89	The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: 
3.78/1.89	final states : [1, 2, 3, 4]
3.78/1.89	transitions: 
3.78/1.89	Cons0(0, 0) -> 0
3.78/1.89	Nil0() -> 0
3.78/1.89	Capture0() -> 0
3.78/1.89	Swap0() -> 0
3.78/1.89	True0() -> 0
3.78/1.89	False0() -> 0
3.78/1.89	@0(0, 0) -> 1
3.78/1.89	game0(0, 0, 0) -> 2
3.78/1.89	equal0(0, 0) -> 3
3.78/1.89	goal0(0, 0, 0) -> 4
3.78/1.89	@1(0, 0) -> 5
3.78/1.89	Cons1(0, 5) -> 1
3.78/1.89	Cons1(0, 0) -> 6
3.78/1.89	game1(6, 0, 0) -> 2
3.78/1.89	game1(0, 0, 0) -> 2
3.78/1.89	True1() -> 3
3.78/1.89	False1() -> 3
3.78/1.89	@1(0, 0) -> 2
3.78/1.89	game1(0, 0, 0) -> 4
3.78/1.89	Cons1(0, 5) -> 2
3.78/1.89	Cons1(0, 5) -> 5
3.78/1.89	Cons1(0, 6) -> 6
3.78/1.89	game1(6, 0, 0) -> 4
3.78/1.89	game1(0, 6, 0) -> 2
3.78/1.89	@1(6, 0) -> 2
3.78/1.89	@1(0, 0) -> 4
3.78/1.89	Cons1(0, 5) -> 4
3.78/1.89	@2(0, 0) -> 7
3.78/1.89	Cons2(0, 7) -> 2
3.78/1.89	@2(6, 0) -> 7
3.78/1.89	game1(6, 6, 0) -> 2
3.78/1.89	game1(0, 6, 0) -> 4
3.78/1.89	@1(0, 6) -> 2
3.78/1.89	@1(6, 0) -> 4
3.78/1.89	@1(0, 6) -> 5
3.78/1.89	Cons2(0, 7) -> 4
3.78/1.89	game1(6, 6, 0) -> 4
3.78/1.89	@1(6, 6) -> 2
3.78/1.89	@1(0, 6) -> 4
3.78/1.89	Cons1(0, 5) -> 7
3.78/1.89	Cons2(0, 7) -> 7
3.78/1.89	@2(0, 6) -> 7
3.78/1.89	@2(6, 6) -> 7
3.78/1.89	@1(6, 6) -> 4
3.78/1.89	0 -> 1
3.78/1.89	0 -> 2
3.78/1.89	0 -> 5
3.78/1.89	0 -> 4
3.78/1.89	0 -> 7
3.78/1.89	6 -> 2
3.78/1.89	6 -> 4
3.78/1.89	6 -> 5
3.78/1.89	6 -> 7
3.78/1.89	
3.78/1.89	----------------------------------------
3.78/1.89	
3.78/1.89	(4)
3.78/1.89	BOUNDS(1, n^1)
3.78/1.89	
3.78/1.89	----------------------------------------
3.78/1.89	
3.78/1.89	(5) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
3.78/1.89	Transformed a relative TRS into a decreasing-loop problem.
3.78/1.89	----------------------------------------
3.78/1.89	
3.78/1.89	(6)
3.78/1.89	Obligation:
3.78/1.89	Analyzing the following TRS for decreasing loops:
3.78/1.89	
3.78/1.89	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
3.78/1.89	
3.78/1.89	
3.78/1.89	The TRS R consists of the following rules:
3.78/1.89	
3.78/1.89	   @(Cons(x, xs), ys) -> Cons(x, @(xs, ys))
3.78/1.89	   @(Nil, ys) -> ys
3.78/1.89	   game(p1, Cons(x', xs'), Cons(Capture, xs)) -> game(Cons(x', p1), xs', xs)
3.78/1.89	   game(p1, p2, Cons(Swap, xs)) -> game(p2, p1, xs)
3.78/1.89	   equal(Capture, Capture) -> True
3.78/1.89	   equal(Capture, Swap) -> False
3.78/1.89	   equal(Swap, Capture) -> False
3.78/1.89	   equal(Swap, Swap) -> True
3.78/1.89	   game(p1, p2, Nil) -> @(p1, p2)
3.78/1.89	   goal(p1, p2, moves) -> game(p1, p2, moves)
3.78/1.89	
3.78/1.89	S is empty.
3.78/1.89	Rewrite Strategy: INNERMOST
3.78/1.89	----------------------------------------
3.78/1.89	
3.78/1.89	(7) DecreasingLoopProof (LOWER BOUND(ID))
3.78/1.89	The following loop(s) give(s) rise to the lower bound Omega(n^1):
3.78/1.89	
3.78/1.89	The rewrite sequence
3.78/1.89	
3.78/1.89	game(p1, Cons(x', xs'), Cons(Capture, xs)) ->^+ game(Cons(x', p1), xs', xs)
3.78/1.89	
3.78/1.89	gives rise to a decreasing loop by considering the right hand sides subterm at position [].
3.78/1.89	
3.78/1.89	The pumping substitution is [xs' / Cons(x', xs'), xs / Cons(Capture, xs)].
3.78/1.89	
3.78/1.89	The result substitution is [p1 / Cons(x', p1)].
3.78/1.89	
3.78/1.89	
3.78/1.89	
3.78/1.89	
3.78/1.89	----------------------------------------
3.78/1.89	
3.78/1.89	(8)
3.78/1.89	Complex Obligation (BEST)
3.78/1.89	
3.78/1.89	----------------------------------------
3.78/1.89	
3.78/1.89	(9)
3.78/1.89	Obligation:
3.78/1.89	Proved the lower bound n^1 for the following obligation:
3.78/1.89	
3.78/1.89	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
3.78/1.89	
3.78/1.89	
3.78/1.89	The TRS R consists of the following rules:
3.78/1.89	
3.78/1.89	   @(Cons(x, xs), ys) -> Cons(x, @(xs, ys))
3.78/1.89	   @(Nil, ys) -> ys
3.78/1.89	   game(p1, Cons(x', xs'), Cons(Capture, xs)) -> game(Cons(x', p1), xs', xs)
3.78/1.89	   game(p1, p2, Cons(Swap, xs)) -> game(p2, p1, xs)
3.78/1.89	   equal(Capture, Capture) -> True
3.78/1.89	   equal(Capture, Swap) -> False
3.78/1.89	   equal(Swap, Capture) -> False
3.78/1.89	   equal(Swap, Swap) -> True
3.78/1.89	   game(p1, p2, Nil) -> @(p1, p2)
3.78/1.89	   goal(p1, p2, moves) -> game(p1, p2, moves)
3.78/1.89	
3.78/1.89	S is empty.
3.78/1.89	Rewrite Strategy: INNERMOST
3.78/1.89	----------------------------------------
3.78/1.89	
3.78/1.89	(10) LowerBoundPropagationProof (FINISHED)
3.78/1.89	Propagated lower bound.
3.78/1.89	----------------------------------------
3.78/1.89	
3.78/1.89	(11)
3.78/1.89	BOUNDS(n^1, INF)
3.78/1.89	
3.78/1.89	----------------------------------------
3.78/1.89	
3.78/1.89	(12)
3.78/1.89	Obligation:
3.78/1.89	Analyzing the following TRS for decreasing loops:
3.78/1.89	
3.78/1.89	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
3.78/1.89	
3.78/1.89	
3.78/1.89	The TRS R consists of the following rules:
3.78/1.89	
3.78/1.89	   @(Cons(x, xs), ys) -> Cons(x, @(xs, ys))
3.78/1.89	   @(Nil, ys) -> ys
3.78/1.89	   game(p1, Cons(x', xs'), Cons(Capture, xs)) -> game(Cons(x', p1), xs', xs)
3.78/1.89	   game(p1, p2, Cons(Swap, xs)) -> game(p2, p1, xs)
3.78/1.89	   equal(Capture, Capture) -> True
3.78/1.89	   equal(Capture, Swap) -> False
3.78/1.89	   equal(Swap, Capture) -> False
3.78/1.89	   equal(Swap, Swap) -> True
3.78/1.89	   game(p1, p2, Nil) -> @(p1, p2)
3.78/1.89	   goal(p1, p2, moves) -> game(p1, p2, moves)
3.78/1.89	
3.78/1.89	S is empty.
3.78/1.89	Rewrite Strategy: INNERMOST
3.88/1.94	EOF