3.62/1.62	YES
3.92/1.64	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
3.92/1.64	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.92/1.64	
3.92/1.64	
3.92/1.64	Outermost Termination of the given OTRS could be proven:
3.92/1.64	
3.92/1.64	(0) OTRS
3.92/1.64	(1) Raffelsieper-Zantema-Transformation [SOUND, 0 ms]
3.92/1.64	(2) QTRS
3.92/1.64	(3) QTRSRRRProof [EQUIVALENT, 33 ms]
3.92/1.64	(4) QTRS
3.92/1.64	(5) AAECC Innermost [EQUIVALENT, 0 ms]
3.92/1.64	(6) QTRS
3.92/1.64	(7) DependencyPairsProof [EQUIVALENT, 0 ms]
3.92/1.64	(8) QDP
3.92/1.64	(9) DependencyGraphProof [EQUIVALENT, 0 ms]
3.92/1.64	(10) AND
3.92/1.64	    (11) QDP
3.92/1.64	        (12) UsableRulesProof [EQUIVALENT, 0 ms]
3.92/1.64	        (13) QDP
3.92/1.64	        (14) QReductionProof [EQUIVALENT, 0 ms]
3.92/1.64	        (15) QDP
3.92/1.64	        (16) QDPSizeChangeProof [EQUIVALENT, 0 ms]
3.92/1.64	        (17) YES
3.92/1.64	    (18) QDP
3.92/1.64	        (19) UsableRulesProof [EQUIVALENT, 0 ms]
3.92/1.64	        (20) QDP
3.92/1.64	        (21) QReductionProof [EQUIVALENT, 0 ms]
3.92/1.64	        (22) QDP
3.92/1.64	        (23) QDPSizeChangeProof [EQUIVALENT, 0 ms]
3.92/1.64	        (24) YES
3.92/1.64	    (25) QDP
3.92/1.64	        (26) UsableRulesProof [EQUIVALENT, 0 ms]
3.92/1.64	        (27) QDP
3.92/1.64	        (28) QReductionProof [EQUIVALENT, 0 ms]
3.92/1.64	        (29) QDP
3.92/1.64	        (30) RFCMatchBoundsDPProof [EQUIVALENT, 0 ms]
3.92/1.64	        (31) YES
3.92/1.64	
3.92/1.64	
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(0)
3.92/1.64	Obligation:
3.92/1.64	Term rewrite system R:
3.92/1.64	The TRS R consists of the following rules:
3.92/1.64	
3.92/1.64	   f(g(x)) -> x
3.92/1.64	   g(b) -> f(g(b))
3.92/1.64	
3.92/1.64	
3.92/1.64	
3.92/1.64	Outermost Strategy.
3.92/1.64	
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(1) Raffelsieper-Zantema-Transformation (SOUND)
3.92/1.64	We applied the Raffelsieper-Zantema transformation  to transform the outermost TRS to a standard TRS.
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(2)
3.92/1.64	Obligation:
3.92/1.64	Q restricted rewrite system:
3.92/1.64	The TRS R consists of the following rules:
3.92/1.64	
3.92/1.64	   down(f(g(x))) -> up(x)
3.92/1.64	   down(g(b)) -> up(f(g(b)))
3.92/1.64	   top(up(x)) -> top(down(x))
3.92/1.64	   down(f(f(y3))) -> f_flat(down(f(y3)))
3.92/1.64	   down(f(b)) -> f_flat(down(b))
3.92/1.64	   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
3.92/1.64	   down(g(f(y6))) -> g_flat(down(f(y6)))
3.92/1.64	   down(g(g(y7))) -> g_flat(down(g(y7)))
3.92/1.64	   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
3.92/1.64	   f_flat(up(x_1)) -> up(f(x_1))
3.92/1.64	   g_flat(up(x_1)) -> up(g(x_1))
3.92/1.64	
3.92/1.64	Q is empty.
3.92/1.64	
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(3) QTRSRRRProof (EQUIVALENT)
3.92/1.64	Used ordering:
3.92/1.64	Polynomial interpretation [POLO]:
3.92/1.64	
3.92/1.64	   POL(b) = 0
3.92/1.64	   POL(down(x_1)) = 2 + 2*x_1
3.92/1.64	   POL(f(x_1)) = x_1
3.92/1.64	   POL(f_flat(x_1)) = x_1
3.92/1.64	   POL(fresh_constant) = 1
3.92/1.64	   POL(g(x_1)) = 1 + 2*x_1
3.92/1.64	   POL(g_flat(x_1)) = 2*x_1
3.92/1.64	   POL(top(x_1)) = x_1
3.92/1.64	   POL(up(x_1)) = 2 + 2*x_1
3.92/1.64	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
3.92/1.64	
3.92/1.64	   down(f(g(x))) -> up(x)
3.92/1.64	
3.92/1.64	
3.92/1.64	
3.92/1.64	
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(4)
3.92/1.64	Obligation:
3.92/1.64	Q restricted rewrite system:
3.92/1.64	The TRS R consists of the following rules:
3.92/1.64	
3.92/1.64	   down(g(b)) -> up(f(g(b)))
3.92/1.64	   top(up(x)) -> top(down(x))
3.92/1.64	   down(f(f(y3))) -> f_flat(down(f(y3)))
3.92/1.64	   down(f(b)) -> f_flat(down(b))
3.92/1.64	   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
3.92/1.64	   down(g(f(y6))) -> g_flat(down(f(y6)))
3.92/1.64	   down(g(g(y7))) -> g_flat(down(g(y7)))
3.92/1.64	   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
3.92/1.64	   f_flat(up(x_1)) -> up(f(x_1))
3.92/1.64	   g_flat(up(x_1)) -> up(g(x_1))
3.92/1.64	
3.92/1.64	Q is empty.
3.92/1.64	
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(5) AAECC Innermost (EQUIVALENT)
3.92/1.64	We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is 
3.92/1.64	   down(f(f(y3))) -> f_flat(down(f(y3)))
3.92/1.64	   down(f(b)) -> f_flat(down(b))
3.92/1.64	   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
3.92/1.64	   down(g(f(y6))) -> g_flat(down(f(y6)))
3.92/1.64	   down(g(g(y7))) -> g_flat(down(g(y7)))
3.92/1.64	   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
3.92/1.64	   f_flat(up(x_1)) -> up(f(x_1))
3.92/1.64	   g_flat(up(x_1)) -> up(g(x_1))
3.92/1.64	   down(g(b)) -> up(f(g(b)))
3.92/1.64	
3.92/1.64	The TRS R 2 is 
3.92/1.64	   top(up(x)) -> top(down(x))
3.92/1.64	
3.92/1.64	The signature Sigma is {top_1}
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(6)
3.92/1.64	Obligation:
3.92/1.64	Q restricted rewrite system:
3.92/1.64	The TRS R consists of the following rules:
3.92/1.64	
3.92/1.64	   down(g(b)) -> up(f(g(b)))
3.92/1.64	   top(up(x)) -> top(down(x))
3.92/1.64	   down(f(f(y3))) -> f_flat(down(f(y3)))
3.92/1.64	   down(f(b)) -> f_flat(down(b))
3.92/1.64	   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
3.92/1.64	   down(g(f(y6))) -> g_flat(down(f(y6)))
3.92/1.64	   down(g(g(y7))) -> g_flat(down(g(y7)))
3.92/1.64	   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
3.92/1.64	   f_flat(up(x_1)) -> up(f(x_1))
3.92/1.64	   g_flat(up(x_1)) -> up(g(x_1))
3.92/1.64	
3.92/1.64	The set Q consists of the following terms:
3.92/1.64	
3.92/1.64	   down(g(b))
3.92/1.64	   top(up(x0))
3.92/1.64	   down(f(f(x0)))
3.92/1.64	   down(f(b))
3.92/1.64	   down(f(fresh_constant))
3.92/1.64	   down(g(f(x0)))
3.92/1.64	   down(g(g(x0)))
3.92/1.64	   down(g(fresh_constant))
3.92/1.64	   f_flat(up(x0))
3.92/1.64	   g_flat(up(x0))
3.92/1.64	
3.92/1.64	
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(7) DependencyPairsProof (EQUIVALENT)
3.92/1.64	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(8)
3.92/1.64	Obligation:
3.92/1.64	Q DP problem:
3.92/1.64	The TRS P consists of the following rules:
3.92/1.64	
3.92/1.64	   TOP(up(x)) -> TOP(down(x))
3.92/1.64	   TOP(up(x)) -> DOWN(x)
3.92/1.64	   DOWN(f(f(y3))) -> F_FLAT(down(f(y3)))
3.92/1.64	   DOWN(f(f(y3))) -> DOWN(f(y3))
3.92/1.64	   DOWN(f(b)) -> F_FLAT(down(b))
3.92/1.64	   DOWN(f(b)) -> DOWN(b)
3.92/1.64	   DOWN(f(fresh_constant)) -> F_FLAT(down(fresh_constant))
3.92/1.64	   DOWN(f(fresh_constant)) -> DOWN(fresh_constant)
3.92/1.64	   DOWN(g(f(y6))) -> G_FLAT(down(f(y6)))
3.92/1.64	   DOWN(g(f(y6))) -> DOWN(f(y6))
3.92/1.64	   DOWN(g(g(y7))) -> G_FLAT(down(g(y7)))
3.92/1.64	   DOWN(g(g(y7))) -> DOWN(g(y7))
3.92/1.64	   DOWN(g(fresh_constant)) -> G_FLAT(down(fresh_constant))
3.92/1.64	   DOWN(g(fresh_constant)) -> DOWN(fresh_constant)
3.92/1.64	
3.92/1.64	The TRS R consists of the following rules:
3.92/1.64	
3.92/1.64	   down(g(b)) -> up(f(g(b)))
3.92/1.64	   top(up(x)) -> top(down(x))
3.92/1.64	   down(f(f(y3))) -> f_flat(down(f(y3)))
3.92/1.64	   down(f(b)) -> f_flat(down(b))
3.92/1.64	   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
3.92/1.64	   down(g(f(y6))) -> g_flat(down(f(y6)))
3.92/1.64	   down(g(g(y7))) -> g_flat(down(g(y7)))
3.92/1.64	   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
3.92/1.64	   f_flat(up(x_1)) -> up(f(x_1))
3.92/1.64	   g_flat(up(x_1)) -> up(g(x_1))
3.92/1.64	
3.92/1.64	The set Q consists of the following terms:
3.92/1.64	
3.92/1.64	   down(g(b))
3.92/1.64	   top(up(x0))
3.92/1.64	   down(f(f(x0)))
3.92/1.64	   down(f(b))
3.92/1.64	   down(f(fresh_constant))
3.92/1.64	   down(g(f(x0)))
3.92/1.64	   down(g(g(x0)))
3.92/1.64	   down(g(fresh_constant))
3.92/1.64	   f_flat(up(x0))
3.92/1.64	   g_flat(up(x0))
3.92/1.64	
3.92/1.64	We have to consider all minimal (P,Q,R)-chains.
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(9) DependencyGraphProof (EQUIVALENT)
3.92/1.64	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 11 less nodes.
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(10)
3.92/1.64	Complex Obligation (AND)
3.92/1.64	
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(11)
3.92/1.64	Obligation:
3.92/1.64	Q DP problem:
3.92/1.64	The TRS P consists of the following rules:
3.92/1.64	
3.92/1.64	   DOWN(f(f(y3))) -> DOWN(f(y3))
3.92/1.64	
3.92/1.64	The TRS R consists of the following rules:
3.92/1.64	
3.92/1.64	   down(g(b)) -> up(f(g(b)))
3.92/1.64	   top(up(x)) -> top(down(x))
3.92/1.64	   down(f(f(y3))) -> f_flat(down(f(y3)))
3.92/1.64	   down(f(b)) -> f_flat(down(b))
3.92/1.64	   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
3.92/1.64	   down(g(f(y6))) -> g_flat(down(f(y6)))
3.92/1.64	   down(g(g(y7))) -> g_flat(down(g(y7)))
3.92/1.64	   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
3.92/1.64	   f_flat(up(x_1)) -> up(f(x_1))
3.92/1.64	   g_flat(up(x_1)) -> up(g(x_1))
3.92/1.64	
3.92/1.64	The set Q consists of the following terms:
3.92/1.64	
3.92/1.64	   down(g(b))
3.92/1.64	   top(up(x0))
3.92/1.64	   down(f(f(x0)))
3.92/1.64	   down(f(b))
3.92/1.64	   down(f(fresh_constant))
3.92/1.64	   down(g(f(x0)))
3.92/1.64	   down(g(g(x0)))
3.92/1.64	   down(g(fresh_constant))
3.92/1.64	   f_flat(up(x0))
3.92/1.64	   g_flat(up(x0))
3.92/1.64	
3.92/1.64	We have to consider all minimal (P,Q,R)-chains.
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(12) UsableRulesProof (EQUIVALENT)
3.92/1.64	As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(13)
3.92/1.64	Obligation:
3.92/1.64	Q DP problem:
3.92/1.64	The TRS P consists of the following rules:
3.92/1.64	
3.92/1.64	   DOWN(f(f(y3))) -> DOWN(f(y3))
3.92/1.64	
3.92/1.64	R is empty.
3.92/1.64	The set Q consists of the following terms:
3.92/1.64	
3.92/1.64	   down(g(b))
3.92/1.64	   top(up(x0))
3.92/1.64	   down(f(f(x0)))
3.92/1.64	   down(f(b))
3.92/1.64	   down(f(fresh_constant))
3.92/1.64	   down(g(f(x0)))
3.92/1.64	   down(g(g(x0)))
3.92/1.64	   down(g(fresh_constant))
3.92/1.64	   f_flat(up(x0))
3.92/1.64	   g_flat(up(x0))
3.92/1.64	
3.92/1.64	We have to consider all minimal (P,Q,R)-chains.
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(14) QReductionProof (EQUIVALENT)
3.92/1.64	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
3.92/1.64	
3.92/1.64	   down(g(b))
3.92/1.64	   top(up(x0))
3.92/1.64	   down(f(f(x0)))
3.92/1.64	   down(f(b))
3.92/1.64	   down(f(fresh_constant))
3.92/1.64	   down(g(f(x0)))
3.92/1.64	   down(g(g(x0)))
3.92/1.64	   down(g(fresh_constant))
3.92/1.64	   f_flat(up(x0))
3.92/1.64	   g_flat(up(x0))
3.92/1.64	
3.92/1.64	
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(15)
3.92/1.64	Obligation:
3.92/1.64	Q DP problem:
3.92/1.64	The TRS P consists of the following rules:
3.92/1.64	
3.92/1.64	   DOWN(f(f(y3))) -> DOWN(f(y3))
3.92/1.64	
3.92/1.64	R is empty.
3.92/1.64	Q is empty.
3.92/1.64	We have to consider all minimal (P,Q,R)-chains.
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(16) QDPSizeChangeProof (EQUIVALENT)
3.92/1.64	By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 
3.92/1.64	
3.92/1.64	From the DPs we obtained the following set of size-change graphs:
3.92/1.64	*DOWN(f(f(y3))) -> DOWN(f(y3))
3.92/1.64	The graph contains the following edges 1 > 1
3.92/1.64	
3.92/1.64	
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(17)
3.92/1.64	YES
3.92/1.64	
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(18)
3.92/1.64	Obligation:
3.92/1.64	Q DP problem:
3.92/1.64	The TRS P consists of the following rules:
3.92/1.64	
3.92/1.64	   DOWN(g(g(y7))) -> DOWN(g(y7))
3.92/1.64	
3.92/1.64	The TRS R consists of the following rules:
3.92/1.64	
3.92/1.64	   down(g(b)) -> up(f(g(b)))
3.92/1.64	   top(up(x)) -> top(down(x))
3.92/1.64	   down(f(f(y3))) -> f_flat(down(f(y3)))
3.92/1.64	   down(f(b)) -> f_flat(down(b))
3.92/1.64	   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
3.92/1.64	   down(g(f(y6))) -> g_flat(down(f(y6)))
3.92/1.64	   down(g(g(y7))) -> g_flat(down(g(y7)))
3.92/1.64	   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
3.92/1.64	   f_flat(up(x_1)) -> up(f(x_1))
3.92/1.64	   g_flat(up(x_1)) -> up(g(x_1))
3.92/1.64	
3.92/1.64	The set Q consists of the following terms:
3.92/1.64	
3.92/1.64	   down(g(b))
3.92/1.64	   top(up(x0))
3.92/1.64	   down(f(f(x0)))
3.92/1.64	   down(f(b))
3.92/1.64	   down(f(fresh_constant))
3.92/1.64	   down(g(f(x0)))
3.92/1.64	   down(g(g(x0)))
3.92/1.64	   down(g(fresh_constant))
3.92/1.64	   f_flat(up(x0))
3.92/1.64	   g_flat(up(x0))
3.92/1.64	
3.92/1.64	We have to consider all minimal (P,Q,R)-chains.
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(19) UsableRulesProof (EQUIVALENT)
3.92/1.64	As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(20)
3.92/1.64	Obligation:
3.92/1.64	Q DP problem:
3.92/1.64	The TRS P consists of the following rules:
3.92/1.64	
3.92/1.64	   DOWN(g(g(y7))) -> DOWN(g(y7))
3.92/1.64	
3.92/1.64	R is empty.
3.92/1.64	The set Q consists of the following terms:
3.92/1.64	
3.92/1.64	   down(g(b))
3.92/1.64	   top(up(x0))
3.92/1.64	   down(f(f(x0)))
3.92/1.64	   down(f(b))
3.92/1.64	   down(f(fresh_constant))
3.92/1.64	   down(g(f(x0)))
3.92/1.64	   down(g(g(x0)))
3.92/1.64	   down(g(fresh_constant))
3.92/1.64	   f_flat(up(x0))
3.92/1.64	   g_flat(up(x0))
3.92/1.64	
3.92/1.64	We have to consider all minimal (P,Q,R)-chains.
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(21) QReductionProof (EQUIVALENT)
3.92/1.64	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
3.92/1.64	
3.92/1.64	   down(g(b))
3.92/1.64	   top(up(x0))
3.92/1.64	   down(f(f(x0)))
3.92/1.64	   down(f(b))
3.92/1.64	   down(f(fresh_constant))
3.92/1.64	   down(g(f(x0)))
3.92/1.64	   down(g(g(x0)))
3.92/1.64	   down(g(fresh_constant))
3.92/1.64	   f_flat(up(x0))
3.92/1.64	   g_flat(up(x0))
3.92/1.64	
3.92/1.64	
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(22)
3.92/1.64	Obligation:
3.92/1.64	Q DP problem:
3.92/1.64	The TRS P consists of the following rules:
3.92/1.64	
3.92/1.64	   DOWN(g(g(y7))) -> DOWN(g(y7))
3.92/1.64	
3.92/1.64	R is empty.
3.92/1.64	Q is empty.
3.92/1.64	We have to consider all minimal (P,Q,R)-chains.
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(23) QDPSizeChangeProof (EQUIVALENT)
3.92/1.64	By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 
3.92/1.64	
3.92/1.64	From the DPs we obtained the following set of size-change graphs:
3.92/1.64	*DOWN(g(g(y7))) -> DOWN(g(y7))
3.92/1.64	The graph contains the following edges 1 > 1
3.92/1.64	
3.92/1.64	
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(24)
3.92/1.64	YES
3.92/1.64	
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(25)
3.92/1.64	Obligation:
3.92/1.64	Q DP problem:
3.92/1.64	The TRS P consists of the following rules:
3.92/1.64	
3.92/1.64	   TOP(up(x)) -> TOP(down(x))
3.92/1.64	
3.92/1.64	The TRS R consists of the following rules:
3.92/1.64	
3.92/1.64	   down(g(b)) -> up(f(g(b)))
3.92/1.64	   top(up(x)) -> top(down(x))
3.92/1.64	   down(f(f(y3))) -> f_flat(down(f(y3)))
3.92/1.64	   down(f(b)) -> f_flat(down(b))
3.92/1.64	   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
3.92/1.64	   down(g(f(y6))) -> g_flat(down(f(y6)))
3.92/1.64	   down(g(g(y7))) -> g_flat(down(g(y7)))
3.92/1.64	   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
3.92/1.64	   f_flat(up(x_1)) -> up(f(x_1))
3.92/1.64	   g_flat(up(x_1)) -> up(g(x_1))
3.92/1.64	
3.92/1.64	The set Q consists of the following terms:
3.92/1.64	
3.92/1.64	   down(g(b))
3.92/1.64	   top(up(x0))
3.92/1.64	   down(f(f(x0)))
3.92/1.64	   down(f(b))
3.92/1.64	   down(f(fresh_constant))
3.92/1.64	   down(g(f(x0)))
3.92/1.64	   down(g(g(x0)))
3.92/1.64	   down(g(fresh_constant))
3.92/1.64	   f_flat(up(x0))
3.92/1.64	   g_flat(up(x0))
3.92/1.64	
3.92/1.64	We have to consider all minimal (P,Q,R)-chains.
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(26) UsableRulesProof (EQUIVALENT)
3.92/1.64	As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(27)
3.92/1.64	Obligation:
3.92/1.64	Q DP problem:
3.92/1.64	The TRS P consists of the following rules:
3.92/1.64	
3.92/1.64	   TOP(up(x)) -> TOP(down(x))
3.92/1.64	
3.92/1.64	The TRS R consists of the following rules:
3.92/1.64	
3.92/1.64	   down(g(b)) -> up(f(g(b)))
3.92/1.64	   down(f(f(y3))) -> f_flat(down(f(y3)))
3.92/1.64	   down(f(b)) -> f_flat(down(b))
3.92/1.64	   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
3.92/1.64	   down(g(f(y6))) -> g_flat(down(f(y6)))
3.92/1.64	   down(g(g(y7))) -> g_flat(down(g(y7)))
3.92/1.64	   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
3.92/1.64	   g_flat(up(x_1)) -> up(g(x_1))
3.92/1.64	   f_flat(up(x_1)) -> up(f(x_1))
3.92/1.64	
3.92/1.64	The set Q consists of the following terms:
3.92/1.64	
3.92/1.64	   down(g(b))
3.92/1.64	   top(up(x0))
3.92/1.64	   down(f(f(x0)))
3.92/1.64	   down(f(b))
3.92/1.64	   down(f(fresh_constant))
3.92/1.64	   down(g(f(x0)))
3.92/1.64	   down(g(g(x0)))
3.92/1.64	   down(g(fresh_constant))
3.92/1.64	   f_flat(up(x0))
3.92/1.64	   g_flat(up(x0))
3.92/1.64	
3.92/1.64	We have to consider all minimal (P,Q,R)-chains.
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(28) QReductionProof (EQUIVALENT)
3.92/1.64	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
3.92/1.64	
3.92/1.64	   top(up(x0))
3.92/1.64	
3.92/1.64	
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(29)
3.92/1.64	Obligation:
3.92/1.64	Q DP problem:
3.92/1.64	The TRS P consists of the following rules:
3.92/1.64	
3.92/1.64	   TOP(up(x)) -> TOP(down(x))
3.92/1.64	
3.92/1.64	The TRS R consists of the following rules:
3.92/1.64	
3.92/1.64	   down(g(b)) -> up(f(g(b)))
3.92/1.64	   down(f(f(y3))) -> f_flat(down(f(y3)))
3.92/1.64	   down(f(b)) -> f_flat(down(b))
3.92/1.64	   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
3.92/1.64	   down(g(f(y6))) -> g_flat(down(f(y6)))
3.92/1.64	   down(g(g(y7))) -> g_flat(down(g(y7)))
3.92/1.64	   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
3.92/1.64	   g_flat(up(x_1)) -> up(g(x_1))
3.92/1.64	   f_flat(up(x_1)) -> up(f(x_1))
3.92/1.64	
3.92/1.64	The set Q consists of the following terms:
3.92/1.64	
3.92/1.64	   down(g(b))
3.92/1.64	   down(f(f(x0)))
3.92/1.64	   down(f(b))
3.92/1.64	   down(f(fresh_constant))
3.92/1.64	   down(g(f(x0)))
3.92/1.64	   down(g(g(x0)))
3.92/1.64	   down(g(fresh_constant))
3.92/1.64	   f_flat(up(x0))
3.92/1.64	   g_flat(up(x0))
3.92/1.64	
3.92/1.64	We have to consider all minimal (P,Q,R)-chains.
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(30) RFCMatchBoundsDPProof (EQUIVALENT)
3.92/1.64	Finiteness of the DP problem can be shown by a matchbound of 3. 
3.92/1.64	As the DP problem is minimal we only have to initialize the certificate graph by the rules of P:
3.92/1.64	
3.92/1.64	   TOP(up(x)) -> TOP(down(x))
3.92/1.64	
3.92/1.64	To find matches we regarded all rules of R and P:
3.92/1.64	
3.92/1.64	   down(g(b)) -> up(f(g(b)))
3.92/1.64	   down(f(f(y3))) -> f_flat(down(f(y3)))
3.92/1.64	   down(f(b)) -> f_flat(down(b))
3.92/1.64	   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
3.92/1.64	   down(g(f(y6))) -> g_flat(down(f(y6)))
3.92/1.64	   down(g(g(y7))) -> g_flat(down(g(y7)))
3.92/1.64	   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
3.92/1.64	   g_flat(up(x_1)) -> up(g(x_1))
3.92/1.64	   f_flat(up(x_1)) -> up(f(x_1))
3.92/1.64	   TOP(up(x)) -> TOP(down(x))
3.92/1.64	
3.92/1.64	The certificate found is represented by the following graph.
3.92/1.64	The certificate consists of the following enumerated nodes:
3.92/1.64	400, 401, 402, 403, 404, 405, 406, 407, 409, 410, 411, 412, 414, 415
3.92/1.64	
3.92/1.64	Node 400 is start node and node 401 is final node.
3.92/1.64	
3.92/1.64	Those nodes are connected through the following edges:
3.92/1.64	
3.92/1.64	* 400 to 402 labelled TOP_1(0)* 400 to 409 labelled TOP_1(1)* 401 to 401 labelled #_1(0)* 402 to 401 labelled down_1(0)* 402 to 403 labelled up_1(1)* 402 to 406 labelled f_flat_1(1), g_flat_1(1)* 402 to 410 labelled up_1(2)* 403 to 404 labelled f_1(1)* 404 to 405 labelled g_1(1)* 405 to 401 labelled b(1)* 406 to 407 labelled down_1(1)* 406 to 406 labelled f_flat_1(1), g_flat_1(1)* 406 to 403 labelled up_1(1)* 406 to 410 labelled up_1(2)* 407 to 401 labelled f_1(1), b(1), fresh_constant(1), g_1(1)* 409 to 403 labelled down_1(1)* 409 to 410 labelled down_1(1)* 409 to 411 labelled f_flat_1(2), g_flat_1(2)* 410 to 403 labelled f_1(2), g_1(2)* 410 to 410 labelled f_1(2), g_1(2)* 411 to 412 labelled down_1(2)* 411 to 411 labelled f_flat_1(2), g_flat_1(2)* 411 to 414 labelled f_flat_1(3), g_flat_1(3)* 412 to 404 labelled f_1(2)* 412 to 403 labelled f_1(2), g_1(2)* 412 to 410 labelled f_1(2), g_1(2)* 414 to 415 labelled down_1(3)* 414 to 411 labelled f_flat_1(2), g_flat_1(2)* 414 to 414 labelled f_flat_1(3), g_flat_1(3)* 415 to 403 labelled f_1(3), g_1(3)* 415 to 410 labelled f_1(3), g_1(3)
3.92/1.64	
3.92/1.64	
3.92/1.64	----------------------------------------
3.92/1.64	
3.92/1.64	(31)
3.92/1.64	YES
3.92/1.67	EOF