/export/starexec/sandbox2/solver/bin/starexec_run_ttt2-1.17+nonreach /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES Problem: f(a(),f(a(),f(b(),f(a(),f(a(),f(b(),f(a(),x))))))) -> f(a(),f(b(),f(a(),f(a(),f(b(),f(a(),f(a(),f(a(),f(b(),x))))))))) Proof: Extended Uncurrying Processor: application symbol: f symbol table: b ==> b0/0 b1/1 a ==> a0/0 a1/1 uncurry-rules: f(a0(),x1) -> a1(x1) f(b0(),x3) -> b1(x3) eta-rules: problem: a1(a1(b1(a1(a1(b1(a1(x))))))) -> a1(b1(a1(a1(b1(a1(a1(a1(b1(x))))))))) f(a0(),x1) -> a1(x1) f(b0(),x3) -> b1(x3) Matrix Interpretation Processor: dim=3 interpretation: [1 0 0] [b1](x0) = [0 0 0]x0 [0 0 1] , [0] [b0] = [0] [0], [1 0 0] [a1](x0) = [0 0 0]x0 [0 0 1] , [0] [a0] = [0] [1], [1 0 1] [1 0 1] [f](x0, x1) = [0 0 1]x0 + [1 0 1]x1 [0 0 0] [0 0 1] orientation: [1 0 0] [1 0 0] a1(a1(b1(a1(a1(b1(a1(x))))))) = [0 0 0]x >= [0 0 0]x = a1(b1(a1(a1(b1(a1(a1(a1(b1(x))))))))) [0 0 1] [0 0 1] [1 0 1] [1] [1 0 0] f(a0(),x1) = [1 0 1]x1 + [1] >= [0 0 0]x1 = a1(x1) [0 0 1] [0] [0 0 1] [1 0 1] [1 0 0] f(b0(),x3) = [1 0 1]x3 >= [0 0 0]x3 = b1(x3) [0 0 1] [0 0 1] problem: a1(a1(b1(a1(a1(b1(a1(x))))))) -> a1(b1(a1(a1(b1(a1(a1(a1(b1(x))))))))) f(b0(),x3) -> b1(x3) Matrix Interpretation Processor: dim=3 interpretation: [1 0 0] [0] [b1](x0) = [0 0 1]x0 + [1] [0 0 1] [0], [0] [b0] = [1] [0], [a1](x0) = x0 , [1 0 0] [1 0 0] [1] [f](x0, x1) = [0 0 0]x0 + [0 0 1]x1 + [1] [0 1 0] [0 0 1] [0] orientation: [1 0 0] [0] [1 0 0] [0] a1(a1(b1(a1(a1(b1(a1(x))))))) = [0 0 1]x + [1] >= [0 0 1]x + [1] = a1(b1(a1(a1(b1(a1(a1(a1(b1(x))))))))) [0 0 1] [0] [0 0 1] [0] [1 0 0] [1] [1 0 0] [0] f(b0(),x3) = [0 0 1]x3 + [1] >= [0 0 1]x3 + [1] = b1(x3) [0 0 1] [1] [0 0 1] [0] problem: a1(a1(b1(a1(a1(b1(a1(x))))))) -> a1(b1(a1(a1(b1(a1(a1(a1(b1(x))))))))) DP Processor: DPs: a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(b1(x)) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(b1(x))) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(a1(b1(x)))) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(b1(a1(a1(a1(b1(x)))))) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(b1(a1(a1(a1(b1(x))))))) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(b1(a1(a1(b1(a1(a1(a1(b1(x))))))))) TRS: a1(a1(b1(a1(a1(b1(a1(x))))))) -> a1(b1(a1(a1(b1(a1(a1(a1(b1(x))))))))) EDG Processor: DPs: a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(b1(x)) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(b1(x))) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(a1(b1(x)))) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(b1(a1(a1(a1(b1(x)))))) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(b1(a1(a1(a1(b1(x))))))) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(b1(a1(a1(b1(a1(a1(a1(b1(x))))))))) TRS: a1(a1(b1(a1(a1(b1(a1(x))))))) -> a1(b1(a1(a1(b1(a1(a1(a1(b1(x))))))))) graph: a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(b1(a1(a1(a1(b1(x))))))) -> a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(b1(x)) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(b1(a1(a1(a1(b1(x))))))) -> a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(b1(x))) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(b1(a1(a1(a1(b1(x))))))) -> a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(a1(b1(x)))) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(b1(a1(a1(a1(b1(x))))))) -> a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(b1(a1(a1(a1(b1(x)))))) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(b1(a1(a1(a1(b1(x))))))) -> a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(b1(a1(a1(a1(b1(x))))))) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(b1(a1(a1(a1(b1(x))))))) -> a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(b1(a1(a1(b1(a1(a1(a1(b1(x))))))))) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(b1(x))) -> a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(b1(x)) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(b1(x))) -> a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(b1(x))) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(b1(x))) -> a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(a1(b1(x)))) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(b1(x))) -> a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(b1(a1(a1(a1(b1(x)))))) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(b1(x))) -> a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(b1(a1(a1(a1(b1(x))))))) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(b1(x))) -> a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(b1(a1(a1(b1(a1(a1(a1(b1(x))))))))) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(a1(b1(x)))) -> a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(b1(x)) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(a1(b1(x)))) -> a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(b1(x))) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(a1(b1(x)))) -> a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(a1(b1(x)))) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(a1(b1(x)))) -> a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(b1(a1(a1(a1(b1(x)))))) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(a1(b1(x)))) -> a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(b1(a1(a1(a1(b1(x))))))) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(a1(b1(x)))) -> a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(b1(a1(a1(b1(a1(a1(a1(b1(x))))))))) SCC Processor: #sccs: 1 #rules: 3 #arcs: 18/36 DPs: a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(b1(a1(a1(a1(b1(x))))))) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(a1(b1(x)))) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(b1(x))) TRS: a1(a1(b1(a1(a1(b1(a1(x))))))) -> a1(b1(a1(a1(b1(a1(a1(a1(b1(x))))))))) Bounds Processor: bound: 1 enrichment: match-dp automaton: final states: {1} transitions: f80() -> 2* a{1,#,0}(50) -> 51* a{1,#,0}(64) -> 65* a{1,#,0}(8) -> 1* a{1,0}(75) -> 76* a{1,0}(20) -> 21* a{1,0}(5) -> 6* a{1,0}(7) -> 8* a{1,0}(79) -> 80* a{1,0}(74) -> 75* a{1,0}(4) -> 5* a{1,0}(76) -> 77* a{1,0}(66) -> 67* a{1,0}(78) -> 79* a{1,0}(18) -> 19* a{1,0}(3) -> 4* b{1,0}(80) -> 81* b{1,0}(77) -> 78* b{1,0}(67) -> 68* b{1,0}(2) -> 3* b{1,0}(19) -> 20* b{1,0}(6) -> 7* b{1,0}(73) -> 74* a{1,#,1}(48) -> 49* a{1,1}(45) -> 46* a{1,1}(47) -> 48* a{1,1}(44) -> 45* a{1,1}(43) -> 44* b{1,1}(42) -> 43* b{1,1}(46) -> 47* 5 -> 73* 6 -> 77* 8 -> 18* 18 -> 42* 19 -> 80* 21 -> 76,5 44 -> 64* 45 -> 50* 48 -> 66* 49 -> 1* 51 -> 1* 65 -> 1* 68 -> 18* 81 -> 5* problem: DPs: a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(a1(b1(x)))) a{1,#}(a1(b1(a1(a1(b1(a1(x))))))) -> a{1,#}(a1(b1(x))) TRS: a1(a1(b1(a1(a1(b1(a1(x))))))) -> a1(b1(a1(a1(b1(a1(a1(a1(b1(x))))))))) Bounds Processor: bound: 1 enrichment: match automaton: final states: {7,6,1} transitions: f160() -> 2* a{1,#,0}(5) -> 1* a{1,#,0}(4) -> 6* a{1,0}(10) -> 11* a{1,0}(5) -> 8* a{1,0}(12) -> 7* a{1,0}(9) -> 10* a{1,0}(4) -> 5* a{1,0}(3) -> 4* b{1,0}(2) -> 3* b{1,0}(11) -> 12* b{1,0}(8) -> 9* a{1,#,1}(16) -> 17* a{1,#,1}(23) -> 24* a{1,1}(30) -> 31* a{1,1}(15) -> 16* a{1,1}(57) -> 58* a{1,1}(52) -> 53* a{1,1}(32) -> 33* a{1,1}(27) -> 28* a{1,1}(59) -> 60* a{1,1}(54) -> 55* a{1,1}(29) -> 30* a{1,1}(14) -> 15* a{1,1}(56) -> 57* a{1,1}(53) -> 54* b{1,1}(55) -> 56* b{1,1}(67) -> 68* b{1,1}(61) -> 62* b{1,1}(51) -> 52* b{1,1}(31) -> 32* b{1,1}(58) -> 59* b{1,1}(28) -> 29* b{1,1}(13) -> 14* 1 -> 24,6 5 -> 13* 6 -> 1* 7 -> 16,27,5 10 -> 51* 15 -> 23* 16 -> 27* 17 -> 1,6 24 -> 17,1,6 32 -> 61* 33 -> 28,8 59 -> 67* 60 -> 31,11 62 -> 14* 68 -> 52* problem: DPs: TRS: a1(a1(b1(a1(a1(b1(a1(x))))))) -> a1(b1(a1(a1(b1(a1(a1(a1(b1(x))))))))) Qed