TRS Innermost pair #487523965

details

property	value
status	complete
benchmark	#4.36.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	Applicative_AG01_innermost

run statistics

property	value
solver	AProVE
configuration	standard
runtime (wallclock)	3.92698693275 seconds
cpu usage	7.536390018
max memory	5.19897088E8

stage attributes

key	value
output-size	60951
starexec-result	YES

output

/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


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


YES
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


Termination w.r.t. Q of the given QTRS could be proven:

(0) QTRS
(1) DependencyPairsProof [EQUIVALENT, 91 ms]
(2) QDP
(3) DependencyGraphProof [EQUIVALENT, 0 ms]
(4) AND
    (5) QDP
        (6) UsableRulesProof [EQUIVALENT, 0 ms]
        (7) QDP
        (8) ATransformationProof [EQUIVALENT, 0 ms]
        (9) QDP
        (10) QReductionProof [EQUIVALENT, 0 ms]
        (11) QDP
        (12) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (13) YES
    (14) QDP
        (15) UsableRulesProof [EQUIVALENT, 0 ms]
        (16) QDP
        (17) ATransformationProof [EQUIVALENT, 0 ms]
        (18) QDP
        (19) QReductionProof [EQUIVALENT, 0 ms]
        (20) QDP
        (21) QDPOrderProof [EQUIVALENT, 23 ms]
        (22) QDP
        (23) DependencyGraphProof [EQUIVALENT, 0 ms]
        (24) TRUE
    (25) QDP
        (26) UsableRulesProof [EQUIVALENT, 0 ms]
        (27) QDP
        (28) ATransformationProof [EQUIVALENT, 0 ms]
        (29) QDP
        (30) QReductionProof [EQUIVALENT, 0 ms]
        (31) QDP
        (32) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (33) YES
    (34) QDP
        (35) UsableRulesProof [EQUIVALENT, 0 ms]
        (36) QDP
        (37) ATransformationProof [EQUIVALENT, 0 ms]
        (38) QDP
        (39) QReductionProof [EQUIVALENT, 0 ms]
        (40) QDP
        (41) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (42) YES
    (43) QDP
        (44) UsableRulesProof [EQUIVALENT, 0 ms]
        (45) QDP
        (46) ATransformationProof [EQUIVALENT, 0 ms]
        (47) QDP
        (48) QReductionProof [EQUIVALENT, 0 ms]
        (49) QDP
        (50) QDPOrderProof [EQUIVALENT, 245 ms]
        (51) QDP
        (52) PisEmptyProof [EQUIVALENT, 0 ms]
        (53) YES
    (54) QDP
        (55) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (56) YES


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

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

   app(app(eq, 0), 0) -> true
   app(app(eq, 0), app(s, m)) -> false
   app(app(eq, app(s, n)), 0) -> false
   app(app(eq, app(s, n)), app(s, m)) -> app(app(eq, n), m)
   app(app(le, 0), m) -> true
   app(app(le, app(s, n)), 0) -> false
   app(app(le, app(s, n)), app(s, m)) -> app(app(le, n), m)
   app(min, app(app(cons, 0), nil)) -> 0
   app(min, app(app(cons, app(s, n)), nil)) -> app(s, n)
   app(min, app(app(cons, n), app(app(cons, m), x))) -> app(app(if_min, app(app(le, n), m)), app(app(cons, n), app(app(cons, m), x)))
   app(app(if_min, true), app(app(cons, n), app(app(cons, m), x))) -> app(min, app(app(cons, n), x))
   app(app(if_min, false), app(app(cons, n), app(app(cons, m), x))) -> app(min, app(app(cons, m), x))
   app(app(app(replace, n), m), nil) -> nil
   app(app(app(replace, n), m), app(app(cons, k), x)) -> app(app(app(app(if_replace, app(app(eq, n), k)), n), m), app(app(cons, k), x))
   app(app(app(app(if_replace, true), n), m), app(app(cons, k), x)) -> app(app(cons, m), x)
   app(app(app(app(if_replace, false), n), m), app(app(cons, k), x)) -> app(app(cons, k), app(app(app(replace, n), m), x))
   app(sort, nil) -> nil
   app(sort, app(app(cons, n), x)) -> app(app(cons, app(min, app(app(cons, n), x))), app(sort, app(app(app(replace, app(min, app(app(cons, n), x))), n), x)))
   app(app(map, f), nil) -> nil
   app(app(map, f), app(app(cons, x), xs)) -> app(app(cons, app(f, x)), app(app(map, f), xs))
   app(app(filter, f), nil) -> nil

popout

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

job log

popout

actions all output return to TRS Innermost