TRS Stand 20472 pair #381710740

details

property	value
status	complete
benchmark	ternary-hard.xml
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n020.star.cs.uiowa.edu
space	CiME_04

run statistics

property	value
solver	Wanda
configuration	FirstOrder
runtime (wallclock)	0.343022108078 seconds
cpu usage	0.3397846
max memory	1.3881344E7

stage attributes

key	value
output-size	16691
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.

  !940 : [] --> o 
  !minus : [o * o] --> o 
  !plus : [o * o] --> o 
  !times : [o * o] --> o 
  0 : [o] --> o 
  1 : [o] --> o 
  j : [o] --> o 
  opp : [o] --> o 

  0(!940) => !940 
  !plus(!940, X) => X 
  !plus(X, !940) => X 
  !plus(0(X), 0(Y)) => 0(!plus(X, Y)) 
  !plus(0(X), 1(Y)) => 1(!plus(X, Y)) 
  !plus(1(X), 0(Y)) => 1(!plus(X, Y)) 
  !plus(0(X), j(Y)) => j(!plus(X, Y)) 
  !plus(j(X), 0(Y)) => j(!plus(X, Y)) 
  !plus(1(X), 1(Y)) => j(!plus(!plus(X, Y), 1(!940))) 
  !plus(j(X), j(Y)) => 1(!plus(!plus(X, Y), j(!940))) 
  !plus(1(X), j(Y)) => 0(!plus(X, Y)) 
  !plus(j(X), 1(Y)) => 0(!plus(X, Y)) 
  !plus(!plus(X, Y), Z) => !plus(X, !plus(Y, Z)) 
  opp(!940) => !940 
  opp(0(X)) => 0(opp(X)) 
  opp(1(X)) => j(opp(X)) 
  opp(j(X)) => 1(opp(X)) 
  !minus(X, Y) => !plus(X, opp(Y)) 
  !times(!940, X) => !940 
  !times(0(X), Y) => 0(!times(X, Y)) 
  !times(1(X), Y) => !plus(0(!times(X, Y)), Y) 
  !times(j(X), Y) => !minus(0(!times(X, Y)), Y) 
  !times(!times(X, Y), Z) => !times(X, !times(Y, Z)) 
  !times(!plus(X, Y), Z) => !plus(!times(X, Z), !times(Y, Z)) 
  !times(X, !plus(Y, Z)) => !plus(!times(X, Y), !times(X, Z)) 

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] !plus#(0(X), 0(Y)) =#> 0#(!plus(X, Y))   
    1] !plus#(0(X), 0(Y)) =#> !plus#(X, Y)   
    2] !plus#(0(X), 1(Y)) =#> !plus#(X, Y)   
    3] !plus#(1(X), 0(Y)) =#> !plus#(X, Y)   
    4] !plus#(0(X), j(Y)) =#> !plus#(X, Y)   
    5] !plus#(j(X), 0(Y)) =#> !plus#(X, Y)   
    6] !plus#(1(X), 1(Y)) =#> !plus#(!plus(X, Y), 1(!940))   
    7] !plus#(1(X), 1(Y)) =#> !plus#(X, Y)   
    8] !plus#(j(X), j(Y)) =#> !plus#(!plus(X, Y), j(!940))   
    9] !plus#(j(X), j(Y)) =#> !plus#(X, Y)   
    10] !plus#(1(X), j(Y)) =#> 0#(!plus(X, Y))   
    11] !plus#(1(X), j(Y)) =#> !plus#(X, Y)   
    12] !plus#(j(X), 1(Y)) =#> 0#(!plus(X, Y))   
    13] !plus#(j(X), 1(Y)) =#> !plus#(X, Y)   
    14] !plus#(!plus(X, Y), Z) =#> !plus#(X, !plus(Y, Z))   
    15] !plus#(!plus(X, Y), Z) =#> !plus#(Y, Z)   
    16] opp#(0(X)) =#> 0#(opp(X))   
    17] opp#(0(X)) =#> opp#(X)   
    18] opp#(1(X)) =#> opp#(X)   
    19] opp#(j(X)) =#> opp#(X)   
    20] !minus#(X, Y) =#> !plus#(X, opp(Y))   
    21] !minus#(X, Y) =#> opp#(Y)   
    22] !times#(0(X), Y) =#> 0#(!times(X, Y))   
    23] !times#(0(X), Y) =#> !times#(X, Y)   
    24] !times#(1(X), Y) =#> !plus#(0(!times(X, Y)), Y)   
    25] !times#(1(X), Y) =#> 0#(!times(X, Y))   
    26] !times#(1(X), Y) =#> !times#(X, Y)   
    27] !times#(j(X), Y) =#> !minus#(0(!times(X, Y)), Y)   
    28] !times#(j(X), Y) =#> 0#(!times(X, Y))   
    29] !times#(j(X), Y) =#> !times#(X, Y)   
    30] !times#(!times(X, Y), Z) =#> !times#(X, !times(Y, Z))   
    31] !times#(!times(X, Y), Z) =#> !times#(Y, Z)   
    32] !times#(!plus(X, Y), Z) =#> !plus#(!times(X, Z), !times(Y, Z))   
    33] !times#(!plus(X, Y), Z) =#> !times#(X, Z)   
    34] !times#(!plus(X, Y), Z) =#> !times#(Y, Z)   
    35] !times#(X, !plus(Y, Z)) =#> !plus#(!times(X, Y), !times(X, Z))   
    36] !times#(X, !plus(Y, Z)) =#> !times#(X, Y)   
    37] !times#(X, !plus(Y, Z)) =#> !times#(X, Z)   

  Rules R_0:

    0(!940) => !940 
    !plus(!940, X) => X 
    !plus(X, !940) => X 
    !plus(0(X), 0(Y)) => 0(!plus(X, Y)) 
    !plus(0(X), 1(Y)) => 1(!plus(X, Y)) 
    !plus(1(X), 0(Y)) => 1(!plus(X, Y)) 
    !plus(0(X), j(Y)) => j(!plus(X, Y))

popout

output may be truncated. 'popout' for the full output.

job log

popout

actions all output return to TRS Stand 20472