java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/mergesort.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 05:33:15,533 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 05:33:15,536 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 05:33:15,547 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 05:33:15,547 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 05:33:15,548 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 05:33:15,549 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 05:33:15,552 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 05:33:15,553 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 05:33:15,555 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 05:33:15,556 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 05:33:15,556 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 05:33:15,557 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 05:33:15,559 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 05:33:15,560 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 05:33:15,560 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 05:33:15,562 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 05:33:15,564 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 05:33:15,566 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 05:33:15,567 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 05:33:15,568 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 05:33:15,570 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 05:33:15,570 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 05:33:15,570 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 05:33:15,571 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 05:33:15,572 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 05:33:15,573 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 05:33:15,573 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 05:33:15,575 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 05:33:15,575 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 05:33:15,575 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 05:33:15,576 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 05:33:15,576 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 05:33:15,577 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 05:33:15,578 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 05:33:15,578 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-22 05:33:15,592 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 05:33:15,592 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 05:33:15,592 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 05:33:15,593 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 05:33:15,594 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 05:33:15,594 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 05:33:15,594 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 05:33:15,594 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 05:33:15,595 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 05:33:15,595 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 05:33:15,595 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 05:33:15,595 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 05:33:15,596 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 05:33:15,596 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 05:33:15,596 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 05:33:15,596 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 05:33:15,596 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 05:33:15,598 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 05:33:15,598 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 05:33:15,652 INFO ]: Repository-Root is: /tmp [2018-06-22 05:33:15,671 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 05:33:15,679 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 05:33:15,680 INFO ]: Initializing SmtParser... [2018-06-22 05:33:15,681 INFO ]: SmtParser initialized [2018-06-22 05:33:15,682 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/mergesort.c.smt2 [2018-06-22 05:33:15,683 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-22 05:33:15,785 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/mergesort.c.smt2 unknown [2018-06-22 05:33:16,251 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/mergesort.c.smt2 [2018-06-22 05:33:16,257 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 05:33:16,262 INFO ]: Walking toolchain with 4 elements. [2018-06-22 05:33:16,262 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 05:33:16,262 INFO ]: Initializing ChcToBoogie... [2018-06-22 05:33:16,263 INFO ]: ChcToBoogie initialized [2018-06-22 05:33:16,267 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 05:33:16" (1/1) ... [2018-06-22 05:33:16,340 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:33:16 Unit [2018-06-22 05:33:16,341 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 05:33:16,341 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 05:33:16,341 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 05:33:16,341 INFO ]: Boogie Preprocessor initialized [2018-06-22 05:33:16,365 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:33:16" (1/1) ... [2018-06-22 05:33:16,365 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:33:16" (1/1) ... [2018-06-22 05:33:16,377 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:33:16" (1/1) ... [2018-06-22 05:33:16,377 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:33:16" (1/1) ... [2018-06-22 05:33:16,385 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:33:16" (1/1) ... [2018-06-22 05:33:16,387 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:33:16" (1/1) ... [2018-06-22 05:33:16,389 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:33:16" (1/1) ... [2018-06-22 05:33:16,392 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 05:33:16,393 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 05:33:16,393 INFO ]: Initializing RCFGBuilder... [2018-06-22 05:33:16,393 INFO ]: RCFGBuilder initialized [2018-06-22 05:33:16,394 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:33:16" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-22 05:33:16,437 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 05:33:16,438 INFO ]: Found specification of procedure gotoProc [2018-06-22 05:33:16,438 INFO ]: Found implementation of procedure gotoProc [2018-06-22 05:33:16,438 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 05:33:16,438 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 05:33:16,438 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 05:33:16,739 INFO ]: Using library mode [2018-06-22 05:33:16,740 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 05:33:16 BoogieIcfgContainer [2018-06-22 05:33:16,740 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 05:33:16,742 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 05:33:16,742 INFO ]: Initializing TraceAbstraction... [2018-06-22 05:33:16,745 INFO ]: TraceAbstraction initialized [2018-06-22 05:33:16,746 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 05:33:16" (1/3) ... [2018-06-22 05:33:16,747 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@29a5ec4c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 05:33:16, skipping insertion in model container [2018-06-22 05:33:16,747 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:33:16" (2/3) ... [2018-06-22 05:33:16,747 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@29a5ec4c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 05:33:16, skipping insertion in model container [2018-06-22 05:33:16,747 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 05:33:16" (3/3) ... [2018-06-22 05:33:16,749 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 05:33:16,759 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 05:33:16,767 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 05:33:16,810 INFO ]: Using default assertion order modulation [2018-06-22 05:33:16,810 INFO ]: Interprodecural is true [2018-06-22 05:33:16,810 INFO ]: Hoare is false [2018-06-22 05:33:16,811 INFO ]: Compute interpolants for FPandBP [2018-06-22 05:33:16,811 INFO ]: Backedges is TWOTRACK [2018-06-22 05:33:16,811 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 05:33:16,811 INFO ]: Difference is false [2018-06-22 05:33:16,811 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 05:33:16,811 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 05:33:16,825 INFO ]: Start isEmpty. Operand 10 states. [2018-06-22 05:33:16,845 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-22 05:33:16,845 INFO ]: Found error trace [2018-06-22 05:33:16,846 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:33:16,846 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:33:16,859 INFO ]: Analyzing trace with hash 1284994894, now seen corresponding path program 1 times [2018-06-22 05:33:16,861 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:33:16,861 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:33:16,903 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:33:16,903 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:33:16,904 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:33:16,951 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:33:17,054 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:33:17,056 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 05:33:17,056 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 05:33:17,057 INFO ]: Interpolant automaton has 3 states [2018-06-22 05:33:17,068 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 05:33:17,069 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 05:33:17,071 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-22 05:33:17,139 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:33:17,140 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-22 05:33:17,144 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 05:33:17,146 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-22 05:33:17,146 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:33:17,159 INFO ]: With dead ends: 9 [2018-06-22 05:33:17,159 INFO ]: Without dead ends: 9 [2018-06-22 05:33:17,161 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 05:33:17,176 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-22 05:33:17,193 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-22 05:33:17,194 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-22 05:33:17,195 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-22 05:33:17,196 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-22 05:33:17,196 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:33:17,196 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-22 05:33:17,196 INFO ]: Interpolant automaton has 3 states. [2018-06-22 05:33:17,196 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-22 05:33:17,197 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 05:33:17,197 INFO ]: Found error trace [2018-06-22 05:33:17,197 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:33:17,197 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:33:17,197 INFO ]: Analyzing trace with hash 1180964567, now seen corresponding path program 1 times [2018-06-22 05:33:17,197 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:33:17,197 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:33:17,198 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:33:17,198 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:33:17,198 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:33:17,273 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:33:17,460 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:33:17,460 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:33:17,460 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:33:17,469 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:33:17,554 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:33:17,567 INFO ]: Computing forward predicates... [2018-06-22 05:33:18,167 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:33:18,190 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:33:18,190 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-22 05:33:18,191 INFO ]: Interpolant automaton has 5 states [2018-06-22 05:33:18,191 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-22 05:33:18,191 INFO ]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 05:33:18,191 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-22 05:33:18,344 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:33:18,344 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-22 05:33:18,345 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 05:33:18,345 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-22 05:33:18,345 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:33:18,345 INFO ]: With dead ends: 10 [2018-06-22 05:33:18,345 INFO ]: Without dead ends: 10 [2018-06-22 05:33:18,346 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-06-22 05:33:18,346 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-22 05:33:18,347 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-22 05:33:18,347 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-22 05:33:18,348 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-22 05:33:18,348 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-22 05:33:18,348 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:33:18,348 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-22 05:33:18,348 INFO ]: Interpolant automaton has 5 states. [2018-06-22 05:33:18,348 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-22 05:33:18,348 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 05:33:18,348 INFO ]: Found error trace [2018-06-22 05:33:18,348 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:33:18,348 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:33:18,349 INFO ]: Analyzing trace with hash -2043975570, now seen corresponding path program 2 times [2018-06-22 05:33:18,349 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:33:18,349 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:33:18,350 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:33:18,350 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:33:18,350 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:33:18,504 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:33:18,820 WARN ]: Spent 109.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-22 05:33:18,998 WARN ]: Spent 103.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-22 05:33:18,999 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:33:18,999 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:33:18,999 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:33:19,006 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 05:33:19,124 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 05:33:19,124 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:33:19,129 INFO ]: Computing forward predicates... [2018-06-22 05:33:22,583 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:33:22,616 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:33:22,616 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 6 [2018-06-22 05:33:22,616 INFO ]: Interpolant automaton has 6 states [2018-06-22 05:33:22,616 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-22 05:33:22,616 INFO ]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-06-22 05:33:22,616 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 6 states. [2018-06-22 05:33:22,725 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:33:22,725 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-22 05:33:22,726 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 05:33:22,726 INFO ]: Start accepts. Automaton has 6 states. Word has length 9 [2018-06-22 05:33:22,726 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:33:22,726 INFO ]: With dead ends: 11 [2018-06-22 05:33:22,726 INFO ]: Without dead ends: 11 [2018-06-22 05:33:22,727 INFO ]: 0 DeclaredPredicates, 15 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=26, Invalid=30, Unknown=0, NotChecked=0, Total=56 [2018-06-22 05:33:22,727 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-22 05:33:22,728 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-22 05:33:22,728 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-22 05:33:22,728 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-22 05:33:22,728 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 9 [2018-06-22 05:33:22,728 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:33:22,728 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-22 05:33:22,728 INFO ]: Interpolant automaton has 6 states. [2018-06-22 05:33:22,728 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-22 05:33:22,729 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-22 05:33:22,729 INFO ]: Found error trace [2018-06-22 05:33:22,729 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:33:22,729 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:33:22,729 INFO ]: Analyzing trace with hash 1062095287, now seen corresponding path program 3 times [2018-06-22 05:33:22,729 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:33:22,729 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:33:22,730 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:33:22,730 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:33:22,730 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:33:22,815 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:33:23,625 WARN ]: Spent 545.00 ms on a formula simplification that was a NOOP. DAG size: 15 [2018-06-22 05:33:23,819 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:33:23,819 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:33:23,819 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:33:23,828 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 05:33:23,952 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-22 05:33:23,952 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:33:23,956 INFO ]: Computing forward predicates... [2018-06-22 05:33:31,124 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:33:31,147 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:33:31,147 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2018-06-22 05:33:31,147 INFO ]: Interpolant automaton has 7 states [2018-06-22 05:33:31,148 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-22 05:33:31,148 INFO ]: CoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2018-06-22 05:33:31,148 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 7 states. [2018-06-22 05:33:31,301 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:33:31,301 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-22 05:33:31,301 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 05:33:31,301 INFO ]: Start accepts. Automaton has 7 states. Word has length 10 [2018-06-22 05:33:31,302 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:33:31,302 INFO ]: With dead ends: 12 [2018-06-22 05:33:31,302 INFO ]: Without dead ends: 12 [2018-06-22 05:33:31,302 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 7 SyntacticMatches, 3 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2018-06-22 05:33:31,302 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-22 05:33:31,305 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-22 05:33:31,305 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-22 05:33:31,305 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-22 05:33:31,305 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-06-22 05:33:31,305 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:33:31,305 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-22 05:33:31,305 INFO ]: Interpolant automaton has 7 states. [2018-06-22 05:33:31,306 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-22 05:33:31,306 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-22 05:33:31,306 INFO ]: Found error trace [2018-06-22 05:33:31,306 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:33:31,306 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:33:31,306 INFO ]: Analyzing trace with hash -1433955954, now seen corresponding path program 4 times [2018-06-22 05:33:31,306 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:33:31,306 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:33:31,307 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:33:31,307 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:33:31,307 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:33:31,403 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:33:31,814 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:33:31,814 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:33:31,814 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:33:31,820 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 05:33:31,905 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 05:33:31,905 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:33:31,910 INFO ]: Computing forward predicates... [2018-06-22 05:33:33,777 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 05:33:33,885 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:33:33,930 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:33:39,965 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:33:39,987 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:33:39,987 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 8 [2018-06-22 05:33:39,987 INFO ]: Interpolant automaton has 8 states [2018-06-22 05:33:39,987 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 05:33:39,988 INFO ]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2018-06-22 05:33:39,988 INFO ]: Start difference. First operand 12 states and 12 transitions. Second operand 8 states. [2018-06-22 05:33:40,171 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:33:40,171 INFO ]: Finished difference Result 13 states and 13 transitions. [2018-06-22 05:33:40,171 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 05:33:40,171 INFO ]: Start accepts. Automaton has 8 states. Word has length 11 [2018-06-22 05:33:40,171 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:33:40,171 INFO ]: With dead ends: 13 [2018-06-22 05:33:40,171 INFO ]: Without dead ends: 13 [2018-06-22 05:33:40,172 INFO ]: 0 DeclaredPredicates, 22 GetRequests, 7 SyntacticMatches, 4 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=60, Invalid=96, Unknown=0, NotChecked=0, Total=156 [2018-06-22 05:33:40,172 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 05:33:40,173 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 05:33:40,173 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 05:33:40,173 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 13 transitions. [2018-06-22 05:33:40,173 INFO ]: Start accepts. Automaton has 13 states and 13 transitions. Word has length 11 [2018-06-22 05:33:40,173 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:33:40,173 INFO ]: Abstraction has 13 states and 13 transitions. [2018-06-22 05:33:40,173 INFO ]: Interpolant automaton has 8 states. [2018-06-22 05:33:40,174 INFO ]: Start isEmpty. Operand 13 states and 13 transitions. [2018-06-22 05:33:40,174 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-22 05:33:40,174 INFO ]: Found error trace [2018-06-22 05:33:40,174 INFO ]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:33:40,174 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:33:40,174 INFO ]: Analyzing trace with hash -1502133097, now seen corresponding path program 5 times [2018-06-22 05:33:40,174 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:33:40,174 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:33:40,175 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:33:40,175 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:33:40,175 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:33:40,271 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:33:40,713 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:33:40,713 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:33:40,713 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:33:40,721 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 05:33:40,819 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-22 05:33:40,819 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:33:40,824 INFO ]: Computing forward predicates... [2018-06-22 05:33:41,414 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:33:41,444 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:33:41,451 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:33:45,923 WARN ]: Spent 178.00 ms on a formula simplification. DAG size of input: 73 DAG size of output: 16 [2018-06-22 05:34:03,245 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:34:03,351 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:34:03,351 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 10 [2018-06-22 05:34:03,352 INFO ]: Interpolant automaton has 10 states [2018-06-22 05:34:03,352 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-22 05:34:03,352 INFO ]: CoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2018-06-22 05:34:03,352 INFO ]: Start difference. First operand 13 states and 13 transitions. Second operand 10 states. [2018-06-22 05:34:03,694 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:34:03,694 INFO ]: Finished difference Result 14 states and 14 transitions. [2018-06-22 05:34:03,694 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 05:34:03,694 INFO ]: Start accepts. Automaton has 10 states. Word has length 12 [2018-06-22 05:34:03,694 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:34:03,695 INFO ]: With dead ends: 14 [2018-06-22 05:34:03,695 INFO ]: Without dead ends: 14 [2018-06-22 05:34:03,695 INFO ]: 0 DeclaredPredicates, 25 GetRequests, 7 SyntacticMatches, 4 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 44 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=84, Invalid=156, Unknown=0, NotChecked=0, Total=240 [2018-06-22 05:34:03,695 INFO ]: Start minimizeSevpa. Operand 14 states. [2018-06-22 05:34:03,697 INFO ]: Finished minimizeSevpa. Reduced states from 14 to 14. [2018-06-22 05:34:03,697 INFO ]: Start removeUnreachable. Operand 14 states. [2018-06-22 05:34:03,697 INFO ]: Finished removeUnreachable. Reduced from 14 states to 14 states and 14 transitions. [2018-06-22 05:34:03,697 INFO ]: Start accepts. Automaton has 14 states and 14 transitions. Word has length 12 [2018-06-22 05:34:03,698 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:34:03,698 INFO ]: Abstraction has 14 states and 14 transitions. [2018-06-22 05:34:03,698 INFO ]: Interpolant automaton has 10 states. [2018-06-22 05:34:03,698 INFO ]: Start isEmpty. Operand 14 states and 14 transitions. [2018-06-22 05:34:03,698 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 05:34:03,698 INFO ]: Found error trace [2018-06-22 05:34:03,698 INFO ]: trace histogram [6, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:34:03,698 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:34:03,698 INFO ]: Analyzing trace with hash 679342766, now seen corresponding path program 6 times [2018-06-22 05:34:03,698 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:34:03,698 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:34:03,705 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:34:03,705 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:34:03,705 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:34:03,861 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:34:04,257 WARN ]: Spent 155.00 ms on a formula simplification that was a NOOP. DAG size: 16 [2018-06-22 05:34:04,498 WARN ]: Spent 171.00 ms on a formula simplification. DAG size of input: 16 DAG size of output: 13 [2018-06-22 05:34:04,521 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:34:04,522 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:34:04,522 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-22 05:34:04,543 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:34:04,650 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2018-06-22 05:34:04,650 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:34:04,656 INFO ]: Computing forward predicates... [2018-06-22 05:34:05,617 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:34:15,341 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:34:15,341 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:34:15,401 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:34:15,401 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:34:15,452 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 05:34:15,452 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 05:34:15,453 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:34:15,453 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:34:15,453 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:34:15,537 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:34:15,537 WARN ]: expecting exponential blowup for input size 6 Received shutdown request... [2018-06-22 05:34:18,060 INFO ]: Timeout while computing interpolants [2018-06-22 05:34:18,260 WARN ]: Destroyed unattended storables created during the last iteration: 8 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:34:18,260 WARN ]: Verification canceled [2018-06-22 05:34:18,294 WARN ]: Timeout [2018-06-22 05:34:18,294 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 05:34:18 BoogieIcfgContainer [2018-06-22 05:34:18,294 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 05:34:18,308 INFO ]: Toolchain (without parser) took 62050.43 ms. Allocated memory was 306.7 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 248.3 MB in the beginning and 775.3 MB in the end (delta: -527.0 MB). Peak memory consumption was 677.3 MB. Max. memory is 3.6 GB. [2018-06-22 05:34:18,309 INFO ]: SmtParser took 0.11 ms. Allocated memory is still 306.7 MB. Free memory is still 272.3 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 05:34:18,309 INFO ]: ChcToBoogie took 78.42 ms. Allocated memory is still 306.7 MB. Free memory was 248.3 MB in the beginning and 246.3 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 05:34:18,310 INFO ]: Boogie Preprocessor took 51.24 ms. Allocated memory is still 306.7 MB. Free memory was 246.3 MB in the beginning and 244.3 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 05:34:18,310 INFO ]: RCFGBuilder took 346.84 ms. Allocated memory is still 306.7 MB. Free memory was 244.3 MB in the beginning and 227.3 MB in the end (delta: 17.0 MB). Peak memory consumption was 17.0 MB. Max. memory is 3.6 GB. [2018-06-22 05:34:18,313 INFO ]: TraceAbstraction took 61552.36 ms. Allocated memory was 306.7 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 226.3 MB in the beginning and 775.3 MB in the end (delta: -548.9 MB). Peak memory consumption was 655.4 MB. Max. memory is 3.6 GB. [2018-06-22 05:34:18,316 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.11 ms. Allocated memory is still 306.7 MB. Free memory is still 272.3 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 78.42 ms. Allocated memory is still 306.7 MB. Free memory was 248.3 MB in the beginning and 246.3 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 51.24 ms. Allocated memory is still 306.7 MB. Free memory was 246.3 MB in the beginning and 244.3 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 346.84 ms. Allocated memory is still 306.7 MB. Free memory was 244.3 MB in the beginning and 227.3 MB in the end (delta: 17.0 MB). Peak memory consumption was 17.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 61552.36 ms. Allocated memory was 306.7 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 226.3 MB in the beginning and 775.3 MB in the end (delta: -548.9 MB). Peak memory consumption was 655.4 MB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 14 with TraceHistMax 6, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantifier-free) to 10 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 61.4s OverallTime, 7 OverallIterations, 6 TraceHistogramMax, 1.0s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 42 SDtfs, 11 SDslu, 105 SDs, 0 SdLazy, 45 SolverSat, 27 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.2s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 96 GetRequests, 37 SyntacticMatches, 14 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 93 ImplicationChecksByTransitivity, 3.5s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=14occurred in iteration=6, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 6 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 0.9s SatisfiabilityAnalysisTime, 44.3s InterpolantComputationTime, 107 NumberOfCodeBlocks, 107 NumberOfCodeBlocksAsserted, 17 NumberOfCheckSat, 96 ConstructedInterpolants, 0 QuantifiedInterpolants, 4174 SizeOfPredicates, 30 NumberOfNonLiveVariables, 1580 ConjunctsInSsa, 165 ConjunctsInUnsatCore, 11 InterpolantComputations, 1 PerfectInterpolantSequences, 0/70 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/mergesort.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_05-34-18-364.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/mergesort.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_05-34-18-364.csv Completed graceful shutdown