4.48/2.09	YES
4.50/2.10	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
4.50/2.10	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.50/2.10	
4.50/2.10	
4.50/2.10	Termination w.r.t. Q of the given QTRS could be proven:
4.50/2.10	
4.50/2.10	(0) QTRS
4.50/2.10	(1) DependencyPairsProof [EQUIVALENT, 3 ms]
4.50/2.10	(2) QDP
4.50/2.10	(3) DependencyGraphProof [EQUIVALENT, 0 ms]
4.50/2.10	(4) QDP
4.50/2.10	(5) UsableRulesProof [EQUIVALENT, 0 ms]
4.50/2.10	(6) QDP
4.50/2.10	(7) QReductionProof [EQUIVALENT, 0 ms]
4.50/2.10	(8) QDP
4.50/2.10	(9) TransformationProof [EQUIVALENT, 0 ms]
4.50/2.10	(10) QDP
4.50/2.10	(11) Induction-Processor [SOUND, 10 ms]
4.50/2.10	(12) AND
4.50/2.10	    (13) QDP
4.50/2.10	        (14) PisEmptyProof [EQUIVALENT, 0 ms]
4.50/2.10	        (15) YES
4.50/2.10	    (16) QTRS
4.50/2.10	        (17) QTRSRRRProof [EQUIVALENT, 18 ms]
4.50/2.10	        (18) QTRS
4.50/2.10	        (19) QTRSRRRProof [EQUIVALENT, 0 ms]
4.50/2.10	        (20) QTRS
4.50/2.10	        (21) RisEmptyProof [EQUIVALENT, 0 ms]
4.50/2.10	        (22) YES
4.50/2.10	
4.50/2.10	
4.50/2.10	----------------------------------------
4.50/2.10	
4.50/2.10	(0)
4.50/2.10	Obligation:
4.50/2.10	Q restricted rewrite system:
4.50/2.10	The TRS R consists of the following rules:
4.50/2.10	
4.50/2.10	   f(0, 1, X) -> f(g(X, X), X, X)
4.50/2.10	   g(X, Y) -> X
4.50/2.10	   g(X, Y) -> Y
4.50/2.10	
4.50/2.10	The set Q consists of the following terms:
4.50/2.10	
4.50/2.10	   f(0, 1, x0)
4.50/2.10	   g(x0, x1)
4.50/2.10	
4.50/2.10	
4.50/2.10	----------------------------------------
4.50/2.10	
4.50/2.10	(1) DependencyPairsProof (EQUIVALENT)
4.50/2.10	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
4.50/2.10	----------------------------------------
4.50/2.10	
4.50/2.10	(2)
4.50/2.10	Obligation:
4.50/2.10	Q DP problem:
4.50/2.10	The TRS P consists of the following rules:
4.50/2.10	
4.50/2.10	   F(0, 1, X) -> F(g(X, X), X, X)
4.50/2.10	   F(0, 1, X) -> G(X, X)
4.50/2.10	
4.50/2.10	The TRS R consists of the following rules:
4.50/2.10	
4.50/2.10	   f(0, 1, X) -> f(g(X, X), X, X)
4.50/2.10	   g(X, Y) -> X
4.50/2.10	   g(X, Y) -> Y
4.50/2.10	
4.50/2.10	The set Q consists of the following terms:
4.50/2.10	
4.50/2.10	   f(0, 1, x0)
4.50/2.10	   g(x0, x1)
4.50/2.10	
4.50/2.10	We have to consider all minimal (P,Q,R)-chains.
4.50/2.10	----------------------------------------
4.50/2.10	
4.50/2.10	(3) DependencyGraphProof (EQUIVALENT)
4.50/2.10	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node.
4.50/2.10	----------------------------------------
4.50/2.10	
4.50/2.10	(4)
4.50/2.10	Obligation:
4.50/2.10	Q DP problem:
4.50/2.10	The TRS P consists of the following rules:
4.50/2.10	
4.50/2.10	   F(0, 1, X) -> F(g(X, X), X, X)
4.50/2.10	
4.50/2.10	The TRS R consists of the following rules:
4.50/2.10	
4.50/2.10	   f(0, 1, X) -> f(g(X, X), X, X)
4.50/2.10	   g(X, Y) -> X
4.50/2.10	   g(X, Y) -> Y
4.50/2.10	
4.50/2.10	The set Q consists of the following terms:
4.50/2.10	
4.50/2.10	   f(0, 1, x0)
4.50/2.10	   g(x0, x1)
4.50/2.10	
4.50/2.10	We have to consider all minimal (P,Q,R)-chains.
4.50/2.10	----------------------------------------
4.50/2.10	
4.50/2.10	(5) UsableRulesProof (EQUIVALENT)
4.50/2.10	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.
4.50/2.10	----------------------------------------
4.50/2.10	
4.50/2.10	(6)
4.50/2.10	Obligation:
4.50/2.10	Q DP problem:
4.50/2.10	The TRS P consists of the following rules:
4.50/2.10	
4.50/2.10	   F(0, 1, X) -> F(g(X, X), X, X)
4.50/2.10	
4.50/2.10	The TRS R consists of the following rules:
4.50/2.10	
4.50/2.10	   g(X, Y) -> X
4.50/2.10	   g(X, Y) -> Y
4.50/2.10	
4.50/2.10	The set Q consists of the following terms:
4.50/2.10	
4.50/2.10	   f(0, 1, x0)
4.50/2.10	   g(x0, x1)
4.50/2.10	
4.50/2.10	We have to consider all minimal (P,Q,R)-chains.
4.50/2.10	----------------------------------------
4.50/2.10	
4.50/2.10	(7) QReductionProof (EQUIVALENT)
4.50/2.10	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
4.50/2.10	
4.50/2.10	   f(0, 1, x0)
4.50/2.10	
4.50/2.10	
4.50/2.10	----------------------------------------
4.50/2.10	
4.50/2.10	(8)
4.50/2.10	Obligation:
4.50/2.10	Q DP problem:
4.50/2.10	The TRS P consists of the following rules:
4.50/2.10	
4.50/2.10	   F(0, 1, X) -> F(g(X, X), X, X)
4.50/2.10	
4.50/2.10	The TRS R consists of the following rules:
4.50/2.10	
4.50/2.10	   g(X, Y) -> X
4.50/2.10	   g(X, Y) -> Y
4.50/2.10	
4.50/2.10	The set Q consists of the following terms:
4.50/2.10	
4.50/2.10	   g(x0, x1)
4.50/2.10	
4.50/2.10	We have to consider all minimal (P,Q,R)-chains.
4.50/2.10	----------------------------------------
4.50/2.10	
4.50/2.10	(9) TransformationProof (EQUIVALENT)
4.50/2.10	By instantiating [LPAR04] the rule F(0, 1, X) -> F(g(X, X), X, X) we obtained the following new rules [LPAR04]:
4.50/2.10	
4.50/2.10	   (F(0, 1, 1) -> F(g(1, 1), 1, 1),F(0, 1, 1) -> F(g(1, 1), 1, 1))
4.50/2.10	
4.50/2.10	
4.50/2.10	----------------------------------------
4.50/2.10	
4.50/2.10	(10)
4.50/2.10	Obligation:
4.50/2.10	Q DP problem:
4.50/2.10	The TRS P consists of the following rules:
4.50/2.10	
4.50/2.10	   F(0, 1, 1) -> F(g(1, 1), 1, 1)
4.50/2.10	
4.50/2.10	The TRS R consists of the following rules:
4.50/2.10	
4.50/2.10	   g(X, Y) -> X
4.50/2.10	   g(X, Y) -> Y
4.50/2.10	
4.50/2.10	The set Q consists of the following terms:
4.50/2.10	
4.50/2.10	   g(x0, x1)
4.50/2.10	
4.50/2.10	We have to consider all minimal (P,Q,R)-chains.
4.50/2.10	----------------------------------------
4.50/2.10	
4.50/2.10	(11) Induction-Processor (SOUND)
4.50/2.10	
4.50/2.10	This DP could be deleted by the Induction-Processor:
4.50/2.10	F(0, 1, 1) -> F(g(1, 1), 1, 1)
4.50/2.10	
4.50/2.10	
4.50/2.10	This order was computed:
4.50/2.10	Polynomial interpretation [POLO]:
4.50/2.10	
4.50/2.10	   POL(0) = 1
4.50/2.10	   POL(1) = 0
4.50/2.10	   POL(F(x_1, x_2, x_3)) = x_1
4.50/2.10	   POL(g(x_1, x_2)) = 1 + x_1 + x_2
4.50/2.10	
4.50/2.10	At least one of these decreasing rules is always used after the deleted DP:
4.50/2.10	g(X, Y) -> X
4.50/2.10	g(X', Y') -> Y'
4.50/2.10	
4.50/2.10	
4.50/2.10	The following formula is valid:
4.50/2.10	z0:sort[a0].(~(z0=0)->g'(z0, z0)=true)
4.50/2.10	
4.50/2.10	
4.50/2.10	The transformed set:
4.50/2.10	g'(X, Y) -> true
4.50/2.10	g(X, Y) -> X
4.50/2.10	g(X', Y') -> Y'
4.50/2.10	equal_bool(true, false) -> false
4.50/2.10	equal_bool(false, true) -> false
4.50/2.10	equal_bool(true, true) -> true
4.50/2.10	equal_bool(false, false) -> true
4.50/2.10	and(true, x) -> x
4.50/2.10	and(false, x) -> false
4.50/2.10	or(true, x) -> true
4.50/2.10	or(false, x) -> x
4.50/2.10	not(false) -> true
4.50/2.10	not(true) -> false
4.50/2.10	isa_true(true) -> true
4.50/2.10	isa_true(false) -> false
4.50/2.10	isa_false(true) -> false
4.50/2.10	isa_false(false) -> true
4.50/2.10	equal_sort[a0](0, 0) -> true
4.50/2.10	equal_sort[a0](0, 1) -> false
4.50/2.10	equal_sort[a0](1, 0) -> false
4.50/2.10	equal_sort[a0](1, 1) -> true
4.50/2.10	equal_sort[a10](witness_sort[a10], witness_sort[a10]) -> true
4.50/2.10	
4.50/2.10	
4.50/2.10	The proof given by the theorem prover:
4.50/2.10	The following output was given by the internal theorem prover:proof of internal
4.50/2.10	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.50/2.10	
4.50/2.10	
4.50/2.10	Partial correctness of the following Program
4.50/2.10	
4.50/2.10	   [x, X, Y, X', Y']
4.50/2.10	   equal_bool(true, false) -> false
4.50/2.10	   equal_bool(false, true) -> false
4.50/2.10	   equal_bool(true, true) -> true
4.50/2.10	   equal_bool(false, false) -> true
4.50/2.10	   true and x -> x
4.50/2.10	   false and x -> false
4.50/2.10	   true or x -> true
4.50/2.10	   false or x -> x
4.50/2.10	   not(false) -> true
4.50/2.10	   not(true) -> false
4.50/2.10	   isa_true(true) -> true
4.50/2.10	   isa_true(false) -> false
4.50/2.10	   isa_false(true) -> false
4.50/2.10	   isa_false(false) -> true
4.50/2.10	   equal_sort[a0](0, 0) -> true
4.50/2.10	   equal_sort[a0](0, 1) -> false
4.50/2.10	   equal_sort[a0](1, 0) -> false
4.50/2.10	   equal_sort[a0](1, 1) -> true
4.50/2.10	   equal_sort[a10](witness_sort[a10], witness_sort[a10]) -> true
4.50/2.10	   g'(X, Y) -> true
4.50/2.10	   g(X, Y) -> X
4.50/2.10	   g(X', Y') -> Y'
4.50/2.10	
4.50/2.10	using the following formula:
4.50/2.10	z0:sort[a0].(~(z0=0)->g'(z0, z0)=true)
4.50/2.10	
4.50/2.10	could be successfully shown:
4.50/2.10	(0) Formula
4.50/2.10	(1) Symbolic evaluation [EQUIVALENT, 0 ms]
4.50/2.10	(2) YES
4.50/2.10	
4.50/2.10	
4.50/2.10	----------------------------------------
4.50/2.10	
4.50/2.10	(0)
4.50/2.10	Obligation:
4.50/2.10	Formula:
4.50/2.10	z0:sort[a0].(~(z0=0)->g'(z0, z0)=true)
4.50/2.10	
4.50/2.10	There are no hypotheses.
4.50/2.10	
4.50/2.10	
4.50/2.10	
4.50/2.10	
4.50/2.10	----------------------------------------
4.50/2.10	
4.50/2.10	(1) Symbolic evaluation (EQUIVALENT)
4.50/2.10	Could be reduced to the following new obligation by simple symbolic evaluation:
4.50/2.10	True
4.50/2.10	----------------------------------------
4.50/2.10	
4.50/2.10	(2)
4.50/2.10	YES
4.50/2.10	
4.50/2.10	----------------------------------------
4.50/2.10	
4.50/2.10	(12)
4.50/2.10	Complex Obligation (AND)
4.50/2.10	
4.50/2.10	----------------------------------------
4.50/2.10	
4.50/2.10	(13)
4.50/2.10	Obligation:
4.50/2.10	Q DP problem:
4.50/2.10	P is empty.
4.50/2.10	The TRS R consists of the following rules:
4.50/2.10	
4.50/2.10	   g(X, Y) -> X
4.50/2.10	   g(X, Y) -> Y
4.50/2.10	
4.50/2.10	The set Q consists of the following terms:
4.50/2.10	
4.50/2.10	   g(x0, x1)
4.50/2.10	
4.50/2.10	We have to consider all minimal (P,Q,R)-chains.
4.50/2.10	----------------------------------------
4.50/2.10	
4.50/2.10	(14) PisEmptyProof (EQUIVALENT)
4.50/2.10	The TRS P is empty. Hence, there is no (P,Q,R) chain.
4.50/2.10	----------------------------------------
4.50/2.10	
4.50/2.10	(15)
4.50/2.10	YES
4.50/2.10	
4.50/2.10	----------------------------------------
4.50/2.10	
4.50/2.10	(16)
4.50/2.10	Obligation:
4.50/2.10	Q restricted rewrite system:
4.50/2.10	The TRS R consists of the following rules:
4.50/2.10	
4.50/2.10	   g'(X, Y) -> true
4.50/2.10	   g(X, Y) -> X
4.50/2.10	   g(X', Y') -> Y'
4.50/2.10	   equal_bool(true, false) -> false
4.50/2.10	   equal_bool(false, true) -> false
4.50/2.10	   equal_bool(true, true) -> true
4.50/2.10	   equal_bool(false, false) -> true
4.50/2.10	   and(true, x) -> x
4.50/2.10	   and(false, x) -> false
4.50/2.10	   or(true, x) -> true
4.50/2.10	   or(false, x) -> x
4.50/2.10	   not(false) -> true
4.50/2.10	   not(true) -> false
4.50/2.10	   isa_true(true) -> true
4.50/2.10	   isa_true(false) -> false
4.50/2.10	   isa_false(true) -> false
4.50/2.10	   isa_false(false) -> true
4.50/2.10	   equal_sort[a0](0, 0) -> true
4.50/2.10	   equal_sort[a0](0, 1) -> false
4.50/2.10	   equal_sort[a0](1, 0) -> false
4.50/2.10	   equal_sort[a0](1, 1) -> true
4.50/2.10	   equal_sort[a10](witness_sort[a10], witness_sort[a10]) -> true
4.50/2.10	
4.50/2.10	Q is empty.
4.50/2.10	
4.50/2.10	----------------------------------------
4.50/2.10	
4.50/2.10	(17) QTRSRRRProof (EQUIVALENT)
4.50/2.10	Used ordering:
4.50/2.10	Polynomial interpretation [POLO]:
4.50/2.10	
4.50/2.10	   POL(0) = 0
4.50/2.10	   POL(1) = 0
4.50/2.10	   POL(and(x_1, x_2)) = 2 + 2*x_1 + x_2
4.50/2.10	   POL(equal_bool(x_1, x_2)) = 2*x_1 + x_2
4.50/2.10	   POL(equal_sort[a0](x_1, x_2)) = x_1 + x_2
4.50/2.10	   POL(equal_sort[a10](x_1, x_2)) = x_1 + x_2
4.50/2.10	   POL(false) = 0
4.50/2.10	   POL(g(x_1, x_2)) = x_1 + x_2
4.50/2.10	   POL(g'(x_1, x_2)) = 2 + x_1 + x_2
4.50/2.10	   POL(isa_false(x_1)) = x_1
4.50/2.10	   POL(isa_true(x_1)) = x_1
4.50/2.10	   POL(not(x_1)) = x_1
4.50/2.10	   POL(or(x_1, x_2)) = 2 + 2*x_1 + x_2
4.50/2.10	   POL(true) = 0
4.50/2.10	   POL(witness_sort[a10]) = 0
4.50/2.10	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
4.50/2.10	
4.50/2.10	   g'(X, Y) -> true
4.50/2.10	   and(true, x) -> x
4.50/2.10	   and(false, x) -> false
4.50/2.10	   or(true, x) -> true
4.50/2.10	   or(false, x) -> x
4.50/2.10	
4.50/2.10	
4.50/2.10	
4.50/2.10	
4.50/2.10	----------------------------------------
4.50/2.10	
4.50/2.10	(18)
4.50/2.10	Obligation:
4.50/2.10	Q restricted rewrite system:
4.50/2.10	The TRS R consists of the following rules:
4.50/2.10	
4.50/2.10	   g(X, Y) -> X
4.50/2.10	   g(X', Y') -> Y'
4.50/2.10	   equal_bool(true, false) -> false
4.50/2.10	   equal_bool(false, true) -> false
4.50/2.10	   equal_bool(true, true) -> true
4.50/2.10	   equal_bool(false, false) -> true
4.50/2.10	   not(false) -> true
4.50/2.10	   not(true) -> false
4.50/2.10	   isa_true(true) -> true
4.50/2.10	   isa_true(false) -> false
4.50/2.10	   isa_false(true) -> false
4.50/2.10	   isa_false(false) -> true
4.50/2.10	   equal_sort[a0](0, 0) -> true
4.50/2.10	   equal_sort[a0](0, 1) -> false
4.50/2.10	   equal_sort[a0](1, 0) -> false
4.50/2.10	   equal_sort[a0](1, 1) -> true
4.50/2.10	   equal_sort[a10](witness_sort[a10], witness_sort[a10]) -> true
4.50/2.10	
4.50/2.10	Q is empty.
4.50/2.10	
4.50/2.10	----------------------------------------
4.50/2.10	
4.50/2.10	(19) QTRSRRRProof (EQUIVALENT)
4.50/2.10	Used ordering:
4.50/2.10	Knuth-Bendix order [KBO] with precedence:isa_false_1 > witness_sort[a10] > equal_sort[a10]_2 > equal_bool_2 > 1 > 0 > g_2 > equal_sort[a0]_2 > true > isa_true_1 > not_1 > false
4.50/2.10	
4.50/2.10	and weight map:
4.50/2.10	
4.50/2.10	   true=2
4.50/2.10	   false=2
4.50/2.10	   0=1
4.50/2.10	   1=1
4.50/2.10	   witness_sort[a10]=1
4.50/2.10	   not_1=1
4.50/2.10	   isa_true_1=1
4.50/2.10	   isa_false_1=0
4.50/2.10	   g_2=0
4.50/2.10	   equal_bool_2=0
4.50/2.10	   equal_sort[a0]_2=0
4.50/2.10	   equal_sort[a10]_2=0
4.50/2.10	
4.50/2.10	The variable weight is 1With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
4.50/2.10	
4.50/2.10	   g(X, Y) -> X
4.50/2.10	   g(X', Y') -> Y'
4.50/2.10	   equal_bool(true, false) -> false
4.50/2.10	   equal_bool(false, true) -> false
4.50/2.10	   equal_bool(true, true) -> true
4.50/2.10	   equal_bool(false, false) -> true
4.50/2.10	   not(false) -> true
4.50/2.10	   not(true) -> false
4.50/2.10	   isa_true(true) -> true
4.50/2.10	   isa_true(false) -> false
4.50/2.10	   isa_false(true) -> false
4.50/2.10	   isa_false(false) -> true
4.50/2.10	   equal_sort[a0](0, 0) -> true
4.50/2.10	   equal_sort[a0](0, 1) -> false
4.50/2.10	   equal_sort[a0](1, 0) -> false
4.50/2.10	   equal_sort[a0](1, 1) -> true
4.50/2.10	   equal_sort[a10](witness_sort[a10], witness_sort[a10]) -> true
4.50/2.10	
4.50/2.10	
4.50/2.10	
4.50/2.10	
4.50/2.10	----------------------------------------
4.50/2.10	
4.50/2.10	(20)
4.50/2.10	Obligation:
4.50/2.10	Q restricted rewrite system:
4.50/2.10	R is empty.
4.50/2.10	Q is empty.
4.50/2.10	
4.50/2.10	----------------------------------------
4.50/2.10	
4.50/2.10	(21) RisEmptyProof (EQUIVALENT)
4.50/2.10	The TRS R is empty. Hence, termination is trivially proven.
4.50/2.10	----------------------------------------
4.50/2.10	
4.50/2.10	(22)
4.50/2.10	YES
4.53/2.13	EOF