TRS Equat 89423 pair #381732673

details

property	value
status	complete
benchmark	AC42.xml
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n022.star.cs.uiowa.edu
space	Mixed_C

run statistics

property	value
solver	AProVE
configuration	standard
runtime (wallclock)	1.87714195251 seconds
cpu usage	4.254743637
max memory	2.38403584E8

stage attributes

key	value
output-size	13462
starexec-result	YES

output

/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 of the given ETRS could be proven:

(0) ETRS
(1) EquationalDependencyPairsProof [EQUIVALENT, 0 ms]
(2) EDP
(3) EDependencyGraphProof [EQUIVALENT, 0 ms]
(4) AND
    (5) EDP
        (6) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
        (7) EDP
        (8) EUsableRulesReductionPairsProof [EQUIVALENT, 6 ms]
        (9) EDP
        (10) PisEmptyProof [EQUIVALENT, 0 ms]
        (11) YES
    (12) EDP
        (13) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
        (14) EDP
        (15) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
        (16) EDP
        (17) PisEmptyProof [EQUIVALENT, 0 ms]
        (18) YES
    (19) EDP
        (20) EDPPoloProof [EQUIVALENT, 0 ms]
        (21) EDP
        (22) PisEmptyProof [EQUIVALENT, 0 ms]
        (23) YES


----------------------------------------

(0)
Obligation:
Equational rewrite system:
The TRS R consists of the following rules:

   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   pred(s(x)) -> x
   minus(x, 0) -> x
   minus(x, s(y)) -> pred(minus(x, y))
   gcd(0, y) -> y
   gcd(s(x), 0) -> s(x)
   gcd(s(x), s(y)) -> if_gcd(le(y, x), s(x), s(y))
   if_gcd(true, s(x), s(y)) -> gcd(minus(x, y), s(y))
   if_gcd(false, s(x), s(y)) -> gcd(minus(y, x), s(x))

The set E consists of the following equations:

   gcd(x, y) == gcd(y, x)


----------------------------------------

(1) EquationalDependencyPairsProof (EQUIVALENT)
Using Dependency Pairs [AG00,DA_STEIN] we result in the following initial EDP problem:
The TRS P consists of the following rules:

   LE(s(x), s(y)) -> LE(x, y)
   MINUS(x, s(y)) -> PRED(minus(x, y))
   MINUS(x, s(y)) -> MINUS(x, y)
   GCD(s(x), s(y)) -> IF_GCD(le(y, x), s(x), s(y))
   GCD(s(x), s(y)) -> LE(y, x)
   IF_GCD(true, s(x), s(y)) -> GCD(minus(x, y), s(y))
   IF_GCD(true, s(x), s(y)) -> MINUS(x, y)
   IF_GCD(false, s(x), s(y)) -> GCD(minus(y, x), s(x))
   IF_GCD(false, s(x), s(y)) -> MINUS(y, x)

The TRS R consists of the following rules:

   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   pred(s(x)) -> x
   minus(x, 0) -> x
   minus(x, s(y)) -> pred(minus(x, y))
   gcd(0, y) -> y
   gcd(s(x), 0) -> s(x)
   gcd(s(x), s(y)) -> if_gcd(le(y, x), s(x), s(y))
   if_gcd(true, s(x), s(y)) -> gcd(minus(x, y), s(y))
   if_gcd(false, s(x), s(y)) -> gcd(minus(y, x), s(x))

The set E consists of the following equations:

   gcd(x, y) == gcd(y, x)

The set E# consists of the following equations:

   GCD(x, y) == GCD(y, x)

popout

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

job log

popout

actions all output return to TRS Equat 89423