/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files
--------------------------------------------------------------------------------
MAYBE
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
Outermost Termination of the given OTRS could not be shown:
(0) OTRS
(1) Thiemann-SpecialC-Transformation [EQUIVALENT, 0 ms]
(2) QTRS
(3) QTRSRRRProof [EQUIVALENT, 33 ms]
(4) QTRS
(5) DependencyPairsProof [EQUIVALENT, 0 ms]
(6) QDP
(7) DependencyGraphProof [EQUIVALENT, 0 ms]
(8) AND
(9) QDP
(10) UsableRulesProof [EQUIVALENT, 0 ms]
(11) QDP
(12) QReductionProof [EQUIVALENT, 0 ms]
(13) QDP
(14) MRRProof [EQUIVALENT, 0 ms]
(15) QDP
(16) MRRProof [EQUIVALENT, 7 ms]
(17) QDP
(18) DependencyGraphProof [EQUIVALENT, 0 ms]
(19) QDP
(20) UsableRulesProof [EQUIVALENT, 0 ms]
(21) QDP
(22) QReductionProof [EQUIVALENT, 0 ms]
(23) QDP
(24) UsableRulesReductionPairsProof [EQUIVALENT, 8 ms]
(25) QDP
(26) DependencyGraphProof [EQUIVALENT, 0 ms]
(27) TRUE
(28) QDP
(29) UsableRulesProof [EQUIVALENT, 0 ms]
(30) QDP
(31) QReductionProof [EQUIVALENT, 0 ms]
(32) QDP
(33) TransformationProof [SOUND, 0 ms]
(34) QDP
(35) UsableRulesProof [EQUIVALENT, 0 ms]
(36) QDP
(37) QReductionProof [EQUIVALENT, 0 ms]
(38) QDP
(39) Trivial-Transformation [SOUND, 0 ms]
(40) QTRS
(41) QTRSRRRProof [EQUIVALENT, 55 ms]
(42) QTRS
(43) AAECC Innermost [EQUIVALENT, 0 ms]
(44) QTRS
(45) DependencyPairsProof [EQUIVALENT, 0 ms]
(46) QDP
(47) DependencyGraphProof [EQUIVALENT, 0 ms]
(48) QDP
(49) UsableRulesProof [EQUIVALENT, 0 ms]
(50) QDP
(51) QReductionProof [EQUIVALENT, 0 ms]
(52) QDP
(53) TransformationProof [EQUIVALENT, 0 ms]
(54) QDP
(55) TransformationProof [EQUIVALENT, 0 ms]
(56) QDP
(57) TransformationProof [EQUIVALENT, 0 ms]
(58) QDP
(59) TransformationProof [EQUIVALENT, 0 ms]
(60) QDP
(61) TransformationProof [EQUIVALENT, 0 ms]
(62) QDP
(63) UsableRulesProof [EQUIVALENT, 0 ms]
(64) QDP
(65) QReductionProof [EQUIVALENT, 0 ms]
(66) QDP
(67) NonTerminationLoopProof [COMPLETE, 0 ms]
(68) NO
(69) Raffelsieper-Zantema-Transformation [SOUND, 0 ms]
(70) QTRS
(71) QTRSRRRProof [EQUIVALENT, 83 ms]
(72) QTRS
(73) AAECC Innermost [EQUIVALENT, 0 ms]
(74) QTRS
(75) DependencyPairsProof [EQUIVALENT, 0 ms]
(76) QDP
(77) DependencyGraphProof [EQUIVALENT, 0 ms]
(78) AND
(79) QDP
(80) UsableRulesProof [EQUIVALENT, 0 ms]
(81) QDP
(82) QReductionProof [EQUIVALENT, 0 ms]
(83) QDP
(84) QDPSizeChangeProof [EQUIVALENT, 0 ms]
(85) YES
(86) QDP
(87) UsableRulesProof [EQUIVALENT, 0 ms]
(88) QDP
(89) QReductionProof [EQUIVALENT, 0 ms]
(90) QDP
(91) TransformationProof [EQUIVALENT, 0 ms]
(92) QDP
(93) DependencyGraphProof [EQUIVALENT, 0 ms]
(94) QDP
(95) TransformationProof [EQUIVALENT, 0 ms]
(96) QDP
(97) TransformationProof [EQUIVALENT, 0 ms]
(98) QDP
(99) TransformationProof [EQUIVALENT, 0 ms]
(100) QDP
(101) DependencyGraphProof [EQUIVALENT, 0 ms]
(102) QDP
(103) TransformationProof [EQUIVALENT, 0 ms]
(104) QDP
(105) DependencyGraphProof [EQUIVALENT, 0 ms]
(106) QDP
(107) QDPOrderProof [EQUIVALENT, 11 ms]
(108) QDP
(109) MNOCProof [EQUIVALENT, 0 ms]
(110) QDP
(111) SplitQDPProof [EQUIVALENT, 0 ms]
(112) AND
(113) QDP
(114) SemLabProof [SOUND, 0 ms]
(115) QDP
(116) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
(117) QDP
(118) DependencyGraphProof [EQUIVALENT, 0 ms]
(119) QDP
(120) PisEmptyProof [SOUND, 0 ms]
(121) TRUE
(122) QDP
(123) SplitQDPProof [EQUIVALENT, 0 ms]
(124) AND
(125) QDP
(126) SemLabProof [SOUND, 0 ms]
(127) QDP
(128) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
(129) QDP
(130) DependencyGraphProof [EQUIVALENT, 0 ms]
(131) QDP
(132) PisEmptyProof [SOUND, 0 ms]
(133) TRUE
(134) QDP
(135) SplitQDPProof [EQUIVALENT, 0 ms]
(136) AND
(137) QDP
(138) SemLabProof [SOUND, 0 ms]
(139) QDP
(140) MRRProof [EQUIVALENT, 0 ms]
(141) QDP
(142) DependencyGraphProof [EQUIVALENT, 0 ms]
(143) QDP
(144) UsableRulesReductionPairsProof [EQUIVALENT, 3 ms]
(145) QDP
(146) MRRProof [EQUIVALENT, 0 ms]
(147) QDP
(148) PisEmptyProof [SOUND, 0 ms]
(149) TRUE
(150) QDP
(151) QReductionProof [EQUIVALENT, 0 ms]
(152) QDP
(153) SplitQDPProof [EQUIVALENT, 0 ms]
(154) AND
(155) QDP
(156) SemLabProof [SOUND, 0 ms]
(157) QDP
(158) MRRProof [EQUIVALENT, 0 ms]
(159) QDP
(160) DependencyGraphProof [EQUIVALENT, 0 ms]
(161) QDP
(162) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
(163) QDP
(164) MRRProof [EQUIVALENT, 0 ms]
(165) QDP
(166) PisEmptyProof [SOUND, 0 ms]
(167) TRUE
(168) QDP
(169) QReductionProof [EQUIVALENT, 0 ms]
(170) QDP
(171) MNOCProof [EQUIVALENT, 0 ms]
(172) QDP
----------------------------------------
(0)
Obligation:
Term rewrite system R:
The TRS R consists of the following rules:
g(b) -> g(f(f(f(f(f(b))))))
f(b) -> b
g(f(b)) -> c
Outermost Strategy.
----------------------------------------
(1) Thiemann-SpecialC-Transformation (EQUIVALENT)
We applied the Thiemann-SpecialC transformation to transform the outermost TRS to an innermost TRS.
----------------------------------------
(2)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:
top(go_up(x)) -> top(reduce(x))
reduce(g(x_1)) -> check_g(redex_g(x_1))
reduce(f(x_1)) -> check_f(redex_f(x_1))
redex_g(b) -> result_g(g(f(f(f(f(f(b)))))))
redex_f(b) -> result_f(b)
redex_g(f(b)) -> result_g(c)
check_g(result_g(x)) -> go_up(x)
check_f(result_f(x)) -> go_up(x)
check_g(redex_g(x_1)) -> in_g_1(reduce(x_1))
check_f(redex_f(x_1)) -> in_f_1(reduce(x_1))
in_g_1(go_up(x_1)) -> go_up(g(x_1))
in_f_1(go_up(x_1)) -> go_up(f(x_1))
The set Q consists of the following terms:
top(go_up(x0))
reduce(g(x0))
reduce(f(x0))
redex_g(b)
redex_f(b)
redex_g(f(b))
check_g(result_g(x0))
check_f(result_f(x0))
check_g(redex_g(x0))
check_f(redex_f(x0))
in_g_1(go_up(x0))
in_f_1(go_up(x0))
----------------------------------------
(3) QTRSRRRProof (EQUIVALENT)
Used ordering:
Polynomial interpretation [POLO]:
POL(b) = 0
POL(c) = 0
POL(check_f(x_1)) = 2*x_1
POL(check_g(x_1)) = 2*x_1
POL(f(x_1)) = 2*x_1
POL(g(x_1)) = 1 + 2*x_1
POL(go_up(x_1)) = 2*x_1
POL(in_f_1(x_1)) = 2*x_1
POL(in_g_1(x_1)) = 2 + 2*x_1
POL(redex_f(x_1)) = 2*x_1
POL(redex_g(x_1)) = 1 + 2*x_1
POL(reduce(x_1)) = 2*x_1
POL(result_f(x_1)) = 2*x_1
POL(result_g(x_1)) = x_1
POL(top(x_1)) = 2*x_1
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
redex_g(f(b)) -> result_g(c)
----------------------------------------
(4)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:
top(go_up(x)) -> top(reduce(x))
reduce(g(x_1)) -> check_g(redex_g(x_1))
reduce(f(x_1)) -> check_f(redex_f(x_1))
redex_g(b) -> result_g(g(f(f(f(f(f(b)))))))
redex_f(b) -> result_f(b)
check_g(result_g(x)) -> go_up(x)
check_f(result_f(x)) -> go_up(x)
check_g(redex_g(x_1)) -> in_g_1(reduce(x_1))
check_f(redex_f(x_1)) -> in_f_1(reduce(x_1))
in_g_1(go_up(x_1)) -> go_up(g(x_1))
in_f_1(go_up(x_1)) -> go_up(f(x_1))
The set Q consists of the following terms:
top(go_up(x0))
reduce(g(x0))
reduce(f(x0))
redex_g(b)
redex_f(b)
redex_g(f(b))
check_g(result_g(x0))
check_f(result_f(x0))
check_g(redex_g(x0))
check_f(redex_f(x0))
in_g_1(go_up(x0))
in_f_1(go_up(x0))
----------------------------------------
(5) DependencyPairsProof (EQUIVALENT)
Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
----------------------------------------
(6)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(go_up(x)) -> TOP(reduce(x))
TOP(go_up(x)) -> REDUCE(x)
REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1))
REDUCE(g(x_1)) -> REDEX_G(x_1)
REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1))
REDUCE(f(x_1)) -> REDEX_F(x_1)
CHECK_G(redex_g(x_1)) -> IN_G_1(reduce(x_1))
CHECK_G(redex_g(x_1)) -> REDUCE(x_1)
CHECK_F(redex_f(x_1)) -> IN_F_1(reduce(x_1))
CHECK_F(redex_f(x_1)) -> REDUCE(x_1)
The TRS R consists of the following rules:
top(go_up(x)) -> top(reduce(x))
reduce(g(x_1)) -> check_g(redex_g(x_1))
reduce(f(x_1)) -> check_f(redex_f(x_1))
redex_g(b) -> result_g(g(f(f(f(f(f(b)))))))
redex_f(b) -> result_f(b)
check_g(result_g(x)) -> go_up(x)
check_f(result_f(x)) -> go_up(x)
check_g(redex_g(x_1)) -> in_g_1(reduce(x_1))
check_f(redex_f(x_1)) -> in_f_1(reduce(x_1))
in_g_1(go_up(x_1)) -> go_up(g(x_1))
in_f_1(go_up(x_1)) -> go_up(f(x_1))
The set Q consists of the following terms:
top(go_up(x0))
reduce(g(x0))
reduce(f(x0))
redex_g(b)
redex_f(b)
redex_g(f(b))
check_g(result_g(x0))
check_f(result_f(x0))
check_g(redex_g(x0))
check_f(redex_f(x0))
in_g_1(go_up(x0))
in_f_1(go_up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(7) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 5 less nodes.
----------------------------------------
(8)
Complex Obligation (AND)
----------------------------------------
(9)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
CHECK_G(redex_g(x_1)) -> REDUCE(x_1)
REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1))
REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1))
CHECK_F(redex_f(x_1)) -> REDUCE(x_1)
The TRS R consists of the following rules:
top(go_up(x)) -> top(reduce(x))
reduce(g(x_1)) -> check_g(redex_g(x_1))
reduce(f(x_1)) -> check_f(redex_f(x_1))
redex_g(b) -> result_g(g(f(f(f(f(f(b)))))))
redex_f(b) -> result_f(b)
check_g(result_g(x)) -> go_up(x)
check_f(result_f(x)) -> go_up(x)
check_g(redex_g(x_1)) -> in_g_1(reduce(x_1))
check_f(redex_f(x_1)) -> in_f_1(reduce(x_1))
in_g_1(go_up(x_1)) -> go_up(g(x_1))
in_f_1(go_up(x_1)) -> go_up(f(x_1))
The set Q consists of the following terms:
top(go_up(x0))
reduce(g(x0))
reduce(f(x0))
redex_g(b)
redex_f(b)
redex_g(f(b))
check_g(result_g(x0))
check_f(result_f(x0))
check_g(redex_g(x0))
check_f(redex_f(x0))
in_g_1(go_up(x0))
in_f_1(go_up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(10) UsableRulesProof (EQUIVALENT)
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.
----------------------------------------
(11)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
CHECK_G(redex_g(x_1)) -> REDUCE(x_1)
REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1))
REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1))
CHECK_F(redex_f(x_1)) -> REDUCE(x_1)
The TRS R consists of the following rules:
redex_f(b) -> result_f(b)
redex_g(b) -> result_g(g(f(f(f(f(f(b)))))))
The set Q consists of the following terms:
top(go_up(x0))
reduce(g(x0))
reduce(f(x0))
redex_g(b)
redex_f(b)
redex_g(f(b))
check_g(result_g(x0))
check_f(result_f(x0))
check_g(redex_g(x0))
check_f(redex_f(x0))
in_g_1(go_up(x0))
in_f_1(go_up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(12) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
top(go_up(x0))
reduce(g(x0))
reduce(f(x0))
check_g(result_g(x0))
check_f(result_f(x0))
check_g(redex_g(x0))
check_f(redex_f(x0))
in_g_1(go_up(x0))
in_f_1(go_up(x0))
----------------------------------------
(13)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
CHECK_G(redex_g(x_1)) -> REDUCE(x_1)
REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1))
REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1))
CHECK_F(redex_f(x_1)) -> REDUCE(x_1)
The TRS R consists of the following rules:
redex_f(b) -> result_f(b)
redex_g(b) -> result_g(g(f(f(f(f(f(b)))))))
The set Q consists of the following terms:
redex_g(b)
redex_f(b)
redex_g(f(b))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(14) MRRProof (EQUIVALENT)
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.
Strictly oriented rules of the TRS R:
redex_f(b) -> result_f(b)
Used ordering: Polynomial interpretation [POLO]:
POL(CHECK_F(x_1)) = x_1
POL(CHECK_G(x_1)) = 1 + 2*x_1
POL(REDUCE(x_1)) = 1 + 2*x_1
POL(b) = 0
POL(f(x_1)) = 2*x_1
POL(g(x_1)) = x_1
POL(redex_f(x_1)) = 1 + 2*x_1
POL(redex_g(x_1)) = x_1
POL(result_f(x_1)) = x_1
POL(result_g(x_1)) = 2*x_1
----------------------------------------
(15)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
CHECK_G(redex_g(x_1)) -> REDUCE(x_1)
REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1))
REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1))
CHECK_F(redex_f(x_1)) -> REDUCE(x_1)
The TRS R consists of the following rules:
redex_g(b) -> result_g(g(f(f(f(f(f(b)))))))
The set Q consists of the following terms:
redex_g(b)
redex_f(b)
redex_g(f(b))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(16) MRRProof (EQUIVALENT)
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.
Strictly oriented dependency pairs:
CHECK_G(redex_g(x_1)) -> REDUCE(x_1)
Used ordering: Polynomial interpretation [POLO]:
POL(CHECK_F(x_1)) = 2*x_1
POL(CHECK_G(x_1)) = 2*x_1
POL(REDUCE(x_1)) = 2*x_1
POL(b) = 0
POL(f(x_1)) = 2*x_1
POL(g(x_1)) = 1 + 2*x_1
POL(redex_f(x_1)) = 2*x_1
POL(redex_g(x_1)) = 1 + x_1
POL(result_g(x_1)) = x_1
----------------------------------------
(17)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1))
REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1))
CHECK_F(redex_f(x_1)) -> REDUCE(x_1)
The TRS R consists of the following rules:
redex_g(b) -> result_g(g(f(f(f(f(f(b)))))))
The set Q consists of the following terms:
redex_g(b)
redex_f(b)
redex_g(f(b))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(18) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node.
----------------------------------------
(19)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1))
CHECK_F(redex_f(x_1)) -> REDUCE(x_1)
The TRS R consists of the following rules:
redex_g(b) -> result_g(g(f(f(f(f(f(b)))))))
The set Q consists of the following terms:
redex_g(b)
redex_f(b)
redex_g(f(b))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(20) UsableRulesProof (EQUIVALENT)
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.
----------------------------------------
(21)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1))
CHECK_F(redex_f(x_1)) -> REDUCE(x_1)
R is empty.
The set Q consists of the following terms:
redex_g(b)
redex_f(b)
redex_g(f(b))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(22) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
redex_g(b)
redex_g(f(b))
----------------------------------------
(23)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1))
CHECK_F(redex_f(x_1)) -> REDUCE(x_1)
R is empty.
The set Q consists of the following terms:
redex_f(b)
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(24) UsableRulesReductionPairsProof (EQUIVALENT)
By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.
The following dependency pairs can be deleted:
REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1))
No rules are removed from R.
Used ordering: POLO with Polynomial interpretation [POLO]:
POL(CHECK_F(x_1)) = 2*x_1
POL(REDUCE(x_1)) = 2*x_1
POL(f(x_1)) = 2*x_1
POL(redex_f(x_1)) = x_1
----------------------------------------
(25)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
CHECK_F(redex_f(x_1)) -> REDUCE(x_1)
R is empty.
The set Q consists of the following terms:
redex_f(b)
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(26) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node.
----------------------------------------
(27)
TRUE
----------------------------------------
(28)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(go_up(x)) -> TOP(reduce(x))
The TRS R consists of the following rules:
top(go_up(x)) -> top(reduce(x))
reduce(g(x_1)) -> check_g(redex_g(x_1))
reduce(f(x_1)) -> check_f(redex_f(x_1))
redex_g(b) -> result_g(g(f(f(f(f(f(b)))))))
redex_f(b) -> result_f(b)
check_g(result_g(x)) -> go_up(x)
check_f(result_f(x)) -> go_up(x)
check_g(redex_g(x_1)) -> in_g_1(reduce(x_1))
check_f(redex_f(x_1)) -> in_f_1(reduce(x_1))
in_g_1(go_up(x_1)) -> go_up(g(x_1))
in_f_1(go_up(x_1)) -> go_up(f(x_1))
The set Q consists of the following terms:
top(go_up(x0))
reduce(g(x0))
reduce(f(x0))
redex_g(b)
redex_f(b)
redex_g(f(b))
check_g(result_g(x0))
check_f(result_f(x0))
check_g(redex_g(x0))
check_f(redex_f(x0))
in_g_1(go_up(x0))
in_f_1(go_up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(29) UsableRulesProof (EQUIVALENT)
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.
----------------------------------------
(30)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(go_up(x)) -> TOP(reduce(x))
The TRS R consists of the following rules:
reduce(g(x_1)) -> check_g(redex_g(x_1))
reduce(f(x_1)) -> check_f(redex_f(x_1))
redex_f(b) -> result_f(b)
check_f(result_f(x)) -> go_up(x)
check_f(redex_f(x_1)) -> in_f_1(reduce(x_1))
in_f_1(go_up(x_1)) -> go_up(f(x_1))
redex_g(b) -> result_g(g(f(f(f(f(f(b)))))))
check_g(result_g(x)) -> go_up(x)
check_g(redex_g(x_1)) -> in_g_1(reduce(x_1))
in_g_1(go_up(x_1)) -> go_up(g(x_1))
The set Q consists of the following terms:
top(go_up(x0))
reduce(g(x0))
reduce(f(x0))
redex_g(b)
redex_f(b)
redex_g(f(b))
check_g(result_g(x0))
check_f(result_f(x0))
check_g(redex_g(x0))
check_f(redex_f(x0))
in_g_1(go_up(x0))
in_f_1(go_up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(31) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
top(go_up(x0))
----------------------------------------
(32)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(go_up(x)) -> TOP(reduce(x))
The TRS R consists of the following rules:
reduce(g(x_1)) -> check_g(redex_g(x_1))
reduce(f(x_1)) -> check_f(redex_f(x_1))
redex_f(b) -> result_f(b)
check_f(result_f(x)) -> go_up(x)
check_f(redex_f(x_1)) -> in_f_1(reduce(x_1))
in_f_1(go_up(x_1)) -> go_up(f(x_1))
redex_g(b) -> result_g(g(f(f(f(f(f(b)))))))
check_g(result_g(x)) -> go_up(x)
check_g(redex_g(x_1)) -> in_g_1(reduce(x_1))
in_g_1(go_up(x_1)) -> go_up(g(x_1))
The set Q consists of the following terms:
reduce(g(x0))
reduce(f(x0))
redex_g(b)
redex_f(b)
redex_g(f(b))
check_g(result_g(x0))
check_f(result_f(x0))
check_g(redex_g(x0))
check_f(redex_f(x0))
in_g_1(go_up(x0))
in_f_1(go_up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(33) TransformationProof (SOUND)
By narrowing [LPAR04] the rule TOP(go_up(x)) -> TOP(reduce(x)) at position [0] we obtained the following new rules [LPAR04]:
(TOP(go_up(g(x0))) -> TOP(check_g(redex_g(x0))),TOP(go_up(g(x0))) -> TOP(check_g(redex_g(x0))))
(TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))),TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))))
----------------------------------------
(34)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(go_up(g(x0))) -> TOP(check_g(redex_g(x0)))
TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0)))
The TRS R consists of the following rules:
reduce(g(x_1)) -> check_g(redex_g(x_1))
reduce(f(x_1)) -> check_f(redex_f(x_1))
redex_f(b) -> result_f(b)
check_f(result_f(x)) -> go_up(x)
check_f(redex_f(x_1)) -> in_f_1(reduce(x_1))
in_f_1(go_up(x_1)) -> go_up(f(x_1))
redex_g(b) -> result_g(g(f(f(f(f(f(b)))))))
check_g(result_g(x)) -> go_up(x)
check_g(redex_g(x_1)) -> in_g_1(reduce(x_1))
in_g_1(go_up(x_1)) -> go_up(g(x_1))
The set Q consists of the following terms:
reduce(g(x0))
reduce(f(x0))
redex_g(b)
redex_f(b)
redex_g(f(b))
check_g(result_g(x0))
check_f(result_f(x0))
check_g(redex_g(x0))
check_f(redex_f(x0))
in_g_1(go_up(x0))
in_f_1(go_up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(35) UsableRulesProof (EQUIVALENT)
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.
----------------------------------------
(36)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(go_up(x)) -> TOP(reduce(x))
The TRS R consists of the following rules:
reduce(g(x_1)) -> check_g(redex_g(x_1))
reduce(f(x_1)) -> check_f(redex_f(x_1))
redex_f(b) -> result_f(b)
check_f(result_f(x)) -> go_up(x)
check_f(redex_f(x_1)) -> in_f_1(reduce(x_1))
in_f_1(go_up(x_1)) -> go_up(f(x_1))
redex_g(b) -> result_g(g(f(f(f(f(f(b)))))))
check_g(result_g(x)) -> go_up(x)
check_g(redex_g(x_1)) -> in_g_1(reduce(x_1))
in_g_1(go_up(x_1)) -> go_up(g(x_1))
The set Q consists of the following terms:
top(go_up(x0))
reduce(g(x0))
reduce(f(x0))
redex_g(b)
redex_f(b)
redex_g(f(b))
check_g(result_g(x0))
check_f(result_f(x0))
check_g(redex_g(x0))
check_f(redex_f(x0))
in_g_1(go_up(x0))
in_f_1(go_up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(37) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
top(go_up(x0))
----------------------------------------
(38)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(go_up(x)) -> TOP(reduce(x))
The TRS R consists of the following rules:
reduce(g(x_1)) -> check_g(redex_g(x_1))
reduce(f(x_1)) -> check_f(redex_f(x_1))
redex_f(b) -> result_f(b)
check_f(result_f(x)) -> go_up(x)
check_f(redex_f(x_1)) -> in_f_1(reduce(x_1))
in_f_1(go_up(x_1)) -> go_up(f(x_1))
redex_g(b) -> result_g(g(f(f(f(f(f(b)))))))
check_g(result_g(x)) -> go_up(x)
check_g(redex_g(x_1)) -> in_g_1(reduce(x_1))
in_g_1(go_up(x_1)) -> go_up(g(x_1))
The set Q consists of the following terms:
reduce(g(x0))
reduce(f(x0))
redex_g(b)
redex_f(b)
redex_g(f(b))
check_g(result_g(x0))
check_f(result_f(x0))
check_g(redex_g(x0))
check_f(redex_f(x0))
in_g_1(go_up(x0))
in_f_1(go_up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(39) Trivial-Transformation (SOUND)
We applied the Trivial transformation to transform the outermost TRS to a standard TRS.
----------------------------------------
(40)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:
g(b) -> g(f(f(f(f(f(b))))))
f(b) -> b
g(f(b)) -> c
Q is empty.
----------------------------------------
(41) QTRSRRRProof (EQUIVALENT)
Used ordering:
Polynomial interpretation [POLO]:
POL(b) = 0
POL(c) = 0
POL(f(x_1)) = x_1
POL(g(x_1)) = 1 + 2*x_1
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
g(f(b)) -> c
----------------------------------------
(42)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:
g(b) -> g(f(f(f(f(f(b))))))
f(b) -> b
Q is empty.
----------------------------------------
(43) AAECC Innermost (EQUIVALENT)
We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is
f(b) -> b
The TRS R 2 is
g(b) -> g(f(f(f(f(f(b))))))
The signature Sigma is {g_1}
----------------------------------------
(44)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:
g(b) -> g(f(f(f(f(f(b))))))
f(b) -> b
The set Q consists of the following terms:
g(b)
f(b)
----------------------------------------
(45) DependencyPairsProof (EQUIVALENT)
Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
----------------------------------------
(46)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
G(b) -> G(f(f(f(f(f(b))))))
G(b) -> F(f(f(f(f(b)))))
G(b) -> F(f(f(f(b))))
G(b) -> F(f(f(b)))
G(b) -> F(f(b))
G(b) -> F(b)
The TRS R consists of the following rules:
g(b) -> g(f(f(f(f(f(b))))))
f(b) -> b
The set Q consists of the following terms:
g(b)
f(b)
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(47) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 5 less nodes.
----------------------------------------
(48)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
G(b) -> G(f(f(f(f(f(b))))))
The TRS R consists of the following rules:
g(b) -> g(f(f(f(f(f(b))))))
f(b) -> b
The set Q consists of the following terms:
g(b)
f(b)
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(49) UsableRulesProof (EQUIVALENT)
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.
----------------------------------------
(50)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
G(b) -> G(f(f(f(f(f(b))))))
The TRS R consists of the following rules:
f(b) -> b
The set Q consists of the following terms:
g(b)
f(b)
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(51) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
g(b)
----------------------------------------
(52)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
G(b) -> G(f(f(f(f(f(b))))))
The TRS R consists of the following rules:
f(b) -> b
The set Q consists of the following terms:
f(b)
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(53) TransformationProof (EQUIVALENT)
By rewriting [LPAR04] the rule G(b) -> G(f(f(f(f(f(b)))))) at position [0,0,0,0,0] we obtained the following new rules [LPAR04]:
(G(b) -> G(f(f(f(f(b))))),G(b) -> G(f(f(f(f(b))))))
----------------------------------------
(54)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
G(b) -> G(f(f(f(f(b)))))
The TRS R consists of the following rules:
f(b) -> b
The set Q consists of the following terms:
f(b)
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(55) TransformationProof (EQUIVALENT)
By rewriting [LPAR04] the rule G(b) -> G(f(f(f(f(b))))) at position [0,0,0,0] we obtained the following new rules [LPAR04]:
(G(b) -> G(f(f(f(b)))),G(b) -> G(f(f(f(b)))))
----------------------------------------
(56)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
G(b) -> G(f(f(f(b))))
The TRS R consists of the following rules:
f(b) -> b
The set Q consists of the following terms:
f(b)
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(57) TransformationProof (EQUIVALENT)
By rewriting [LPAR04] the rule G(b) -> G(f(f(f(b)))) at position [0,0,0] we obtained the following new rules [LPAR04]:
(G(b) -> G(f(f(b))),G(b) -> G(f(f(b))))
----------------------------------------
(58)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
G(b) -> G(f(f(b)))
The TRS R consists of the following rules:
f(b) -> b
The set Q consists of the following terms:
f(b)
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(59) TransformationProof (EQUIVALENT)
By rewriting [LPAR04] the rule G(b) -> G(f(f(b))) at position [0,0] we obtained the following new rules [LPAR04]:
(G(b) -> G(f(b)),G(b) -> G(f(b)))
----------------------------------------
(60)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
G(b) -> G(f(b))
The TRS R consists of the following rules:
f(b) -> b
The set Q consists of the following terms:
f(b)
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(61) TransformationProof (EQUIVALENT)
By rewriting [LPAR04] the rule G(b) -> G(f(b)) at position [0] we obtained the following new rules [LPAR04]:
(G(b) -> G(b),G(b) -> G(b))
----------------------------------------
(62)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
G(b) -> G(b)
The TRS R consists of the following rules:
f(b) -> b
The set Q consists of the following terms:
f(b)
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(63) UsableRulesProof (EQUIVALENT)
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.
----------------------------------------
(64)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
G(b) -> G(b)
R is empty.
The set Q consists of the following terms:
f(b)
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(65) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
f(b)
----------------------------------------
(66)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
G(b) -> G(b)
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(67) NonTerminationLoopProof (COMPLETE)
We used the non-termination processor [FROCOS05] to show that the DP problem is infinite.
Found a loop by semiunifying a rule from P directly.
s = G(b) evaluates to t =G(b)
Thus s starts an infinite chain as s semiunifies with t with the following substitutions:
* Matcher: [ ]
* Semiunifier: [ ]
--------------------------------------------------------------------------------
Rewriting sequence
The DP semiunifies directly so there is only one rewrite step from G(b) to G(b).
----------------------------------------
(68)
NO
----------------------------------------
(69) Raffelsieper-Zantema-Transformation (SOUND)
We applied the Raffelsieper-Zantema transformation to transform the outermost TRS to a standard TRS.
----------------------------------------
(70)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(f(b)) -> up(b)
down(g(f(b))) -> up(c)
top(up(x)) -> top(down(x))
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(c)) -> g_flat(down(c))
down(g(fresh_constant)) -> g_flat(down(fresh_constant))
down(f(g(y6))) -> f_flat(down(g(y6)))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(c)) -> f_flat(down(c))
down(f(fresh_constant)) -> f_flat(down(fresh_constant))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
down(g(f(c))) -> g_flat(down(f(c)))
down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
g_flat(up(x_1)) -> up(g(x_1))
f_flat(up(x_1)) -> up(f(x_1))
Q is empty.
----------------------------------------
(71) QTRSRRRProof (EQUIVALENT)
Used ordering:
Polynomial interpretation [POLO]:
POL(b) = 0
POL(c) = 0
POL(down(x_1)) = x_1
POL(f(x_1)) = x_1
POL(f_flat(x_1)) = x_1
POL(fresh_constant) = 0
POL(g(x_1)) = 1 + 2*x_1
POL(g_flat(x_1)) = 1 + 2*x_1
POL(top(x_1)) = 2*x_1
POL(up(x_1)) = x_1
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
down(g(f(b))) -> up(c)
----------------------------------------
(72)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(f(b)) -> up(b)
top(up(x)) -> top(down(x))
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(c)) -> g_flat(down(c))
down(g(fresh_constant)) -> g_flat(down(fresh_constant))
down(f(g(y6))) -> f_flat(down(g(y6)))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(c)) -> f_flat(down(c))
down(f(fresh_constant)) -> f_flat(down(fresh_constant))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
down(g(f(c))) -> g_flat(down(f(c)))
down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
g_flat(up(x_1)) -> up(g(x_1))
f_flat(up(x_1)) -> up(f(x_1))
Q is empty.
----------------------------------------
(73) AAECC Innermost (EQUIVALENT)
We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(c)) -> g_flat(down(c))
down(g(fresh_constant)) -> g_flat(down(fresh_constant))
down(f(g(y6))) -> f_flat(down(g(y6)))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(c)) -> f_flat(down(c))
down(f(fresh_constant)) -> f_flat(down(fresh_constant))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
down(g(f(c))) -> g_flat(down(f(c)))
down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
g_flat(up(x_1)) -> up(g(x_1))
f_flat(up(x_1)) -> up(f(x_1))
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(f(b)) -> up(b)
The TRS R 2 is
top(up(x)) -> top(down(x))
The signature Sigma is {top_1}
----------------------------------------
(74)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(f(b)) -> up(b)
top(up(x)) -> top(down(x))
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(c)) -> g_flat(down(c))
down(g(fresh_constant)) -> g_flat(down(fresh_constant))
down(f(g(y6))) -> f_flat(down(g(y6)))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(c)) -> f_flat(down(c))
down(f(fresh_constant)) -> f_flat(down(fresh_constant))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
down(g(f(c))) -> g_flat(down(f(c)))
down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
g_flat(up(x_1)) -> up(g(x_1))
f_flat(up(x_1)) -> up(f(x_1))
The set Q consists of the following terms:
down(g(b))
down(f(b))
top(up(x0))
down(g(g(x0)))
down(g(c))
down(g(fresh_constant))
down(f(g(x0)))
down(f(f(x0)))
down(f(c))
down(f(fresh_constant))
down(g(f(g(x0))))
down(g(f(f(x0))))
down(g(f(c)))
down(g(f(fresh_constant)))
g_flat(up(x0))
f_flat(up(x0))
----------------------------------------
(75) DependencyPairsProof (EQUIVALENT)
Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
----------------------------------------
(76)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(up(x)) -> TOP(down(x))
TOP(up(x)) -> DOWN(x)
DOWN(g(g(y3))) -> G_FLAT(down(g(y3)))
DOWN(g(g(y3))) -> DOWN(g(y3))
DOWN(g(c)) -> G_FLAT(down(c))
DOWN(g(c)) -> DOWN(c)
DOWN(g(fresh_constant)) -> G_FLAT(down(fresh_constant))
DOWN(g(fresh_constant)) -> DOWN(fresh_constant)
DOWN(f(g(y6))) -> F_FLAT(down(g(y6)))
DOWN(f(g(y6))) -> DOWN(g(y6))
DOWN(f(f(y7))) -> F_FLAT(down(f(y7)))
DOWN(f(f(y7))) -> DOWN(f(y7))
DOWN(f(c)) -> F_FLAT(down(c))
DOWN(f(c)) -> DOWN(c)
DOWN(f(fresh_constant)) -> F_FLAT(down(fresh_constant))
DOWN(f(fresh_constant)) -> DOWN(fresh_constant)
DOWN(g(f(g(y9)))) -> G_FLAT(down(f(g(y9))))
DOWN(g(f(g(y9)))) -> DOWN(f(g(y9)))
DOWN(g(f(f(y10)))) -> G_FLAT(down(f(f(y10))))
DOWN(g(f(f(y10)))) -> DOWN(f(f(y10)))
DOWN(g(f(c))) -> G_FLAT(down(f(c)))
DOWN(g(f(c))) -> DOWN(f(c))
DOWN(g(f(fresh_constant))) -> G_FLAT(down(f(fresh_constant)))
DOWN(g(f(fresh_constant))) -> DOWN(f(fresh_constant))
The TRS R consists of the following rules:
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(f(b)) -> up(b)
top(up(x)) -> top(down(x))
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(c)) -> g_flat(down(c))
down(g(fresh_constant)) -> g_flat(down(fresh_constant))
down(f(g(y6))) -> f_flat(down(g(y6)))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(c)) -> f_flat(down(c))
down(f(fresh_constant)) -> f_flat(down(fresh_constant))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
down(g(f(c))) -> g_flat(down(f(c)))
down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
g_flat(up(x_1)) -> up(g(x_1))
f_flat(up(x_1)) -> up(f(x_1))
The set Q consists of the following terms:
down(g(b))
down(f(b))
top(up(x0))
down(g(g(x0)))
down(g(c))
down(g(fresh_constant))
down(f(g(x0)))
down(f(f(x0)))
down(f(c))
down(f(fresh_constant))
down(g(f(g(x0))))
down(g(f(f(x0))))
down(g(f(c)))
down(g(f(fresh_constant)))
g_flat(up(x0))
f_flat(up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(77) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 18 less nodes.
----------------------------------------
(78)
Complex Obligation (AND)
----------------------------------------
(79)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
DOWN(g(f(g(y9)))) -> DOWN(f(g(y9)))
DOWN(f(g(y6))) -> DOWN(g(y6))
DOWN(g(g(y3))) -> DOWN(g(y3))
DOWN(g(f(f(y10)))) -> DOWN(f(f(y10)))
DOWN(f(f(y7))) -> DOWN(f(y7))
The TRS R consists of the following rules:
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(f(b)) -> up(b)
top(up(x)) -> top(down(x))
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(c)) -> g_flat(down(c))
down(g(fresh_constant)) -> g_flat(down(fresh_constant))
down(f(g(y6))) -> f_flat(down(g(y6)))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(c)) -> f_flat(down(c))
down(f(fresh_constant)) -> f_flat(down(fresh_constant))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
down(g(f(c))) -> g_flat(down(f(c)))
down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
g_flat(up(x_1)) -> up(g(x_1))
f_flat(up(x_1)) -> up(f(x_1))
The set Q consists of the following terms:
down(g(b))
down(f(b))
top(up(x0))
down(g(g(x0)))
down(g(c))
down(g(fresh_constant))
down(f(g(x0)))
down(f(f(x0)))
down(f(c))
down(f(fresh_constant))
down(g(f(g(x0))))
down(g(f(f(x0))))
down(g(f(c)))
down(g(f(fresh_constant)))
g_flat(up(x0))
f_flat(up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(80) UsableRulesProof (EQUIVALENT)
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.
----------------------------------------
(81)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
DOWN(g(f(g(y9)))) -> DOWN(f(g(y9)))
DOWN(f(g(y6))) -> DOWN(g(y6))
DOWN(g(g(y3))) -> DOWN(g(y3))
DOWN(g(f(f(y10)))) -> DOWN(f(f(y10)))
DOWN(f(f(y7))) -> DOWN(f(y7))
R is empty.
The set Q consists of the following terms:
down(g(b))
down(f(b))
top(up(x0))
down(g(g(x0)))
down(g(c))
down(g(fresh_constant))
down(f(g(x0)))
down(f(f(x0)))
down(f(c))
down(f(fresh_constant))
down(g(f(g(x0))))
down(g(f(f(x0))))
down(g(f(c)))
down(g(f(fresh_constant)))
g_flat(up(x0))
f_flat(up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(82) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
down(g(b))
down(f(b))
top(up(x0))
down(g(g(x0)))
down(g(c))
down(g(fresh_constant))
down(f(g(x0)))
down(f(f(x0)))
down(f(c))
down(f(fresh_constant))
down(g(f(g(x0))))
down(g(f(f(x0))))
down(g(f(c)))
down(g(f(fresh_constant)))
g_flat(up(x0))
f_flat(up(x0))
----------------------------------------
(83)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
DOWN(g(f(g(y9)))) -> DOWN(f(g(y9)))
DOWN(f(g(y6))) -> DOWN(g(y6))
DOWN(g(g(y3))) -> DOWN(g(y3))
DOWN(g(f(f(y10)))) -> DOWN(f(f(y10)))
DOWN(f(f(y7))) -> DOWN(f(y7))
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(84) QDPSizeChangeProof (EQUIVALENT)
By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem.
From the DPs we obtained the following set of size-change graphs:
*DOWN(f(g(y6))) -> DOWN(g(y6))
The graph contains the following edges 1 > 1
*DOWN(g(g(y3))) -> DOWN(g(y3))
The graph contains the following edges 1 > 1
*DOWN(g(f(g(y9)))) -> DOWN(f(g(y9)))
The graph contains the following edges 1 > 1
*DOWN(g(f(f(y10)))) -> DOWN(f(f(y10)))
The graph contains the following edges 1 > 1
*DOWN(f(f(y7))) -> DOWN(f(y7))
The graph contains the following edges 1 > 1
----------------------------------------
(85)
YES
----------------------------------------
(86)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(up(x)) -> TOP(down(x))
The TRS R consists of the following rules:
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(f(b)) -> up(b)
top(up(x)) -> top(down(x))
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(c)) -> g_flat(down(c))
down(g(fresh_constant)) -> g_flat(down(fresh_constant))
down(f(g(y6))) -> f_flat(down(g(y6)))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(c)) -> f_flat(down(c))
down(f(fresh_constant)) -> f_flat(down(fresh_constant))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
down(g(f(c))) -> g_flat(down(f(c)))
down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
g_flat(up(x_1)) -> up(g(x_1))
f_flat(up(x_1)) -> up(f(x_1))
The set Q consists of the following terms:
down(g(b))
down(f(b))
top(up(x0))
down(g(g(x0)))
down(g(c))
down(g(fresh_constant))
down(f(g(x0)))
down(f(f(x0)))
down(f(c))
down(f(fresh_constant))
down(g(f(g(x0))))
down(g(f(f(x0))))
down(g(f(c)))
down(g(f(fresh_constant)))
g_flat(up(x0))
f_flat(up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(87) UsableRulesProof (EQUIVALENT)
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.
----------------------------------------
(88)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(up(x)) -> TOP(down(x))
The TRS R consists of the following rules:
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(f(b)) -> up(b)
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(c)) -> g_flat(down(c))
down(g(fresh_constant)) -> g_flat(down(fresh_constant))
down(f(g(y6))) -> f_flat(down(g(y6)))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(c)) -> f_flat(down(c))
down(f(fresh_constant)) -> f_flat(down(fresh_constant))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
down(g(f(c))) -> g_flat(down(f(c)))
down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
g_flat(up(x_1)) -> up(g(x_1))
f_flat(up(x_1)) -> up(f(x_1))
The set Q consists of the following terms:
down(g(b))
down(f(b))
top(up(x0))
down(g(g(x0)))
down(g(c))
down(g(fresh_constant))
down(f(g(x0)))
down(f(f(x0)))
down(f(c))
down(f(fresh_constant))
down(g(f(g(x0))))
down(g(f(f(x0))))
down(g(f(c)))
down(g(f(fresh_constant)))
g_flat(up(x0))
f_flat(up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(89) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
top(up(x0))
----------------------------------------
(90)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(up(x)) -> TOP(down(x))
The TRS R consists of the following rules:
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(f(b)) -> up(b)
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(c)) -> g_flat(down(c))
down(g(fresh_constant)) -> g_flat(down(fresh_constant))
down(f(g(y6))) -> f_flat(down(g(y6)))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(c)) -> f_flat(down(c))
down(f(fresh_constant)) -> f_flat(down(fresh_constant))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
down(g(f(c))) -> g_flat(down(f(c)))
down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
g_flat(up(x_1)) -> up(g(x_1))
f_flat(up(x_1)) -> up(f(x_1))
The set Q consists of the following terms:
down(g(b))
down(f(b))
down(g(g(x0)))
down(g(c))
down(g(fresh_constant))
down(f(g(x0)))
down(f(f(x0)))
down(f(c))
down(f(fresh_constant))
down(g(f(g(x0))))
down(g(f(f(x0))))
down(g(f(c)))
down(g(f(fresh_constant)))
g_flat(up(x0))
f_flat(up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(91) TransformationProof (EQUIVALENT)
By narrowing [LPAR04] the rule TOP(up(x)) -> TOP(down(x)) at position [0] we obtained the following new rules [LPAR04]:
(TOP(up(g(b))) -> TOP(up(g(f(f(f(f(f(b)))))))),TOP(up(g(b))) -> TOP(up(g(f(f(f(f(f(b)))))))))
(TOP(up(f(b))) -> TOP(up(b)),TOP(up(f(b))) -> TOP(up(b)))
(TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0)))),TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0)))))
(TOP(up(g(c))) -> TOP(g_flat(down(c))),TOP(up(g(c))) -> TOP(g_flat(down(c))))
(TOP(up(g(fresh_constant))) -> TOP(g_flat(down(fresh_constant))),TOP(up(g(fresh_constant))) -> TOP(g_flat(down(fresh_constant))))
(TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))),TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))))
(TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0)))),TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0)))))
(TOP(up(f(c))) -> TOP(f_flat(down(c))),TOP(up(f(c))) -> TOP(f_flat(down(c))))
(TOP(up(f(fresh_constant))) -> TOP(f_flat(down(fresh_constant))),TOP(up(f(fresh_constant))) -> TOP(f_flat(down(fresh_constant))))
(TOP(up(g(f(g(x0))))) -> TOP(g_flat(down(f(g(x0))))),TOP(up(g(f(g(x0))))) -> TOP(g_flat(down(f(g(x0))))))
(TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0))))),TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0))))))
(TOP(up(g(f(c)))) -> TOP(g_flat(down(f(c)))),TOP(up(g(f(c)))) -> TOP(g_flat(down(f(c)))))
(TOP(up(g(f(fresh_constant)))) -> TOP(g_flat(down(f(fresh_constant)))),TOP(up(g(f(fresh_constant)))) -> TOP(g_flat(down(f(fresh_constant)))))
----------------------------------------
(92)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(up(g(b))) -> TOP(up(g(f(f(f(f(f(b))))))))
TOP(up(f(b))) -> TOP(up(b))
TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
TOP(up(g(c))) -> TOP(g_flat(down(c)))
TOP(up(g(fresh_constant))) -> TOP(g_flat(down(fresh_constant)))
TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
TOP(up(f(c))) -> TOP(f_flat(down(c)))
TOP(up(f(fresh_constant))) -> TOP(f_flat(down(fresh_constant)))
TOP(up(g(f(g(x0))))) -> TOP(g_flat(down(f(g(x0)))))
TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0)))))
TOP(up(g(f(c)))) -> TOP(g_flat(down(f(c))))
TOP(up(g(f(fresh_constant)))) -> TOP(g_flat(down(f(fresh_constant))))
The TRS R consists of the following rules:
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(f(b)) -> up(b)
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(c)) -> g_flat(down(c))
down(g(fresh_constant)) -> g_flat(down(fresh_constant))
down(f(g(y6))) -> f_flat(down(g(y6)))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(c)) -> f_flat(down(c))
down(f(fresh_constant)) -> f_flat(down(fresh_constant))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
down(g(f(c))) -> g_flat(down(f(c)))
down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
g_flat(up(x_1)) -> up(g(x_1))
f_flat(up(x_1)) -> up(f(x_1))
The set Q consists of the following terms:
down(g(b))
down(f(b))
down(g(g(x0)))
down(g(c))
down(g(fresh_constant))
down(f(g(x0)))
down(f(f(x0)))
down(f(c))
down(f(fresh_constant))
down(g(f(g(x0))))
down(g(f(f(x0))))
down(g(f(c)))
down(g(f(fresh_constant)))
g_flat(up(x0))
f_flat(up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(93) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 5 less nodes.
----------------------------------------
(94)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0)))))
TOP(up(g(b))) -> TOP(up(g(f(f(f(f(f(b))))))))
TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
TOP(up(g(f(g(x0))))) -> TOP(g_flat(down(f(g(x0)))))
TOP(up(g(f(c)))) -> TOP(g_flat(down(f(c))))
TOP(up(g(f(fresh_constant)))) -> TOP(g_flat(down(f(fresh_constant))))
The TRS R consists of the following rules:
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(f(b)) -> up(b)
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(c)) -> g_flat(down(c))
down(g(fresh_constant)) -> g_flat(down(fresh_constant))
down(f(g(y6))) -> f_flat(down(g(y6)))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(c)) -> f_flat(down(c))
down(f(fresh_constant)) -> f_flat(down(fresh_constant))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
down(g(f(c))) -> g_flat(down(f(c)))
down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
g_flat(up(x_1)) -> up(g(x_1))
f_flat(up(x_1)) -> up(f(x_1))
The set Q consists of the following terms:
down(g(b))
down(f(b))
down(g(g(x0)))
down(g(c))
down(g(fresh_constant))
down(f(g(x0)))
down(f(f(x0)))
down(f(c))
down(f(fresh_constant))
down(g(f(g(x0))))
down(g(f(f(x0))))
down(g(f(c)))
down(g(f(fresh_constant)))
g_flat(up(x0))
f_flat(up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(95) TransformationProof (EQUIVALENT)
By rewriting [LPAR04] the rule TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0))))) at position [0,0] we obtained the following new rules [LPAR04]:
(TOP(up(g(f(f(x0))))) -> TOP(g_flat(f_flat(down(f(x0))))),TOP(up(g(f(f(x0))))) -> TOP(g_flat(f_flat(down(f(x0))))))
----------------------------------------
(96)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(up(g(b))) -> TOP(up(g(f(f(f(f(f(b))))))))
TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
TOP(up(g(f(g(x0))))) -> TOP(g_flat(down(f(g(x0)))))
TOP(up(g(f(c)))) -> TOP(g_flat(down(f(c))))
TOP(up(g(f(fresh_constant)))) -> TOP(g_flat(down(f(fresh_constant))))
TOP(up(g(f(f(x0))))) -> TOP(g_flat(f_flat(down(f(x0)))))
The TRS R consists of the following rules:
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(f(b)) -> up(b)
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(c)) -> g_flat(down(c))
down(g(fresh_constant)) -> g_flat(down(fresh_constant))
down(f(g(y6))) -> f_flat(down(g(y6)))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(c)) -> f_flat(down(c))
down(f(fresh_constant)) -> f_flat(down(fresh_constant))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
down(g(f(c))) -> g_flat(down(f(c)))
down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
g_flat(up(x_1)) -> up(g(x_1))
f_flat(up(x_1)) -> up(f(x_1))
The set Q consists of the following terms:
down(g(b))
down(f(b))
down(g(g(x0)))
down(g(c))
down(g(fresh_constant))
down(f(g(x0)))
down(f(f(x0)))
down(f(c))
down(f(fresh_constant))
down(g(f(g(x0))))
down(g(f(f(x0))))
down(g(f(c)))
down(g(f(fresh_constant)))
g_flat(up(x0))
f_flat(up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(97) TransformationProof (EQUIVALENT)
By rewriting [LPAR04] the rule TOP(up(g(f(g(x0))))) -> TOP(g_flat(down(f(g(x0))))) at position [0,0] we obtained the following new rules [LPAR04]:
(TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0))))),TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0))))))
----------------------------------------
(98)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(up(g(b))) -> TOP(up(g(f(f(f(f(f(b))))))))
TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
TOP(up(g(f(c)))) -> TOP(g_flat(down(f(c))))
TOP(up(g(f(fresh_constant)))) -> TOP(g_flat(down(f(fresh_constant))))
TOP(up(g(f(f(x0))))) -> TOP(g_flat(f_flat(down(f(x0)))))
TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
The TRS R consists of the following rules:
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(f(b)) -> up(b)
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(c)) -> g_flat(down(c))
down(g(fresh_constant)) -> g_flat(down(fresh_constant))
down(f(g(y6))) -> f_flat(down(g(y6)))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(c)) -> f_flat(down(c))
down(f(fresh_constant)) -> f_flat(down(fresh_constant))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
down(g(f(c))) -> g_flat(down(f(c)))
down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
g_flat(up(x_1)) -> up(g(x_1))
f_flat(up(x_1)) -> up(f(x_1))
The set Q consists of the following terms:
down(g(b))
down(f(b))
down(g(g(x0)))
down(g(c))
down(g(fresh_constant))
down(f(g(x0)))
down(f(f(x0)))
down(f(c))
down(f(fresh_constant))
down(g(f(g(x0))))
down(g(f(f(x0))))
down(g(f(c)))
down(g(f(fresh_constant)))
g_flat(up(x0))
f_flat(up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(99) TransformationProof (EQUIVALENT)
By rewriting [LPAR04] the rule TOP(up(g(f(c)))) -> TOP(g_flat(down(f(c)))) at position [0,0] we obtained the following new rules [LPAR04]:
(TOP(up(g(f(c)))) -> TOP(g_flat(f_flat(down(c)))),TOP(up(g(f(c)))) -> TOP(g_flat(f_flat(down(c)))))
----------------------------------------
(100)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(up(g(b))) -> TOP(up(g(f(f(f(f(f(b))))))))
TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
TOP(up(g(f(fresh_constant)))) -> TOP(g_flat(down(f(fresh_constant))))
TOP(up(g(f(f(x0))))) -> TOP(g_flat(f_flat(down(f(x0)))))
TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
TOP(up(g(f(c)))) -> TOP(g_flat(f_flat(down(c))))
The TRS R consists of the following rules:
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(f(b)) -> up(b)
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(c)) -> g_flat(down(c))
down(g(fresh_constant)) -> g_flat(down(fresh_constant))
down(f(g(y6))) -> f_flat(down(g(y6)))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(c)) -> f_flat(down(c))
down(f(fresh_constant)) -> f_flat(down(fresh_constant))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
down(g(f(c))) -> g_flat(down(f(c)))
down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
g_flat(up(x_1)) -> up(g(x_1))
f_flat(up(x_1)) -> up(f(x_1))
The set Q consists of the following terms:
down(g(b))
down(f(b))
down(g(g(x0)))
down(g(c))
down(g(fresh_constant))
down(f(g(x0)))
down(f(f(x0)))
down(f(c))
down(f(fresh_constant))
down(g(f(g(x0))))
down(g(f(f(x0))))
down(g(f(c)))
down(g(f(fresh_constant)))
g_flat(up(x0))
f_flat(up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(101) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node.
----------------------------------------
(102)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(up(g(f(f(x0))))) -> TOP(g_flat(f_flat(down(f(x0)))))
TOP(up(g(b))) -> TOP(up(g(f(f(f(f(f(b))))))))
TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
TOP(up(g(f(fresh_constant)))) -> TOP(g_flat(down(f(fresh_constant))))
TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
The TRS R consists of the following rules:
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(f(b)) -> up(b)
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(c)) -> g_flat(down(c))
down(g(fresh_constant)) -> g_flat(down(fresh_constant))
down(f(g(y6))) -> f_flat(down(g(y6)))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(c)) -> f_flat(down(c))
down(f(fresh_constant)) -> f_flat(down(fresh_constant))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
down(g(f(c))) -> g_flat(down(f(c)))
down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
g_flat(up(x_1)) -> up(g(x_1))
f_flat(up(x_1)) -> up(f(x_1))
The set Q consists of the following terms:
down(g(b))
down(f(b))
down(g(g(x0)))
down(g(c))
down(g(fresh_constant))
down(f(g(x0)))
down(f(f(x0)))
down(f(c))
down(f(fresh_constant))
down(g(f(g(x0))))
down(g(f(f(x0))))
down(g(f(c)))
down(g(f(fresh_constant)))
g_flat(up(x0))
f_flat(up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(103) TransformationProof (EQUIVALENT)
By rewriting [LPAR04] the rule TOP(up(g(f(fresh_constant)))) -> TOP(g_flat(down(f(fresh_constant)))) at position [0,0] we obtained the following new rules [LPAR04]:
(TOP(up(g(f(fresh_constant)))) -> TOP(g_flat(f_flat(down(fresh_constant)))),TOP(up(g(f(fresh_constant)))) -> TOP(g_flat(f_flat(down(fresh_constant)))))
----------------------------------------
(104)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(up(g(f(f(x0))))) -> TOP(g_flat(f_flat(down(f(x0)))))
TOP(up(g(b))) -> TOP(up(g(f(f(f(f(f(b))))))))
TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
TOP(up(g(f(fresh_constant)))) -> TOP(g_flat(f_flat(down(fresh_constant))))
The TRS R consists of the following rules:
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(f(b)) -> up(b)
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(c)) -> g_flat(down(c))
down(g(fresh_constant)) -> g_flat(down(fresh_constant))
down(f(g(y6))) -> f_flat(down(g(y6)))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(c)) -> f_flat(down(c))
down(f(fresh_constant)) -> f_flat(down(fresh_constant))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
down(g(f(c))) -> g_flat(down(f(c)))
down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
g_flat(up(x_1)) -> up(g(x_1))
f_flat(up(x_1)) -> up(f(x_1))
The set Q consists of the following terms:
down(g(b))
down(f(b))
down(g(g(x0)))
down(g(c))
down(g(fresh_constant))
down(f(g(x0)))
down(f(f(x0)))
down(f(c))
down(f(fresh_constant))
down(g(f(g(x0))))
down(g(f(f(x0))))
down(g(f(c)))
down(g(f(fresh_constant)))
g_flat(up(x0))
f_flat(up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(105) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node.
----------------------------------------
(106)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(up(g(b))) -> TOP(up(g(f(f(f(f(f(b))))))))
TOP(up(g(f(f(x0))))) -> TOP(g_flat(f_flat(down(f(x0)))))
TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
The TRS R consists of the following rules:
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(f(b)) -> up(b)
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(c)) -> g_flat(down(c))
down(g(fresh_constant)) -> g_flat(down(fresh_constant))
down(f(g(y6))) -> f_flat(down(g(y6)))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(c)) -> f_flat(down(c))
down(f(fresh_constant)) -> f_flat(down(fresh_constant))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
down(g(f(c))) -> g_flat(down(f(c)))
down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
g_flat(up(x_1)) -> up(g(x_1))
f_flat(up(x_1)) -> up(f(x_1))
The set Q consists of the following terms:
down(g(b))
down(f(b))
down(g(g(x0)))
down(g(c))
down(g(fresh_constant))
down(f(g(x0)))
down(f(f(x0)))
down(f(c))
down(f(fresh_constant))
down(g(f(g(x0))))
down(g(f(f(x0))))
down(g(f(c)))
down(g(f(fresh_constant)))
g_flat(up(x0))
f_flat(up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(107) QDPOrderProof (EQUIVALENT)
We use the reduction pair processor [LPAR04,JAR06].
The following pairs can be oriented strictly and are deleted.
TOP(up(g(b))) -> TOP(up(g(f(f(f(f(f(b))))))))
The remaining pairs can at least be oriented weakly.
Used ordering: Polynomial interpretation [POLO]:
POL(TOP(x_1)) = x_1
POL(b) = 1
POL(c) = 0
POL(down(x_1)) = 0
POL(f(x_1)) = 0
POL(f_flat(x_1)) = 0
POL(fresh_constant) = 0
POL(g(x_1)) = x_1
POL(g_flat(x_1)) = x_1
POL(up(x_1)) = x_1
The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
down(f(g(y6))) -> f_flat(down(g(y6)))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(c)) -> f_flat(down(c))
down(f(fresh_constant)) -> f_flat(down(fresh_constant))
f_flat(up(x_1)) -> up(f(x_1))
g_flat(up(x_1)) -> up(g(x_1))
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(c)) -> g_flat(down(c))
down(g(fresh_constant)) -> g_flat(down(fresh_constant))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
down(g(f(c))) -> g_flat(down(f(c)))
down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
----------------------------------------
(108)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(up(g(f(f(x0))))) -> TOP(g_flat(f_flat(down(f(x0)))))
TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
The TRS R consists of the following rules:
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(f(b)) -> up(b)
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(c)) -> g_flat(down(c))
down(g(fresh_constant)) -> g_flat(down(fresh_constant))
down(f(g(y6))) -> f_flat(down(g(y6)))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(c)) -> f_flat(down(c))
down(f(fresh_constant)) -> f_flat(down(fresh_constant))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
down(g(f(c))) -> g_flat(down(f(c)))
down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
g_flat(up(x_1)) -> up(g(x_1))
f_flat(up(x_1)) -> up(f(x_1))
The set Q consists of the following terms:
down(g(b))
down(f(b))
down(g(g(x0)))
down(g(c))
down(g(fresh_constant))
down(f(g(x0)))
down(f(f(x0)))
down(f(c))
down(f(fresh_constant))
down(g(f(g(x0))))
down(g(f(f(x0))))
down(g(f(c)))
down(g(f(fresh_constant)))
g_flat(up(x0))
f_flat(up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(109) MNOCProof (EQUIVALENT)
We use the modular non-overlap check [FROCOS05] to decrease Q to the empty set.
----------------------------------------
(110)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(up(g(f(f(x0))))) -> TOP(g_flat(f_flat(down(f(x0)))))
TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
The TRS R consists of the following rules:
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(f(b)) -> up(b)
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(c)) -> g_flat(down(c))
down(g(fresh_constant)) -> g_flat(down(fresh_constant))
down(f(g(y6))) -> f_flat(down(g(y6)))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(c)) -> f_flat(down(c))
down(f(fresh_constant)) -> f_flat(down(fresh_constant))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
down(g(f(c))) -> g_flat(down(f(c)))
down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
g_flat(up(x_1)) -> up(g(x_1))
f_flat(up(x_1)) -> up(f(x_1))
Q is empty.
We have to consider all (P,Q,R)-chains.
----------------------------------------
(111) SplitQDPProof (EQUIVALENT)
We show in the first subproof that some pairs and rules can be removed, afterwards, we continue with the remaining DP-Problem
----------------------------------------
(112)
Complex Obligation (AND)
----------------------------------------
(113)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(up(g(f(f(x0))))) -> TOP(g_flat(f_flat(down(f(x0)))))
TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
The TRS R consists of the following rules:
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(f(b)) -> up(b)
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(c)) -> g_flat(down(c))
down(g(fresh_constant)) -> g_flat(down(fresh_constant))
down(f(g(y6))) -> f_flat(down(g(y6)))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(c)) -> f_flat(down(c))
down(f(fresh_constant)) -> f_flat(down(fresh_constant))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
down(g(f(c))) -> g_flat(down(f(c)))
down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
g_flat(up(x_1)) -> up(g(x_1))
f_flat(up(x_1)) -> up(f(x_1))
The set Q consists of the following terms:
down(g(b))
down(f(b))
down(g(g(x0)))
down(g(c))
down(g(fresh_constant))
down(f(g(x0)))
down(f(f(x0)))
down(f(c))
down(f(fresh_constant))
down(g(f(g(x0))))
down(g(f(f(x0))))
down(g(f(c)))
down(g(f(fresh_constant)))
g_flat(up(x0))
f_flat(up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(114) SemLabProof (SOUND)
We found the following model for the rules of the TRSs R and P.
Interpretation over the domain with elements from 0 to 1.
b: 0
c: 0
down: 0
f: 0
fresh_constant: 1
up: 0
f_flat: 0
TOP: 0
g_flat: 0
g: 0
By semantic labelling [SEMLAB] we obtain the following labelled QDP problem.
----------------------------------------
(115)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(f.0(x0)))))
TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
TOP.0(up.0(g.0(g.1(x0)))) -> TOP.0(g_flat.0(down.0(g.1(x0))))
TOP.0(up.0(g.0(f.0(f.1(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(f.1(x0)))))
TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
TOP.0(up.0(f.0(g.1(x0)))) -> TOP.0(f_flat.0(down.0(g.1(x0))))
TOP.0(up.0(f.0(f.0(x0)))) -> TOP.0(f_flat.0(down.0(f.0(x0))))
TOP.0(up.0(f.0(f.1(x0)))) -> TOP.0(f_flat.0(down.0(f.1(x0))))
TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
TOP.0(up.0(g.0(f.0(g.1(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.1(x0)))))
The TRS R consists of the following rules:
down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
down.0(f.0(b.)) -> up.0(b.)
down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
down.0(g.0(c.)) -> g_flat.0(down.0(c.))
down.0(g.1(fresh_constant.)) -> g_flat.0(down.1(fresh_constant.))
down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
down.0(f.0(f.0(y7))) -> f_flat.0(down.0(f.0(y7)))
down.0(f.0(f.1(y7))) -> f_flat.0(down.0(f.1(y7)))
down.0(f.0(c.)) -> f_flat.0(down.0(c.))
down.0(f.1(fresh_constant.)) -> f_flat.0(down.1(fresh_constant.))
down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
down.0(g.0(f.0(f.1(y10)))) -> g_flat.0(down.0(f.0(f.1(y10))))
down.0(g.0(f.0(c.))) -> g_flat.0(down.0(f.0(c.)))
down.0(g.0(f.1(fresh_constant.))) -> g_flat.0(down.0(f.1(fresh_constant.)))
g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
g_flat.0(up.1(x_1)) -> up.0(g.1(x_1))
f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
f_flat.0(up.1(x_1)) -> up.0(f.1(x_1))
The set Q consists of the following terms:
down.0(g.0(b.))
down.0(f.0(b.))
down.0(g.0(g.0(x0)))
down.0(g.0(g.1(x0)))
down.0(g.0(c.))
down.0(g.1(fresh_constant.))
down.0(f.0(g.0(x0)))
down.0(f.0(g.1(x0)))
down.0(f.0(f.0(x0)))
down.0(f.0(f.1(x0)))
down.0(f.0(c.))
down.0(f.1(fresh_constant.))
down.0(g.0(f.0(g.0(x0))))
down.0(g.0(f.0(g.1(x0))))
down.0(g.0(f.0(f.0(x0))))
down.0(g.0(f.0(f.1(x0))))
down.0(g.0(f.0(c.)))
down.0(g.0(f.1(fresh_constant.)))
g_flat.0(up.0(x0))
g_flat.0(up.1(x0))
f_flat.0(up.0(x0))
f_flat.0(up.1(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(116) UsableRulesReductionPairsProof (EQUIVALENT)
By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.
No dependency pairs are removed.
The following rules are removed from R:
down.0(g.1(fresh_constant.)) -> g_flat.0(down.1(fresh_constant.))
down.0(f.1(fresh_constant.)) -> f_flat.0(down.1(fresh_constant.))
g_flat.0(up.1(x_1)) -> up.0(g.1(x_1))
f_flat.0(up.1(x_1)) -> up.0(f.1(x_1))
Used ordering: POLO with Polynomial interpretation [POLO]:
POL(TOP.0(x_1)) = x_1
POL(b.) = 0
POL(c.) = 0
POL(down.0(x_1)) = 1 + x_1
POL(down.1(x_1)) = x_1
POL(f.0(x_1)) = x_1
POL(f.1(x_1)) = x_1
POL(f_flat.0(x_1)) = x_1
POL(fresh_constant.) = 0
POL(g.0(x_1)) = 1 + x_1
POL(g.1(x_1)) = 1 + x_1
POL(g_flat.0(x_1)) = 1 + x_1
POL(up.0(x_1)) = 1 + x_1
POL(up.1(x_1)) = 1 + x_1
----------------------------------------
(117)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(f.0(x0)))))
TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
TOP.0(up.0(g.0(g.1(x0)))) -> TOP.0(g_flat.0(down.0(g.1(x0))))
TOP.0(up.0(g.0(f.0(f.1(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(f.1(x0)))))
TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
TOP.0(up.0(f.0(g.1(x0)))) -> TOP.0(f_flat.0(down.0(g.1(x0))))
TOP.0(up.0(f.0(f.0(x0)))) -> TOP.0(f_flat.0(down.0(f.0(x0))))
TOP.0(up.0(f.0(f.1(x0)))) -> TOP.0(f_flat.0(down.0(f.1(x0))))
TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
TOP.0(up.0(g.0(f.0(g.1(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.1(x0)))))
The TRS R consists of the following rules:
f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
down.0(g.0(c.)) -> g_flat.0(down.0(c.))
down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
down.0(g.0(f.0(f.1(y10)))) -> g_flat.0(down.0(f.0(f.1(y10))))
down.0(g.0(f.0(c.))) -> g_flat.0(down.0(f.0(c.)))
down.0(g.0(f.1(fresh_constant.))) -> g_flat.0(down.0(f.1(fresh_constant.)))
down.0(f.0(c.)) -> f_flat.0(down.0(c.))
down.0(f.0(f.1(y7))) -> f_flat.0(down.0(f.1(y7)))
down.0(f.0(f.0(y7))) -> f_flat.0(down.0(f.0(y7)))
down.0(f.0(b.)) -> up.0(b.)
down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
The set Q consists of the following terms:
down.0(g.0(b.))
down.0(f.0(b.))
down.0(g.0(g.0(x0)))
down.0(g.0(g.1(x0)))
down.0(g.0(c.))
down.0(g.1(fresh_constant.))
down.0(f.0(g.0(x0)))
down.0(f.0(g.1(x0)))
down.0(f.0(f.0(x0)))
down.0(f.0(f.1(x0)))
down.0(f.0(c.))
down.0(f.1(fresh_constant.))
down.0(g.0(f.0(g.0(x0))))
down.0(g.0(f.0(g.1(x0))))
down.0(g.0(f.0(f.0(x0))))
down.0(g.0(f.0(f.1(x0))))
down.0(g.0(f.0(c.)))
down.0(g.0(f.1(fresh_constant.)))
g_flat.0(up.0(x0))
g_flat.0(up.1(x0))
f_flat.0(up.0(x0))
f_flat.0(up.1(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(118) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 5 less nodes.
----------------------------------------
(119)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
TOP.0(up.0(f.0(f.0(x0)))) -> TOP.0(f_flat.0(down.0(f.0(x0))))
TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(f.0(x0)))))
TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
The TRS R consists of the following rules:
f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
down.0(g.0(c.)) -> g_flat.0(down.0(c.))
down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
down.0(g.0(f.0(f.1(y10)))) -> g_flat.0(down.0(f.0(f.1(y10))))
down.0(g.0(f.0(c.))) -> g_flat.0(down.0(f.0(c.)))
down.0(g.0(f.1(fresh_constant.))) -> g_flat.0(down.0(f.1(fresh_constant.)))
down.0(f.0(c.)) -> f_flat.0(down.0(c.))
down.0(f.0(f.1(y7))) -> f_flat.0(down.0(f.1(y7)))
down.0(f.0(f.0(y7))) -> f_flat.0(down.0(f.0(y7)))
down.0(f.0(b.)) -> up.0(b.)
down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
The set Q consists of the following terms:
down.0(g.0(b.))
down.0(f.0(b.))
down.0(g.0(g.0(x0)))
down.0(g.0(g.1(x0)))
down.0(g.0(c.))
down.0(g.1(fresh_constant.))
down.0(f.0(g.0(x0)))
down.0(f.0(g.1(x0)))
down.0(f.0(f.0(x0)))
down.0(f.0(f.1(x0)))
down.0(f.0(c.))
down.0(f.1(fresh_constant.))
down.0(g.0(f.0(g.0(x0))))
down.0(g.0(f.0(g.1(x0))))
down.0(g.0(f.0(f.0(x0))))
down.0(g.0(f.0(f.1(x0))))
down.0(g.0(f.0(c.)))
down.0(g.0(f.1(fresh_constant.)))
g_flat.0(up.0(x0))
g_flat.0(up.1(x0))
f_flat.0(up.0(x0))
f_flat.0(up.1(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(120) PisEmptyProof (SOUND)
The TRS P is empty. Hence, there is no (P,Q,R) chain.
----------------------------------------
(121)
TRUE
----------------------------------------
(122)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
TOP(up(g(f(f(x0))))) -> TOP(g_flat(f_flat(down(f(x0)))))
TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
The TRS R consists of the following rules:
f_flat(up(x_1)) -> up(f(x_1))
g_flat(up(x_1)) -> up(g(x_1))
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(c)) -> g_flat(down(c))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
down(g(f(c))) -> g_flat(down(f(c)))
down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
down(f(c)) -> f_flat(down(c))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(b)) -> up(b)
down(f(g(y6))) -> f_flat(down(g(y6)))
The set Q consists of the following terms:
down(g(b))
down(f(b))
down(g(g(x0)))
down(g(c))
down(g(fresh_constant))
down(f(g(x0)))
down(f(f(x0)))
down(f(c))
down(f(fresh_constant))
down(g(f(g(x0))))
down(g(f(f(x0))))
down(g(f(c)))
down(g(f(fresh_constant)))
g_flat(up(x0))
f_flat(up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(123) SplitQDPProof (EQUIVALENT)
We show in the first subproof that some pairs and rules can be removed, afterwards, we continue with the remaining DP-Problem
----------------------------------------
(124)
Complex Obligation (AND)
----------------------------------------
(125)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
TOP(up(g(f(f(x0))))) -> TOP(g_flat(f_flat(down(f(x0)))))
TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
The TRS R consists of the following rules:
f_flat(up(x_1)) -> up(f(x_1))
g_flat(up(x_1)) -> up(g(x_1))
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(c)) -> g_flat(down(c))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
down(g(f(c))) -> g_flat(down(f(c)))
down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
down(f(c)) -> f_flat(down(c))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(b)) -> up(b)
down(f(g(y6))) -> f_flat(down(g(y6)))
The set Q consists of the following terms:
down(g(b))
down(f(b))
down(g(g(x0)))
down(g(c))
down(g(fresh_constant))
down(f(g(x0)))
down(f(f(x0)))
down(f(c))
down(f(fresh_constant))
down(g(f(g(x0))))
down(g(f(f(x0))))
down(g(f(c)))
down(g(f(fresh_constant)))
g_flat(up(x0))
f_flat(up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(126) SemLabProof (SOUND)
We found the following model for the rules of the TRSs R and P.
Interpretation over the domain with elements from 0 to 1.
b: 0
c: 1
down: 0
f: 0
fresh_constant: 0
up: 0
f_flat: 0
TOP: 0
g_flat: 0
g: 0
By semantic labelling [SEMLAB] we obtain the following labelled QDP problem.
----------------------------------------
(127)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
TOP.0(up.0(g.0(g.1(x0)))) -> TOP.0(g_flat.0(down.0(g.1(x0))))
TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
TOP.0(up.0(f.0(g.1(x0)))) -> TOP.0(f_flat.0(down.0(g.1(x0))))
TOP.0(up.0(f.0(f.0(x0)))) -> TOP.0(f_flat.0(down.0(f.0(x0))))
TOP.0(up.0(f.0(f.1(x0)))) -> TOP.0(f_flat.0(down.0(f.1(x0))))
TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(f.0(x0)))))
TOP.0(up.0(g.0(f.0(f.1(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(f.1(x0)))))
TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
TOP.0(up.0(g.0(f.0(g.1(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.1(x0)))))
The TRS R consists of the following rules:
f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
f_flat.0(up.1(x_1)) -> up.0(f.1(x_1))
g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
g_flat.0(up.1(x_1)) -> up.0(g.1(x_1))
down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
down.0(g.1(c.)) -> g_flat.0(down.1(c.))
down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
down.0(g.0(f.0(f.1(y10)))) -> g_flat.0(down.0(f.0(f.1(y10))))
down.0(g.0(f.1(c.))) -> g_flat.0(down.0(f.1(c.)))
down.0(g.0(f.0(fresh_constant.))) -> g_flat.0(down.0(f.0(fresh_constant.)))
down.0(f.1(c.)) -> f_flat.0(down.1(c.))
down.0(f.0(f.0(y7))) -> f_flat.0(down.0(f.0(y7)))
down.0(f.0(f.1(y7))) -> f_flat.0(down.0(f.1(y7)))
down.0(f.0(b.)) -> up.0(b.)
down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
The set Q consists of the following terms:
down.0(g.0(b.))
down.0(f.0(b.))
down.0(g.0(g.0(x0)))
down.0(g.0(g.1(x0)))
down.0(g.1(c.))
down.0(g.0(fresh_constant.))
down.0(f.0(g.0(x0)))
down.0(f.0(g.1(x0)))
down.0(f.0(f.0(x0)))
down.0(f.0(f.1(x0)))
down.0(f.1(c.))
down.0(f.0(fresh_constant.))
down.0(g.0(f.0(g.0(x0))))
down.0(g.0(f.0(g.1(x0))))
down.0(g.0(f.0(f.0(x0))))
down.0(g.0(f.0(f.1(x0))))
down.0(g.0(f.1(c.)))
down.0(g.0(f.0(fresh_constant.)))
g_flat.0(up.0(x0))
g_flat.0(up.1(x0))
f_flat.0(up.0(x0))
f_flat.0(up.1(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(128) UsableRulesReductionPairsProof (EQUIVALENT)
By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.
No dependency pairs are removed.
The following rules are removed from R:
f_flat.0(up.1(x_1)) -> up.0(f.1(x_1))
g_flat.0(up.1(x_1)) -> up.0(g.1(x_1))
down.0(g.1(c.)) -> g_flat.0(down.1(c.))
down.0(f.1(c.)) -> f_flat.0(down.1(c.))
Used ordering: POLO with Polynomial interpretation [POLO]:
POL(TOP.0(x_1)) = x_1
POL(b.) = 0
POL(c.) = 0
POL(down.0(x_1)) = 1 + x_1
POL(down.1(x_1)) = x_1
POL(f.0(x_1)) = x_1
POL(f.1(x_1)) = x_1
POL(f_flat.0(x_1)) = x_1
POL(fresh_constant.) = 0
POL(g.0(x_1)) = 1 + x_1
POL(g.1(x_1)) = 1 + x_1
POL(g_flat.0(x_1)) = 1 + x_1
POL(up.0(x_1)) = 1 + x_1
POL(up.1(x_1)) = 1 + x_1
----------------------------------------
(129)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
TOP.0(up.0(g.0(g.1(x0)))) -> TOP.0(g_flat.0(down.0(g.1(x0))))
TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
TOP.0(up.0(f.0(g.1(x0)))) -> TOP.0(f_flat.0(down.0(g.1(x0))))
TOP.0(up.0(f.0(f.0(x0)))) -> TOP.0(f_flat.0(down.0(f.0(x0))))
TOP.0(up.0(f.0(f.1(x0)))) -> TOP.0(f_flat.0(down.0(f.1(x0))))
TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(f.0(x0)))))
TOP.0(up.0(g.0(f.0(f.1(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(f.1(x0)))))
TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
TOP.0(up.0(g.0(f.0(g.1(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.1(x0)))))
The TRS R consists of the following rules:
f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
down.0(g.0(f.0(f.1(y10)))) -> g_flat.0(down.0(f.0(f.1(y10))))
down.0(g.0(f.1(c.))) -> g_flat.0(down.0(f.1(c.)))
down.0(g.0(f.0(fresh_constant.))) -> g_flat.0(down.0(f.0(fresh_constant.)))
down.0(f.0(f.1(y7))) -> f_flat.0(down.0(f.1(y7)))
down.0(f.0(f.0(y7))) -> f_flat.0(down.0(f.0(y7)))
down.0(f.0(b.)) -> up.0(b.)
down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
The set Q consists of the following terms:
down.0(g.0(b.))
down.0(f.0(b.))
down.0(g.0(g.0(x0)))
down.0(g.0(g.1(x0)))
down.0(g.1(c.))
down.0(g.0(fresh_constant.))
down.0(f.0(g.0(x0)))
down.0(f.0(g.1(x0)))
down.0(f.0(f.0(x0)))
down.0(f.0(f.1(x0)))
down.0(f.1(c.))
down.0(f.0(fresh_constant.))
down.0(g.0(f.0(g.0(x0))))
down.0(g.0(f.0(g.1(x0))))
down.0(g.0(f.0(f.0(x0))))
down.0(g.0(f.0(f.1(x0))))
down.0(g.0(f.1(c.)))
down.0(g.0(f.0(fresh_constant.)))
g_flat.0(up.0(x0))
g_flat.0(up.1(x0))
f_flat.0(up.0(x0))
f_flat.0(up.1(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(130) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 5 less nodes.
----------------------------------------
(131)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
TOP.0(up.0(f.0(f.0(x0)))) -> TOP.0(f_flat.0(down.0(f.0(x0))))
TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(f.0(x0)))))
TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
The TRS R consists of the following rules:
f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
down.0(g.0(f.0(f.1(y10)))) -> g_flat.0(down.0(f.0(f.1(y10))))
down.0(g.0(f.1(c.))) -> g_flat.0(down.0(f.1(c.)))
down.0(g.0(f.0(fresh_constant.))) -> g_flat.0(down.0(f.0(fresh_constant.)))
down.0(f.0(f.1(y7))) -> f_flat.0(down.0(f.1(y7)))
down.0(f.0(f.0(y7))) -> f_flat.0(down.0(f.0(y7)))
down.0(f.0(b.)) -> up.0(b.)
down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
The set Q consists of the following terms:
down.0(g.0(b.))
down.0(f.0(b.))
down.0(g.0(g.0(x0)))
down.0(g.0(g.1(x0)))
down.0(g.1(c.))
down.0(g.0(fresh_constant.))
down.0(f.0(g.0(x0)))
down.0(f.0(g.1(x0)))
down.0(f.0(f.0(x0)))
down.0(f.0(f.1(x0)))
down.0(f.1(c.))
down.0(f.0(fresh_constant.))
down.0(g.0(f.0(g.0(x0))))
down.0(g.0(f.0(g.1(x0))))
down.0(g.0(f.0(f.0(x0))))
down.0(g.0(f.0(f.1(x0))))
down.0(g.0(f.1(c.)))
down.0(g.0(f.0(fresh_constant.)))
g_flat.0(up.0(x0))
g_flat.0(up.1(x0))
f_flat.0(up.0(x0))
f_flat.0(up.1(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(132) PisEmptyProof (SOUND)
The TRS P is empty. Hence, there is no (P,Q,R) chain.
----------------------------------------
(133)
TRUE
----------------------------------------
(134)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
TOP(up(g(f(f(x0))))) -> TOP(g_flat(f_flat(down(f(x0)))))
TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
The TRS R consists of the following rules:
f_flat(up(x_1)) -> up(f(x_1))
g_flat(up(x_1)) -> up(g(x_1))
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
down(g(f(c))) -> g_flat(down(f(c)))
down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(b)) -> up(b)
down(f(g(y6))) -> f_flat(down(g(y6)))
The set Q consists of the following terms:
down(g(b))
down(f(b))
down(g(g(x0)))
down(g(c))
down(g(fresh_constant))
down(f(g(x0)))
down(f(f(x0)))
down(f(c))
down(f(fresh_constant))
down(g(f(g(x0))))
down(g(f(f(x0))))
down(g(f(c)))
down(g(f(fresh_constant)))
g_flat(up(x0))
f_flat(up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(135) SplitQDPProof (EQUIVALENT)
We show in the first subproof that some pairs and rules can be removed, afterwards, we continue with the remaining DP-Problem
----------------------------------------
(136)
Complex Obligation (AND)
----------------------------------------
(137)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
TOP(up(g(f(f(x0))))) -> TOP(g_flat(f_flat(down(f(x0)))))
TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
The TRS R consists of the following rules:
f_flat(up(x_1)) -> up(f(x_1))
g_flat(up(x_1)) -> up(g(x_1))
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
down(g(f(c))) -> g_flat(down(f(c)))
down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(b)) -> up(b)
down(f(g(y6))) -> f_flat(down(g(y6)))
The set Q consists of the following terms:
down(g(b))
down(f(b))
down(g(g(x0)))
down(g(c))
down(g(fresh_constant))
down(f(g(x0)))
down(f(f(x0)))
down(f(c))
down(f(fresh_constant))
down(g(f(g(x0))))
down(g(f(f(x0))))
down(g(f(c)))
down(g(f(fresh_constant)))
g_flat(up(x0))
f_flat(up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(138) SemLabProof (SOUND)
We found the following model for the rules of the TRSs R and P.
Interpretation over the domain with elements from 0 to 1.
b: 0
c: 0
down: 0
f: x0
fresh_constant: 1
up: 0
f_flat: 0
TOP: 0
g_flat: 0
g: 0
By semantic labelling [SEMLAB] we obtain the following labelled QDP problem.
----------------------------------------
(139)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
TOP.0(up.0(g.0(g.1(x0)))) -> TOP.0(g_flat.0(down.0(g.1(x0))))
TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
TOP.0(up.0(f.0(g.1(x0)))) -> TOP.0(f_flat.0(down.0(g.1(x0))))
TOP.0(up.0(f.0(f.0(x0)))) -> TOP.0(f_flat.0(down.0(f.0(x0))))
TOP.0(up.1(f.1(f.1(x0)))) -> TOP.0(f_flat.0(down.1(f.1(x0))))
TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(f.0(x0)))))
TOP.0(up.0(g.1(f.1(f.1(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.1(f.1(x0)))))
TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
TOP.0(up.0(g.0(f.0(g.1(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.1(x0)))))
The TRS R consists of the following rules:
f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
f_flat.0(up.1(x_1)) -> up.1(f.1(x_1))
g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
g_flat.0(up.1(x_1)) -> up.0(g.1(x_1))
down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
down.0(g.1(f.1(f.1(y10)))) -> g_flat.0(down.1(f.1(f.1(y10))))
down.0(g.0(f.0(c.))) -> g_flat.0(down.0(f.0(c.)))
down.0(g.1(f.1(fresh_constant.))) -> g_flat.0(down.1(f.1(fresh_constant.)))
down.0(f.0(f.0(y7))) -> f_flat.0(down.0(f.0(y7)))
down.1(f.1(f.1(y7))) -> f_flat.0(down.1(f.1(y7)))
down.0(f.0(b.)) -> up.0(b.)
down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
The set Q consists of the following terms:
down.0(g.0(b.))
down.0(f.0(b.))
down.0(g.0(g.0(x0)))
down.0(g.0(g.1(x0)))
down.0(g.0(c.))
down.0(g.1(fresh_constant.))
down.0(f.0(g.0(x0)))
down.0(f.0(g.1(x0)))
down.0(f.0(f.0(x0)))
down.1(f.1(f.1(x0)))
down.0(f.0(c.))
down.1(f.1(fresh_constant.))
down.0(g.0(f.0(g.0(x0))))
down.0(g.0(f.0(g.1(x0))))
down.0(g.0(f.0(f.0(x0))))
down.0(g.1(f.1(f.1(x0))))
down.0(g.0(f.0(c.)))
down.0(g.1(f.1(fresh_constant.)))
g_flat.0(up.0(x0))
g_flat.0(up.1(x0))
f_flat.0(up.0(x0))
f_flat.0(up.1(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(140) MRRProof (EQUIVALENT)
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.
Strictly oriented dependency pairs:
TOP.0(up.1(f.1(f.1(x0)))) -> TOP.0(f_flat.0(down.1(f.1(x0))))
TOP.0(up.0(g.1(f.1(f.1(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.1(f.1(x0)))))
Strictly oriented rules of the TRS R:
down.0(g.1(f.1(f.1(y10)))) -> g_flat.0(down.1(f.1(f.1(y10))))
down.0(g.1(f.1(fresh_constant.))) -> g_flat.0(down.1(f.1(fresh_constant.)))
Used ordering: Polynomial interpretation [POLO]:
POL(TOP.0(x_1)) = x_1
POL(b.) = 0
POL(c.) = 0
POL(down.0(x_1)) = x_1
POL(down.1(x_1)) = x_1
POL(f.0(x_1)) = x_1
POL(f.1(x_1)) = x_1
POL(f_flat.0(x_1)) = x_1
POL(fresh_constant.) = 0
POL(g.0(x_1)) = x_1
POL(g.1(x_1)) = 1 + x_1
POL(g_flat.0(x_1)) = x_1
POL(up.0(x_1)) = x_1
POL(up.1(x_1)) = 1 + x_1
----------------------------------------
(141)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
TOP.0(up.0(g.0(g.1(x0)))) -> TOP.0(g_flat.0(down.0(g.1(x0))))
TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
TOP.0(up.0(f.0(g.1(x0)))) -> TOP.0(f_flat.0(down.0(g.1(x0))))
TOP.0(up.0(f.0(f.0(x0)))) -> TOP.0(f_flat.0(down.0(f.0(x0))))
TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(f.0(x0)))))
TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
TOP.0(up.0(g.0(f.0(g.1(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.1(x0)))))
The TRS R consists of the following rules:
f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
f_flat.0(up.1(x_1)) -> up.1(f.1(x_1))
g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
g_flat.0(up.1(x_1)) -> up.0(g.1(x_1))
down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
down.0(g.0(f.0(c.))) -> g_flat.0(down.0(f.0(c.)))
down.0(f.0(f.0(y7))) -> f_flat.0(down.0(f.0(y7)))
down.1(f.1(f.1(y7))) -> f_flat.0(down.1(f.1(y7)))
down.0(f.0(b.)) -> up.0(b.)
down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
The set Q consists of the following terms:
down.0(g.0(b.))
down.0(f.0(b.))
down.0(g.0(g.0(x0)))
down.0(g.0(g.1(x0)))
down.0(g.0(c.))
down.0(g.1(fresh_constant.))
down.0(f.0(g.0(x0)))
down.0(f.0(g.1(x0)))
down.0(f.0(f.0(x0)))
down.1(f.1(f.1(x0)))
down.0(f.0(c.))
down.1(f.1(fresh_constant.))
down.0(g.0(f.0(g.0(x0))))
down.0(g.0(f.0(g.1(x0))))
down.0(g.0(f.0(f.0(x0))))
down.0(g.1(f.1(f.1(x0))))
down.0(g.0(f.0(c.)))
down.0(g.1(f.1(fresh_constant.)))
g_flat.0(up.0(x0))
g_flat.0(up.1(x0))
f_flat.0(up.0(x0))
f_flat.0(up.1(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(142) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes.
----------------------------------------
(143)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
TOP.0(up.0(f.0(f.0(x0)))) -> TOP.0(f_flat.0(down.0(f.0(x0))))
TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(f.0(x0)))))
TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
The TRS R consists of the following rules:
f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
f_flat.0(up.1(x_1)) -> up.1(f.1(x_1))
g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
g_flat.0(up.1(x_1)) -> up.0(g.1(x_1))
down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
down.0(g.0(f.0(c.))) -> g_flat.0(down.0(f.0(c.)))
down.0(f.0(f.0(y7))) -> f_flat.0(down.0(f.0(y7)))
down.1(f.1(f.1(y7))) -> f_flat.0(down.1(f.1(y7)))
down.0(f.0(b.)) -> up.0(b.)
down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
The set Q consists of the following terms:
down.0(g.0(b.))
down.0(f.0(b.))
down.0(g.0(g.0(x0)))
down.0(g.0(g.1(x0)))
down.0(g.0(c.))
down.0(g.1(fresh_constant.))
down.0(f.0(g.0(x0)))
down.0(f.0(g.1(x0)))
down.0(f.0(f.0(x0)))
down.1(f.1(f.1(x0)))
down.0(f.0(c.))
down.1(f.1(fresh_constant.))
down.0(g.0(f.0(g.0(x0))))
down.0(g.0(f.0(g.1(x0))))
down.0(g.0(f.0(f.0(x0))))
down.0(g.1(f.1(f.1(x0))))
down.0(g.0(f.0(c.)))
down.0(g.1(f.1(fresh_constant.)))
g_flat.0(up.0(x0))
g_flat.0(up.1(x0))
f_flat.0(up.0(x0))
f_flat.0(up.1(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(144) UsableRulesReductionPairsProof (EQUIVALENT)
By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.
No dependency pairs are removed.
The following rules are removed from R:
down.1(f.1(f.1(y7))) -> f_flat.0(down.1(f.1(y7)))
Used ordering: POLO with Polynomial interpretation [POLO]:
POL(TOP.0(x_1)) = x_1
POL(b.) = 0
POL(c.) = 0
POL(down.0(x_1)) = 1 + x_1
POL(f.0(x_1)) = x_1
POL(f.1(x_1)) = x_1
POL(f_flat.0(x_1)) = x_1
POL(g.0(x_1)) = 1 + x_1
POL(g.1(x_1)) = 1 + x_1
POL(g_flat.0(x_1)) = 1 + x_1
POL(up.0(x_1)) = 1 + x_1
POL(up.1(x_1)) = 1 + x_1
----------------------------------------
(145)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
TOP.0(up.0(f.0(f.0(x0)))) -> TOP.0(f_flat.0(down.0(f.0(x0))))
TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(f.0(x0)))))
TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
The TRS R consists of the following rules:
down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
down.0(g.0(f.0(c.))) -> g_flat.0(down.0(f.0(c.)))
f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
f_flat.0(up.1(x_1)) -> up.1(f.1(x_1))
g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
g_flat.0(up.1(x_1)) -> up.0(g.1(x_1))
down.0(f.0(f.0(y7))) -> f_flat.0(down.0(f.0(y7)))
down.0(f.0(b.)) -> up.0(b.)
down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
The set Q consists of the following terms:
down.0(g.0(b.))
down.0(f.0(b.))
down.0(g.0(g.0(x0)))
down.0(g.0(g.1(x0)))
down.0(g.0(c.))
down.0(g.1(fresh_constant.))
down.0(f.0(g.0(x0)))
down.0(f.0(g.1(x0)))
down.0(f.0(f.0(x0)))
down.1(f.1(f.1(x0)))
down.0(f.0(c.))
down.1(f.1(fresh_constant.))
down.0(g.0(f.0(g.0(x0))))
down.0(g.0(f.0(g.1(x0))))
down.0(g.0(f.0(f.0(x0))))
down.0(g.1(f.1(f.1(x0))))
down.0(g.0(f.0(c.)))
down.0(g.1(f.1(fresh_constant.)))
g_flat.0(up.0(x0))
g_flat.0(up.1(x0))
f_flat.0(up.0(x0))
f_flat.0(up.1(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(146) MRRProof (EQUIVALENT)
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.
Strictly oriented rules of the TRS R:
g_flat.0(up.1(x_1)) -> up.0(g.1(x_1))
Used ordering: Polynomial interpretation [POLO]:
POL(TOP.0(x_1)) = x_1
POL(b.) = 0
POL(c.) = 0
POL(down.0(x_1)) = x_1
POL(f.0(x_1)) = x_1
POL(f.1(x_1)) = x_1
POL(f_flat.0(x_1)) = x_1
POL(g.0(x_1)) = 1 + x_1
POL(g.1(x_1)) = x_1
POL(g_flat.0(x_1)) = 1 + x_1
POL(up.0(x_1)) = x_1
POL(up.1(x_1)) = 1 + x_1
----------------------------------------
(147)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
TOP.0(up.0(f.0(f.0(x0)))) -> TOP.0(f_flat.0(down.0(f.0(x0))))
TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(f.0(x0)))))
TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
The TRS R consists of the following rules:
down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
down.0(g.0(f.0(c.))) -> g_flat.0(down.0(f.0(c.)))
f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
f_flat.0(up.1(x_1)) -> up.1(f.1(x_1))
g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
down.0(f.0(f.0(y7))) -> f_flat.0(down.0(f.0(y7)))
down.0(f.0(b.)) -> up.0(b.)
down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
The set Q consists of the following terms:
down.0(g.0(b.))
down.0(f.0(b.))
down.0(g.0(g.0(x0)))
down.0(g.0(g.1(x0)))
down.0(g.0(c.))
down.0(g.1(fresh_constant.))
down.0(f.0(g.0(x0)))
down.0(f.0(g.1(x0)))
down.0(f.0(f.0(x0)))
down.1(f.1(f.1(x0)))
down.0(f.0(c.))
down.1(f.1(fresh_constant.))
down.0(g.0(f.0(g.0(x0))))
down.0(g.0(f.0(g.1(x0))))
down.0(g.0(f.0(f.0(x0))))
down.0(g.1(f.1(f.1(x0))))
down.0(g.0(f.0(c.)))
down.0(g.1(f.1(fresh_constant.)))
g_flat.0(up.0(x0))
g_flat.0(up.1(x0))
f_flat.0(up.0(x0))
f_flat.0(up.1(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(148) PisEmptyProof (SOUND)
The TRS P is empty. Hence, there is no (P,Q,R) chain.
----------------------------------------
(149)
TRUE
----------------------------------------
(150)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
TOP(up(g(f(f(x0))))) -> TOP(g_flat(f_flat(down(f(x0)))))
TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
The TRS R consists of the following rules:
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
down(g(f(c))) -> g_flat(down(f(c)))
f_flat(up(x_1)) -> up(f(x_1))
g_flat(up(x_1)) -> up(g(x_1))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(b)) -> up(b)
down(f(g(y6))) -> f_flat(down(g(y6)))
The set Q consists of the following terms:
down(g(b))
down(f(b))
down(g(g(x0)))
down(g(c))
down(g(fresh_constant))
down(f(g(x0)))
down(f(f(x0)))
down(f(c))
down(f(fresh_constant))
down(g(f(g(x0))))
down(g(f(f(x0))))
down(g(f(c)))
down(g(f(fresh_constant)))
g_flat(up(x0))
f_flat(up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(151) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as they contain symbols which do neither occur in P nor in R.[THIEMANN].
down(g(fresh_constant))
down(f(fresh_constant))
down(g(f(fresh_constant)))
----------------------------------------
(152)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
TOP(up(g(f(f(x0))))) -> TOP(g_flat(f_flat(down(f(x0)))))
TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
The TRS R consists of the following rules:
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
down(g(f(c))) -> g_flat(down(f(c)))
f_flat(up(x_1)) -> up(f(x_1))
g_flat(up(x_1)) -> up(g(x_1))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(b)) -> up(b)
down(f(g(y6))) -> f_flat(down(g(y6)))
The set Q consists of the following terms:
down(g(b))
down(f(b))
down(g(g(x0)))
down(g(c))
down(f(g(x0)))
down(f(f(x0)))
down(f(c))
down(g(f(g(x0))))
down(g(f(f(x0))))
down(g(f(c)))
g_flat(up(x0))
f_flat(up(x0))
We have to consider all (P,Q,R)-chains.
----------------------------------------
(153) SplitQDPProof (EQUIVALENT)
We show in the first subproof that some pairs and rules can be removed, afterwards, we continue with the remaining DP-Problem
----------------------------------------
(154)
Complex Obligation (AND)
----------------------------------------
(155)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
TOP(up(g(f(f(x0))))) -> TOP(g_flat(f_flat(down(f(x0)))))
TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
The TRS R consists of the following rules:
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
down(g(f(c))) -> g_flat(down(f(c)))
f_flat(up(x_1)) -> up(f(x_1))
g_flat(up(x_1)) -> up(g(x_1))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(b)) -> up(b)
down(f(g(y6))) -> f_flat(down(g(y6)))
The set Q consists of the following terms:
down(g(b))
down(f(b))
down(g(g(x0)))
down(g(c))
down(g(fresh_constant))
down(f(g(x0)))
down(f(f(x0)))
down(f(c))
down(f(fresh_constant))
down(g(f(g(x0))))
down(g(f(f(x0))))
down(g(f(c)))
down(g(f(fresh_constant)))
g_flat(up(x0))
f_flat(up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(156) SemLabProof (SOUND)
We found the following model for the rules of the TRSs R and P.
Interpretation over the domain with elements from 0 to 1.
b: 0
c: 1
down: 0
f: x0
fresh_constant: 0
up: 0
f_flat: 0
TOP: 0
g_flat: 0
g: 0
By semantic labelling [SEMLAB] we obtain the following labelled QDP problem.
----------------------------------------
(157)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
TOP.0(up.0(g.0(g.1(x0)))) -> TOP.0(g_flat.0(down.0(g.1(x0))))
TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
TOP.0(up.0(f.0(g.1(x0)))) -> TOP.0(f_flat.0(down.0(g.1(x0))))
TOP.0(up.0(f.0(f.0(x0)))) -> TOP.0(f_flat.0(down.0(f.0(x0))))
TOP.0(up.1(f.1(f.1(x0)))) -> TOP.0(f_flat.0(down.1(f.1(x0))))
TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(f.0(x0)))))
TOP.0(up.0(g.1(f.1(f.1(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.1(f.1(x0)))))
TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
TOP.0(up.0(g.0(f.0(g.1(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.1(x0)))))
The TRS R consists of the following rules:
down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
down.0(g.1(f.1(f.1(y10)))) -> g_flat.0(down.1(f.1(f.1(y10))))
down.0(g.1(f.1(c.))) -> g_flat.0(down.1(f.1(c.)))
f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
f_flat.0(up.1(x_1)) -> up.1(f.1(x_1))
g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
g_flat.0(up.1(x_1)) -> up.0(g.1(x_1))
down.0(f.0(f.0(y7))) -> f_flat.0(down.0(f.0(y7)))
down.1(f.1(f.1(y7))) -> f_flat.0(down.1(f.1(y7)))
down.0(f.0(b.)) -> up.0(b.)
down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
The set Q consists of the following terms:
down.0(g.0(b.))
down.0(f.0(b.))
down.0(g.0(g.0(x0)))
down.0(g.0(g.1(x0)))
down.0(g.1(c.))
down.0(g.0(fresh_constant.))
down.0(f.0(g.0(x0)))
down.0(f.0(g.1(x0)))
down.0(f.0(f.0(x0)))
down.1(f.1(f.1(x0)))
down.1(f.1(c.))
down.0(f.0(fresh_constant.))
down.0(g.0(f.0(g.0(x0))))
down.0(g.0(f.0(g.1(x0))))
down.0(g.0(f.0(f.0(x0))))
down.0(g.1(f.1(f.1(x0))))
down.0(g.1(f.1(c.)))
down.0(g.0(f.0(fresh_constant.)))
g_flat.0(up.0(x0))
g_flat.0(up.1(x0))
f_flat.0(up.0(x0))
f_flat.0(up.1(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(158) MRRProof (EQUIVALENT)
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.
Strictly oriented dependency pairs:
TOP.0(up.1(f.1(f.1(x0)))) -> TOP.0(f_flat.0(down.1(f.1(x0))))
TOP.0(up.0(g.1(f.1(f.1(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.1(f.1(x0)))))
Strictly oriented rules of the TRS R:
down.0(g.1(f.1(f.1(y10)))) -> g_flat.0(down.1(f.1(f.1(y10))))
down.0(g.1(f.1(c.))) -> g_flat.0(down.1(f.1(c.)))
Used ordering: Polynomial interpretation [POLO]:
POL(TOP.0(x_1)) = x_1
POL(b.) = 0
POL(c.) = 0
POL(down.0(x_1)) = 1 + x_1
POL(down.1(x_1)) = x_1
POL(f.0(x_1)) = x_1
POL(f.1(x_1)) = x_1
POL(f_flat.0(x_1)) = x_1
POL(g.0(x_1)) = x_1
POL(g.1(x_1)) = x_1
POL(g_flat.0(x_1)) = x_1
POL(up.0(x_1)) = 1 + x_1
POL(up.1(x_1)) = 1 + x_1
----------------------------------------
(159)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
TOP.0(up.0(g.0(g.1(x0)))) -> TOP.0(g_flat.0(down.0(g.1(x0))))
TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
TOP.0(up.0(f.0(g.1(x0)))) -> TOP.0(f_flat.0(down.0(g.1(x0))))
TOP.0(up.0(f.0(f.0(x0)))) -> TOP.0(f_flat.0(down.0(f.0(x0))))
TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(f.0(x0)))))
TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
TOP.0(up.0(g.0(f.0(g.1(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.1(x0)))))
The TRS R consists of the following rules:
down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
f_flat.0(up.1(x_1)) -> up.1(f.1(x_1))
g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
g_flat.0(up.1(x_1)) -> up.0(g.1(x_1))
down.0(f.0(f.0(y7))) -> f_flat.0(down.0(f.0(y7)))
down.1(f.1(f.1(y7))) -> f_flat.0(down.1(f.1(y7)))
down.0(f.0(b.)) -> up.0(b.)
down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
The set Q consists of the following terms:
down.0(g.0(b.))
down.0(f.0(b.))
down.0(g.0(g.0(x0)))
down.0(g.0(g.1(x0)))
down.0(g.1(c.))
down.0(g.0(fresh_constant.))
down.0(f.0(g.0(x0)))
down.0(f.0(g.1(x0)))
down.0(f.0(f.0(x0)))
down.1(f.1(f.1(x0)))
down.1(f.1(c.))
down.0(f.0(fresh_constant.))
down.0(g.0(f.0(g.0(x0))))
down.0(g.0(f.0(g.1(x0))))
down.0(g.0(f.0(f.0(x0))))
down.0(g.1(f.1(f.1(x0))))
down.0(g.1(f.1(c.)))
down.0(g.0(f.0(fresh_constant.)))
g_flat.0(up.0(x0))
g_flat.0(up.1(x0))
f_flat.0(up.0(x0))
f_flat.0(up.1(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(160) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes.
----------------------------------------
(161)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
TOP.0(up.0(f.0(f.0(x0)))) -> TOP.0(f_flat.0(down.0(f.0(x0))))
TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(f.0(x0)))))
TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
The TRS R consists of the following rules:
down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
f_flat.0(up.1(x_1)) -> up.1(f.1(x_1))
g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
g_flat.0(up.1(x_1)) -> up.0(g.1(x_1))
down.0(f.0(f.0(y7))) -> f_flat.0(down.0(f.0(y7)))
down.1(f.1(f.1(y7))) -> f_flat.0(down.1(f.1(y7)))
down.0(f.0(b.)) -> up.0(b.)
down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
The set Q consists of the following terms:
down.0(g.0(b.))
down.0(f.0(b.))
down.0(g.0(g.0(x0)))
down.0(g.0(g.1(x0)))
down.0(g.1(c.))
down.0(g.0(fresh_constant.))
down.0(f.0(g.0(x0)))
down.0(f.0(g.1(x0)))
down.0(f.0(f.0(x0)))
down.1(f.1(f.1(x0)))
down.1(f.1(c.))
down.0(f.0(fresh_constant.))
down.0(g.0(f.0(g.0(x0))))
down.0(g.0(f.0(g.1(x0))))
down.0(g.0(f.0(f.0(x0))))
down.0(g.1(f.1(f.1(x0))))
down.0(g.1(f.1(c.)))
down.0(g.0(f.0(fresh_constant.)))
g_flat.0(up.0(x0))
g_flat.0(up.1(x0))
f_flat.0(up.0(x0))
f_flat.0(up.1(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(162) UsableRulesReductionPairsProof (EQUIVALENT)
By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.
No dependency pairs are removed.
The following rules are removed from R:
down.1(f.1(f.1(y7))) -> f_flat.0(down.1(f.1(y7)))
Used ordering: POLO with Polynomial interpretation [POLO]:
POL(TOP.0(x_1)) = x_1
POL(b.) = 0
POL(down.0(x_1)) = 1 + x_1
POL(f.0(x_1)) = x_1
POL(f.1(x_1)) = x_1
POL(f_flat.0(x_1)) = x_1
POL(g.0(x_1)) = 1 + x_1
POL(g.1(x_1)) = 1 + x_1
POL(g_flat.0(x_1)) = 1 + x_1
POL(up.0(x_1)) = 1 + x_1
POL(up.1(x_1)) = 1 + x_1
----------------------------------------
(163)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
TOP.0(up.0(f.0(f.0(x0)))) -> TOP.0(f_flat.0(down.0(f.0(x0))))
TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(f.0(x0)))))
TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
The TRS R consists of the following rules:
down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
f_flat.0(up.1(x_1)) -> up.1(f.1(x_1))
g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
g_flat.0(up.1(x_1)) -> up.0(g.1(x_1))
down.0(f.0(f.0(y7))) -> f_flat.0(down.0(f.0(y7)))
down.0(f.0(b.)) -> up.0(b.)
down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
The set Q consists of the following terms:
down.0(g.0(b.))
down.0(f.0(b.))
down.0(g.0(g.0(x0)))
down.0(g.0(g.1(x0)))
down.0(g.1(c.))
down.0(g.0(fresh_constant.))
down.0(f.0(g.0(x0)))
down.0(f.0(g.1(x0)))
down.0(f.0(f.0(x0)))
down.1(f.1(f.1(x0)))
down.1(f.1(c.))
down.0(f.0(fresh_constant.))
down.0(g.0(f.0(g.0(x0))))
down.0(g.0(f.0(g.1(x0))))
down.0(g.0(f.0(f.0(x0))))
down.0(g.1(f.1(f.1(x0))))
down.0(g.1(f.1(c.)))
down.0(g.0(f.0(fresh_constant.)))
g_flat.0(up.0(x0))
g_flat.0(up.1(x0))
f_flat.0(up.0(x0))
f_flat.0(up.1(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(164) MRRProof (EQUIVALENT)
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.
Strictly oriented rules of the TRS R:
g_flat.0(up.1(x_1)) -> up.0(g.1(x_1))
Used ordering: Polynomial interpretation [POLO]:
POL(TOP.0(x_1)) = x_1
POL(b.) = 0
POL(down.0(x_1)) = x_1
POL(f.0(x_1)) = x_1
POL(f.1(x_1)) = x_1
POL(f_flat.0(x_1)) = x_1
POL(g.0(x_1)) = 1 + x_1
POL(g.1(x_1)) = x_1
POL(g_flat.0(x_1)) = 1 + x_1
POL(up.0(x_1)) = x_1
POL(up.1(x_1)) = 1 + x_1
----------------------------------------
(165)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
TOP.0(up.0(f.0(f.0(x0)))) -> TOP.0(f_flat.0(down.0(f.0(x0))))
TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(f.0(x0)))))
TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
The TRS R consists of the following rules:
down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
f_flat.0(up.1(x_1)) -> up.1(f.1(x_1))
g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
down.0(f.0(f.0(y7))) -> f_flat.0(down.0(f.0(y7)))
down.0(f.0(b.)) -> up.0(b.)
down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
The set Q consists of the following terms:
down.0(g.0(b.))
down.0(f.0(b.))
down.0(g.0(g.0(x0)))
down.0(g.0(g.1(x0)))
down.0(g.1(c.))
down.0(g.0(fresh_constant.))
down.0(f.0(g.0(x0)))
down.0(f.0(g.1(x0)))
down.0(f.0(f.0(x0)))
down.1(f.1(f.1(x0)))
down.1(f.1(c.))
down.0(f.0(fresh_constant.))
down.0(g.0(f.0(g.0(x0))))
down.0(g.0(f.0(g.1(x0))))
down.0(g.0(f.0(f.0(x0))))
down.0(g.1(f.1(f.1(x0))))
down.0(g.1(f.1(c.)))
down.0(g.0(f.0(fresh_constant.)))
g_flat.0(up.0(x0))
g_flat.0(up.1(x0))
f_flat.0(up.0(x0))
f_flat.0(up.1(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(166) PisEmptyProof (SOUND)
The TRS P is empty. Hence, there is no (P,Q,R) chain.
----------------------------------------
(167)
TRUE
----------------------------------------
(168)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
TOP(up(g(f(f(x0))))) -> TOP(g_flat(f_flat(down(f(x0)))))
TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
The TRS R consists of the following rules:
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
f_flat(up(x_1)) -> up(f(x_1))
g_flat(up(x_1)) -> up(g(x_1))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(b)) -> up(b)
down(f(g(y6))) -> f_flat(down(g(y6)))
The set Q consists of the following terms:
down(g(b))
down(f(b))
down(g(g(x0)))
down(g(c))
down(g(fresh_constant))
down(f(g(x0)))
down(f(f(x0)))
down(f(c))
down(f(fresh_constant))
down(g(f(g(x0))))
down(g(f(f(x0))))
down(g(f(c)))
down(g(f(fresh_constant)))
g_flat(up(x0))
f_flat(up(x0))
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------
(169) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as they contain symbols which do neither occur in P nor in R.[THIEMANN].
down(g(c))
down(g(fresh_constant))
down(f(c))
down(f(fresh_constant))
down(g(f(c)))
down(g(f(fresh_constant)))
----------------------------------------
(170)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
TOP(up(g(f(f(x0))))) -> TOP(g_flat(f_flat(down(f(x0)))))
TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
The TRS R consists of the following rules:
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
f_flat(up(x_1)) -> up(f(x_1))
g_flat(up(x_1)) -> up(g(x_1))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(b)) -> up(b)
down(f(g(y6))) -> f_flat(down(g(y6)))
The set Q consists of the following terms:
down(g(b))
down(f(b))
down(g(g(x0)))
down(f(g(x0)))
down(f(f(x0)))
down(g(f(g(x0))))
down(g(f(f(x0))))
g_flat(up(x0))
f_flat(up(x0))
We have to consider all (P,Q,R)-chains.
----------------------------------------
(171) MNOCProof (EQUIVALENT)
We use the modular non-overlap check [FROCOS05] to decrease Q to the empty set.
----------------------------------------
(172)
Obligation:
Q DP problem:
The TRS P consists of the following rules:
TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
TOP(up(g(f(f(x0))))) -> TOP(g_flat(f_flat(down(f(x0)))))
TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
The TRS R consists of the following rules:
down(g(b)) -> up(g(f(f(f(f(f(b)))))))
down(g(g(y3))) -> g_flat(down(g(y3)))
down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
f_flat(up(x_1)) -> up(f(x_1))
g_flat(up(x_1)) -> up(g(x_1))
down(f(f(y7))) -> f_flat(down(f(y7)))
down(f(b)) -> up(b)
down(f(g(y6))) -> f_flat(down(g(y6)))
Q is empty.
We have to consider all (P,Q,R)-chains.