3.68/1.79	YES
3.68/1.80	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
3.68/1.80	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.68/1.80	
3.68/1.80	
3.68/1.80	Termination w.r.t. Q of the given QTRS could be proven:
3.68/1.80	
3.68/1.80	(0) QTRS
3.68/1.80	(1) QTRSRRRProof [EQUIVALENT, 53 ms]
3.68/1.80	(2) QTRS
3.68/1.80	(3) QTRSRRRProof [EQUIVALENT, 0 ms]
3.68/1.80	(4) QTRS
3.68/1.80	(5) QTRSRRRProof [EQUIVALENT, 0 ms]
3.68/1.80	(6) QTRS
3.68/1.80	(7) DependencyPairsProof [EQUIVALENT, 0 ms]
3.68/1.80	(8) QDP
3.68/1.80	(9) DependencyGraphProof [EQUIVALENT, 0 ms]
3.68/1.80	(10) TRUE
3.68/1.80	
3.68/1.80	
3.68/1.80	----------------------------------------
3.68/1.80	
3.68/1.80	(0)
3.68/1.80	Obligation:
3.68/1.80	Q restricted rewrite system:
3.68/1.80	The TRS R consists of the following rules:
3.68/1.80	
3.68/1.80	   f(s(X)) -> f(X)
3.68/1.80	   g(cons(0, Y)) -> g(Y)
3.68/1.80	   g(cons(s(X), Y)) -> s(X)
3.68/1.80	   h(cons(X, Y)) -> h(g(cons(X, Y)))
3.68/1.80	
3.68/1.80	The set Q consists of the following terms:
3.68/1.80	
3.68/1.80	   f(s(x0))
3.68/1.80	   g(cons(0, x0))
3.68/1.80	   g(cons(s(x0), x1))
3.68/1.80	   h(cons(x0, x1))
3.68/1.80	
3.68/1.80	
3.68/1.80	----------------------------------------
3.68/1.80	
3.68/1.80	(1) QTRSRRRProof (EQUIVALENT)
3.68/1.80	Used ordering:
3.68/1.80	Polynomial interpretation [POLO]:
3.68/1.80	
3.68/1.80	   POL(0) = 2
3.68/1.80	   POL(cons(x_1, x_2)) = x_1 + x_2
3.68/1.80	   POL(f(x_1)) = 2*x_1
3.68/1.80	   POL(g(x_1)) = x_1
3.68/1.80	   POL(h(x_1)) = 2*x_1
3.68/1.80	   POL(s(x_1)) = 2*x_1
3.68/1.80	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
3.68/1.80	
3.68/1.80	   g(cons(0, Y)) -> g(Y)
3.68/1.80	
3.68/1.80	
3.68/1.80	
3.68/1.80	
3.68/1.80	----------------------------------------
3.68/1.80	
3.68/1.80	(2)
3.68/1.80	Obligation:
3.68/1.80	Q restricted rewrite system:
3.68/1.80	The TRS R consists of the following rules:
3.68/1.80	
3.68/1.80	   f(s(X)) -> f(X)
3.68/1.80	   g(cons(s(X), Y)) -> s(X)
3.68/1.80	   h(cons(X, Y)) -> h(g(cons(X, Y)))
3.68/1.80	
3.68/1.80	The set Q consists of the following terms:
3.68/1.80	
3.68/1.80	   f(s(x0))
3.68/1.80	   g(cons(0, x0))
3.68/1.80	   g(cons(s(x0), x1))
3.68/1.80	   h(cons(x0, x1))
3.68/1.80	
3.68/1.80	
3.68/1.80	----------------------------------------
3.68/1.80	
3.68/1.80	(3) QTRSRRRProof (EQUIVALENT)
3.68/1.80	Used ordering:
3.68/1.80	Polynomial interpretation [POLO]:
3.68/1.80	
3.68/1.80	   POL(cons(x_1, x_2)) = x_1 + 2*x_2
3.68/1.80	   POL(f(x_1)) = 2*x_1
3.68/1.80	   POL(g(x_1)) = x_1
3.68/1.80	   POL(h(x_1)) = x_1
3.68/1.80	   POL(s(x_1)) = 1 + x_1
3.68/1.80	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
3.68/1.80	
3.68/1.80	   f(s(X)) -> f(X)
3.68/1.80	
3.68/1.80	
3.68/1.80	
3.68/1.80	
3.68/1.80	----------------------------------------
3.68/1.80	
3.68/1.80	(4)
3.68/1.80	Obligation:
3.68/1.80	Q restricted rewrite system:
3.68/1.80	The TRS R consists of the following rules:
3.68/1.80	
3.68/1.80	   g(cons(s(X), Y)) -> s(X)
3.68/1.80	   h(cons(X, Y)) -> h(g(cons(X, Y)))
3.68/1.80	
3.68/1.80	The set Q consists of the following terms:
3.68/1.80	
3.68/1.80	   f(s(x0))
3.68/1.80	   g(cons(0, x0))
3.68/1.80	   g(cons(s(x0), x1))
3.68/1.80	   h(cons(x0, x1))
3.68/1.80	
3.68/1.80	
3.68/1.80	----------------------------------------
3.68/1.80	
3.68/1.80	(5) QTRSRRRProof (EQUIVALENT)
3.68/1.80	Used ordering:
3.68/1.80	g/1)YES(
3.68/1.80	cons/2(YES,YES)
3.68/1.80	s/1)YES(
3.68/1.80	h/1)YES(
3.68/1.80	
3.68/1.80	Quasi precedence:
3.68/1.80	trivial
3.68/1.80	
3.68/1.80	
3.68/1.80	Status:
3.68/1.80	cons_2: [1,2]
3.68/1.80	
3.68/1.80	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
3.68/1.80	
3.68/1.80	   g(cons(s(X), Y)) -> s(X)
3.68/1.80	
3.68/1.80	
3.68/1.80	
3.68/1.80	
3.68/1.80	----------------------------------------
3.68/1.80	
3.68/1.80	(6)
3.68/1.80	Obligation:
3.68/1.80	Q restricted rewrite system:
3.68/1.80	The TRS R consists of the following rules:
3.68/1.80	
3.68/1.80	   h(cons(X, Y)) -> h(g(cons(X, Y)))
3.68/1.80	
3.68/1.80	The set Q consists of the following terms:
3.68/1.80	
3.68/1.80	   f(s(x0))
3.68/1.80	   g(cons(0, x0))
3.68/1.80	   g(cons(s(x0), x1))
3.68/1.80	   h(cons(x0, x1))
3.68/1.80	
3.68/1.80	
3.68/1.80	----------------------------------------
3.68/1.80	
3.68/1.80	(7) DependencyPairsProof (EQUIVALENT)
3.68/1.80	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
3.68/1.80	----------------------------------------
3.68/1.80	
3.68/1.80	(8)
3.68/1.80	Obligation:
3.68/1.80	Q DP problem:
3.68/1.80	The TRS P consists of the following rules:
3.68/1.80	
3.68/1.80	   H(cons(X, Y)) -> H(g(cons(X, Y)))
3.68/1.80	
3.68/1.80	The TRS R consists of the following rules:
3.68/1.80	
3.68/1.80	   h(cons(X, Y)) -> h(g(cons(X, Y)))
3.68/1.80	
3.68/1.80	The set Q consists of the following terms:
3.68/1.80	
3.68/1.80	   f(s(x0))
3.68/1.80	   g(cons(0, x0))
3.68/1.80	   g(cons(s(x0), x1))
3.68/1.80	   h(cons(x0, x1))
3.68/1.80	
3.68/1.80	We have to consider all minimal (P,Q,R)-chains.
3.68/1.80	----------------------------------------
3.68/1.80	
3.68/1.80	(9) DependencyGraphProof (EQUIVALENT)
3.68/1.80	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node.
3.68/1.80	----------------------------------------
3.68/1.80	
3.68/1.80	(10)
3.68/1.80	TRUE
3.83/1.82	EOF