3.39/1.53	YES
3.39/1.54	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
3.39/1.54	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.39/1.54	
3.39/1.54	
3.39/1.54	Outermost Termination of the given OTRS could be proven:
3.39/1.54	
3.39/1.54	(0) OTRS
3.39/1.54	(1) Raffelsieper-Zantema-Transformation [SOUND, 0 ms]
3.39/1.54	(2) QTRS
3.39/1.54	(3) QTRSRRRProof [EQUIVALENT, 23 ms]
3.39/1.54	(4) QTRS
3.39/1.54	(5) QTRSRRRProof [EQUIVALENT, 0 ms]
3.39/1.54	(6) QTRS
3.39/1.54	(7) AAECC Innermost [EQUIVALENT, 0 ms]
3.39/1.54	(8) QTRS
3.39/1.54	(9) DependencyPairsProof [EQUIVALENT, 0 ms]
3.39/1.54	(10) QDP
3.39/1.54	(11) DependencyGraphProof [EQUIVALENT, 0 ms]
3.39/1.54	(12) QDP
3.39/1.54	(13) UsableRulesProof [EQUIVALENT, 0 ms]
3.39/1.54	(14) QDP
3.39/1.54	(15) QReductionProof [EQUIVALENT, 0 ms]
3.39/1.54	(16) QDP
3.39/1.54	(17) RFCMatchBoundsDPProof [EQUIVALENT, 0 ms]
3.39/1.54	(18) YES
3.39/1.54	
3.39/1.54	
3.39/1.54	----------------------------------------
3.39/1.54	
3.39/1.54	(0)
3.39/1.54	Obligation:
3.39/1.54	Term rewrite system R:
3.39/1.54	The TRS R consists of the following rules:
3.39/1.54	
3.39/1.54	   f(x) -> g(f(x))
3.39/1.54	   g(f(x)) -> x
3.39/1.54	   g(x) -> a
3.39/1.54	
3.39/1.54	
3.39/1.54	
3.39/1.54	Outermost Strategy.
3.39/1.54	
3.39/1.54	----------------------------------------
3.39/1.54	
3.39/1.54	(1) Raffelsieper-Zantema-Transformation (SOUND)
3.39/1.54	We applied the Raffelsieper-Zantema transformation  to transform the outermost TRS to a standard TRS.
3.39/1.54	----------------------------------------
3.39/1.54	
3.39/1.54	(2)
3.39/1.54	Obligation:
3.39/1.54	Q restricted rewrite system:
3.39/1.54	The TRS R consists of the following rules:
3.39/1.54	
3.39/1.54	   down(f(x)) -> up(g(f(x)))
3.39/1.54	   down(g(f(x))) -> up(x)
3.39/1.54	   down(g(x)) -> up(a)
3.39/1.54	   top(up(x)) -> top(down(x))
3.39/1.54	   f_flat(up(x_1)) -> up(f(x_1))
3.39/1.54	   g_flat(up(x_1)) -> up(g(x_1))
3.39/1.54	
3.39/1.54	Q is empty.
3.39/1.54	
3.39/1.54	----------------------------------------
3.39/1.54	
3.39/1.54	(3) QTRSRRRProof (EQUIVALENT)
3.39/1.54	Used ordering:
3.39/1.54	Polynomial interpretation [POLO]:
3.39/1.54	
3.39/1.54	   POL(a) = 0
3.39/1.54	   POL(down(x_1)) = 2 + 2*x_1
3.39/1.54	   POL(f(x_1)) = x_1
3.39/1.54	   POL(f_flat(x_1)) = 1 + 2*x_1
3.39/1.54	   POL(g(x_1)) = x_1
3.39/1.54	   POL(g_flat(x_1)) = 2*x_1
3.39/1.54	   POL(top(x_1)) = 2*x_1
3.39/1.54	   POL(up(x_1)) = 2 + 2*x_1
3.39/1.54	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
3.39/1.54	
3.39/1.54	   f_flat(up(x_1)) -> up(f(x_1))
3.39/1.54	   g_flat(up(x_1)) -> up(g(x_1))
3.39/1.54	
3.39/1.54	
3.39/1.54	
3.39/1.54	
3.39/1.54	----------------------------------------
3.39/1.54	
3.39/1.54	(4)
3.39/1.54	Obligation:
3.39/1.54	Q restricted rewrite system:
3.39/1.54	The TRS R consists of the following rules:
3.39/1.54	
3.39/1.54	   down(f(x)) -> up(g(f(x)))
3.39/1.54	   down(g(f(x))) -> up(x)
3.39/1.54	   down(g(x)) -> up(a)
3.39/1.54	   top(up(x)) -> top(down(x))
3.39/1.54	
3.39/1.54	Q is empty.
3.39/1.54	
3.39/1.54	----------------------------------------
3.39/1.54	
3.39/1.54	(5) QTRSRRRProof (EQUIVALENT)
3.39/1.54	Used ordering:
3.39/1.54	Polynomial interpretation [POLO]:
3.39/1.54	
3.39/1.54	   POL(a) = 0
3.39/1.54	   POL(down(x_1)) = 2*x_1
3.39/1.54	   POL(f(x_1)) = 1 + x_1
3.39/1.54	   POL(g(x_1)) = x_1
3.39/1.54	   POL(top(x_1)) = 2*x_1
3.39/1.54	   POL(up(x_1)) = 2*x_1
3.39/1.54	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
3.39/1.54	
3.39/1.54	   down(g(f(x))) -> up(x)
3.39/1.54	
3.39/1.54	
3.39/1.54	
3.39/1.54	
3.39/1.54	----------------------------------------
3.39/1.54	
3.39/1.54	(6)
3.39/1.54	Obligation:
3.39/1.54	Q restricted rewrite system:
3.39/1.54	The TRS R consists of the following rules:
3.39/1.54	
3.39/1.54	   down(f(x)) -> up(g(f(x)))
3.39/1.54	   down(g(x)) -> up(a)
3.39/1.54	   top(up(x)) -> top(down(x))
3.39/1.54	
3.39/1.54	Q is empty.
3.39/1.54	
3.39/1.54	----------------------------------------
3.39/1.54	
3.39/1.54	(7) AAECC Innermost (EQUIVALENT)
3.39/1.54	We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is 
3.39/1.54	   down(f(x)) -> up(g(f(x)))
3.39/1.54	   down(g(x)) -> up(a)
3.39/1.54	
3.39/1.54	The TRS R 2 is 
3.39/1.54	   top(up(x)) -> top(down(x))
3.39/1.54	
3.39/1.54	The signature Sigma is {top_1}
3.39/1.54	----------------------------------------
3.39/1.54	
3.39/1.54	(8)
3.39/1.54	Obligation:
3.39/1.54	Q restricted rewrite system:
3.39/1.54	The TRS R consists of the following rules:
3.39/1.54	
3.39/1.54	   down(f(x)) -> up(g(f(x)))
3.39/1.54	   down(g(x)) -> up(a)
3.39/1.54	   top(up(x)) -> top(down(x))
3.39/1.54	
3.39/1.54	The set Q consists of the following terms:
3.39/1.54	
3.39/1.54	   down(f(x0))
3.39/1.54	   down(g(x0))
3.39/1.54	   top(up(x0))
3.39/1.54	
3.39/1.54	
3.39/1.54	----------------------------------------
3.39/1.54	
3.39/1.54	(9) DependencyPairsProof (EQUIVALENT)
3.39/1.54	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
3.39/1.54	----------------------------------------
3.39/1.54	
3.39/1.54	(10)
3.39/1.54	Obligation:
3.39/1.54	Q DP problem:
3.39/1.54	The TRS P consists of the following rules:
3.39/1.54	
3.39/1.54	   TOP(up(x)) -> TOP(down(x))
3.39/1.54	   TOP(up(x)) -> DOWN(x)
3.39/1.54	
3.39/1.54	The TRS R consists of the following rules:
3.39/1.54	
3.39/1.54	   down(f(x)) -> up(g(f(x)))
3.39/1.54	   down(g(x)) -> up(a)
3.39/1.54	   top(up(x)) -> top(down(x))
3.39/1.54	
3.39/1.54	The set Q consists of the following terms:
3.39/1.54	
3.39/1.54	   down(f(x0))
3.39/1.54	   down(g(x0))
3.39/1.54	   top(up(x0))
3.39/1.54	
3.39/1.54	We have to consider all minimal (P,Q,R)-chains.
3.39/1.54	----------------------------------------
3.39/1.54	
3.39/1.54	(11) DependencyGraphProof (EQUIVALENT)
3.39/1.54	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node.
3.39/1.54	----------------------------------------
3.39/1.54	
3.39/1.54	(12)
3.39/1.54	Obligation:
3.39/1.54	Q DP problem:
3.39/1.54	The TRS P consists of the following rules:
3.39/1.54	
3.39/1.54	   TOP(up(x)) -> TOP(down(x))
3.39/1.54	
3.39/1.54	The TRS R consists of the following rules:
3.39/1.54	
3.39/1.54	   down(f(x)) -> up(g(f(x)))
3.39/1.54	   down(g(x)) -> up(a)
3.39/1.54	   top(up(x)) -> top(down(x))
3.39/1.54	
3.39/1.54	The set Q consists of the following terms:
3.39/1.54	
3.39/1.54	   down(f(x0))
3.39/1.54	   down(g(x0))
3.39/1.54	   top(up(x0))
3.39/1.54	
3.39/1.54	We have to consider all minimal (P,Q,R)-chains.
3.39/1.54	----------------------------------------
3.39/1.54	
3.39/1.54	(13) UsableRulesProof (EQUIVALENT)
3.39/1.54	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.39/1.54	----------------------------------------
3.39/1.54	
3.39/1.54	(14)
3.39/1.54	Obligation:
3.39/1.54	Q DP problem:
3.39/1.54	The TRS P consists of the following rules:
3.39/1.54	
3.39/1.54	   TOP(up(x)) -> TOP(down(x))
3.39/1.54	
3.39/1.54	The TRS R consists of the following rules:
3.39/1.54	
3.39/1.54	   down(f(x)) -> up(g(f(x)))
3.39/1.54	   down(g(x)) -> up(a)
3.39/1.54	
3.39/1.54	The set Q consists of the following terms:
3.39/1.54	
3.39/1.54	   down(f(x0))
3.39/1.54	   down(g(x0))
3.39/1.54	   top(up(x0))
3.39/1.54	
3.39/1.54	We have to consider all minimal (P,Q,R)-chains.
3.39/1.54	----------------------------------------
3.39/1.54	
3.39/1.54	(15) QReductionProof (EQUIVALENT)
3.39/1.54	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
3.39/1.54	
3.39/1.54	   top(up(x0))
3.39/1.54	
3.39/1.54	
3.39/1.54	----------------------------------------
3.39/1.54	
3.39/1.54	(16)
3.39/1.54	Obligation:
3.39/1.54	Q DP problem:
3.39/1.54	The TRS P consists of the following rules:
3.39/1.54	
3.39/1.54	   TOP(up(x)) -> TOP(down(x))
3.39/1.54	
3.39/1.54	The TRS R consists of the following rules:
3.39/1.54	
3.39/1.54	   down(f(x)) -> up(g(f(x)))
3.39/1.54	   down(g(x)) -> up(a)
3.39/1.54	
3.39/1.54	The set Q consists of the following terms:
3.39/1.54	
3.39/1.54	   down(f(x0))
3.39/1.54	   down(g(x0))
3.39/1.54	
3.39/1.54	We have to consider all minimal (P,Q,R)-chains.
3.39/1.54	----------------------------------------
3.39/1.54	
3.39/1.54	(17) RFCMatchBoundsDPProof (EQUIVALENT)
3.39/1.54	Finiteness of the DP problem can be shown by a matchbound of 2. 
3.39/1.54	As the DP problem is minimal we only have to initialize the certificate graph by the rules of P:
3.39/1.54	
3.39/1.54	   TOP(up(x)) -> TOP(down(x))
3.39/1.54	
3.39/1.54	To find matches we regarded all rules of R and P:
3.39/1.54	
3.39/1.54	   down(f(x)) -> up(g(f(x)))
3.39/1.54	   down(g(x)) -> up(a)
3.39/1.54	   TOP(up(x)) -> TOP(down(x))
3.39/1.54	
3.39/1.54	The certificate found is represented by the following graph.
3.39/1.54	The certificate consists of the following enumerated nodes:
3.39/1.54	162, 163, 164, 165, 166, 167, 168, 169
3.39/1.54	
3.39/1.54	Node 162 is start node and node 163 is final node.
3.39/1.54	
3.39/1.54	Those nodes are connected through the following edges:
3.39/1.54	
3.39/1.54	* 162 to 164 labelled TOP_1(0)* 162 to 167 labelled TOP_1(1)* 162 to 169 labelled TOP_1(2)* 163 to 163 labelled #_1(0)* 164 to 163 labelled down_1(0)* 164 to 165 labelled up_1(1)* 165 to 166 labelled g_1(1)* 165 to 163 labelled a(1)* 166 to 163 labelled f_1(1)* 167 to 165 labelled down_1(1)* 167 to 168 labelled up_1(2)* 168 to 166 labelled a(2)* 169 to 168 labelled down_1(2)
3.39/1.54	
3.39/1.54	
3.39/1.54	----------------------------------------
3.39/1.54	
3.39/1.54	(18)
3.39/1.54	YES
3.49/1.57	EOF