Java_Bytecode pair #487571601

details

property	value
status	complete
benchmark	Test7.jar
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n084.star.cs.uiowa.edu
space	Julia_10_Iterative

run statistics

property	value
solver	AProVE
configuration	standard
runtime (wallclock)	3.85149598122 seconds
cpu usage	10.708857587
max memory	8.5551104E8

stage attributes

key	value
output-size	53852
starexec-result	YES

output

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


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


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


termination of the given Bare JBC problem could be proven:

(0) Bare JBC problem
(1) BareJBCToJBCProof [EQUIVALENT, 96 ms]
(2) JBC problem
(3) JBCToGraph [EQUIVALENT, 622 ms]
(4) JBCTerminationGraph
(5) TerminationGraphToSCCProof [SOUND, 0 ms]
(6) AND
    (7) JBCTerminationSCC
        (8) SCCToIRSProof [SOUND, 43 ms]
        (9) IRSwT
        (10) IRSFormatTransformerProof [EQUIVALENT, 0 ms]
        (11) IRSwT
        (12) IRSwTTerminationDigraphProof [EQUIVALENT, 11 ms]
        (13) IRSwT
        (14) IntTRSCompressionProof [EQUIVALENT, 0 ms]
        (15) IRSwT
        (16) TempFilterProof [SOUND, 2 ms]
        (17) IRSwT
        (18) IRSwTToQDPProof [SOUND, 0 ms]
        (19) QDP
        (20) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (21) YES
    (22) JBCTerminationSCC
        (23) SCCToQDPProof [SOUND, 100 ms]
        (24) QDP
        (25) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (26) YES
    (27) JBCTerminationSCC
        (28) SCCToIRSProof [SOUND, 45 ms]
        (29) IRSwT
        (30) IRSFormatTransformerProof [EQUIVALENT, 0 ms]
        (31) IRSwT
        (32) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms]
        (33) IRSwT
        (34) IntTRSCompressionProof [EQUIVALENT, 0 ms]
        (35) IRSwT
        (36) TempFilterProof [SOUND, 5 ms]
        (37) IntTRS
        (38) RankingReductionPairProof [EQUIVALENT, 0 ms]
        (39) YES
    (40) JBCTerminationSCC
        (41) SCCToIRSProof [SOUND, 44 ms]
        (42) IRSwT
        (43) IRSFormatTransformerProof [EQUIVALENT, 0 ms]
        (44) IRSwT
        (45) IRSwTTerminationDigraphProof [EQUIVALENT, 24 ms]
        (46) IRSwT
        (47) IntTRSCompressionProof [EQUIVALENT, 0 ms]
        (48) IRSwT
        (49) TempFilterProof [SOUND, 45 ms]
        (50) IntTRS
        (51) RankingReductionPairProof [EQUIVALENT, 26 ms]
        (52) IntTRS
        (53) RankingReductionPairProof [EQUIVALENT, 0 ms]
        (54) YES


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

(0)
Obligation:
need to prove termination of the following program:
public class Test7 {
    public static void main(String[] args) {
	List[] ls = { List.mk(args.length), List.mk(args.length), List.mk(args.length) };

	for (int k = 0; k < ls.length; k++) {
	    int len = length(ls[0]);
	    for (int i = 0; i < len; i++)
		bubble(ls[0]);
	}
    }

    private static void bubble(List l) {
	for (List cursor = l; cursor != null && cursor.getTail() != null; cursor = cursor.getTail())
	    if (cursor.head > cursor.getTail().head) {
		int temp = cursor.head;
		cursor.head = cursor.getTail().head;
		cursor.getTail().head = temp;
	    }
    }

    private static int length(List list) {
	int len = 0;

	while (list != null) {
	    list = list.getTail();

popout

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

job log

popout

actions all output return to Java_Bytecode