TRS Stand 20472 pair #381711722

details
property	value
status	complete
benchmark	cime5.xml
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n028.star.cs.uiowa.edu
space	Secret_05_TRS
run statistics
property	value
solver	Wanda
configuration	FirstOrder
runtime (wallclock)	3.13282108307 seconds
cpu usage	3.129404932
max memory	8.7556096E7
stage attributes
key	value
output-size	54538
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.

  cons : [o * o] --> o 
  if : [o * o] --> o 
  iff : [o * o] --> o 
  intersect!450ii!450in : [o * o] --> o 
  intersect!450ii!450out : [] --> o 
  nil : [] --> o 
  p : [o] --> o 
  reduce!450ii!450in : [o * o] --> o 
  reduce!450ii!450out : [] --> o 
  sequent : [o * o] --> o 
  tautology!450i!450in : [o] --> o 
  tautology!450i!450out : [] --> o 
  u!4501!4501 : [o] --> o 
  u!45010!4501 : [o] --> o 
  u!45011!4501 : [o] --> o 
  u!45012!4501 : [o * o * o * o * o] --> o 
  u!45012!4502 : [o] --> o 
  u!45013!4501 : [o] --> o 
  u!45014!4501 : [o] --> o 
  u!45015!4501 : [o] --> o 
  u!45016!4501 : [o] --> o 
  u!4502!4501 : [o] --> o 
  u!4503!4501 : [o] --> o 
  u!4504!4501 : [o] --> o 
  u!4505!4501 : [o] --> o 
  u!4506!4501 : [o * o * o * o * o] --> o 
  u!4506!4502 : [o] --> o 
  u!4507!4501 : [o] --> o 
  u!4508!4501 : [o] --> o 
  u!4509!4501 : [o] --> o 
  x!4502a : [o * o] --> o 
  x!4502b : [o * o] --> o 
  x!4502d : [o] --> o 

  intersect!450ii!450in(cons(X, Y), cons(X, Z)) => intersect!450ii!450out 
  intersect!450ii!450in(X, cons(Y, Z)) => u!4501!4501(intersect!450ii!450in(X, Z)) 
  u!4501!4501(intersect!450ii!450out) => intersect!450ii!450out 
  intersect!450ii!450in(cons(X, Y), Z) => u!4502!4501(intersect!450ii!450in(Y, Z)) 
  u!4502!4501(intersect!450ii!450out) => intersect!450ii!450out 
  reduce!450ii!450in(sequent(cons(if(X, Y), Z), U), V) => u!4503!4501(reduce!450ii!450in(sequent(cons(x!4502b(x!4502d(Y), X), Z), U), V)) 
  u!4503!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(iff(X, Y), Z), U), V) => u!4504!4501(reduce!450ii!450in(sequent(cons(x!4502a(if(X, Y), if(Y, X)), Z), U), V)) 
  u!4504!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(x!4502a(X, Y), Z), U), V) => u!4505!4501(reduce!450ii!450in(sequent(cons(X, cons(Y, Z)), U), V)) 
  u!4505!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(x!4502b(X, Y), Z), U), V) => u!4506!4501(reduce!450ii!450in(sequent(cons(X, Z), U), V), Y, Z, U, V) 
  u!4506!4501(reduce!450ii!450out, X, Y, Z, U) => u!4506!4502(reduce!450ii!450in(sequent(cons(X, Y), Z), U)) 
  u!4506!4502(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(x!4502d(X), Y), Z), U) => u!4507!4501(reduce!450ii!450in(sequent(Y, cons(X, Z)), U)) 
  u!4507!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(if(Y, Z), U)), V) => u!4508!4501(reduce!450ii!450in(sequent(X, cons(x!4502b(x!4502d(Z), Y), U)), V)) 
  u!4508!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(iff(Y, Z), U)), V) => u!4509!4501(reduce!450ii!450in(sequent(X, cons(x!4502a(if(Y, Z), if(Z, Y)), U)), V)) 
  u!4509!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(p(X), Y), Z), sequent(U, V)) => u!45010!4501(reduce!450ii!450in(sequent(Y, Z), sequent(cons(p(X), U), V))) 
  u!45010!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(x!4502b(Y, Z), U)), V) => u!45011!4501(reduce!450ii!450in(sequent(X, cons(Y, cons(Z, U))), V)) 
  u!45011!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(x!4502a(Y, Z), U)), V) => u!45012!4501(reduce!450ii!450in(sequent(X, cons(Y, U)), V), X, Z, U, V) 
  u!45012!4501(reduce!450ii!450out, X, Y, Z, U) => u!45012!4502(reduce!450ii!450in(sequent(X, cons(Y, Z)), U)) 
  u!45012!4502(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(x!4502d(Y), Z)), U) => u!45013!4501(reduce!450ii!450in(sequent(cons(Y, X), Z), U)) 
  u!45013!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(nil, cons(p(X), Y)), sequent(Z, U)) => u!45014!4501(reduce!450ii!450in(sequent(nil, Y), sequent(Z, cons(p(X), U)))) 
  u!45014!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(nil, nil), sequent(X, Y)) => u!45015!4501(intersect!450ii!450in(X, Y)) 
  u!45015!4501(intersect!450ii!450out) => reduce!450ii!450out 
  tautology!450i!450in(X) => u!45016!4501(reduce!450ii!450in(sequent(nil, cons(X, nil)), sequent(nil, nil))) 
  u!45016!4501(reduce!450ii!450out) => tautology!450i!450out 

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, all):

  Dependency Pairs P_0:

    0] intersect!450ii!450in#(X, cons(Y, Z)) =#> u!4501!4501#(intersect!450ii!450in(X, Z))   
    1] intersect!450ii!450in#(X, cons(Y, Z)) =#> intersect!450ii!450in#(X, Z)   
    2] intersect!450ii!450in#(cons(X, Y), Z) =#> u!4502!4501#(intersect!450ii!450in(Y, Z))   
    3] intersect!450ii!450in#(cons(X, Y), Z) =#> intersect!450ii!450in#(Y, Z)   
    4] reduce!450ii!450in#(sequent(cons(if(X, Y), Z), U), V) =#> u!4503!4501#(reduce!450ii!450in(sequent(cons(x!4502b(x!4502d(Y), X), Z), U), V))   
    5] reduce!450ii!450in#(sequent(cons(if(X, Y), Z), U), V) =#> reduce!450ii!450in#(sequent(cons(x!4502b(x!4502d(Y), X), Z), U), V)   
    6] reduce!450ii!450in#(sequent(cons(iff(X, Y), Z), U), V) =#> u!4504!4501#(reduce!450ii!450in(sequent(cons(x!4502a(if(X, Y), if(Y, X)), Z), U), V))   
    7] reduce!450ii!450in#(sequent(cons(iff(X, Y), Z), U), V) =#> reduce!450ii!450in#(sequent(cons(x!4502a(if(X, Y), if(Y, X)), Z), U), V)   
    8] reduce!450ii!450in#(sequent(cons(x!4502a(X, Y), Z), U), V) =#> u!4505!4501#(reduce!450ii!450in(sequent(cons(X, cons(Y, Z)), U), V))   
    9] reduce!450ii!450in#(sequent(cons(x!4502a(X, Y), Z), U), V) =#> reduce!450ii!450in#(sequent(cons(X, cons(Y, Z)), U), V)   
    10] reduce!450ii!450in#(sequent(cons(x!4502b(X, Y), Z), U), V) =#> u!4506!4501#(reduce!450ii!450in(sequent(cons(X, Z), U), V), Y, Z, U, V)   
    11] reduce!450ii!450in#(sequent(cons(x!4502b(X, Y), Z), U), V) =#> reduce!450ii!450in#(sequent(cons(X, Z), U), V)   
    12] u!4506!4501#(reduce!450ii!450out, X, Y, Z, U) =#> u!4506!4502#(reduce!450ii!450in(sequent(cons(X, Y), Z), U))
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions all output return to TRS Stand 20472