/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: r0(0(x1)) -> 0(r0(x1)) r0(1(x1)) -> 1(r0(x1)) r0(m(x1)) -> m(r0(x1)) r1(0(x1)) -> 0(r1(x1)) r1(1(x1)) -> 1(r1(x1)) r1(m(x1)) -> m(r1(x1)) r0(b(x1)) -> qr(0(b(x1))) r1(b(x1)) -> qr(1(b(x1))) 0(qr(x1)) -> qr(0(x1)) 1(qr(x1)) -> qr(1(x1)) m(qr(x1)) -> ql(m(x1)) 0(ql(x1)) -> ql(0(x1)) 1(ql(x1)) -> ql(1(x1)) b(ql(0(x1))) -> 0(b(r0(x1))) b(ql(1(x1))) -> 1(b(r1(x1))) Proof: String Reversal Processor: 0(r0(x1)) -> r0(0(x1)) 1(r0(x1)) -> r0(1(x1)) m(r0(x1)) -> r0(m(x1)) 0(r1(x1)) -> r1(0(x1)) 1(r1(x1)) -> r1(1(x1)) m(r1(x1)) -> r1(m(x1)) b(r0(x1)) -> b(0(qr(x1))) b(r1(x1)) -> b(1(qr(x1))) qr(0(x1)) -> 0(qr(x1)) qr(1(x1)) -> 1(qr(x1)) qr(m(x1)) -> m(ql(x1)) ql(0(x1)) -> 0(ql(x1)) ql(1(x1)) -> 1(ql(x1)) 0(ql(b(x1))) -> r0(b(0(x1))) 1(ql(b(x1))) -> r1(b(1(x1))) Matrix Interpretation Processor: dim=3 interpretation: [1 0 0] [ql](x0) = [0 1 1]x0 [0 0 0] , [1 0 0] [qr](x0) = [0 0 0]x0 [0 0 0] , [1 0 0] [0] [b](x0) = [0 1 1]x0 + [0] [0 0 0] [1], [1 0 0] [r1](x0) = [0 1 1]x0 [0 0 0] , [1 0 0] [m](x0) = [0 0 0]x0 [0 0 0] , [1 1 1] [1](x0) = [0 1 0]x0 [0 0 1] , [1 0 0] [r0](x0) = [0 1 1]x0 [0 0 0] , [1 0 0] [0](x0) = [0 1 1]x0 [0 0 0] orientation: [1 0 0] [1 0 0] 0(r0(x1)) = [0 1 1]x1 >= [0 1 1]x1 = r0(0(x1)) [0 0 0] [0 0 0] [1 1 1] [1 1 1] 1(r0(x1)) = [0 1 1]x1 >= [0 1 1]x1 = r0(1(x1)) [0 0 0] [0 0 0] [1 0 0] [1 0 0] m(r0(x1)) = [0 0 0]x1 >= [0 0 0]x1 = r0(m(x1)) [0 0 0] [0 0 0] [1 0 0] [1 0 0] 0(r1(x1)) = [0 1 1]x1 >= [0 1 1]x1 = r1(0(x1)) [0 0 0] [0 0 0] [1 1 1] [1 1 1] 1(r1(x1)) = [0 1 1]x1 >= [0 1 1]x1 = r1(1(x1)) [0 0 0] [0 0 0] [1 0 0] [1 0 0] m(r1(x1)) = [0 0 0]x1 >= [0 0 0]x1 = r1(m(x1)) [0 0 0] [0 0 0] [1 0 0] [0] [1 0 0] [0] b(r0(x1)) = [0 1 1]x1 + [0] >= [0 0 0]x1 + [0] = b(0(qr(x1))) [0 0 0] [1] [0 0 0] [1] [1 0 0] [0] [1 0 0] [0] b(r1(x1)) = [0 1 1]x1 + [0] >= [0 0 0]x1 + [0] = b(1(qr(x1))) [0 0 0] [1] [0 0 0] [1] [1 0 0] [1 0 0] qr(0(x1)) = [0 0 0]x1 >= [0 0 0]x1 = 0(qr(x1)) [0 0 0] [0 0 0] [1 1 1] [1 0 0] qr(1(x1)) = [0 0 0]x1 >= [0 0 0]x1 = 1(qr(x1)) [0 0 0] [0 0 0] [1 0 0] [1 0 0] qr(m(x1)) = [0 0 0]x1 >= [0 0 0]x1 = m(ql(x1)) [0 0 0] [0 0 0] [1 0 0] [1 0 0] ql(0(x1)) = [0 1 1]x1 >= [0 1 1]x1 = 0(ql(x1)) [0 0 0] [0 0 0] [1 1 1] [1 1 1] ql(1(x1)) = [0 1 1]x1 >= [0 1 1]x1 = 1(ql(x1)) [0 0 0] [0 0 0] [1 0 0] [0] [1 0 0] [0] 0(ql(b(x1))) = [0 1 1]x1 + [1] >= [0 1 1]x1 + [1] = r0(b(0(x1))) [0 0 0] [0] [0 0 0] [0] [1 1 1] [1] [1 1 1] [0] 1(ql(b(x1))) = [0 1 1]x1 + [1] >= [0 1 1]x1 + [1] = r1(b(1(x1))) [0 0 0] [0] [0 0 0] [0] problem: 0(r0(x1)) -> r0(0(x1)) 1(r0(x1)) -> r0(1(x1)) m(r0(x1)) -> r0(m(x1)) 0(r1(x1)) -> r1(0(x1)) 1(r1(x1)) -> r1(1(x1)) m(r1(x1)) -> r1(m(x1)) b(r0(x1)) -> b(0(qr(x1))) b(r1(x1)) -> b(1(qr(x1))) qr(0(x1)) -> 0(qr(x1)) qr(1(x1)) -> 1(qr(x1)) qr(m(x1)) -> m(ql(x1)) ql(0(x1)) -> 0(ql(x1)) ql(1(x1)) -> 1(ql(x1)) 0(ql(b(x1))) -> r0(b(0(x1))) Matrix Interpretation Processor: dim=1 interpretation: [ql](x0) = 8x0, [qr](x0) = 8x0, [b](x0) = x0, [r1](x0) = 8x0 + 2, [m](x0) = 2x0, [1](x0) = x0, [r0](x0) = 8x0, [0](x0) = x0 orientation: 0(r0(x1)) = 8x1 >= 8x1 = r0(0(x1)) 1(r0(x1)) = 8x1 >= 8x1 = r0(1(x1)) m(r0(x1)) = 16x1 >= 16x1 = r0(m(x1)) 0(r1(x1)) = 8x1 + 2 >= 8x1 + 2 = r1(0(x1)) 1(r1(x1)) = 8x1 + 2 >= 8x1 + 2 = r1(1(x1)) m(r1(x1)) = 16x1 + 4 >= 16x1 + 2 = r1(m(x1)) b(r0(x1)) = 8x1 >= 8x1 = b(0(qr(x1))) b(r1(x1)) = 8x1 + 2 >= 8x1 = b(1(qr(x1))) qr(0(x1)) = 8x1 >= 8x1 = 0(qr(x1)) qr(1(x1)) = 8x1 >= 8x1 = 1(qr(x1)) qr(m(x1)) = 16x1 >= 16x1 = m(ql(x1)) ql(0(x1)) = 8x1 >= 8x1 = 0(ql(x1)) ql(1(x1)) = 8x1 >= 8x1 = 1(ql(x1)) 0(ql(b(x1))) = 8x1 >= 8x1 = r0(b(0(x1))) problem: 0(r0(x1)) -> r0(0(x1)) 1(r0(x1)) -> r0(1(x1)) m(r0(x1)) -> r0(m(x1)) 0(r1(x1)) -> r1(0(x1)) 1(r1(x1)) -> r1(1(x1)) b(r0(x1)) -> b(0(qr(x1))) qr(0(x1)) -> 0(qr(x1)) qr(1(x1)) -> 1(qr(x1)) qr(m(x1)) -> m(ql(x1)) ql(0(x1)) -> 0(ql(x1)) ql(1(x1)) -> 1(ql(x1)) 0(ql(b(x1))) -> r0(b(0(x1))) String Reversal Processor: r0(0(x1)) -> 0(r0(x1)) r0(1(x1)) -> 1(r0(x1)) r0(m(x1)) -> m(r0(x1)) r1(0(x1)) -> 0(r1(x1)) r1(1(x1)) -> 1(r1(x1)) r0(b(x1)) -> qr(0(b(x1))) 0(qr(x1)) -> qr(0(x1)) 1(qr(x1)) -> qr(1(x1)) m(qr(x1)) -> ql(m(x1)) 0(ql(x1)) -> ql(0(x1)) 1(ql(x1)) -> ql(1(x1)) b(ql(0(x1))) -> 0(b(r0(x1))) Matrix Interpretation Processor: dim=1 interpretation: [ql](x0) = 2x0 + 1, [qr](x0) = 2x0 + 1, [b](x0) = x0 + 8, [r1](x0) = 8x0 + 2, [m](x0) = 8x0 + 7, [1](x0) = 2x0 + 1, [r0](x0) = 2x0 + 1, [0](x0) = x0 orientation: r0(0(x1)) = 2x1 + 1 >= 2x1 + 1 = 0(r0(x1)) r0(1(x1)) = 4x1 + 3 >= 4x1 + 3 = 1(r0(x1)) r0(m(x1)) = 16x1 + 15 >= 16x1 + 15 = m(r0(x1)) r1(0(x1)) = 8x1 + 2 >= 8x1 + 2 = 0(r1(x1)) r1(1(x1)) = 16x1 + 10 >= 16x1 + 5 = 1(r1(x1)) r0(b(x1)) = 2x1 + 17 >= 2x1 + 17 = qr(0(b(x1))) 0(qr(x1)) = 2x1 + 1 >= 2x1 + 1 = qr(0(x1)) 1(qr(x1)) = 4x1 + 3 >= 4x1 + 3 = qr(1(x1)) m(qr(x1)) = 16x1 + 15 >= 16x1 + 15 = ql(m(x1)) 0(ql(x1)) = 2x1 + 1 >= 2x1 + 1 = ql(0(x1)) 1(ql(x1)) = 4x1 + 3 >= 4x1 + 3 = ql(1(x1)) b(ql(0(x1))) = 2x1 + 9 >= 2x1 + 9 = 0(b(r0(x1))) problem: r0(0(x1)) -> 0(r0(x1)) r0(1(x1)) -> 1(r0(x1)) r0(m(x1)) -> m(r0(x1)) r1(0(x1)) -> 0(r1(x1)) r0(b(x1)) -> qr(0(b(x1))) 0(qr(x1)) -> qr(0(x1)) 1(qr(x1)) -> qr(1(x1)) m(qr(x1)) -> ql(m(x1)) 0(ql(x1)) -> ql(0(x1)) 1(ql(x1)) -> ql(1(x1)) b(ql(0(x1))) -> 0(b(r0(x1))) Matrix Interpretation Processor: dim=3 interpretation: [ql](x0) = x0 , [qr](x0) = x0 , [1 1 0] [b](x0) = [0 0 0]x0 [0 0 0] , [1 1 1] [r1](x0) = [0 0 0]x0 [0 0 0] , [m](x0) = x0 , [0] [1](x0) = x0 + [1] [1], [1 0 1] [r0](x0) = [0 0 1]x0 [0 1 0] , [1 0 1] [0](x0) = [0 0 1]x0 [0 1 0] orientation: [1 1 1] [1 1 1] r0(0(x1)) = [0 1 0]x1 >= [0 1 0]x1 = 0(r0(x1)) [0 0 1] [0 0 1] [1 0 1] [1] [1 0 1] [0] r0(1(x1)) = [0 0 1]x1 + [1] >= [0 0 1]x1 + [1] = 1(r0(x1)) [0 1 0] [1] [0 1 0] [1] [1 0 1] [1 0 1] r0(m(x1)) = [0 0 1]x1 >= [0 0 1]x1 = m(r0(x1)) [0 1 0] [0 1 0] [1 1 2] [1 1 1] r1(0(x1)) = [0 0 0]x1 >= [0 0 0]x1 = 0(r1(x1)) [0 0 0] [0 0 0] [1 1 0] [1 1 0] r0(b(x1)) = [0 0 0]x1 >= [0 0 0]x1 = qr(0(b(x1))) [0 0 0] [0 0 0] [1 0 1] [1 0 1] 0(qr(x1)) = [0 0 1]x1 >= [0 0 1]x1 = qr(0(x1)) [0 1 0] [0 1 0] [0] [0] 1(qr(x1)) = x1 + [1] >= x1 + [1] = qr(1(x1)) [1] [1] m(qr(x1)) = x1 >= x1 = ql(m(x1)) [1 0 1] [1 0 1] 0(ql(x1)) = [0 0 1]x1 >= [0 0 1]x1 = ql(0(x1)) [0 1 0] [0 1 0] [0] [0] 1(ql(x1)) = x1 + [1] >= x1 + [1] = ql(1(x1)) [1] [1] [1 0 2] [1 0 2] b(ql(0(x1))) = [0 0 0]x1 >= [0 0 0]x1 = 0(b(r0(x1))) [0 0 0] [0 0 0] problem: r0(0(x1)) -> 0(r0(x1)) r0(m(x1)) -> m(r0(x1)) r1(0(x1)) -> 0(r1(x1)) r0(b(x1)) -> qr(0(b(x1))) 0(qr(x1)) -> qr(0(x1)) 1(qr(x1)) -> qr(1(x1)) m(qr(x1)) -> ql(m(x1)) 0(ql(x1)) -> ql(0(x1)) 1(ql(x1)) -> ql(1(x1)) b(ql(0(x1))) -> 0(b(r0(x1))) Matrix Interpretation Processor: dim=1 interpretation: [ql](x0) = 2x0 + 2, [qr](x0) = 2x0 + 2, [b](x0) = 8x0, [r1](x0) = x0 + 8, [m](x0) = x0, [1](x0) = 4x0 + 3, [r0](x0) = 2x0 + 2, [0](x0) = x0 orientation: r0(0(x1)) = 2x1 + 2 >= 2x1 + 2 = 0(r0(x1)) r0(m(x1)) = 2x1 + 2 >= 2x1 + 2 = m(r0(x1)) r1(0(x1)) = x1 + 8 >= x1 + 8 = 0(r1(x1)) r0(b(x1)) = 16x1 + 2 >= 16x1 + 2 = qr(0(b(x1))) 0(qr(x1)) = 2x1 + 2 >= 2x1 + 2 = qr(0(x1)) 1(qr(x1)) = 8x1 + 11 >= 8x1 + 8 = qr(1(x1)) m(qr(x1)) = 2x1 + 2 >= 2x1 + 2 = ql(m(x1)) 0(ql(x1)) = 2x1 + 2 >= 2x1 + 2 = ql(0(x1)) 1(ql(x1)) = 8x1 + 11 >= 8x1 + 8 = ql(1(x1)) b(ql(0(x1))) = 16x1 + 16 >= 16x1 + 16 = 0(b(r0(x1))) problem: r0(0(x1)) -> 0(r0(x1)) r0(m(x1)) -> m(r0(x1)) r1(0(x1)) -> 0(r1(x1)) r0(b(x1)) -> qr(0(b(x1))) 0(qr(x1)) -> qr(0(x1)) m(qr(x1)) -> ql(m(x1)) 0(ql(x1)) -> ql(0(x1)) b(ql(0(x1))) -> 0(b(r0(x1))) String Reversal Processor: 0(r0(x1)) -> r0(0(x1)) m(r0(x1)) -> r0(m(x1)) 0(r1(x1)) -> r1(0(x1)) b(r0(x1)) -> b(0(qr(x1))) qr(0(x1)) -> 0(qr(x1)) qr(m(x1)) -> m(ql(x1)) ql(0(x1)) -> 0(ql(x1)) 0(ql(b(x1))) -> r0(b(0(x1))) Matrix Interpretation Processor: dim=3 interpretation: [1 0 0] [ql](x0) = [0 1 0]x0 [0 0 0] , [1 0 0] [qr](x0) = [0 1 0]x0 [0 0 0] , [1 0 0] [b](x0) = [1 0 0]x0 [1 0 0] , [1 0 0] [0] [r1](x0) = [0 0 1]x0 + [1] [0 0 0] [0], [1 1 0] [0] [m](x0) = [0 1 0]x0 + [1] [0 0 1] [0], [1 0 0] [0] [r0](x0) = [0 1 1]x0 + [1] [0 0 0] [0], [1 0 0] [0] [0](x0) = [1 1 0]x0 + [1] [0 0 0] [0] orientation: [1 0 0] [0] [1 0 0] [0] 0(r0(x1)) = [1 1 1]x1 + [2] >= [1 1 0]x1 + [2] = r0(0(x1)) [0 0 0] [0] [0 0 0] [0] [1 1 1] [1] [1 1 0] [0] m(r0(x1)) = [0 1 1]x1 + [2] >= [0 1 1]x1 + [2] = r0(m(x1)) [0 0 0] [0] [0 0 0] [0] [1 0 0] [0] [1 0 0] [0] 0(r1(x1)) = [1 0 1]x1 + [2] >= [0 0 0]x1 + [1] = r1(0(x1)) [0 0 0] [0] [0 0 0] [0] [1 0 0] [1 0 0] b(r0(x1)) = [1 0 0]x1 >= [1 0 0]x1 = b(0(qr(x1))) [1 0 0] [1 0 0] [1 0 0] [0] [1 0 0] [0] qr(0(x1)) = [1 1 0]x1 + [1] >= [1 1 0]x1 + [1] = 0(qr(x1)) [0 0 0] [0] [0 0 0] [0] [1 1 0] [0] [1 1 0] [0] qr(m(x1)) = [0 1 0]x1 + [1] >= [0 1 0]x1 + [1] = m(ql(x1)) [0 0 0] [0] [0 0 0] [0] [1 0 0] [0] [1 0 0] [0] ql(0(x1)) = [1 1 0]x1 + [1] >= [1 1 0]x1 + [1] = 0(ql(x1)) [0 0 0] [0] [0 0 0] [0] [1 0 0] [0] [1 0 0] [0] 0(ql(b(x1))) = [2 0 0]x1 + [1] >= [2 0 0]x1 + [1] = r0(b(0(x1))) [0 0 0] [0] [0 0 0] [0] problem: 0(r0(x1)) -> r0(0(x1)) 0(r1(x1)) -> r1(0(x1)) b(r0(x1)) -> b(0(qr(x1))) qr(0(x1)) -> 0(qr(x1)) qr(m(x1)) -> m(ql(x1)) ql(0(x1)) -> 0(ql(x1)) 0(ql(b(x1))) -> r0(b(0(x1))) String Reversal Processor: r0(0(x1)) -> 0(r0(x1)) r1(0(x1)) -> 0(r1(x1)) r0(b(x1)) -> qr(0(b(x1))) 0(qr(x1)) -> qr(0(x1)) m(qr(x1)) -> ql(m(x1)) 0(ql(x1)) -> ql(0(x1)) b(ql(0(x1))) -> 0(b(r0(x1))) Bounds Processor: bound: 1 enrichment: match automaton: final states: {14,13,11,9,6,4,1} transitions: f80() -> 2* 00(15) -> 14* 00(5) -> 4* 00(7) -> 8* 00(2) -> 10* 00(3) -> 1* r00(2) -> 3* r10(2) -> 5* qr0(10) -> 9* qr0(8) -> 6* b0(2) -> 7* b0(3) -> 15* ql0(10) -> 13* ql0(12) -> 11* m0(2) -> 12* qr1(17) -> 18* 01(22) -> 23* 01(16) -> 17* 1 -> 3* 4 -> 5* 6 -> 3* 8 -> 16* 9 -> 10* 11 -> 12* 13 -> 10* 14 -> 7* 17 -> 22* 18 -> 1,3 23 -> 17* problem: Qed