/export/starexec/sandbox/solver/bin/starexec_run_ttt2 /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/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: [a1](x0) = x0 , [0] [a0] = [1] [0], [0] [b0] = [0] [0], [1 0 0] [0] [b1](x0) = [0 0 0]x0 + [1] [0 1 0] [0], [1 1 0] [1 1 1] [0] [f](x0, x1) = [0 0 0]x0 + [0 1 1]x1 + [1] [0 0 0] [1 1 1] [0] orientation: [1 0 0] [0] [1 0 0] [0] a1(a1(b1(a1(a1(b1(a1(x))))))) = [0 0 0]x + [1] >= [0 0 0]x + [1] = a1(b1(a1(a1(b1(a1(a1(a1(b1(x))))))))) [0 0 0] [1] [0 0 0] [1] [1 1 1] [1] f(a0(),x1) = [0 1 1]x1 + [1] >= x1 = a1(x1) [1 1 1] [0] [1 1 1] [0] [1 0 0] [0] f(b0(),x3) = [0 1 1]x3 + [1] >= [0 0 0]x3 + [1] = b1(x3) [1 1 1] [0] [0 1 0] [0] 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] [a1](x0) = [0 0 0]x0 [0 0 0] , [0] [b0] = [0] [1], [1 0 0] [b1](x0) = [1 0 0]x0 [0 0 0] , [1 0 1] [1 0 0] [f](x0, x1) = [0 0 0]x0 + [1 0 0]x1 [0 0 0] [1 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 0] [0 0 0] [1 0 0] [1] [1 0 0] f(b0(),x3) = [1 0 0]x3 + [0] >= [1 0 0]x3 = b1(x3) [1 0 1] [0] [0 0 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: a{1,1}(43) -> 44* a{1,1}(45) -> 46* a{1,1}(47) -> 48* a{1,1}(44) -> 45* a{1,#,1}(48) -> 49* b{1,0}(2) -> 3* b{1,0}(80) -> 81* b{1,0}(67) -> 68* b{1,0}(6) -> 7* b{1,0}(84) -> 85* b{1,0}(87) -> 88* b{1,0}(19) -> 20* f80() -> 2* a{1,0}(7) -> 8* a{1,0}(5) -> 6* a{1,0}(81) -> 82* a{1,0}(3) -> 4* a{1,0}(86) -> 87* a{1,0}(66) -> 67* a{1,0}(18) -> 19* a{1,0}(85) -> 86* a{1,0}(83) -> 84* a{1,0}(4) -> 5* a{1,0}(82) -> 83* a{1,0}(20) -> 21* a{1,#,0}(64) -> 65* a{1,#,0}(8) -> 1* a{1,#,0}(50) -> 51* b{1,1}(42) -> 43* b{1,1}(46) -> 47* 19 -> 87* 68 -> 18* 48 -> 66* 45 -> 50* 88 -> 5* 6 -> 84* 21 -> 83,5 44 -> 64* 8 -> 18* 49 -> 1* 65 -> 1* 5 -> 80* 18 -> 42* 51 -> 1* 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: a{1,1}(59) -> 60* a{1,1}(54) -> 55* a{1,1}(33) -> 34* a{1,1}(35) -> 36* a{1,1}(15) -> 16* a{1,1}(32) -> 33* a{1,1}(30) -> 31* a{1,1}(28) -> 29* a{1,1}(14) -> 15* a{1,1}(56) -> 57* a{1,1}(57) -> 58* a{1,1}(29) -> 30* a{1,#,1}(23) -> 24* a{1,#,1}(16) -> 17* b{1,0}(2) -> 3* b{1,0}(11) -> 12* b{1,0}(8) -> 9* a{1,0}(5) -> 8* a{1,0}(10) -> 11* a{1,0}(3) -> 4* a{1,0}(9) -> 10* a{1,0}(12) -> 7* a{1,0}(4) -> 5* a{1,#,0}(4) -> 6* a{1,#,0}(5) -> 1* f160() -> 2* b{1,1}(31) -> 32* b{1,1}(13) -> 14* b{1,1}(58) -> 59* b{1,1}(67) -> 68* b{1,1}(61) -> 62* b{1,1}(55) -> 56* b{1,1}(34) -> 35* b{1,1}(27) -> 28* 24 -> 17,1,6 68 -> 28* 17 -> 1,6 35 -> 67* 7 -> 16,54,5 16 -> 54* 6 -> 1* 36 -> 58,11 60 -> 55,8 1 -> 24,6 62 -> 14* 59 -> 61* 5 -> 13* 15 -> 23* 10 -> 27* problem: DPs: TRS: a1(a1(b1(a1(a1(b1(a1(x))))))) -> a1(b1(a1(a1(b1(a1(a1(a1(b1(x))))))))) Qed