Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
HRS union beta 16688 pair #381734929
details
property
value
status
complete
benchmark
Applicative_first_order_05__31.xml
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n093.star.cs.uiowa.edu
space
Uncurried_Applicative_11
run statistics
property
value
solver
Wanda
configuration
HigherOrder
runtime (wallclock)
0.233746051788 seconds
cpu usage
0.22974382
max memory
1.3910016E7
stage attributes
key
value
output-size
8710
starexec-result
YES
output
/export/starexec/sandbox2/solver/bin/starexec_run_HigherOrder /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES We consider the system theBenchmark. Alphabet: !faccolon : [] --> b -> b -> b !facplus : [] --> b -> b -> b a : [] --> b cons : [] --> d -> e -> e false : [] --> c filter : [] --> d -> c -> e -> e filter2 : [] --> c -> d -> c -> d -> e -> e g : [] --> b -> a -> b map : [] --> d -> d -> e -> e nil : [] --> e true : [] --> c Rules: !faccolon (!faccolon x y) z => !faccolon x (!faccolon y z) !faccolon (!facplus x y) z => !facplus (!faccolon x z) (!faccolon y z) !faccolon x (!facplus y (f z)) => !faccolon (g x z) (!facplus y a) map f nil => nil map f (cons x y) => cons (f x) (map f y) filter f nil => nil filter f (cons x y) => filter2 (f x) f x y filter2 true f x y => cons x (filter f y) filter2 false f x y => filter f y Using the transformations described in [Kop11], this system can be brought in a form without leading free variables in the left-hand side, and where the left-hand side of a variable is always a functional term or application headed by a functional term. We now transform the resulting AFS into an AFSM by replacing all free variables by meta-variables (with arity 0). This leads to the following AFSM: Alphabet: !faccolon : [b * b] --> b !facplus : [b * b] --> b a : [] --> b cons : [d * e] --> e false : [] --> c filter : [d -> c * e] --> e filter2 : [c * d -> c * d * e] --> e g : [b * a] --> b map : [d -> d * e] --> e nil : [] --> e true : [] --> c ~AP1 : [a -> b * a] --> b Rules: !faccolon(!faccolon(X, Y), Z) => !faccolon(X, !faccolon(Y, Z)) !faccolon(!facplus(X, Y), Z) => !facplus(!faccolon(X, Z), !faccolon(Y, Z)) !faccolon(X, !facplus(Y, ~AP1(F, Z))) => !faccolon(g(X, Z), !facplus(Y, a)) map(F, nil) => nil map(F, cons(X, Y)) => cons(F X, map(F, Y)) filter(F, nil) => nil filter(F, cons(X, Y)) => filter2(F X, F, X, Y) filter2(true, F, X, Y) => cons(X, filter(F, Y)) filter2(false, F, X, Y) => filter(F, Y) !faccolon(X, !facplus(Y, g(Z, U))) => !faccolon(g(X, U), !facplus(Y, a)) ~AP1(F, X) => F X We use the dependency pair framework as described in [Kop12, Ch. 6/7], with static dependency pairs (see [KusIsoSakBla09] and the adaptation for AFSMs and accessible arguments in [Kop13]). We thus obtain the following dependency pair problem (P_0, R_0, static, formative): Dependency Pairs P_0: 0] !faccolon#(!faccolon(X, Y), Z) =#> !faccolon#(X, !faccolon(Y, Z)) 1] !faccolon#(!faccolon(X, Y), Z) =#> !faccolon#(Y, Z) 2] !faccolon#(!facplus(X, Y), Z) =#> !faccolon#(X, Z) 3] !faccolon#(!facplus(X, Y), Z) =#> !faccolon#(Y, Z) 4] !faccolon#(X, !facplus(Y, ~AP1(F, Z))) =#> !faccolon#(g(X, Z), !facplus(Y, a)) 5] map#(F, cons(X, Y)) =#> map#(F, Y) 6] filter#(F, cons(X, Y)) =#> filter2#(F X, F, X, Y) 7] filter2#(true, F, X, Y) =#> filter#(F, Y) 8] filter2#(false, F, X, Y) =#> filter#(F, Y) 9] !faccolon#(X, !facplus(Y, g(Z, U))) =#> !faccolon#(g(X, U), !facplus(Y, a)) Rules R_0: !faccolon(!faccolon(X, Y), Z) => !faccolon(X, !faccolon(Y, Z)) !faccolon(!facplus(X, Y), Z) => !facplus(!faccolon(X, Z), !faccolon(Y, Z)) !faccolon(X, !facplus(Y, ~AP1(F, Z))) => !faccolon(g(X, Z), !facplus(Y, a)) map(F, nil) => nil map(F, cons(X, Y)) => cons(F X, map(F, Y)) filter(F, nil) => nil filter(F, cons(X, Y)) => filter2(F X, F, X, Y) filter2(true, F, X, Y) => cons(X, filter(F, Y)) filter2(false, F, X, Y) => filter(F, Y) !faccolon(X, !facplus(Y, g(Z, U))) => !faccolon(g(X, U), !facplus(Y, a)) ~AP1(F, X) => F X Thus, the original system is terminating if (P_0, R_0, static, formative) is finite.
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to HRS union beta 16688