/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) QTRSRRRProof [EQUIVALENT, 310 ms] (2) QTRS (3) QTRSRRRProof [EQUIVALENT, 24 ms] (4) QTRS (5) RisEmptyProof [EQUIVALENT, 0 ms] (6) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a__U11(tt, V1, V2) -> a__U12(a__isNat(V1), V2) a__U12(tt, V2) -> a__U13(a__isNat(V2)) a__U13(tt) -> tt a__U21(tt, V1) -> a__U22(a__isNat(V1)) a__U22(tt) -> tt a__U31(tt, N) -> mark(N) a__U41(tt, M, N) -> s(a__plus(mark(N), mark(M))) a__and(tt, X) -> mark(X) a__isNat(0) -> tt a__isNat(plus(V1, V2)) -> a__U11(a__and(a__isNatKind(V1), isNatKind(V2)), V1, V2) a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) a__isNatKind(0) -> tt a__isNatKind(plus(V1, V2)) -> a__and(a__isNatKind(V1), isNatKind(V2)) a__isNatKind(s(V1)) -> a__isNatKind(V1) a__plus(N, 0) -> a__U31(a__and(a__isNat(N), isNatKind(N)), N) a__plus(N, s(M)) -> a__U41(a__and(a__and(a__isNat(M), isNatKind(M)), and(isNat(N), isNatKind(N))), M, N) mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) mark(U12(X1, X2)) -> a__U12(mark(X1), X2) mark(isNat(X)) -> a__isNat(X) mark(U13(X)) -> a__U13(mark(X)) mark(U21(X1, X2)) -> a__U21(mark(X1), X2) mark(U22(X)) -> a__U22(mark(X)) mark(U31(X1, X2)) -> a__U31(mark(X1), X2) mark(U41(X1, X2, X3)) -> a__U41(mark(X1), X2, X3) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(and(X1, X2)) -> a__and(mark(X1), X2) mark(isNatKind(X)) -> a__isNatKind(X) mark(tt) -> tt mark(s(X)) -> s(mark(X)) mark(0) -> 0 a__U11(X1, X2, X3) -> U11(X1, X2, X3) a__U12(X1, X2) -> U12(X1, X2) a__isNat(X) -> isNat(X) a__U13(X) -> U13(X) a__U21(X1, X2) -> U21(X1, X2) a__U22(X) -> U22(X) a__U31(X1, X2) -> U31(X1, X2) a__U41(X1, X2, X3) -> U41(X1, X2, X3) a__plus(X1, X2) -> plus(X1, X2) a__and(X1, X2) -> and(X1, X2) a__isNatKind(X) -> isNatKind(X) Q is empty. ---------------------------------------- (1) QTRSRRRProof (EQUIVALENT) Used ordering: a__U11/3(YES,YES,YES) tt/0) a__U12/2(YES,YES) a__isNat/1(YES) a__U13/1)YES( a__U21/2(YES,YES) a__U22/1)YES( a__U31/2(YES,YES) mark/1)YES( a__U41/3(YES,YES,YES) s/1(YES) a__plus/2(YES,YES) a__and/2(YES,YES) 0/0) plus/2(YES,YES) a__isNatKind/1)YES( isNatKind/1)YES( and/2(YES,YES) isNat/1(YES) U11/3(YES,YES,YES) U12/2(YES,YES) U13/1)YES( U21/2(YES,YES) U22/1)YES( U31/2(YES,YES) U41/3(YES,YES,YES) Quasi precedence: [a__U41_3, a__plus_2, plus_2, U41_3] > [a__U11_3, U11_3] > [a__U12_2, a__isNat_1, isNat_1, U12_2] [a__U41_3, a__plus_2, plus_2, U41_3] > [a__U31_2, U31_2] [a__U41_3, a__plus_2, plus_2, U41_3] > s_1 > [a__U21_2, U21_2] > [a__U12_2, a__isNat_1, isNat_1, U12_2] [a__U41_3, a__plus_2, plus_2, U41_3] > s_1 > [a__and_2, and_2] 0 > tt > [a__U12_2, a__isNat_1, isNat_1, U12_2] 0 > [a__U31_2, U31_2] 0 > [a__and_2, and_2] Status: a__U11_3: multiset status tt: multiset status a__U12_2: multiset status a__isNat_1: multiset status a__U21_2: multiset status a__U31_2: multiset status a__U41_3: [2,3,1] s_1: multiset status a__plus_2: [2,1] a__and_2: multiset status 0: multiset status plus_2: [2,1] and_2: multiset status isNat_1: multiset status U11_3: multiset status U12_2: multiset status U21_2: multiset status U31_2: multiset status U41_3: [2,3,1] With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: a__U11(tt, V1, V2) -> a__U12(a__isNat(V1), V2) a__U12(tt, V2) -> a__U13(a__isNat(V2)) a__U21(tt, V1) -> a__U22(a__isNat(V1)) a__U31(tt, N) -> mark(N) a__U41(tt, M, N) -> s(a__plus(mark(N), mark(M))) a__and(tt, X) -> mark(X) a__isNat(0) -> tt a__isNat(plus(V1, V2)) -> a__U11(a__and(a__isNatKind(V1), isNatKind(V2)), V1, V2) a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) a__isNatKind(0) -> tt a__isNatKind(plus(V1, V2)) -> a__and(a__isNatKind(V1), isNatKind(V2)) a__isNatKind(s(V1)) -> a__isNatKind(V1) a__plus(N, 0) -> a__U31(a__and(a__isNat(N), isNatKind(N)), N) a__plus(N, s(M)) -> a__U41(a__and(a__and(a__isNat(M), isNatKind(M)), and(isNat(N), isNatKind(N))), M, N) ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a__U13(tt) -> tt a__U22(tt) -> tt mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) mark(U12(X1, X2)) -> a__U12(mark(X1), X2) mark(isNat(X)) -> a__isNat(X) mark(U13(X)) -> a__U13(mark(X)) mark(U21(X1, X2)) -> a__U21(mark(X1), X2) mark(U22(X)) -> a__U22(mark(X)) mark(U31(X1, X2)) -> a__U31(mark(X1), X2) mark(U41(X1, X2, X3)) -> a__U41(mark(X1), X2, X3) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(and(X1, X2)) -> a__and(mark(X1), X2) mark(isNatKind(X)) -> a__isNatKind(X) mark(tt) -> tt mark(s(X)) -> s(mark(X)) mark(0) -> 0 a__U11(X1, X2, X3) -> U11(X1, X2, X3) a__U12(X1, X2) -> U12(X1, X2) a__isNat(X) -> isNat(X) a__U13(X) -> U13(X) a__U21(X1, X2) -> U21(X1, X2) a__U22(X) -> U22(X) a__U31(X1, X2) -> U31(X1, X2) a__U41(X1, X2, X3) -> U41(X1, X2, X3) a__plus(X1, X2) -> plus(X1, X2) a__and(X1, X2) -> and(X1, X2) a__isNatKind(X) -> isNatKind(X) Q is empty. ---------------------------------------- (3) QTRSRRRProof (EQUIVALENT) Used ordering: Knuth-Bendix order [KBO] with precedence:mark_1 > a__U11_3 > tt > 0 > s_1 > a__isNatKind_1 > U11_3 > a__U12_2 > a__U41_3 > a__U22_1 > U22_1 > U41_3 > isNatKind_1 > a__isNat_1 > U12_2 > a__U13_1 > U13_1 > a__plus_2 > a__U21_2 > a__U31_2 > U21_2 > a__and_2 > and_2 > plus_2 > U31_2 > isNat_1 and weight map: tt=1 0=1 a__U13_1=1 a__U22_1=1 mark_1=0 isNat_1=1 a__isNat_1=1 U13_1=1 U22_1=1 isNatKind_1=1 a__isNatKind_1=1 s_1=1 U11_3=0 a__U11_3=0 U12_2=0 a__U12_2=0 U21_2=0 a__U21_2=0 U31_2=0 a__U31_2=0 U41_3=0 a__U41_3=0 plus_2=0 a__plus_2=0 and_2=0 a__and_2=0 The variable weight is 1With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: a__U13(tt) -> tt a__U22(tt) -> tt mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) mark(U12(X1, X2)) -> a__U12(mark(X1), X2) mark(isNat(X)) -> a__isNat(X) mark(U13(X)) -> a__U13(mark(X)) mark(U21(X1, X2)) -> a__U21(mark(X1), X2) mark(U22(X)) -> a__U22(mark(X)) mark(U31(X1, X2)) -> a__U31(mark(X1), X2) mark(U41(X1, X2, X3)) -> a__U41(mark(X1), X2, X3) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(and(X1, X2)) -> a__and(mark(X1), X2) mark(isNatKind(X)) -> a__isNatKind(X) mark(tt) -> tt mark(s(X)) -> s(mark(X)) mark(0) -> 0 a__U11(X1, X2, X3) -> U11(X1, X2, X3) a__U12(X1, X2) -> U12(X1, X2) a__isNat(X) -> isNat(X) a__U13(X) -> U13(X) a__U21(X1, X2) -> U21(X1, X2) a__U22(X) -> U22(X) a__U31(X1, X2) -> U31(X1, X2) a__U41(X1, X2, X3) -> U41(X1, X2, X3) a__plus(X1, X2) -> plus(X1, X2) a__and(X1, X2) -> and(X1, X2) a__isNatKind(X) -> isNatKind(X) ---------------------------------------- (4) Obligation: Q restricted rewrite system: R is empty. Q is empty. ---------------------------------------- (5) RisEmptyProof (EQUIVALENT) The TRS R is empty. Hence, termination is trivially proven. ---------------------------------------- (6) YES