12.57/4.18	YES
12.93/4.23	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
12.93/4.23	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
12.93/4.23	
12.93/4.23	
12.93/4.23	Termination w.r.t. Q of the given QTRS could be proven:
12.93/4.23	
12.93/4.23	(0) QTRS
12.93/4.23	(1) QTRS Reverse [EQUIVALENT, 0 ms]
12.93/4.23	(2) QTRS
12.93/4.23	(3) DependencyPairsProof [EQUIVALENT, 20 ms]
12.93/4.23	(4) QDP
12.93/4.23	(5) DependencyGraphProof [EQUIVALENT, 0 ms]
12.93/4.23	(6) AND
12.93/4.23	    (7) QDP
12.93/4.23	        (8) UsableRulesProof [EQUIVALENT, 0 ms]
12.93/4.23	        (9) QDP
12.93/4.23	        (10) MRRProof [EQUIVALENT, 31 ms]
12.93/4.23	        (11) QDP
12.93/4.23	        (12) PisEmptyProof [EQUIVALENT, 0 ms]
12.93/4.23	        (13) YES
12.93/4.23	    (14) QDP
12.93/4.23	        (15) UsableRulesProof [EQUIVALENT, 0 ms]
12.93/4.23	        (16) QDP
12.93/4.23	        (17) QDPOrderProof [EQUIVALENT, 12 ms]
12.93/4.23	        (18) QDP
12.93/4.23	        (19) PisEmptyProof [EQUIVALENT, 0 ms]
12.93/4.23	        (20) YES
12.93/4.23	
12.93/4.23	
12.93/4.23	----------------------------------------
12.93/4.23	
12.93/4.23	(0)
12.93/4.23	Obligation:
12.93/4.23	Q restricted rewrite system:
12.93/4.23	The TRS R consists of the following rules:
12.93/4.23	
12.93/4.23	   1(2(1(x1))) -> 2(0(2(x1)))
12.93/4.23	   0(2(1(x1))) -> 1(0(2(x1)))
12.93/4.23	   L(2(1(x1))) -> L(1(0(2(x1))))
12.93/4.23	   1(2(0(x1))) -> 2(0(1(x1)))
12.93/4.23	   1(2(R(x1))) -> 2(0(1(R(x1))))
12.93/4.23	   0(2(0(x1))) -> 1(0(1(x1)))
12.93/4.23	   L(2(0(x1))) -> L(1(0(1(x1))))
12.93/4.23	   0(2(R(x1))) -> 1(0(1(R(x1))))
12.93/4.23	
12.93/4.23	Q is empty.
12.93/4.23	
12.93/4.23	----------------------------------------
12.93/4.23	
12.93/4.23	(1) QTRS Reverse (EQUIVALENT)
12.93/4.23	We applied the QTRS Reverse Processor [REVERSE].
12.93/4.23	----------------------------------------
12.93/4.23	
12.93/4.23	(2)
12.93/4.23	Obligation:
12.93/4.23	Q restricted rewrite system:
12.93/4.23	The TRS R consists of the following rules:
12.93/4.23	
12.93/4.23	   1(2(1(x1))) -> 2(0(2(x1)))
12.93/4.23	   1(2(0(x1))) -> 2(0(1(x1)))
12.93/4.23	   1(2(L(x1))) -> 2(0(1(L(x1))))
12.93/4.23	   0(2(1(x1))) -> 1(0(2(x1)))
12.93/4.23	   R(2(1(x1))) -> R(1(0(2(x1))))
12.93/4.23	   0(2(0(x1))) -> 1(0(1(x1)))
12.93/4.23	   0(2(L(x1))) -> 1(0(1(L(x1))))
12.93/4.23	   R(2(0(x1))) -> R(1(0(1(x1))))
12.93/4.23	
12.93/4.23	Q is empty.
12.93/4.23	
12.93/4.23	----------------------------------------
12.93/4.23	
12.93/4.23	(3) DependencyPairsProof (EQUIVALENT)
12.93/4.23	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
12.93/4.23	----------------------------------------
12.93/4.23	
12.93/4.23	(4)
12.93/4.23	Obligation:
12.93/4.23	Q DP problem:
12.93/4.23	The TRS P consists of the following rules:
12.93/4.23	
12.93/4.23	   1^1(2(1(x1))) -> 0^1(2(x1))
12.93/4.23	   1^1(2(0(x1))) -> 0^1(1(x1))
12.93/4.23	   1^1(2(0(x1))) -> 1^1(x1)
12.93/4.23	   1^1(2(L(x1))) -> 0^1(1(L(x1)))
12.93/4.23	   1^1(2(L(x1))) -> 1^1(L(x1))
12.93/4.23	   0^1(2(1(x1))) -> 1^1(0(2(x1)))
12.93/4.23	   0^1(2(1(x1))) -> 0^1(2(x1))
12.93/4.23	   R^1(2(1(x1))) -> R^1(1(0(2(x1))))
12.93/4.23	   R^1(2(1(x1))) -> 1^1(0(2(x1)))
12.93/4.23	   R^1(2(1(x1))) -> 0^1(2(x1))
12.93/4.23	   0^1(2(0(x1))) -> 1^1(0(1(x1)))
12.93/4.23	   0^1(2(0(x1))) -> 0^1(1(x1))
12.93/4.23	   0^1(2(0(x1))) -> 1^1(x1)
12.93/4.23	   0^1(2(L(x1))) -> 1^1(0(1(L(x1))))
12.93/4.23	   0^1(2(L(x1))) -> 0^1(1(L(x1)))
12.93/4.23	   0^1(2(L(x1))) -> 1^1(L(x1))
12.93/4.23	   R^1(2(0(x1))) -> R^1(1(0(1(x1))))
12.93/4.23	   R^1(2(0(x1))) -> 1^1(0(1(x1)))
12.93/4.23	   R^1(2(0(x1))) -> 0^1(1(x1))
12.93/4.23	   R^1(2(0(x1))) -> 1^1(x1)
12.93/4.23	
12.93/4.23	The TRS R consists of the following rules:
12.93/4.23	
12.93/4.23	   1(2(1(x1))) -> 2(0(2(x1)))
12.93/4.23	   1(2(0(x1))) -> 2(0(1(x1)))
12.93/4.23	   1(2(L(x1))) -> 2(0(1(L(x1))))
12.93/4.23	   0(2(1(x1))) -> 1(0(2(x1)))
12.93/4.23	   R(2(1(x1))) -> R(1(0(2(x1))))
12.93/4.23	   0(2(0(x1))) -> 1(0(1(x1)))
12.93/4.23	   0(2(L(x1))) -> 1(0(1(L(x1))))
12.93/4.23	   R(2(0(x1))) -> R(1(0(1(x1))))
12.93/4.23	
12.93/4.23	Q is empty.
12.93/4.23	We have to consider all minimal (P,Q,R)-chains.
12.93/4.23	----------------------------------------
12.93/4.23	
12.93/4.23	(5) DependencyGraphProof (EQUIVALENT)
12.93/4.23	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 10 less nodes.
12.93/4.23	----------------------------------------
12.93/4.23	
12.93/4.23	(6)
12.93/4.23	Complex Obligation (AND)
12.93/4.23	
12.93/4.23	----------------------------------------
12.93/4.23	
12.93/4.23	(7)
12.93/4.23	Obligation:
12.93/4.23	Q DP problem:
12.93/4.23	The TRS P consists of the following rules:
12.93/4.23	
12.93/4.23	   0^1(2(1(x1))) -> 1^1(0(2(x1)))
12.93/4.23	   1^1(2(1(x1))) -> 0^1(2(x1))
12.93/4.23	   0^1(2(1(x1))) -> 0^1(2(x1))
12.93/4.23	   0^1(2(0(x1))) -> 1^1(0(1(x1)))
12.93/4.23	   1^1(2(0(x1))) -> 0^1(1(x1))
12.93/4.23	   0^1(2(0(x1))) -> 0^1(1(x1))
12.93/4.23	   0^1(2(0(x1))) -> 1^1(x1)
12.93/4.23	   1^1(2(0(x1))) -> 1^1(x1)
12.93/4.23	
12.93/4.23	The TRS R consists of the following rules:
12.93/4.23	
12.93/4.23	   1(2(1(x1))) -> 2(0(2(x1)))
12.93/4.23	   1(2(0(x1))) -> 2(0(1(x1)))
12.93/4.23	   1(2(L(x1))) -> 2(0(1(L(x1))))
12.93/4.23	   0(2(1(x1))) -> 1(0(2(x1)))
12.93/4.23	   R(2(1(x1))) -> R(1(0(2(x1))))
12.93/4.23	   0(2(0(x1))) -> 1(0(1(x1)))
12.93/4.23	   0(2(L(x1))) -> 1(0(1(L(x1))))
12.93/4.23	   R(2(0(x1))) -> R(1(0(1(x1))))
12.93/4.23	
12.93/4.23	Q is empty.
12.93/4.23	We have to consider all minimal (P,Q,R)-chains.
12.93/4.23	----------------------------------------
12.93/4.23	
12.93/4.23	(8) UsableRulesProof (EQUIVALENT)
12.93/4.23	We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R.
12.93/4.23	----------------------------------------
12.93/4.23	
12.93/4.23	(9)
12.93/4.23	Obligation:
12.93/4.23	Q DP problem:
12.93/4.23	The TRS P consists of the following rules:
12.93/4.23	
12.93/4.23	   0^1(2(1(x1))) -> 1^1(0(2(x1)))
12.93/4.23	   1^1(2(1(x1))) -> 0^1(2(x1))
12.93/4.23	   0^1(2(1(x1))) -> 0^1(2(x1))
12.93/4.23	   0^1(2(0(x1))) -> 1^1(0(1(x1)))
12.93/4.23	   1^1(2(0(x1))) -> 0^1(1(x1))
12.93/4.23	   0^1(2(0(x1))) -> 0^1(1(x1))
12.93/4.23	   0^1(2(0(x1))) -> 1^1(x1)
12.93/4.23	   1^1(2(0(x1))) -> 1^1(x1)
12.93/4.23	
12.93/4.23	The TRS R consists of the following rules:
12.93/4.23	
12.93/4.23	   1(2(1(x1))) -> 2(0(2(x1)))
12.93/4.23	   1(2(0(x1))) -> 2(0(1(x1)))
12.93/4.23	   1(2(L(x1))) -> 2(0(1(L(x1))))
12.93/4.23	   0(2(1(x1))) -> 1(0(2(x1)))
12.93/4.23	   0(2(0(x1))) -> 1(0(1(x1)))
12.93/4.23	   0(2(L(x1))) -> 1(0(1(L(x1))))
12.93/4.23	
12.93/4.23	Q is empty.
12.93/4.23	We have to consider all minimal (P,Q,R)-chains.
12.93/4.23	----------------------------------------
12.93/4.23	
12.93/4.23	(10) MRRProof (EQUIVALENT)
12.93/4.23	By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented.
12.93/4.23	
12.93/4.23	Strictly oriented dependency pairs:
12.93/4.23	
12.93/4.23	   0^1(2(1(x1))) -> 1^1(0(2(x1)))
12.93/4.23	   1^1(2(1(x1))) -> 0^1(2(x1))
12.93/4.23	   0^1(2(1(x1))) -> 0^1(2(x1))
12.93/4.23	   0^1(2(0(x1))) -> 1^1(0(1(x1)))
12.93/4.23	   1^1(2(0(x1))) -> 0^1(1(x1))
12.93/4.23	   0^1(2(0(x1))) -> 0^1(1(x1))
12.93/4.23	   0^1(2(0(x1))) -> 1^1(x1)
12.93/4.23	   1^1(2(0(x1))) -> 1^1(x1)
12.93/4.23	
12.93/4.23	
12.93/4.23	Used ordering: Polynomial interpretation [POLO]:
12.93/4.23	
12.93/4.23	   POL(0(x_1)) = x_1
12.93/4.23	   POL(0^1(x_1)) = 2 + 2*x_1
12.93/4.23	   POL(1(x_1)) = 1 + x_1
12.93/4.23	   POL(1^1(x_1)) = 1 + 2*x_1
12.93/4.23	   POL(2(x_1)) = 2 + x_1
12.93/4.23	   POL(L(x_1)) = x_1
12.93/4.23	
12.93/4.23	
12.93/4.23	----------------------------------------
12.93/4.23	
12.93/4.23	(11)
12.93/4.23	Obligation:
12.93/4.23	Q DP problem:
12.93/4.23	P is empty.
12.93/4.23	The TRS R consists of the following rules:
12.93/4.23	
12.93/4.23	   1(2(1(x1))) -> 2(0(2(x1)))
12.93/4.23	   1(2(0(x1))) -> 2(0(1(x1)))
12.93/4.23	   1(2(L(x1))) -> 2(0(1(L(x1))))
12.93/4.23	   0(2(1(x1))) -> 1(0(2(x1)))
12.93/4.23	   0(2(0(x1))) -> 1(0(1(x1)))
12.93/4.23	   0(2(L(x1))) -> 1(0(1(L(x1))))
12.93/4.23	
12.93/4.23	Q is empty.
12.93/4.23	We have to consider all minimal (P,Q,R)-chains.
12.93/4.23	----------------------------------------
12.93/4.23	
12.93/4.23	(12) PisEmptyProof (EQUIVALENT)
12.93/4.23	The TRS P is empty. Hence, there is no (P,Q,R) chain.
12.93/4.23	----------------------------------------
12.93/4.23	
12.93/4.23	(13)
12.93/4.23	YES
12.93/4.23	
12.93/4.23	----------------------------------------
12.93/4.23	
12.93/4.23	(14)
12.93/4.23	Obligation:
12.93/4.23	Q DP problem:
12.93/4.23	The TRS P consists of the following rules:
12.93/4.23	
12.93/4.23	   R^1(2(0(x1))) -> R^1(1(0(1(x1))))
12.93/4.23	   R^1(2(1(x1))) -> R^1(1(0(2(x1))))
12.93/4.23	
12.93/4.23	The TRS R consists of the following rules:
12.93/4.23	
12.93/4.23	   1(2(1(x1))) -> 2(0(2(x1)))
12.93/4.23	   1(2(0(x1))) -> 2(0(1(x1)))
12.93/4.23	   1(2(L(x1))) -> 2(0(1(L(x1))))
12.93/4.23	   0(2(1(x1))) -> 1(0(2(x1)))
12.93/4.23	   R(2(1(x1))) -> R(1(0(2(x1))))
12.93/4.23	   0(2(0(x1))) -> 1(0(1(x1)))
12.93/4.23	   0(2(L(x1))) -> 1(0(1(L(x1))))
12.93/4.23	   R(2(0(x1))) -> R(1(0(1(x1))))
12.93/4.23	
12.93/4.23	Q is empty.
12.93/4.23	We have to consider all minimal (P,Q,R)-chains.
12.93/4.23	----------------------------------------
12.93/4.23	
12.93/4.23	(15) UsableRulesProof (EQUIVALENT)
12.93/4.23	We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R.
12.93/4.23	----------------------------------------
12.93/4.23	
12.93/4.23	(16)
12.93/4.23	Obligation:
12.93/4.23	Q DP problem:
12.93/4.23	The TRS P consists of the following rules:
12.93/4.23	
12.93/4.23	   R^1(2(0(x1))) -> R^1(1(0(1(x1))))
12.93/4.23	   R^1(2(1(x1))) -> R^1(1(0(2(x1))))
12.93/4.23	
12.93/4.23	The TRS R consists of the following rules:
12.93/4.23	
12.93/4.23	   0(2(1(x1))) -> 1(0(2(x1)))
12.93/4.23	   0(2(0(x1))) -> 1(0(1(x1)))
12.93/4.23	   0(2(L(x1))) -> 1(0(1(L(x1))))
12.93/4.23	   1(2(1(x1))) -> 2(0(2(x1)))
12.93/4.23	   1(2(0(x1))) -> 2(0(1(x1)))
12.93/4.23	   1(2(L(x1))) -> 2(0(1(L(x1))))
12.93/4.23	
12.93/4.23	Q is empty.
12.93/4.23	We have to consider all minimal (P,Q,R)-chains.
12.93/4.23	----------------------------------------
12.93/4.23	
12.93/4.23	(17) QDPOrderProof (EQUIVALENT)
12.93/4.23	We use the reduction pair processor [LPAR04,JAR06].
12.93/4.23	
12.93/4.23	
12.93/4.23	The following pairs can be oriented strictly and are deleted.
12.93/4.23	
12.93/4.23	   R^1(2(0(x1))) -> R^1(1(0(1(x1))))
12.93/4.23	   R^1(2(1(x1))) -> R^1(1(0(2(x1))))
12.93/4.23	The remaining pairs can at least be oriented weakly.
12.93/4.23	Used ordering:  Polynomial interpretation [POLO]:
12.93/4.23	
12.93/4.23	   POL(0(x_1)) = 0
12.93/4.23	   POL(1(x_1)) = x_1
12.93/4.23	   POL(2(x_1)) = 1
12.93/4.23	   POL(L(x_1)) = x_1
12.93/4.23	   POL(R^1(x_1)) = x_1
12.93/4.23	
12.93/4.23	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
12.93/4.23	
12.93/4.23	   1(2(1(x1))) -> 2(0(2(x1)))
12.93/4.23	   1(2(0(x1))) -> 2(0(1(x1)))
12.93/4.23	   1(2(L(x1))) -> 2(0(1(L(x1))))
12.93/4.23	   0(2(1(x1))) -> 1(0(2(x1)))
12.93/4.23	   0(2(0(x1))) -> 1(0(1(x1)))
12.93/4.23	   0(2(L(x1))) -> 1(0(1(L(x1))))
12.93/4.23	
12.93/4.23	
12.93/4.23	----------------------------------------
12.93/4.23	
12.93/4.23	(18)
12.93/4.23	Obligation:
12.93/4.23	Q DP problem:
12.93/4.23	P is empty.
12.93/4.23	The TRS R consists of the following rules:
12.93/4.23	
12.93/4.23	   0(2(1(x1))) -> 1(0(2(x1)))
12.93/4.23	   0(2(0(x1))) -> 1(0(1(x1)))
12.93/4.23	   0(2(L(x1))) -> 1(0(1(L(x1))))
12.93/4.23	   1(2(1(x1))) -> 2(0(2(x1)))
12.93/4.23	   1(2(0(x1))) -> 2(0(1(x1)))
12.93/4.23	   1(2(L(x1))) -> 2(0(1(L(x1))))
12.93/4.23	
12.93/4.23	Q is empty.
12.93/4.23	We have to consider all minimal (P,Q,R)-chains.
12.93/4.23	----------------------------------------
12.93/4.23	
12.93/4.23	(19) PisEmptyProof (EQUIVALENT)
12.93/4.23	The TRS P is empty. Hence, there is no (P,Q,R) chain.
12.93/4.23	----------------------------------------
12.93/4.23	
12.93/4.23	(20)
12.93/4.23	YES
13.15/4.40	EOF