Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
TRS Stand 20472 pair #381711876
details
property
value
status
complete
benchmark
19.xml
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n056.star.cs.uiowa.edu
space
Various_04
run statistics
property
value
solver
Wanda
configuration
FirstOrder
runtime (wallclock)
0.101422071457 seconds
cpu usage
0.096803737
max memory
3223552.0
stage attributes
key
value
output-size
6622
starexec-result
YES
output
/export/starexec/sandbox2/solver/bin/starexec_run_FirstOrder /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES We consider the system theBenchmark. We are asked to determine termination of the following first-order TRS. !colon : [o * o] --> o e : [] --> o i : [o] --> o !colon(X, X) => e !colon(X, e) => X i(!colon(X, Y)) => !colon(Y, X) !colon(!colon(X, Y), Z) => !colon(X, !colon(Z, i(Y))) !colon(e, X) => i(X) i(i(X)) => X i(e) => e !colon(X, !colon(Y, i(X))) => i(Y) !colon(X, !colon(Y, !colon(i(X), Z))) => !colon(i(Z), Y) !colon(i(X), !colon(Y, X)) => i(Y) !colon(i(X), !colon(Y, !colon(X, Z))) => !colon(i(Z), Y) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): !colon(X, X) >? e !colon(X, e) >? X i(!colon(X, Y)) >? !colon(Y, X) !colon(!colon(X, Y), Z) >? !colon(X, !colon(Z, i(Y))) !colon(e, X) >? i(X) i(i(X)) >? X i(e) >? e !colon(X, !colon(Y, i(X))) >? i(Y) !colon(X, !colon(Y, !colon(i(X), Z))) >? !colon(i(Z), Y) !colon(i(X), !colon(Y, X)) >? i(Y) !colon(i(X), !colon(Y, !colon(X, Z))) >? !colon(i(Z), Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !colon = \y0y1.1 + y0 + y1 e = 0 i = \y0.y0 Using this interpretation, the requirements translate to: [[!colon(_x0, _x0)]] = 1 + 2x0 > 0 = [[e]] [[!colon(_x0, e)]] = 1 + x0 > x0 = [[_x0]] [[i(!colon(_x0, _x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[!colon(_x1, _x0)]] [[!colon(!colon(_x0, _x1), _x2)]] = 2 + x0 + x1 + x2 >= 2 + x0 + x1 + x2 = [[!colon(_x0, !colon(_x2, i(_x1)))]] [[!colon(e, _x0)]] = 1 + x0 > x0 = [[i(_x0)]] [[i(i(_x0))]] = x0 >= x0 = [[_x0]] [[i(e)]] = 0 >= 0 = [[e]] [[!colon(_x0, !colon(_x1, i(_x0)))]] = 2 + x1 + 2x0 > x1 = [[i(_x1)]] [[!colon(_x0, !colon(_x1, !colon(i(_x0), _x2)))]] = 3 + x1 + x2 + 2x0 > 1 + x1 + x2 = [[!colon(i(_x2), _x1)]] [[!colon(i(_x0), !colon(_x1, _x0))]] = 2 + x1 + 2x0 > x1 = [[i(_x1)]] [[!colon(i(_x0), !colon(_x1, !colon(_x0, _x2)))]] = 3 + x1 + x2 + 2x0 > 1 + x1 + x2 = [[!colon(i(_x2), _x1)]] We can thus remove the following rules: !colon(X, X) => e !colon(X, e) => X !colon(e, X) => i(X) !colon(X, !colon(Y, i(X))) => i(Y) !colon(X, !colon(Y, !colon(i(X), Z))) => !colon(i(Z), Y) !colon(i(X), !colon(Y, X)) => i(Y) !colon(i(X), !colon(Y, !colon(X, Z))) => !colon(i(Z), Y) We use the dependency pair framework as described in [Kop12, Ch. 6/7], with static dependency pairs (see [KusIsoSakBla09] and the adaptation for AFSMs in [Kop12, Ch. 7.8]). We thus obtain the following dependency pair problem (P_0, R_0, minimal, formative): Dependency Pairs P_0: 0] i#(!colon(X, Y)) =#> !colon#(Y, X) 1] !colon#(!colon(X, Y), Z) =#> !colon#(X, !colon(Z, i(Y))) 2] !colon#(!colon(X, Y), Z) =#> !colon#(Z, i(Y)) 3] !colon#(!colon(X, Y), Z) =#> i#(Y) Rules R_0: i(!colon(X, Y)) => !colon(Y, X) !colon(!colon(X, Y), Z) => !colon(X, !colon(Z, i(Y))) i(i(X)) => X i(e) => e Thus, the original system is terminating if (P_0, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_0, R_0, minimal, formative). The formative rules of (P_0, R_0) are R_1 ::= i(!colon(X, Y)) => !colon(Y, X)
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to TRS Stand 20472