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