java -Xmx8000000000 -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data --generate-csv --csv-dir csv -tc ../../../trunk/examples/toolchains/AutomizerBplInline.xml -s ../../../trunk/examples/settings/pu-bench/svcomp-Reach-32bit-Automizer_Default_PUPT.epf -i ../../../trunk/examples/programs/20170304-DifficultPathPrograms/count_by_k.i_3.bpl -------------------------------------------------------------------------------- This is Ultimate 0.1.23-c372c2b [2018-10-02 12:09:29,632 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-10-02 12:09:29,634 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-10-02 12:09:29,646 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-10-02 12:09:29,646 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-10-02 12:09:29,648 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-10-02 12:09:29,649 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-10-02 12:09:29,652 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-10-02 12:09:29,653 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-10-02 12:09:29,655 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-10-02 12:09:29,655 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-10-02 12:09:29,656 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-10-02 12:09:29,658 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-10-02 12:09:29,659 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-10-02 12:09:29,660 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-10-02 12:09:29,661 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-10-02 12:09:29,664 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-10-02 12:09:29,673 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-10-02 12:09:29,678 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-10-02 12:09:29,680 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-10-02 12:09:29,684 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-10-02 12:09:29,686 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-10-02 12:09:29,690 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-10-02 12:09:29,691 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-10-02 12:09:29,691 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-10-02 12:09:29,692 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-10-02 12:09:29,693 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-10-02 12:09:29,694 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-10-02 12:09:29,696 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-10-02 12:09:29,697 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-10-02 12:09:29,697 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-10-02 12:09:29,698 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-10-02 12:09:29,698 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-10-02 12:09:29,699 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-10-02 12:09:29,699 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-10-02 12:09:29,700 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-10-02 12:09:29,703 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/pu-bench/svcomp-Reach-32bit-Automizer_Default_PUPT.epf [2018-10-02 12:09:29,728 INFO L110 SettingsManager]: Loading preferences was successful [2018-10-02 12:09:29,728 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-10-02 12:09:29,729 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-10-02 12:09:29,729 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-10-02 12:09:29,733 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-10-02 12:09:29,733 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-10-02 12:09:29,733 INFO L133 SettingsManager]: * Use SBE=true [2018-10-02 12:09:29,734 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-10-02 12:09:29,734 INFO L133 SettingsManager]: * sizeof long=4 [2018-10-02 12:09:29,734 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-10-02 12:09:29,734 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-10-02 12:09:29,735 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-10-02 12:09:29,736 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-10-02 12:09:29,736 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-10-02 12:09:29,736 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-10-02 12:09:29,736 INFO L133 SettingsManager]: * sizeof long double=12 [2018-10-02 12:09:29,736 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-10-02 12:09:29,737 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-10-02 12:09:29,737 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-10-02 12:09:29,737 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-10-02 12:09:29,737 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-10-02 12:09:29,737 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-10-02 12:09:29,739 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-10-02 12:09:29,739 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-10-02 12:09:29,739 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-10-02 12:09:29,740 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-10-02 12:09:29,740 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-10-02 12:09:29,740 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-10-02 12:09:29,740 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-10-02 12:09:29,741 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-10-02 12:09:29,741 INFO L133 SettingsManager]: * Use predicate trie based predicate unification=true [2018-10-02 12:09:29,804 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-10-02 12:09:29,817 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-10-02 12:09:29,823 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-10-02 12:09:29,824 INFO L271 PluginConnector]: Initializing Boogie PL CUP Parser... [2018-10-02 12:09:29,825 INFO L276 PluginConnector]: Boogie PL CUP Parser initialized [2018-10-02 12:09:29,826 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/20170304-DifficultPathPrograms/count_by_k.i_3.bpl [2018-10-02 12:09:29,826 INFO L111 BoogieParser]: Parsing: '/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/20170304-DifficultPathPrograms/count_by_k.i_3.bpl' [2018-10-02 12:09:29,885 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-10-02 12:09:29,889 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-10-02 12:09:29,890 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2018-10-02 12:09:29,890 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2018-10-02 12:09:29,890 INFO L276 PluginConnector]: Boogie Procedure Inliner initialized [2018-10-02 12:09:29,911 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "count_by_k.i_3.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 02.10 12:09:29" (1/1) ... [2018-10-02 12:09:29,923 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "count_by_k.i_3.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 02.10 12:09:29" (1/1) ... [2018-10-02 12:09:29,930 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2018-10-02 12:09:29,931 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-10-02 12:09:29,931 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-10-02 12:09:29,932 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-10-02 12:09:29,943 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "count_by_k.i_3.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 02.10 12:09:29" (1/1) ... [2018-10-02 12:09:29,943 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "count_by_k.i_3.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 02.10 12:09:29" (1/1) ... [2018-10-02 12:09:29,944 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "count_by_k.i_3.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 02.10 12:09:29" (1/1) ... [2018-10-02 12:09:29,944 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "count_by_k.i_3.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 02.10 12:09:29" (1/1) ... [2018-10-02 12:09:29,949 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "count_by_k.i_3.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 02.10 12:09:29" (1/1) ... [2018-10-02 12:09:29,951 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "count_by_k.i_3.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 02.10 12:09:29" (1/1) ... [2018-10-02 12:09:29,952 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "count_by_k.i_3.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 02.10 12:09:29" (1/1) ... [2018-10-02 12:09:29,954 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-10-02 12:09:29,954 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-10-02 12:09:29,954 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-10-02 12:09:29,955 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-10-02 12:09:29,956 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "count_by_k.i_3.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 02.10 12:09:29" (1/1) ... No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-10-02 12:09:30,034 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-10-02 12:09:30,035 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-10-02 12:09:30,279 INFO L340 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-10-02 12:09:30,279 INFO L202 PluginConnector]: Adding new model count_by_k.i_3.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.10 12:09:30 BoogieIcfgContainer [2018-10-02 12:09:30,280 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-10-02 12:09:30,281 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-10-02 12:09:30,281 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-10-02 12:09:30,284 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-10-02 12:09:30,284 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "count_by_k.i_3.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 02.10 12:09:29" (1/2) ... [2018-10-02 12:09:30,286 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@169b4fcb and model type count_by_k.i_3.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.10 12:09:30, skipping insertion in model container [2018-10-02 12:09:30,286 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "count_by_k.i_3.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.10 12:09:30" (2/2) ... [2018-10-02 12:09:30,288 INFO L112 eAbstractionObserver]: Analyzing ICFG count_by_k.i_3.bpl [2018-10-02 12:09:30,297 INFO L136 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-10-02 12:09:30,305 INFO L148 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-10-02 12:09:30,351 INFO L133 ementStrategyFactory]: Using default assertion order modulation [2018-10-02 12:09:30,352 INFO L381 AbstractCegarLoop]: Interprodecural is true [2018-10-02 12:09:30,352 INFO L382 AbstractCegarLoop]: Hoare is true [2018-10-02 12:09:30,352 INFO L383 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-10-02 12:09:30,352 INFO L384 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-10-02 12:09:30,352 INFO L385 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-10-02 12:09:30,353 INFO L386 AbstractCegarLoop]: Difference is false [2018-10-02 12:09:30,353 INFO L387 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-10-02 12:09:30,353 INFO L392 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-10-02 12:09:30,368 INFO L276 IsEmpty]: Start isEmpty. Operand 7 states. [2018-10-02 12:09:30,374 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 5 [2018-10-02 12:09:30,375 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:09:30,376 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1] [2018-10-02 12:09:30,377 INFO L423 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:09:30,383 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:09:30,383 INFO L82 PathProgramCache]: Analyzing trace with hash 925639, now seen corresponding path program 1 times [2018-10-02 12:09:30,386 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:09:30,386 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:09:30,437 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:30,437 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-02 12:09:30,437 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:30,474 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:09:30,591 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:30,594 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-02 12:09:30,594 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-10-02 12:09:30,599 INFO L459 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-10-02 12:09:30,615 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-10-02 12:09:30,616 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:09:30,618 INFO L87 Difference]: Start difference. First operand 7 states. Second operand 3 states. [2018-10-02 12:09:30,750 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:09:30,751 INFO L93 Difference]: Finished difference Result 11 states and 12 transitions. [2018-10-02 12:09:30,752 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-10-02 12:09:30,753 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 4 [2018-10-02 12:09:30,754 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:09:30,778 INFO L225 Difference]: With dead ends: 11 [2018-10-02 12:09:30,778 INFO L226 Difference]: Without dead ends: 7 [2018-10-02 12:09:30,788 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s Time 0.0s impTime [2018-10-02 12:09:30,822 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 7 states. [2018-10-02 12:09:30,837 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 7 to 7. [2018-10-02 12:09:30,838 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 7 states. [2018-10-02 12:09:30,839 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 7 transitions. [2018-10-02 12:09:30,840 INFO L78 Accepts]: Start accepts. Automaton has 7 states and 7 transitions. Word has length 4 [2018-10-02 12:09:30,841 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:09:30,841 INFO L480 AbstractCegarLoop]: Abstraction has 7 states and 7 transitions. [2018-10-02 12:09:30,841 INFO L481 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-10-02 12:09:30,841 INFO L276 IsEmpty]: Start isEmpty. Operand 7 states and 7 transitions. [2018-10-02 12:09:30,842 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2018-10-02 12:09:30,842 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:09:30,842 INFO L375 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1] [2018-10-02 12:09:30,842 INFO L423 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:09:30,843 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:09:30,843 INFO L82 PathProgramCache]: Analyzing trace with hash 889591169, now seen corresponding path program 1 times [2018-10-02 12:09:30,843 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:09:30,843 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:09:30,844 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:30,844 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-02 12:09:30,845 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:30,852 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:09:30,924 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:30,927 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:09:30,927 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:09:30,937 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-02 12:09:30,952 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:09:30,959 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:09:31,205 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:31,237 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:09:31,238 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [3, 3] total 4 [2018-10-02 12:09:31,238 INFO L459 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-10-02 12:09:31,239 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-10-02 12:09:31,239 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:09:31,239 INFO L87 Difference]: Start difference. First operand 7 states and 7 transitions. Second operand 5 states. [2018-10-02 12:09:31,469 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:09:31,470 INFO L93 Difference]: Finished difference Result 13 states and 14 transitions. [2018-10-02 12:09:31,470 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-10-02 12:09:31,471 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 6 [2018-10-02 12:09:31,471 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:09:31,471 INFO L225 Difference]: With dead ends: 13 [2018-10-02 12:09:31,472 INFO L226 Difference]: Without dead ends: 11 [2018-10-02 12:09:31,472 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s Time 0.0s impTime [2018-10-02 12:09:31,473 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 11 states. [2018-10-02 12:09:31,476 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-10-02 12:09:31,476 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 11 states. [2018-10-02 12:09:31,477 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-10-02 12:09:31,477 INFO L78 Accepts]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 6 [2018-10-02 12:09:31,478 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:09:31,478 INFO L480 AbstractCegarLoop]: Abstraction has 11 states and 11 transitions. [2018-10-02 12:09:31,478 INFO L481 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-10-02 12:09:31,478 INFO L276 IsEmpty]: Start isEmpty. Operand 11 states and 11 transitions. [2018-10-02 12:09:31,479 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2018-10-02 12:09:31,479 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:09:31,479 INFO L375 BasicCegarLoop]: trace histogram [4, 3, 1, 1, 1] [2018-10-02 12:09:31,479 INFO L423 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:09:31,480 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:09:31,480 INFO L82 PathProgramCache]: Analyzing trace with hash 1946815861, now seen corresponding path program 2 times [2018-10-02 12:09:31,480 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:09:31,480 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:09:31,481 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:31,481 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-02 12:09:31,482 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:31,496 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:09:31,647 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:31,649 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:09:31,650 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/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-10-02 12:09:31,667 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-10-02 12:09:31,693 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-10-02 12:09:31,694 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:09:31,697 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:09:31,932 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:31,954 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:09:31,954 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 6 [2018-10-02 12:09:31,954 INFO L459 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-10-02 12:09:31,955 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-10-02 12:09:31,955 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:09:31,955 INFO L87 Difference]: Start difference. First operand 11 states and 11 transitions. Second operand 7 states. [2018-10-02 12:09:32,306 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:09:32,307 INFO L93 Difference]: Finished difference Result 17 states and 18 transitions. [2018-10-02 12:09:32,308 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-10-02 12:09:32,309 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 10 [2018-10-02 12:09:32,309 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:09:32,309 INFO L225 Difference]: With dead ends: 17 [2018-10-02 12:09:32,310 INFO L226 Difference]: Without dead ends: 15 [2018-10-02 12:09:32,310 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.4s Time 0.1s impTime [2018-10-02 12:09:32,310 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 15 states. [2018-10-02 12:09:32,315 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-10-02 12:09:32,316 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 15 states. [2018-10-02 12:09:32,316 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 15 transitions. [2018-10-02 12:09:32,317 INFO L78 Accepts]: Start accepts. Automaton has 15 states and 15 transitions. Word has length 10 [2018-10-02 12:09:32,317 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:09:32,317 INFO L480 AbstractCegarLoop]: Abstraction has 15 states and 15 transitions. [2018-10-02 12:09:32,317 INFO L481 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-10-02 12:09:32,318 INFO L276 IsEmpty]: Start isEmpty. Operand 15 states and 15 transitions. [2018-10-02 12:09:32,318 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2018-10-02 12:09:32,318 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:09:32,319 INFO L375 BasicCegarLoop]: trace histogram [6, 5, 1, 1, 1] [2018-10-02 12:09:32,319 INFO L423 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:09:32,319 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:09:32,319 INFO L82 PathProgramCache]: Analyzing trace with hash 531164009, now seen corresponding path program 3 times [2018-10-02 12:09:32,320 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:09:32,320 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:09:32,321 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:32,321 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:09:32,322 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:32,340 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:09:32,471 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 0 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:32,472 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:09:32,474 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/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-10-02 12:09:32,486 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-02 12:09:32,527 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2018-10-02 12:09:32,527 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:09:32,529 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:09:32,659 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 0 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:32,680 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:09:32,680 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 8 [2018-10-02 12:09:32,680 INFO L459 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-10-02 12:09:32,681 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-10-02 12:09:32,681 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:09:32,681 INFO L87 Difference]: Start difference. First operand 15 states and 15 transitions. Second operand 9 states. [2018-10-02 12:09:33,354 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:09:33,356 INFO L93 Difference]: Finished difference Result 21 states and 22 transitions. [2018-10-02 12:09:33,356 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-10-02 12:09:33,356 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 14 [2018-10-02 12:09:33,357 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:09:33,358 INFO L225 Difference]: With dead ends: 21 [2018-10-02 12:09:33,358 INFO L226 Difference]: Without dead ends: 19 [2018-10-02 12:09:33,359 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 25 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.4s Time 0.2s impTime [2018-10-02 12:09:33,359 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2018-10-02 12:09:33,365 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-10-02 12:09:33,366 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 19 states. [2018-10-02 12:09:33,367 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 19 transitions. [2018-10-02 12:09:33,367 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 19 transitions. Word has length 14 [2018-10-02 12:09:33,367 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:09:33,368 INFO L480 AbstractCegarLoop]: Abstraction has 19 states and 19 transitions. [2018-10-02 12:09:33,368 INFO L481 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-10-02 12:09:33,368 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 19 transitions. [2018-10-02 12:09:33,369 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2018-10-02 12:09:33,369 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:09:33,369 INFO L375 BasicCegarLoop]: trace histogram [8, 7, 1, 1, 1] [2018-10-02 12:09:33,369 INFO L423 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:09:33,370 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:09:33,370 INFO L82 PathProgramCache]: Analyzing trace with hash 67088221, now seen corresponding path program 4 times [2018-10-02 12:09:33,370 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:09:33,370 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:09:33,371 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:33,371 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:09:33,372 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:33,396 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:09:33,778 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 0 proven. 56 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:33,779 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:09:33,779 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/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-10-02 12:09:33,787 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-02 12:09:33,797 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-02 12:09:33,798 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:09:33,800 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:09:33,996 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 0 proven. 56 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:34,017 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:09:34,018 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 10 [2018-10-02 12:09:34,018 INFO L459 AbstractCegarLoop]: Interpolant automaton has 11 states [2018-10-02 12:09:34,018 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2018-10-02 12:09:34,019 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:09:34,019 INFO L87 Difference]: Start difference. First operand 19 states and 19 transitions. Second operand 11 states. [2018-10-02 12:09:34,646 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:09:34,646 INFO L93 Difference]: Finished difference Result 25 states and 26 transitions. [2018-10-02 12:09:34,647 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-10-02 12:09:34,647 INFO L78 Accepts]: Start accepts. Automaton has 11 states. Word has length 18 [2018-10-02 12:09:34,648 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:09:34,648 INFO L225 Difference]: With dead ends: 25 [2018-10-02 12:09:34,649 INFO L226 Difference]: Without dead ends: 23 [2018-10-02 12:09:34,649 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.9s Time 0.5s impTime [2018-10-02 12:09:34,650 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2018-10-02 12:09:34,654 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-10-02 12:09:34,655 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 23 states. [2018-10-02 12:09:34,655 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 23 transitions. [2018-10-02 12:09:34,656 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 23 transitions. Word has length 18 [2018-10-02 12:09:34,656 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:09:34,656 INFO L480 AbstractCegarLoop]: Abstraction has 23 states and 23 transitions. [2018-10-02 12:09:34,656 INFO L481 AbstractCegarLoop]: Interpolant automaton has 11 states. [2018-10-02 12:09:34,656 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 23 transitions. [2018-10-02 12:09:34,657 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2018-10-02 12:09:34,657 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:09:34,657 INFO L375 BasicCegarLoop]: trace histogram [10, 9, 1, 1, 1] [2018-10-02 12:09:34,658 INFO L423 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:09:34,658 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:09:34,658 INFO L82 PathProgramCache]: Analyzing trace with hash -1767155375, now seen corresponding path program 5 times [2018-10-02 12:09:34,658 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:09:34,658 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:09:34,659 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:34,659 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:09:34,659 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:34,679 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:09:35,206 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 0 proven. 90 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:35,206 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:09:35,207 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/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-10-02 12:09:35,227 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-10-02 12:09:35,262 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 10 check-sat command(s) [2018-10-02 12:09:35,262 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:09:35,264 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:09:35,390 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 0 proven. 90 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:35,411 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:09:35,411 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 12 [2018-10-02 12:09:35,411 INFO L459 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-10-02 12:09:35,412 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-10-02 12:09:35,412 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:09:35,412 INFO L87 Difference]: Start difference. First operand 23 states and 23 transitions. Second operand 13 states. [2018-10-02 12:09:35,811 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:09:35,811 INFO L93 Difference]: Finished difference Result 29 states and 30 transitions. [2018-10-02 12:09:35,812 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-10-02 12:09:35,812 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 22 [2018-10-02 12:09:35,812 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:09:35,813 INFO L225 Difference]: With dead ends: 29 [2018-10-02 12:09:35,813 INFO L226 Difference]: Without dead ends: 27 [2018-10-02 12:09:35,814 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.7s Time 0.4s impTime [2018-10-02 12:09:35,814 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2018-10-02 12:09:35,822 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2018-10-02 12:09:35,822 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 27 states. [2018-10-02 12:09:35,823 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 27 transitions. [2018-10-02 12:09:35,823 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 27 transitions. Word has length 22 [2018-10-02 12:09:35,824 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:09:35,824 INFO L480 AbstractCegarLoop]: Abstraction has 27 states and 27 transitions. [2018-10-02 12:09:35,824 INFO L481 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-10-02 12:09:35,824 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 27 transitions. [2018-10-02 12:09:35,825 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2018-10-02 12:09:35,825 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:09:35,825 INFO L375 BasicCegarLoop]: trace histogram [12, 11, 1, 1, 1] [2018-10-02 12:09:35,826 INFO L423 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:09:35,826 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:09:35,826 INFO L82 PathProgramCache]: Analyzing trace with hash 919136581, now seen corresponding path program 6 times [2018-10-02 12:09:35,826 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:09:35,826 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:09:35,827 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:35,827 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:09:35,827 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:35,845 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:09:36,270 INFO L134 CoverageAnalysis]: Checked inductivity of 132 backedges. 0 proven. 132 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:36,270 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:09:36,271 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/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-10-02 12:09:36,287 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-10-02 12:09:36,302 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 12 check-sat command(s) [2018-10-02 12:09:36,302 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:09:36,304 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:09:36,481 INFO L134 CoverageAnalysis]: Checked inductivity of 132 backedges. 0 proven. 132 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:36,504 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:09:36,504 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 14 [2018-10-02 12:09:36,504 INFO L459 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-10-02 12:09:36,505 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-10-02 12:09:36,505 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:09:36,505 INFO L87 Difference]: Start difference. First operand 27 states and 27 transitions. Second operand 15 states. [2018-10-02 12:09:37,063 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:09:37,064 INFO L93 Difference]: Finished difference Result 33 states and 34 transitions. [2018-10-02 12:09:37,065 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-10-02 12:09:37,065 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 26 [2018-10-02 12:09:37,066 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:09:37,066 INFO L225 Difference]: With dead ends: 33 [2018-10-02 12:09:37,067 INFO L226 Difference]: Without dead ends: 31 [2018-10-02 12:09:37,067 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.8s Time 0.5s impTime [2018-10-02 12:09:37,067 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2018-10-02 12:09:37,074 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2018-10-02 12:09:37,075 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 31 states. [2018-10-02 12:09:37,076 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 31 transitions. [2018-10-02 12:09:37,076 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 31 transitions. Word has length 26 [2018-10-02 12:09:37,076 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:09:37,076 INFO L480 AbstractCegarLoop]: Abstraction has 31 states and 31 transitions. [2018-10-02 12:09:37,077 INFO L481 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-10-02 12:09:37,077 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 31 transitions. [2018-10-02 12:09:37,078 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2018-10-02 12:09:37,078 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:09:37,078 INFO L375 BasicCegarLoop]: trace histogram [14, 13, 1, 1, 1] [2018-10-02 12:09:37,078 INFO L423 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:09:37,078 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:09:37,079 INFO L82 PathProgramCache]: Analyzing trace with hash 1828020025, now seen corresponding path program 7 times [2018-10-02 12:09:37,079 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:09:37,079 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:09:37,080 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:37,080 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:09:37,080 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:37,111 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:09:37,634 INFO L134 CoverageAnalysis]: Checked inductivity of 182 backedges. 0 proven. 182 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:37,635 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:09:37,635 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/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) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:09:37,644 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-02 12:09:37,662 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:09:37,667 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:09:37,831 INFO L134 CoverageAnalysis]: Checked inductivity of 182 backedges. 0 proven. 182 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:37,853 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:09:37,854 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 16 [2018-10-02 12:09:37,854 INFO L459 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-10-02 12:09:37,854 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-10-02 12:09:37,854 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:09:37,855 INFO L87 Difference]: Start difference. First operand 31 states and 31 transitions. Second operand 17 states. [2018-10-02 12:09:38,833 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:09:38,833 INFO L93 Difference]: Finished difference Result 37 states and 38 transitions. [2018-10-02 12:09:38,837 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-10-02 12:09:38,837 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 30 [2018-10-02 12:09:38,837 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:09:38,838 INFO L225 Difference]: With dead ends: 37 [2018-10-02 12:09:38,838 INFO L226 Difference]: Without dead ends: 35 [2018-10-02 12:09:38,838 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 1.2s Time 0.7s impTime [2018-10-02 12:09:38,839 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2018-10-02 12:09:38,845 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 35. [2018-10-02 12:09:38,846 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 35 states. [2018-10-02 12:09:38,847 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 35 transitions. [2018-10-02 12:09:38,847 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 35 transitions. Word has length 30 [2018-10-02 12:09:38,847 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:09:38,847 INFO L480 AbstractCegarLoop]: Abstraction has 35 states and 35 transitions. [2018-10-02 12:09:38,847 INFO L481 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-10-02 12:09:38,847 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 35 transitions. [2018-10-02 12:09:38,848 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2018-10-02 12:09:38,848 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:09:38,848 INFO L375 BasicCegarLoop]: trace histogram [16, 15, 1, 1, 1] [2018-10-02 12:09:38,849 INFO L423 AbstractCegarLoop]: === Iteration 9 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:09:38,849 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:09:38,849 INFO L82 PathProgramCache]: Analyzing trace with hash 726514477, now seen corresponding path program 8 times [2018-10-02 12:09:38,849 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:09:38,849 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:09:38,850 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:38,850 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-02 12:09:38,850 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:38,867 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:09:39,130 INFO L134 CoverageAnalysis]: Checked inductivity of 240 backedges. 0 proven. 240 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:39,130 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:09:39,131 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:09:39,145 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-10-02 12:09:39,173 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-10-02 12:09:39,174 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:09:39,179 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:09:40,064 INFO L134 CoverageAnalysis]: Checked inductivity of 240 backedges. 0 proven. 240 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:40,098 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:09:40,098 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17] total 18 [2018-10-02 12:09:40,099 INFO L459 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-10-02 12:09:40,099 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-10-02 12:09:40,099 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:09:40,100 INFO L87 Difference]: Start difference. First operand 35 states and 35 transitions. Second operand 19 states. [2018-10-02 12:09:41,041 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:09:41,041 INFO L93 Difference]: Finished difference Result 41 states and 42 transitions. [2018-10-02 12:09:41,043 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-10-02 12:09:41,044 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 34 [2018-10-02 12:09:41,044 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:09:41,045 INFO L225 Difference]: With dead ends: 41 [2018-10-02 12:09:41,045 INFO L226 Difference]: Without dead ends: 39 [2018-10-02 12:09:41,046 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 1.5s Time 0.7s impTime [2018-10-02 12:09:41,046 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2018-10-02 12:09:41,053 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 39. [2018-10-02 12:09:41,053 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 39 states. [2018-10-02 12:09:41,054 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 39 transitions. [2018-10-02 12:09:41,054 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 39 transitions. Word has length 34 [2018-10-02 12:09:41,054 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:09:41,054 INFO L480 AbstractCegarLoop]: Abstraction has 39 states and 39 transitions. [2018-10-02 12:09:41,054 INFO L481 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-10-02 12:09:41,055 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 39 transitions. [2018-10-02 12:09:41,055 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2018-10-02 12:09:41,056 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:09:41,056 INFO L375 BasicCegarLoop]: trace histogram [18, 17, 1, 1, 1] [2018-10-02 12:09:41,056 INFO L423 AbstractCegarLoop]: === Iteration 10 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:09:41,056 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:09:41,056 INFO L82 PathProgramCache]: Analyzing trace with hash 225377569, now seen corresponding path program 9 times [2018-10-02 12:09:41,057 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:09:41,057 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:09:41,057 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:41,058 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:09:41,058 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:41,076 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:09:41,392 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 0 proven. 306 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:41,392 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:09:41,393 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:09:41,409 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-02 12:09:41,455 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 18 check-sat command(s) [2018-10-02 12:09:41,455 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:09:41,458 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:09:41,606 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 0 proven. 306 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:41,628 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:09:41,628 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19] total 20 [2018-10-02 12:09:41,629 INFO L459 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-10-02 12:09:41,629 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-10-02 12:09:41,629 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:09:41,629 INFO L87 Difference]: Start difference. First operand 39 states and 39 transitions. Second operand 21 states. [2018-10-02 12:09:42,415 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:09:42,416 INFO L93 Difference]: Finished difference Result 45 states and 46 transitions. [2018-10-02 12:09:42,418 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-10-02 12:09:42,418 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 38 [2018-10-02 12:09:42,418 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:09:42,419 INFO L225 Difference]: With dead ends: 45 [2018-10-02 12:09:42,419 INFO L226 Difference]: Without dead ends: 43 [2018-10-02 12:09:42,419 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 37 SyntacticMatches, 0 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.8s Time 0.6s impTime [2018-10-02 12:09:42,420 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2018-10-02 12:09:42,427 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2018-10-02 12:09:42,427 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 43 states. [2018-10-02 12:09:42,428 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 43 transitions. [2018-10-02 12:09:42,428 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 43 transitions. Word has length 38 [2018-10-02 12:09:42,428 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:09:42,428 INFO L480 AbstractCegarLoop]: Abstraction has 43 states and 43 transitions. [2018-10-02 12:09:42,429 INFO L481 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-10-02 12:09:42,429 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 43 transitions. [2018-10-02 12:09:42,430 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2018-10-02 12:09:42,430 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:09:42,430 INFO L375 BasicCegarLoop]: trace histogram [20, 19, 1, 1, 1] [2018-10-02 12:09:42,430 INFO L423 AbstractCegarLoop]: === Iteration 11 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:09:42,431 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:09:42,431 INFO L82 PathProgramCache]: Analyzing trace with hash -1737087723, now seen corresponding path program 10 times [2018-10-02 12:09:42,431 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:09:42,431 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:09:42,432 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:42,432 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:09:42,432 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:42,453 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:09:42,848 INFO L134 CoverageAnalysis]: Checked inductivity of 380 backedges. 0 proven. 380 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:42,848 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:09:42,848 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:09:42,858 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-02 12:09:42,887 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-02 12:09:42,888 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:09:42,891 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:09:43,050 INFO L134 CoverageAnalysis]: Checked inductivity of 380 backedges. 0 proven. 380 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:43,071 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:09:43,071 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21] total 22 [2018-10-02 12:09:43,072 INFO L459 AbstractCegarLoop]: Interpolant automaton has 23 states [2018-10-02 12:09:43,072 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2018-10-02 12:09:43,072 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:09:43,072 INFO L87 Difference]: Start difference. First operand 43 states and 43 transitions. Second operand 23 states. [2018-10-02 12:09:43,919 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:09:43,920 INFO L93 Difference]: Finished difference Result 49 states and 50 transitions. [2018-10-02 12:09:43,920 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-10-02 12:09:43,920 INFO L78 Accepts]: Start accepts. Automaton has 23 states. Word has length 42 [2018-10-02 12:09:43,921 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:09:43,921 INFO L225 Difference]: With dead ends: 49 [2018-10-02 12:09:43,922 INFO L226 Difference]: Without dead ends: 47 [2018-10-02 12:09:43,922 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 41 SyntacticMatches, 0 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 1.0s Time 0.7s impTime [2018-10-02 12:09:43,922 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2018-10-02 12:09:43,932 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2018-10-02 12:09:43,933 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 47 states. [2018-10-02 12:09:43,934 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 47 transitions. [2018-10-02 12:09:43,934 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 47 transitions. Word has length 42 [2018-10-02 12:09:43,934 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:09:43,934 INFO L480 AbstractCegarLoop]: Abstraction has 47 states and 47 transitions. [2018-10-02 12:09:43,934 INFO L481 AbstractCegarLoop]: Interpolant automaton has 23 states. [2018-10-02 12:09:43,934 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 47 transitions. [2018-10-02 12:09:43,935 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2018-10-02 12:09:43,935 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:09:43,936 INFO L375 BasicCegarLoop]: trace histogram [22, 21, 1, 1, 1] [2018-10-02 12:09:43,936 INFO L423 AbstractCegarLoop]: === Iteration 12 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:09:43,936 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:09:43,936 INFO L82 PathProgramCache]: Analyzing trace with hash 2063610633, now seen corresponding path program 11 times [2018-10-02 12:09:43,936 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:09:43,936 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:09:43,937 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:43,937 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:09:43,938 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:43,967 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:09:44,435 INFO L134 CoverageAnalysis]: Checked inductivity of 462 backedges. 0 proven. 462 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:44,435 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:09:44,436 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:09:44,446 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-10-02 12:09:44,484 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 22 check-sat command(s) [2018-10-02 12:09:44,484 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:09:44,490 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:09:44,654 INFO L134 CoverageAnalysis]: Checked inductivity of 462 backedges. 0 proven. 462 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:44,674 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:09:44,675 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 23] total 24 [2018-10-02 12:09:44,675 INFO L459 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-10-02 12:09:44,676 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-10-02 12:09:44,676 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:09:44,676 INFO L87 Difference]: Start difference. First operand 47 states and 47 transitions. Second operand 25 states. [2018-10-02 12:09:45,805 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:09:45,805 INFO L93 Difference]: Finished difference Result 53 states and 54 transitions. [2018-10-02 12:09:45,806 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2018-10-02 12:09:45,806 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 46 [2018-10-02 12:09:45,806 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:09:45,807 INFO L225 Difference]: With dead ends: 53 [2018-10-02 12:09:45,807 INFO L226 Difference]: Without dead ends: 51 [2018-10-02 12:09:45,807 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 89 GetRequests, 45 SyntacticMatches, 0 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 1.3s Time 1.0s impTime [2018-10-02 12:09:45,807 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2018-10-02 12:09:45,817 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2018-10-02 12:09:45,817 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 51 states. [2018-10-02 12:09:45,818 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 51 transitions. [2018-10-02 12:09:45,818 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 51 transitions. Word has length 46 [2018-10-02 12:09:45,818 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:09:45,818 INFO L480 AbstractCegarLoop]: Abstraction has 51 states and 51 transitions. [2018-10-02 12:09:45,818 INFO L481 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-10-02 12:09:45,818 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 51 transitions. [2018-10-02 12:09:45,819 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2018-10-02 12:09:45,819 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:09:45,819 INFO L375 BasicCegarLoop]: trace histogram [24, 23, 1, 1, 1] [2018-10-02 12:09:45,820 INFO L423 AbstractCegarLoop]: === Iteration 13 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:09:45,820 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:09:45,820 INFO L82 PathProgramCache]: Analyzing trace with hash -852875523, now seen corresponding path program 12 times [2018-10-02 12:09:45,820 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:09:45,820 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:09:45,821 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:45,821 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:09:45,821 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:45,846 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:09:46,307 INFO L134 CoverageAnalysis]: Checked inductivity of 552 backedges. 0 proven. 552 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:46,307 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:09:46,307 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:09:46,316 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-10-02 12:09:46,349 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 24 check-sat command(s) [2018-10-02 12:09:46,349 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:09:46,353 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:09:46,494 INFO L134 CoverageAnalysis]: Checked inductivity of 552 backedges. 0 proven. 552 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:46,515 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:09:46,515 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 25] total 26 [2018-10-02 12:09:46,516 INFO L459 AbstractCegarLoop]: Interpolant automaton has 27 states [2018-10-02 12:09:46,516 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2018-10-02 12:09:46,516 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:09:46,517 INFO L87 Difference]: Start difference. First operand 51 states and 51 transitions. Second operand 27 states. [2018-10-02 12:09:47,845 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:09:47,845 INFO L93 Difference]: Finished difference Result 57 states and 58 transitions. [2018-10-02 12:09:47,847 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2018-10-02 12:09:47,847 INFO L78 Accepts]: Start accepts. Automaton has 27 states. Word has length 50 [2018-10-02 12:09:47,847 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:09:47,848 INFO L225 Difference]: With dead ends: 57 [2018-10-02 12:09:47,848 INFO L226 Difference]: Without dead ends: 55 [2018-10-02 12:09:47,849 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 97 GetRequests, 49 SyntacticMatches, 0 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 1.5s Time 1.2s impTime [2018-10-02 12:09:47,849 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2018-10-02 12:09:47,859 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2018-10-02 12:09:47,859 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 55 states. [2018-10-02 12:09:47,860 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 55 transitions. [2018-10-02 12:09:47,860 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 55 transitions. Word has length 50 [2018-10-02 12:09:47,860 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:09:47,860 INFO L480 AbstractCegarLoop]: Abstraction has 55 states and 55 transitions. [2018-10-02 12:09:47,861 INFO L481 AbstractCegarLoop]: Interpolant automaton has 27 states. [2018-10-02 12:09:47,861 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 55 transitions. [2018-10-02 12:09:47,861 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2018-10-02 12:09:47,862 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:09:47,862 INFO L375 BasicCegarLoop]: trace histogram [26, 25, 1, 1, 1] [2018-10-02 12:09:47,862 INFO L423 AbstractCegarLoop]: === Iteration 14 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:09:47,862 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:09:47,862 INFO L82 PathProgramCache]: Analyzing trace with hash 1351680241, now seen corresponding path program 13 times [2018-10-02 12:09:47,863 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:09:47,863 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:09:47,863 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:47,864 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:09:47,864 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:47,894 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:09:48,500 INFO L134 CoverageAnalysis]: Checked inductivity of 650 backedges. 0 proven. 650 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:48,501 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:09:48,501 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:09:48,508 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-02 12:09:48,549 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:09:48,567 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:09:48,705 INFO L134 CoverageAnalysis]: Checked inductivity of 650 backedges. 0 proven. 650 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:48,725 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:09:48,725 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [27, 27] total 28 [2018-10-02 12:09:48,726 INFO L459 AbstractCegarLoop]: Interpolant automaton has 29 states [2018-10-02 12:09:48,726 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2018-10-02 12:09:48,726 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:09:48,726 INFO L87 Difference]: Start difference. First operand 55 states and 55 transitions. Second operand 29 states. [2018-10-02 12:09:50,109 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:09:50,110 INFO L93 Difference]: Finished difference Result 61 states and 62 transitions. [2018-10-02 12:09:50,110 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2018-10-02 12:09:50,110 INFO L78 Accepts]: Start accepts. Automaton has 29 states. Word has length 54 [2018-10-02 12:09:50,111 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:09:50,111 INFO L225 Difference]: With dead ends: 61 [2018-10-02 12:09:50,112 INFO L226 Difference]: Without dead ends: 59 [2018-10-02 12:09:50,112 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 53 SyntacticMatches, 0 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 1.6s Time 1.3s impTime [2018-10-02 12:09:50,113 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2018-10-02 12:09:50,122 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 59. [2018-10-02 12:09:50,122 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 59 states. [2018-10-02 12:09:50,123 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 59 transitions. [2018-10-02 12:09:50,123 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 59 transitions. Word has length 54 [2018-10-02 12:09:50,123 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:09:50,124 INFO L480 AbstractCegarLoop]: Abstraction has 59 states and 59 transitions. [2018-10-02 12:09:50,124 INFO L481 AbstractCegarLoop]: Interpolant automaton has 29 states. [2018-10-02 12:09:50,124 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 59 transitions. [2018-10-02 12:09:50,124 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2018-10-02 12:09:50,124 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:09:50,125 INFO L375 BasicCegarLoop]: trace histogram [28, 27, 1, 1, 1] [2018-10-02 12:09:50,125 INFO L423 AbstractCegarLoop]: === Iteration 15 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:09:50,125 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:09:50,125 INFO L82 PathProgramCache]: Analyzing trace with hash -1336819483, now seen corresponding path program 14 times [2018-10-02 12:09:50,125 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:09:50,125 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:09:50,126 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:50,126 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-02 12:09:50,126 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:50,159 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:09:50,891 INFO L134 CoverageAnalysis]: Checked inductivity of 756 backedges. 0 proven. 756 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:50,891 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:09:50,891 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:09:50,898 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-10-02 12:09:50,943 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-10-02 12:09:50,944 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:09:50,964 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:09:51,148 INFO L134 CoverageAnalysis]: Checked inductivity of 756 backedges. 0 proven. 756 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:51,171 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:09:51,171 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [29, 29] total 30 [2018-10-02 12:09:51,171 INFO L459 AbstractCegarLoop]: Interpolant automaton has 31 states [2018-10-02 12:09:51,171 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2018-10-02 12:09:51,172 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:09:51,172 INFO L87 Difference]: Start difference. First operand 59 states and 59 transitions. Second operand 31 states. [2018-10-02 12:09:52,829 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:09:52,829 INFO L93 Difference]: Finished difference Result 65 states and 66 transitions. [2018-10-02 12:09:52,829 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2018-10-02 12:09:52,830 INFO L78 Accepts]: Start accepts. Automaton has 31 states. Word has length 58 [2018-10-02 12:09:52,830 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:09:52,830 INFO L225 Difference]: With dead ends: 65 [2018-10-02 12:09:52,830 INFO L226 Difference]: Without dead ends: 63 [2018-10-02 12:09:52,831 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 113 GetRequests, 57 SyntacticMatches, 0 SemanticMatches, 56 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 2.1s Time 1.7s impTime [2018-10-02 12:09:52,831 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2018-10-02 12:09:52,843 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 63. [2018-10-02 12:09:52,843 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 63 states. [2018-10-02 12:09:52,844 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 63 transitions. [2018-10-02 12:09:52,844 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 63 transitions. Word has length 58 [2018-10-02 12:09:52,844 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:09:52,844 INFO L480 AbstractCegarLoop]: Abstraction has 63 states and 63 transitions. [2018-10-02 12:09:52,844 INFO L481 AbstractCegarLoop]: Interpolant automaton has 31 states. [2018-10-02 12:09:52,845 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 63 transitions. [2018-10-02 12:09:52,846 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2018-10-02 12:09:52,846 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:09:52,846 INFO L375 BasicCegarLoop]: trace histogram [30, 29, 1, 1, 1] [2018-10-02 12:09:52,846 INFO L423 AbstractCegarLoop]: === Iteration 16 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:09:52,846 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:09:52,846 INFO L82 PathProgramCache]: Analyzing trace with hash -1056348455, now seen corresponding path program 15 times [2018-10-02 12:09:52,846 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:09:52,847 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:09:52,847 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:52,847 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:09:52,848 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:52,890 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:09:53,808 INFO L134 CoverageAnalysis]: Checked inductivity of 870 backedges. 0 proven. 870 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:53,809 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:09:53,809 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:09:53,818 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-02 12:09:53,851 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 30 check-sat command(s) [2018-10-02 12:09:53,851 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:09:53,855 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:09:54,014 INFO L134 CoverageAnalysis]: Checked inductivity of 870 backedges. 0 proven. 870 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:54,034 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:09:54,034 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [31, 31] total 32 [2018-10-02 12:09:54,034 INFO L459 AbstractCegarLoop]: Interpolant automaton has 33 states [2018-10-02 12:09:54,035 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2018-10-02 12:09:54,035 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:09:54,035 INFO L87 Difference]: Start difference. First operand 63 states and 63 transitions. Second operand 33 states. [2018-10-02 12:09:56,884 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:09:56,884 INFO L93 Difference]: Finished difference Result 69 states and 70 transitions. [2018-10-02 12:09:56,885 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-10-02 12:09:56,885 INFO L78 Accepts]: Start accepts. Automaton has 33 states. Word has length 62 [2018-10-02 12:09:56,885 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:09:56,886 INFO L225 Difference]: With dead ends: 69 [2018-10-02 12:09:56,886 INFO L226 Difference]: Without dead ends: 67 [2018-10-02 12:09:56,887 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 121 GetRequests, 61 SyntacticMatches, 0 SemanticMatches, 60 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 3.3s Time 2.7s impTime [2018-10-02 12:09:56,887 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2018-10-02 12:09:56,898 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 67. [2018-10-02 12:09:56,898 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 67 states. [2018-10-02 12:09:56,898 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 67 transitions. [2018-10-02 12:09:56,899 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 67 transitions. Word has length 62 [2018-10-02 12:09:56,899 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:09:56,899 INFO L480 AbstractCegarLoop]: Abstraction has 67 states and 67 transitions. [2018-10-02 12:09:56,899 INFO L481 AbstractCegarLoop]: Interpolant automaton has 33 states. [2018-10-02 12:09:56,899 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 67 transitions. [2018-10-02 12:09:56,900 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2018-10-02 12:09:56,900 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:09:56,900 INFO L375 BasicCegarLoop]: trace histogram [32, 31, 1, 1, 1] [2018-10-02 12:09:56,901 INFO L423 AbstractCegarLoop]: === Iteration 17 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:09:56,901 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:09:56,901 INFO L82 PathProgramCache]: Analyzing trace with hash -1059786035, now seen corresponding path program 16 times [2018-10-02 12:09:56,901 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:09:56,901 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:09:56,902 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:56,902 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:09:56,902 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:09:56,943 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:09:57,716 INFO L134 CoverageAnalysis]: Checked inductivity of 992 backedges. 0 proven. 992 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:57,716 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:09:57,716 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:09:57,723 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-02 12:09:57,791 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-02 12:09:57,791 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:09:57,823 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:09:58,044 INFO L134 CoverageAnalysis]: Checked inductivity of 992 backedges. 0 proven. 992 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:09:58,072 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:09:58,072 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [33, 33] total 34 [2018-10-02 12:09:58,072 INFO L459 AbstractCegarLoop]: Interpolant automaton has 35 states [2018-10-02 12:09:58,072 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2018-10-02 12:09:58,072 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:09:58,073 INFO L87 Difference]: Start difference. First operand 67 states and 67 transitions. Second operand 35 states. [2018-10-02 12:10:01,599 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:10:01,599 INFO L93 Difference]: Finished difference Result 73 states and 74 transitions. [2018-10-02 12:10:01,599 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2018-10-02 12:10:01,599 INFO L78 Accepts]: Start accepts. Automaton has 35 states. Word has length 66 [2018-10-02 12:10:01,600 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:10:01,600 INFO L225 Difference]: With dead ends: 73 [2018-10-02 12:10:01,600 INFO L226 Difference]: Without dead ends: 71 [2018-10-02 12:10:01,601 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 65 SyntacticMatches, 0 SemanticMatches, 64 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 3.6s Time 3.0s impTime [2018-10-02 12:10:01,601 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2018-10-02 12:10:01,614 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 71. [2018-10-02 12:10:01,615 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 71 states. [2018-10-02 12:10:01,615 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 71 transitions. [2018-10-02 12:10:01,615 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 71 transitions. Word has length 66 [2018-10-02 12:10:01,616 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:10:01,616 INFO L480 AbstractCegarLoop]: Abstraction has 71 states and 71 transitions. [2018-10-02 12:10:01,616 INFO L481 AbstractCegarLoop]: Interpolant automaton has 35 states. [2018-10-02 12:10:01,616 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 71 transitions. [2018-10-02 12:10:01,617 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2018-10-02 12:10:01,617 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:10:01,617 INFO L375 BasicCegarLoop]: trace histogram [34, 33, 1, 1, 1] [2018-10-02 12:10:01,617 INFO L423 AbstractCegarLoop]: === Iteration 18 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:10:01,618 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:10:01,618 INFO L82 PathProgramCache]: Analyzing trace with hash -1756273471, now seen corresponding path program 17 times [2018-10-02 12:10:01,618 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:10:01,618 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:10:01,619 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:10:01,619 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:10:01,619 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:10:01,668 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:10:02,544 INFO L134 CoverageAnalysis]: Checked inductivity of 1122 backedges. 0 proven. 1122 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:10:02,544 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:10:02,545 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:10:02,552 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-10-02 12:10:02,626 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 34 check-sat command(s) [2018-10-02 12:10:02,626 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:10:02,638 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:10:02,835 INFO L134 CoverageAnalysis]: Checked inductivity of 1122 backedges. 0 proven. 1122 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:10:02,856 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:10:02,857 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [35, 35] total 36 [2018-10-02 12:10:02,857 INFO L459 AbstractCegarLoop]: Interpolant automaton has 37 states [2018-10-02 12:10:02,857 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2018-10-02 12:10:02,857 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:10:02,857 INFO L87 Difference]: Start difference. First operand 71 states and 71 transitions. Second operand 37 states. [2018-10-02 12:10:05,110 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:10:05,110 INFO L93 Difference]: Finished difference Result 77 states and 78 transitions. [2018-10-02 12:10:05,110 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 37 states. [2018-10-02 12:10:05,110 INFO L78 Accepts]: Start accepts. Automaton has 37 states. Word has length 70 [2018-10-02 12:10:05,111 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:10:05,111 INFO L225 Difference]: With dead ends: 77 [2018-10-02 12:10:05,112 INFO L226 Difference]: Without dead ends: 75 [2018-10-02 12:10:05,112 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 137 GetRequests, 69 SyntacticMatches, 0 SemanticMatches, 68 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 2.8s Time 2.3s impTime [2018-10-02 12:10:05,112 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 75 states. [2018-10-02 12:10:05,122 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 75 to 75. [2018-10-02 12:10:05,122 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 75 states. [2018-10-02 12:10:05,123 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 75 transitions. [2018-10-02 12:10:05,123 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 75 transitions. Word has length 70 [2018-10-02 12:10:05,123 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:10:05,123 INFO L480 AbstractCegarLoop]: Abstraction has 75 states and 75 transitions. [2018-10-02 12:10:05,123 INFO L481 AbstractCegarLoop]: Interpolant automaton has 37 states. [2018-10-02 12:10:05,123 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 75 transitions. [2018-10-02 12:10:05,124 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2018-10-02 12:10:05,124 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:10:05,124 INFO L375 BasicCegarLoop]: trace histogram [36, 35, 1, 1, 1] [2018-10-02 12:10:05,124 INFO L423 AbstractCegarLoop]: === Iteration 19 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:10:05,124 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:10:05,124 INFO L82 PathProgramCache]: Analyzing trace with hash 362527925, now seen corresponding path program 18 times [2018-10-02 12:10:05,125 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:10:05,125 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:10:05,125 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:10:05,125 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:10:05,126 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:10:05,182 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:10:07,254 INFO L134 CoverageAnalysis]: Checked inductivity of 1260 backedges. 0 proven. 1260 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:10:07,254 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:10:07,254 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:10:07,262 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-10-02 12:10:07,360 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 36 check-sat command(s) [2018-10-02 12:10:07,360 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:10:07,365 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:10:07,556 INFO L134 CoverageAnalysis]: Checked inductivity of 1260 backedges. 0 proven. 1260 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:10:07,575 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:10:07,576 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [37, 37] total 38 [2018-10-02 12:10:07,576 INFO L459 AbstractCegarLoop]: Interpolant automaton has 39 states [2018-10-02 12:10:07,576 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 39 interpolants. [2018-10-02 12:10:07,576 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:10:07,576 INFO L87 Difference]: Start difference. First operand 75 states and 75 transitions. Second operand 39 states. [2018-10-02 12:10:10,132 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:10:10,132 INFO L93 Difference]: Finished difference Result 81 states and 82 transitions. [2018-10-02 12:10:10,132 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 39 states. [2018-10-02 12:10:10,133 INFO L78 Accepts]: Start accepts. Automaton has 39 states. Word has length 74 [2018-10-02 12:10:10,133 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:10:10,134 INFO L225 Difference]: With dead ends: 81 [2018-10-02 12:10:10,134 INFO L226 Difference]: Without dead ends: 79 [2018-10-02 12:10:10,134 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 145 GetRequests, 73 SyntacticMatches, 0 SemanticMatches, 72 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 4.2s Time 3.5s impTime [2018-10-02 12:10:10,134 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 79 states. [2018-10-02 12:10:10,149 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 79 to 79. [2018-10-02 12:10:10,149 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 79 states. [2018-10-02 12:10:10,149 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 79 transitions. [2018-10-02 12:10:10,150 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 79 transitions. Word has length 74 [2018-10-02 12:10:10,150 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:10:10,150 INFO L480 AbstractCegarLoop]: Abstraction has 79 states and 79 transitions. [2018-10-02 12:10:10,150 INFO L481 AbstractCegarLoop]: Interpolant automaton has 39 states. [2018-10-02 12:10:10,150 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 79 transitions. [2018-10-02 12:10:10,151 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2018-10-02 12:10:10,151 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:10:10,151 INFO L375 BasicCegarLoop]: trace histogram [38, 37, 1, 1, 1] [2018-10-02 12:10:10,152 INFO L423 AbstractCegarLoop]: === Iteration 20 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:10:10,152 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:10:10,152 INFO L82 PathProgramCache]: Analyzing trace with hash 911276713, now seen corresponding path program 19 times [2018-10-02 12:10:10,152 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:10:10,152 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:10:10,153 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:10:10,153 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:10:10,153 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:10:10,201 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:10:11,400 INFO L134 CoverageAnalysis]: Checked inductivity of 1406 backedges. 0 proven. 1406 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:10:11,401 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:10:11,401 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:10:11,408 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-02 12:10:11,497 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:10:11,545 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:10:11,723 INFO L134 CoverageAnalysis]: Checked inductivity of 1406 backedges. 0 proven. 1406 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:10:11,745 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:10:11,745 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [39, 39] total 40 [2018-10-02 12:10:11,745 INFO L459 AbstractCegarLoop]: Interpolant automaton has 41 states [2018-10-02 12:10:11,745 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 41 interpolants. [2018-10-02 12:10:11,746 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:10:11,746 INFO L87 Difference]: Start difference. First operand 79 states and 79 transitions. Second operand 41 states. [2018-10-02 12:10:14,752 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:10:14,753 INFO L93 Difference]: Finished difference Result 85 states and 86 transitions. [2018-10-02 12:10:14,753 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2018-10-02 12:10:14,753 INFO L78 Accepts]: Start accepts. Automaton has 41 states. Word has length 78 [2018-10-02 12:10:14,754 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:10:14,754 INFO L225 Difference]: With dead ends: 85 [2018-10-02 12:10:14,754 INFO L226 Difference]: Without dead ends: 83 [2018-10-02 12:10:14,755 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 153 GetRequests, 77 SyntacticMatches, 0 SemanticMatches, 76 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 3.8s Time 3.3s impTime [2018-10-02 12:10:14,755 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 83 states. [2018-10-02 12:10:14,768 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 83 to 83. [2018-10-02 12:10:14,768 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 83 states. [2018-10-02 12:10:14,768 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 83 states to 83 states and 83 transitions. [2018-10-02 12:10:14,768 INFO L78 Accepts]: Start accepts. Automaton has 83 states and 83 transitions. Word has length 78 [2018-10-02 12:10:14,769 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:10:14,769 INFO L480 AbstractCegarLoop]: Abstraction has 83 states and 83 transitions. [2018-10-02 12:10:14,769 INFO L481 AbstractCegarLoop]: Interpolant automaton has 41 states. [2018-10-02 12:10:14,769 INFO L276 IsEmpty]: Start isEmpty. Operand 83 states and 83 transitions. [2018-10-02 12:10:14,769 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2018-10-02 12:10:14,769 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:10:14,769 INFO L375 BasicCegarLoop]: trace histogram [40, 39, 1, 1, 1] [2018-10-02 12:10:14,770 INFO L423 AbstractCegarLoop]: === Iteration 21 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:10:14,770 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:10:14,770 INFO L82 PathProgramCache]: Analyzing trace with hash 1569595037, now seen corresponding path program 20 times [2018-10-02 12:10:14,770 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:10:14,770 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:10:14,771 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:10:14,771 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-02 12:10:14,771 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:10:14,848 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:10:16,015 INFO L134 CoverageAnalysis]: Checked inductivity of 1560 backedges. 0 proven. 1560 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:10:16,016 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:10:16,016 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:10:16,042 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-10-02 12:10:16,149 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-10-02 12:10:16,150 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:10:16,208 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:10:16,539 INFO L134 CoverageAnalysis]: Checked inductivity of 1560 backedges. 0 proven. 1560 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:10:16,558 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:10:16,558 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [41, 41] total 42 [2018-10-02 12:10:16,559 INFO L459 AbstractCegarLoop]: Interpolant automaton has 43 states [2018-10-02 12:10:16,559 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 43 interpolants. [2018-10-02 12:10:16,559 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:10:16,559 INFO L87 Difference]: Start difference. First operand 83 states and 83 transitions. Second operand 43 states. [2018-10-02 12:10:19,984 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:10:19,985 INFO L93 Difference]: Finished difference Result 89 states and 90 transitions. [2018-10-02 12:10:19,985 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 43 states. [2018-10-02 12:10:19,985 INFO L78 Accepts]: Start accepts. Automaton has 43 states. Word has length 82 [2018-10-02 12:10:19,986 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:10:19,986 INFO L225 Difference]: With dead ends: 89 [2018-10-02 12:10:19,986 INFO L226 Difference]: Without dead ends: 87 [2018-10-02 12:10:19,987 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 161 GetRequests, 81 SyntacticMatches, 0 SemanticMatches, 80 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 4.2s Time 3.5s impTime [2018-10-02 12:10:19,987 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 87 states. [2018-10-02 12:10:19,998 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 87 to 87. [2018-10-02 12:10:19,998 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 87 states. [2018-10-02 12:10:19,998 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 87 states to 87 states and 87 transitions. [2018-10-02 12:10:19,998 INFO L78 Accepts]: Start accepts. Automaton has 87 states and 87 transitions. Word has length 82 [2018-10-02 12:10:19,999 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:10:19,999 INFO L480 AbstractCegarLoop]: Abstraction has 87 states and 87 transitions. [2018-10-02 12:10:19,999 INFO L481 AbstractCegarLoop]: Interpolant automaton has 43 states. [2018-10-02 12:10:19,999 INFO L276 IsEmpty]: Start isEmpty. Operand 87 states and 87 transitions. [2018-10-02 12:10:19,999 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2018-10-02 12:10:19,999 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:10:20,000 INFO L375 BasicCegarLoop]: trace histogram [42, 41, 1, 1, 1] [2018-10-02 12:10:20,000 INFO L423 AbstractCegarLoop]: === Iteration 22 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:10:20,000 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:10:20,000 INFO L82 PathProgramCache]: Analyzing trace with hash -1729091439, now seen corresponding path program 21 times [2018-10-02 12:10:20,000 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:10:20,000 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:10:20,001 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:10:20,001 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:10:20,001 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:10:20,084 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:10:21,283 INFO L134 CoverageAnalysis]: Checked inductivity of 1722 backedges. 0 proven. 1722 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:10:21,283 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:10:21,283 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:10:21,290 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-02 12:10:21,340 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 42 check-sat command(s) [2018-10-02 12:10:21,341 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:10:21,345 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:10:21,740 INFO L134 CoverageAnalysis]: Checked inductivity of 1722 backedges. 0 proven. 1722 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:10:21,761 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:10:21,761 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [43, 43] total 44 [2018-10-02 12:10:21,762 INFO L459 AbstractCegarLoop]: Interpolant automaton has 45 states [2018-10-02 12:10:21,762 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2018-10-02 12:10:21,762 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:10:21,762 INFO L87 Difference]: Start difference. First operand 87 states and 87 transitions. Second operand 45 states. [2018-10-02 12:10:25,294 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:10:25,295 INFO L93 Difference]: Finished difference Result 93 states and 94 transitions. [2018-10-02 12:10:25,296 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2018-10-02 12:10:25,296 INFO L78 Accepts]: Start accepts. Automaton has 45 states. Word has length 86 [2018-10-02 12:10:25,296 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:10:25,297 INFO L225 Difference]: With dead ends: 93 [2018-10-02 12:10:25,298 INFO L226 Difference]: Without dead ends: 91 [2018-10-02 12:10:25,298 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 169 GetRequests, 85 SyntacticMatches, 0 SemanticMatches, 84 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 4.4s Time 3.6s impTime [2018-10-02 12:10:25,298 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2018-10-02 12:10:25,310 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 91. [2018-10-02 12:10:25,310 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 91 states. [2018-10-02 12:10:25,311 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 91 transitions. [2018-10-02 12:10:25,311 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 91 transitions. Word has length 86 [2018-10-02 12:10:25,311 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:10:25,311 INFO L480 AbstractCegarLoop]: Abstraction has 91 states and 91 transitions. [2018-10-02 12:10:25,311 INFO L481 AbstractCegarLoop]: Interpolant automaton has 45 states. [2018-10-02 12:10:25,311 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 91 transitions. [2018-10-02 12:10:25,312 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2018-10-02 12:10:25,312 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:10:25,312 INFO L375 BasicCegarLoop]: trace histogram [44, 43, 1, 1, 1] [2018-10-02 12:10:25,312 INFO L423 AbstractCegarLoop]: === Iteration 23 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:10:25,312 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:10:25,312 INFO L82 PathProgramCache]: Analyzing trace with hash -543942523, now seen corresponding path program 22 times [2018-10-02 12:10:25,312 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:10:25,312 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:10:25,313 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:10:25,313 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:10:25,313 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:10:25,411 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:10:27,067 INFO L134 CoverageAnalysis]: Checked inductivity of 1892 backedges. 0 proven. 1892 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:10:27,067 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:10:27,067 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:10:27,074 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-02 12:10:27,109 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-02 12:10:27,109 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:10:27,115 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:10:27,308 INFO L134 CoverageAnalysis]: Checked inductivity of 1892 backedges. 0 proven. 1892 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:10:27,328 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:10:27,328 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [45, 45] total 46 [2018-10-02 12:10:27,329 INFO L459 AbstractCegarLoop]: Interpolant automaton has 47 states [2018-10-02 12:10:27,329 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 47 interpolants. [2018-10-02 12:10:27,329 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:10:27,329 INFO L87 Difference]: Start difference. First operand 91 states and 91 transitions. Second operand 47 states. [2018-10-02 12:10:31,255 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:10:31,256 INFO L93 Difference]: Finished difference Result 97 states and 98 transitions. [2018-10-02 12:10:31,256 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 47 states. [2018-10-02 12:10:31,256 INFO L78 Accepts]: Start accepts. Automaton has 47 states. Word has length 90 [2018-10-02 12:10:31,257 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:10:31,257 INFO L225 Difference]: With dead ends: 97 [2018-10-02 12:10:31,257 INFO L226 Difference]: Without dead ends: 95 [2018-10-02 12:10:31,258 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 177 GetRequests, 89 SyntacticMatches, 0 SemanticMatches, 88 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 5.0s Time 4.4s impTime [2018-10-02 12:10:31,258 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2018-10-02 12:10:31,273 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 95. [2018-10-02 12:10:31,273 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 95 states. [2018-10-02 12:10:31,273 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 95 transitions. [2018-10-02 12:10:31,274 INFO L78 Accepts]: Start accepts. Automaton has 95 states and 95 transitions. Word has length 90 [2018-10-02 12:10:31,274 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:10:31,274 INFO L480 AbstractCegarLoop]: Abstraction has 95 states and 95 transitions. [2018-10-02 12:10:31,274 INFO L481 AbstractCegarLoop]: Interpolant automaton has 47 states. [2018-10-02 12:10:31,274 INFO L276 IsEmpty]: Start isEmpty. Operand 95 states and 95 transitions. [2018-10-02 12:10:31,274 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 95 [2018-10-02 12:10:31,274 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:10:31,275 INFO L375 BasicCegarLoop]: trace histogram [46, 45, 1, 1, 1] [2018-10-02 12:10:31,275 INFO L423 AbstractCegarLoop]: === Iteration 24 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:10:31,275 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:10:31,275 INFO L82 PathProgramCache]: Analyzing trace with hash 1377234553, now seen corresponding path program 23 times [2018-10-02 12:10:31,275 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:10:31,275 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:10:31,276 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:10:31,276 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:10:31,276 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:10:31,383 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:10:33,041 INFO L134 CoverageAnalysis]: Checked inductivity of 2070 backedges. 0 proven. 2070 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:10:33,042 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:10:33,042 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 24 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 24 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:10:33,049 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-10-02 12:10:33,195 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 46 check-sat command(s) [2018-10-02 12:10:33,195 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:10:33,215 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:10:33,875 INFO L134 CoverageAnalysis]: Checked inductivity of 2070 backedges. 0 proven. 2070 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:10:33,894 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:10:33,895 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [47, 47] total 48 [2018-10-02 12:10:33,895 INFO L459 AbstractCegarLoop]: Interpolant automaton has 49 states [2018-10-02 12:10:33,895 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 49 interpolants. [2018-10-02 12:10:33,895 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:10:33,895 INFO L87 Difference]: Start difference. First operand 95 states and 95 transitions. Second operand 49 states. [2018-10-02 12:10:38,100 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:10:38,101 INFO L93 Difference]: Finished difference Result 101 states and 102 transitions. [2018-10-02 12:10:38,101 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 49 states. [2018-10-02 12:10:38,101 INFO L78 Accepts]: Start accepts. Automaton has 49 states. Word has length 94 [2018-10-02 12:10:38,102 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:10:38,102 INFO L225 Difference]: With dead ends: 101 [2018-10-02 12:10:38,103 INFO L226 Difference]: Without dead ends: 99 [2018-10-02 12:10:38,103 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 185 GetRequests, 93 SyntacticMatches, 0 SemanticMatches, 92 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 5.8s Time 4.7s impTime [2018-10-02 12:10:38,104 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states. [2018-10-02 12:10:38,119 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 99. [2018-10-02 12:10:38,120 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 99 states. [2018-10-02 12:10:38,120 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 99 transitions. [2018-10-02 12:10:38,120 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 99 transitions. Word has length 94 [2018-10-02 12:10:38,120 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:10:38,120 INFO L480 AbstractCegarLoop]: Abstraction has 99 states and 99 transitions. [2018-10-02 12:10:38,120 INFO L481 AbstractCegarLoop]: Interpolant automaton has 49 states. [2018-10-02 12:10:38,120 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 99 transitions. [2018-10-02 12:10:38,121 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2018-10-02 12:10:38,121 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:10:38,121 INFO L375 BasicCegarLoop]: trace histogram [48, 47, 1, 1, 1] [2018-10-02 12:10:38,121 INFO L423 AbstractCegarLoop]: === Iteration 25 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:10:38,121 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:10:38,121 INFO L82 PathProgramCache]: Analyzing trace with hash 2056628845, now seen corresponding path program 24 times [2018-10-02 12:10:38,122 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:10:38,122 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:10:38,122 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:10:38,122 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:10:38,122 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:10:38,226 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:10:39,713 INFO L134 CoverageAnalysis]: Checked inductivity of 2256 backedges. 0 proven. 2256 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:10:39,713 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:10:39,713 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:10:39,721 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-10-02 12:10:39,770 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 48 check-sat command(s) [2018-10-02 12:10:39,771 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:10:39,775 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:10:39,992 INFO L134 CoverageAnalysis]: Checked inductivity of 2256 backedges. 0 proven. 2256 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:10:40,015 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:10:40,015 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [49, 49] total 50 [2018-10-02 12:10:40,016 INFO L459 AbstractCegarLoop]: Interpolant automaton has 51 states [2018-10-02 12:10:40,016 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 51 interpolants. [2018-10-02 12:10:40,016 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:10:40,016 INFO L87 Difference]: Start difference. First operand 99 states and 99 transitions. Second operand 51 states. [2018-10-02 12:10:44,815 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:10:44,815 INFO L93 Difference]: Finished difference Result 105 states and 106 transitions. [2018-10-02 12:10:44,816 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 51 states. [2018-10-02 12:10:44,816 INFO L78 Accepts]: Start accepts. Automaton has 51 states. Word has length 98 [2018-10-02 12:10:44,816 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:10:44,817 INFO L225 Difference]: With dead ends: 105 [2018-10-02 12:10:44,817 INFO L226 Difference]: Without dead ends: 103 [2018-10-02 12:10:44,818 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 193 GetRequests, 97 SyntacticMatches, 0 SemanticMatches, 96 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 5.7s Time 5.1s impTime [2018-10-02 12:10:44,818 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states. [2018-10-02 12:10:44,835 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 103. [2018-10-02 12:10:44,836 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 103 states. [2018-10-02 12:10:44,836 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 103 transitions. [2018-10-02 12:10:44,836 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 103 transitions. Word has length 98 [2018-10-02 12:10:44,836 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:10:44,836 INFO L480 AbstractCegarLoop]: Abstraction has 103 states and 103 transitions. [2018-10-02 12:10:44,837 INFO L481 AbstractCegarLoop]: Interpolant automaton has 51 states. [2018-10-02 12:10:44,837 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 103 transitions. [2018-10-02 12:10:44,837 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 103 [2018-10-02 12:10:44,837 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:10:44,838 INFO L375 BasicCegarLoop]: trace histogram [50, 49, 1, 1, 1] [2018-10-02 12:10:44,838 INFO L423 AbstractCegarLoop]: === Iteration 26 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:10:44,838 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:10:44,838 INFO L82 PathProgramCache]: Analyzing trace with hash -1934799775, now seen corresponding path program 25 times [2018-10-02 12:10:44,838 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:10:44,838 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:10:44,839 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:10:44,839 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:10:44,839 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:10:44,939 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:10:46,528 INFO L134 CoverageAnalysis]: Checked inductivity of 2450 backedges. 0 proven. 2450 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:10:46,528 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:10:46,528 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 26 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 26 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:10:46,537 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-02 12:10:46,722 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:10:46,826 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:10:47,178 INFO L134 CoverageAnalysis]: Checked inductivity of 2450 backedges. 0 proven. 2450 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:10:47,198 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:10:47,198 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [51, 51] total 52 [2018-10-02 12:10:47,199 INFO L459 AbstractCegarLoop]: Interpolant automaton has 53 states [2018-10-02 12:10:47,199 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 53 interpolants. [2018-10-02 12:10:47,199 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:10:47,199 INFO L87 Difference]: Start difference. First operand 103 states and 103 transitions. Second operand 53 states. [2018-10-02 12:10:53,222 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:10:53,223 INFO L93 Difference]: Finished difference Result 109 states and 110 transitions. [2018-10-02 12:10:53,223 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 53 states. [2018-10-02 12:10:53,223 INFO L78 Accepts]: Start accepts. Automaton has 53 states. Word has length 102 [2018-10-02 12:10:53,224 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:10:53,225 INFO L225 Difference]: With dead ends: 109 [2018-10-02 12:10:53,225 INFO L226 Difference]: Without dead ends: 107 [2018-10-02 12:10:53,225 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 201 GetRequests, 101 SyntacticMatches, 0 SemanticMatches, 100 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 7.0s Time 6.2s impTime [2018-10-02 12:10:53,226 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 107 states. [2018-10-02 12:10:53,244 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 107 to 107. [2018-10-02 12:10:53,244 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 107 states. [2018-10-02 12:10:53,244 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 107 transitions. [2018-10-02 12:10:53,244 INFO L78 Accepts]: Start accepts. Automaton has 107 states and 107 transitions. Word has length 102 [2018-10-02 12:10:53,245 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:10:53,245 INFO L480 AbstractCegarLoop]: Abstraction has 107 states and 107 transitions. [2018-10-02 12:10:53,245 INFO L481 AbstractCegarLoop]: Interpolant automaton has 53 states. [2018-10-02 12:10:53,245 INFO L276 IsEmpty]: Start isEmpty. Operand 107 states and 107 transitions. [2018-10-02 12:10:53,245 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 107 [2018-10-02 12:10:53,245 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:10:53,245 INFO L375 BasicCegarLoop]: trace histogram [52, 51, 1, 1, 1] [2018-10-02 12:10:53,246 INFO L423 AbstractCegarLoop]: === Iteration 27 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:10:53,246 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:10:53,246 INFO L82 PathProgramCache]: Analyzing trace with hash -1518676907, now seen corresponding path program 26 times [2018-10-02 12:10:53,246 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:10:53,246 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:10:53,247 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:10:53,247 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-02 12:10:53,247 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:10:53,361 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:10:55,172 INFO L134 CoverageAnalysis]: Checked inductivity of 2652 backedges. 0 proven. 2652 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:10:55,173 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:10:55,173 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 27 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 27 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:10:55,180 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-10-02 12:10:55,391 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-10-02 12:10:55,391 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:10:55,514 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:10:55,758 INFO L134 CoverageAnalysis]: Checked inductivity of 2652 backedges. 0 proven. 2652 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:10:55,778 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:10:55,778 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [53, 53] total 54 [2018-10-02 12:10:55,779 INFO L459 AbstractCegarLoop]: Interpolant automaton has 55 states [2018-10-02 12:10:55,779 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 55 interpolants. [2018-10-02 12:10:55,779 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:10:55,779 INFO L87 Difference]: Start difference. First operand 107 states and 107 transitions. Second operand 55 states. [2018-10-02 12:11:02,156 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:11:02,156 INFO L93 Difference]: Finished difference Result 113 states and 114 transitions. [2018-10-02 12:11:02,157 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 55 states. [2018-10-02 12:11:02,157 INFO L78 Accepts]: Start accepts. Automaton has 55 states. Word has length 106 [2018-10-02 12:11:02,157 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:11:02,158 INFO L225 Difference]: With dead ends: 113 [2018-10-02 12:11:02,158 INFO L226 Difference]: Without dead ends: 111 [2018-10-02 12:11:02,159 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 209 GetRequests, 105 SyntacticMatches, 0 SemanticMatches, 104 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 7.5s Time 6.7s impTime [2018-10-02 12:11:02,159 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 111 states. [2018-10-02 12:11:02,176 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 111 to 111. [2018-10-02 12:11:02,176 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 111 states. [2018-10-02 12:11:02,176 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 111 states to 111 states and 111 transitions. [2018-10-02 12:11:02,176 INFO L78 Accepts]: Start accepts. Automaton has 111 states and 111 transitions. Word has length 106 [2018-10-02 12:11:02,176 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:11:02,176 INFO L480 AbstractCegarLoop]: Abstraction has 111 states and 111 transitions. [2018-10-02 12:11:02,177 INFO L481 AbstractCegarLoop]: Interpolant automaton has 55 states. [2018-10-02 12:11:02,177 INFO L276 IsEmpty]: Start isEmpty. Operand 111 states and 111 transitions. [2018-10-02 12:11:02,177 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 111 [2018-10-02 12:11:02,177 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:11:02,177 INFO L375 BasicCegarLoop]: trace histogram [54, 53, 1, 1, 1] [2018-10-02 12:11:02,177 INFO L423 AbstractCegarLoop]: === Iteration 28 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:11:02,177 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:11:02,178 INFO L82 PathProgramCache]: Analyzing trace with hash 194724425, now seen corresponding path program 27 times [2018-10-02 12:11:02,178 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:11:02,178 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:11:02,178 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:11:02,178 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:11:02,179 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:11:02,346 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:11:04,184 INFO L134 CoverageAnalysis]: Checked inductivity of 2862 backedges. 0 proven. 2862 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:11:04,185 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:11:04,185 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 28 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 28 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:11:04,193 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-02 12:11:04,249 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 54 check-sat command(s) [2018-10-02 12:11:04,249 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:11:04,254 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:11:04,545 INFO L134 CoverageAnalysis]: Checked inductivity of 2862 backedges. 0 proven. 2862 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:11:04,565 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:11:04,565 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [55, 55] total 56 [2018-10-02 12:11:04,566 INFO L459 AbstractCegarLoop]: Interpolant automaton has 57 states [2018-10-02 12:11:04,566 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 57 interpolants. [2018-10-02 12:11:04,566 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:11:04,566 INFO L87 Difference]: Start difference. First operand 111 states and 111 transitions. Second operand 57 states. [2018-10-02 12:11:11,149 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:11:11,149 INFO L93 Difference]: Finished difference Result 117 states and 118 transitions. [2018-10-02 12:11:11,150 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 57 states. [2018-10-02 12:11:11,150 INFO L78 Accepts]: Start accepts. Automaton has 57 states. Word has length 110 [2018-10-02 12:11:11,150 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:11:11,151 INFO L225 Difference]: With dead ends: 117 [2018-10-02 12:11:11,151 INFO L226 Difference]: Without dead ends: 115 [2018-10-02 12:11:11,152 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 217 GetRequests, 109 SyntacticMatches, 0 SemanticMatches, 108 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 7.7s Time 7.0s impTime [2018-10-02 12:11:11,152 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 115 states. [2018-10-02 12:11:11,170 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 115 to 115. [2018-10-02 12:11:11,170 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 115 states. [2018-10-02 12:11:11,170 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 115 states to 115 states and 115 transitions. [2018-10-02 12:11:11,171 INFO L78 Accepts]: Start accepts. Automaton has 115 states and 115 transitions. Word has length 110 [2018-10-02 12:11:11,171 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:11:11,171 INFO L480 AbstractCegarLoop]: Abstraction has 115 states and 115 transitions. [2018-10-02 12:11:11,171 INFO L481 AbstractCegarLoop]: Interpolant automaton has 57 states. [2018-10-02 12:11:11,171 INFO L276 IsEmpty]: Start isEmpty. Operand 115 states and 115 transitions. [2018-10-02 12:11:11,171 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 115 [2018-10-02 12:11:11,171 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:11:11,172 INFO L375 BasicCegarLoop]: trace histogram [56, 55, 1, 1, 1] [2018-10-02 12:11:11,172 INFO L423 AbstractCegarLoop]: === Iteration 29 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:11:11,172 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:11:11,172 INFO L82 PathProgramCache]: Analyzing trace with hash 1865127485, now seen corresponding path program 28 times [2018-10-02 12:11:11,172 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:11:11,172 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:11:11,173 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:11:11,173 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:11:11,173 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:11:11,311 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:11:13,490 INFO L134 CoverageAnalysis]: Checked inductivity of 3080 backedges. 0 proven. 3080 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:11:13,490 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:11:13,490 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 29 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 29 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:11:13,500 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-02 12:11:13,759 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-02 12:11:13,759 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:11:13,913 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:11:14,178 INFO L134 CoverageAnalysis]: Checked inductivity of 3080 backedges. 0 proven. 3080 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:11:14,198 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:11:14,198 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [57, 57] total 58 [2018-10-02 12:11:14,199 INFO L459 AbstractCegarLoop]: Interpolant automaton has 59 states [2018-10-02 12:11:14,199 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 59 interpolants. [2018-10-02 12:11:14,199 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:11:14,199 INFO L87 Difference]: Start difference. First operand 115 states and 115 transitions. Second operand 59 states. [2018-10-02 12:11:23,160 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:11:23,161 INFO L93 Difference]: Finished difference Result 121 states and 122 transitions. [2018-10-02 12:11:23,161 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 59 states. [2018-10-02 12:11:23,161 INFO L78 Accepts]: Start accepts. Automaton has 59 states. Word has length 114 [2018-10-02 12:11:23,162 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:11:23,163 INFO L225 Difference]: With dead ends: 121 [2018-10-02 12:11:23,163 INFO L226 Difference]: Without dead ends: 119 [2018-10-02 12:11:23,163 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 225 GetRequests, 113 SyntacticMatches, 0 SemanticMatches, 112 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 10.3s Time 9.4s impTime [2018-10-02 12:11:23,164 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 119 states. [2018-10-02 12:11:23,186 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 119 to 119. [2018-10-02 12:11:23,186 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 119 states. [2018-10-02 12:11:23,187 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 119 states to 119 states and 119 transitions. [2018-10-02 12:11:23,187 INFO L78 Accepts]: Start accepts. Automaton has 119 states and 119 transitions. Word has length 114 [2018-10-02 12:11:23,187 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:11:23,187 INFO L480 AbstractCegarLoop]: Abstraction has 119 states and 119 transitions. [2018-10-02 12:11:23,187 INFO L481 AbstractCegarLoop]: Interpolant automaton has 59 states. [2018-10-02 12:11:23,187 INFO L276 IsEmpty]: Start isEmpty. Operand 119 states and 119 transitions. [2018-10-02 12:11:23,187 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 119 [2018-10-02 12:11:23,188 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:11:23,188 INFO L375 BasicCegarLoop]: trace histogram [58, 57, 1, 1, 1] [2018-10-02 12:11:23,188 INFO L423 AbstractCegarLoop]: === Iteration 30 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:11:23,188 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:11:23,188 INFO L82 PathProgramCache]: Analyzing trace with hash 701026353, now seen corresponding path program 29 times [2018-10-02 12:11:23,188 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:11:23,188 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:11:23,189 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:11:23,189 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:11:23,189 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:11:23,369 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:11:25,577 INFO L134 CoverageAnalysis]: Checked inductivity of 3306 backedges. 0 proven. 3306 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:11:25,577 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:11:25,578 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 30 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 30 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:11:25,585 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-10-02 12:11:25,835 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 58 check-sat command(s) [2018-10-02 12:11:25,836 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:11:25,873 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:11:26,217 INFO L134 CoverageAnalysis]: Checked inductivity of 3306 backedges. 0 proven. 3306 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:11:26,239 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:11:26,239 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [59, 59] total 60 [2018-10-02 12:11:26,239 INFO L459 AbstractCegarLoop]: Interpolant automaton has 61 states [2018-10-02 12:11:26,240 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 61 interpolants. [2018-10-02 12:11:26,240 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:11:26,240 INFO L87 Difference]: Start difference. First operand 119 states and 119 transitions. Second operand 61 states. [2018-10-02 12:11:33,410 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:11:33,410 INFO L93 Difference]: Finished difference Result 125 states and 126 transitions. [2018-10-02 12:11:33,411 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 61 states. [2018-10-02 12:11:33,412 INFO L78 Accepts]: Start accepts. Automaton has 61 states. Word has length 118 [2018-10-02 12:11:33,412 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:11:33,413 INFO L225 Difference]: With dead ends: 125 [2018-10-02 12:11:33,413 INFO L226 Difference]: Without dead ends: 123 [2018-10-02 12:11:33,413 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 233 GetRequests, 117 SyntacticMatches, 0 SemanticMatches, 116 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 8.6s Time 7.7s impTime [2018-10-02 12:11:33,414 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 123 states. [2018-10-02 12:11:33,444 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 123 to 123. [2018-10-02 12:11:33,444 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 123 states. [2018-10-02 12:11:33,445 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 123 states to 123 states and 123 transitions. [2018-10-02 12:11:33,445 INFO L78 Accepts]: Start accepts. Automaton has 123 states and 123 transitions. Word has length 118 [2018-10-02 12:11:33,445 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:11:33,445 INFO L480 AbstractCegarLoop]: Abstraction has 123 states and 123 transitions. [2018-10-02 12:11:33,445 INFO L481 AbstractCegarLoop]: Interpolant automaton has 61 states. [2018-10-02 12:11:33,445 INFO L276 IsEmpty]: Start isEmpty. Operand 123 states and 123 transitions. [2018-10-02 12:11:33,446 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 123 [2018-10-02 12:11:33,446 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:11:33,446 INFO L375 BasicCegarLoop]: trace histogram [60, 59, 1, 1, 1] [2018-10-02 12:11:33,446 INFO L423 AbstractCegarLoop]: === Iteration 31 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:11:33,447 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:11:33,447 INFO L82 PathProgramCache]: Analyzing trace with hash 2123362341, now seen corresponding path program 30 times [2018-10-02 12:11:33,447 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:11:33,447 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:11:33,448 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:11:33,448 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:11:33,448 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:11:33,685 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:11:36,320 INFO L134 CoverageAnalysis]: Checked inductivity of 3540 backedges. 0 proven. 3540 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:11:36,320 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:11:36,320 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 31 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 31 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:11:36,329 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-10-02 12:11:36,401 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 60 check-sat command(s) [2018-10-02 12:11:36,401 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:11:36,411 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:11:36,754 INFO L134 CoverageAnalysis]: Checked inductivity of 3540 backedges. 0 proven. 3540 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:11:36,774 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:11:36,774 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [61, 61] total 62 [2018-10-02 12:11:36,775 INFO L459 AbstractCegarLoop]: Interpolant automaton has 63 states [2018-10-02 12:11:36,775 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 63 interpolants. [2018-10-02 12:11:36,775 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:11:36,775 INFO L87 Difference]: Start difference. First operand 123 states and 123 transitions. Second operand 63 states. [2018-10-02 12:11:45,350 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:11:45,350 INFO L93 Difference]: Finished difference Result 129 states and 130 transitions. [2018-10-02 12:11:45,350 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 63 states. [2018-10-02 12:11:45,350 INFO L78 Accepts]: Start accepts. Automaton has 63 states. Word has length 122 [2018-10-02 12:11:45,351 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:11:45,352 INFO L225 Difference]: With dead ends: 129 [2018-10-02 12:11:45,352 INFO L226 Difference]: Without dead ends: 127 [2018-10-02 12:11:45,352 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 241 GetRequests, 121 SyntacticMatches, 0 SemanticMatches, 120 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 10.5s Time 9.5s impTime [2018-10-02 12:11:45,352 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states. [2018-10-02 12:11:45,373 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 127. [2018-10-02 12:11:45,373 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 127 states. [2018-10-02 12:11:45,373 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 127 transitions. [2018-10-02 12:11:45,373 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 127 transitions. Word has length 122 [2018-10-02 12:11:45,374 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:11:45,374 INFO L480 AbstractCegarLoop]: Abstraction has 127 states and 127 transitions. [2018-10-02 12:11:45,374 INFO L481 AbstractCegarLoop]: Interpolant automaton has 63 states. [2018-10-02 12:11:45,374 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 127 transitions. [2018-10-02 12:11:45,374 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 127 [2018-10-02 12:11:45,374 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:11:45,375 INFO L375 BasicCegarLoop]: trace histogram [62, 61, 1, 1, 1] [2018-10-02 12:11:45,375 INFO L423 AbstractCegarLoop]: === Iteration 32 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:11:45,375 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:11:45,375 INFO L82 PathProgramCache]: Analyzing trace with hash -635570663, now seen corresponding path program 31 times [2018-10-02 12:11:45,375 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:11:45,375 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:11:45,376 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:11:45,376 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:11:45,376 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:11:45,552 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:11:48,086 INFO L134 CoverageAnalysis]: Checked inductivity of 3782 backedges. 0 proven. 3782 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:11:48,086 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:11:48,086 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 32 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 32 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:11:48,095 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-02 12:11:48,429 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:11:48,630 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:11:49,005 INFO L134 CoverageAnalysis]: Checked inductivity of 3782 backedges. 0 proven. 3782 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:11:49,025 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:11:49,025 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [63, 63] total 64 [2018-10-02 12:11:49,026 INFO L459 AbstractCegarLoop]: Interpolant automaton has 65 states [2018-10-02 12:11:49,026 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 65 interpolants. [2018-10-02 12:11:49,026 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:11:49,027 INFO L87 Difference]: Start difference. First operand 127 states and 127 transitions. Second operand 65 states. [2018-10-02 12:11:57,297 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:11:57,298 INFO L93 Difference]: Finished difference Result 133 states and 134 transitions. [2018-10-02 12:11:57,303 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 65 states. [2018-10-02 12:11:57,304 INFO L78 Accepts]: Start accepts. Automaton has 65 states. Word has length 126 [2018-10-02 12:11:57,304 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:11:57,305 INFO L225 Difference]: With dead ends: 133 [2018-10-02 12:11:57,305 INFO L226 Difference]: Without dead ends: 131 [2018-10-02 12:11:57,305 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 249 GetRequests, 125 SyntacticMatches, 0 SemanticMatches, 124 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 10.1s Time 9.1s impTime [2018-10-02 12:11:57,305 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 131 states. [2018-10-02 12:11:57,337 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 131 to 131. [2018-10-02 12:11:57,338 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 131 states. [2018-10-02 12:11:57,338 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 131 states to 131 states and 131 transitions. [2018-10-02 12:11:57,339 INFO L78 Accepts]: Start accepts. Automaton has 131 states and 131 transitions. Word has length 126 [2018-10-02 12:11:57,339 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:11:57,339 INFO L480 AbstractCegarLoop]: Abstraction has 131 states and 131 transitions. [2018-10-02 12:11:57,339 INFO L481 AbstractCegarLoop]: Interpolant automaton has 65 states. [2018-10-02 12:11:57,339 INFO L276 IsEmpty]: Start isEmpty. Operand 131 states and 131 transitions. [2018-10-02 12:11:57,340 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 131 [2018-10-02 12:11:57,340 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:11:57,340 INFO L375 BasicCegarLoop]: trace histogram [64, 63, 1, 1, 1] [2018-10-02 12:11:57,340 INFO L423 AbstractCegarLoop]: === Iteration 33 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:11:57,340 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:11:57,341 INFO L82 PathProgramCache]: Analyzing trace with hash 311419405, now seen corresponding path program 32 times [2018-10-02 12:11:57,341 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:11:57,341 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:11:57,341 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:11:57,342 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-02 12:11:57,342 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:11:57,587 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:12:00,433 INFO L134 CoverageAnalysis]: Checked inductivity of 4032 backedges. 0 proven. 4032 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:12:00,433 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:12:00,433 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 33 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 33 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:12:00,441 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-10-02 12:12:00,814 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-10-02 12:12:00,814 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:12:01,035 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:12:01,691 INFO L134 CoverageAnalysis]: Checked inductivity of 4032 backedges. 0 proven. 4032 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:12:01,711 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:12:01,711 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [65, 65] total 66 [2018-10-02 12:12:01,712 INFO L459 AbstractCegarLoop]: Interpolant automaton has 67 states [2018-10-02 12:12:01,712 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 67 interpolants. [2018-10-02 12:12:01,712 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:12:01,712 INFO L87 Difference]: Start difference. First operand 131 states and 131 transitions. Second operand 67 states. [2018-10-02 12:12:12,617 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:12:12,618 INFO L93 Difference]: Finished difference Result 137 states and 138 transitions. [2018-10-02 12:12:12,618 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 67 states. [2018-10-02 12:12:12,618 INFO L78 Accepts]: Start accepts. Automaton has 67 states. Word has length 130 [2018-10-02 12:12:12,619 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:12:12,619 INFO L225 Difference]: With dead ends: 137 [2018-10-02 12:12:12,620 INFO L226 Difference]: Without dead ends: 135 [2018-10-02 12:12:12,620 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 257 GetRequests, 129 SyntacticMatches, 0 SemanticMatches, 128 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 13.1s Time 11.7s impTime [2018-10-02 12:12:12,620 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 135 states. [2018-10-02 12:12:12,652 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 135 to 135. [2018-10-02 12:12:12,652 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 135 states. [2018-10-02 12:12:12,653 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 135 states to 135 states and 135 transitions. [2018-10-02 12:12:12,653 INFO L78 Accepts]: Start accepts. Automaton has 135 states and 135 transitions. Word has length 130 [2018-10-02 12:12:12,653 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:12:12,653 INFO L480 AbstractCegarLoop]: Abstraction has 135 states and 135 transitions. [2018-10-02 12:12:12,653 INFO L481 AbstractCegarLoop]: Interpolant automaton has 67 states. [2018-10-02 12:12:12,654 INFO L276 IsEmpty]: Start isEmpty. Operand 135 states and 135 transitions. [2018-10-02 12:12:12,654 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 135 [2018-10-02 12:12:12,654 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:12:12,655 INFO L375 BasicCegarLoop]: trace histogram [66, 65, 1, 1, 1] [2018-10-02 12:12:12,655 INFO L423 AbstractCegarLoop]: === Iteration 34 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:12:12,655 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:12:12,655 INFO L82 PathProgramCache]: Analyzing trace with hash -1484606463, now seen corresponding path program 33 times [2018-10-02 12:12:12,655 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:12:12,655 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:12:12,656 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:12:12,656 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:12:12,656 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:12:12,931 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:12:16,020 INFO L134 CoverageAnalysis]: Checked inductivity of 4290 backedges. 0 proven. 4290 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:12:16,020 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:12:16,020 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 34 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 34 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:12:16,028 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-02 12:12:16,103 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 66 check-sat command(s) [2018-10-02 12:12:16,104 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:12:16,111 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:12:16,443 INFO L134 CoverageAnalysis]: Checked inductivity of 4290 backedges. 0 proven. 4290 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:12:16,476 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:12:16,476 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [67, 67] total 68 [2018-10-02 12:12:16,477 INFO L459 AbstractCegarLoop]: Interpolant automaton has 69 states [2018-10-02 12:12:16,477 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 69 interpolants. [2018-10-02 12:12:16,477 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:12:16,477 INFO L87 Difference]: Start difference. First operand 135 states and 135 transitions. Second operand 69 states. [2018-10-02 12:12:28,831 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:12:28,832 INFO L93 Difference]: Finished difference Result 141 states and 142 transitions. [2018-10-02 12:12:28,832 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 69 states. [2018-10-02 12:12:28,832 INFO L78 Accepts]: Start accepts. Automaton has 69 states. Word has length 134 [2018-10-02 12:12:28,833 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:12:28,833 INFO L225 Difference]: With dead ends: 141 [2018-10-02 12:12:28,833 INFO L226 Difference]: Without dead ends: 139 [2018-10-02 12:12:28,834 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 265 GetRequests, 133 SyntacticMatches, 0 SemanticMatches, 132 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 14.4s Time 13.4s impTime [2018-10-02 12:12:28,834 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 139 states. [2018-10-02 12:12:28,865 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 139 to 139. [2018-10-02 12:12:28,865 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 139 states. [2018-10-02 12:12:28,866 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 139 transitions. [2018-10-02 12:12:28,866 INFO L78 Accepts]: Start accepts. Automaton has 139 states and 139 transitions. Word has length 134 [2018-10-02 12:12:28,866 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:12:28,866 INFO L480 AbstractCegarLoop]: Abstraction has 139 states and 139 transitions. [2018-10-02 12:12:28,866 INFO L481 AbstractCegarLoop]: Interpolant automaton has 69 states. [2018-10-02 12:12:28,867 INFO L276 IsEmpty]: Start isEmpty. Operand 139 states and 139 transitions. [2018-10-02 12:12:28,867 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 139 [2018-10-02 12:12:28,867 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:12:28,867 INFO L375 BasicCegarLoop]: trace histogram [68, 67, 1, 1, 1] [2018-10-02 12:12:28,868 INFO L423 AbstractCegarLoop]: === Iteration 35 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:12:28,868 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:12:28,868 INFO L82 PathProgramCache]: Analyzing trace with hash 34827253, now seen corresponding path program 34 times [2018-10-02 12:12:28,868 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:12:28,868 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:12:28,869 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:12:28,869 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:12:28,869 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:12:29,123 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:12:32,316 INFO L134 CoverageAnalysis]: Checked inductivity of 4556 backedges. 0 proven. 4556 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:12:32,317 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:12:32,317 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 35 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 35 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:12:32,325 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-02 12:12:32,365 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-02 12:12:32,365 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:12:32,369 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:12:32,699 INFO L134 CoverageAnalysis]: Checked inductivity of 4556 backedges. 0 proven. 4556 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:12:32,729 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:12:32,730 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [69, 69] total 70 [2018-10-02 12:12:32,730 INFO L459 AbstractCegarLoop]: Interpolant automaton has 71 states [2018-10-02 12:12:32,730 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 71 interpolants. [2018-10-02 12:12:32,731 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:12:32,731 INFO L87 Difference]: Start difference. First operand 139 states and 139 transitions. Second operand 71 states. [2018-10-02 12:12:45,194 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:12:45,194 INFO L93 Difference]: Finished difference Result 145 states and 146 transitions. [2018-10-02 12:12:45,194 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 71 states. [2018-10-02 12:12:45,195 INFO L78 Accepts]: Start accepts. Automaton has 71 states. Word has length 138 [2018-10-02 12:12:45,195 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:12:45,196 INFO L225 Difference]: With dead ends: 145 [2018-10-02 12:12:45,196 INFO L226 Difference]: Without dead ends: 143 [2018-10-02 12:12:45,196 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 273 GetRequests, 137 SyntacticMatches, 0 SemanticMatches, 136 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 14.6s Time 13.4s impTime [2018-10-02 12:12:45,196 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 143 states. [2018-10-02 12:12:45,223 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 143 to 143. [2018-10-02 12:12:45,223 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 143 states. [2018-10-02 12:12:45,224 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 143 states to 143 states and 143 transitions. [2018-10-02 12:12:45,224 INFO L78 Accepts]: Start accepts. Automaton has 143 states and 143 transitions. Word has length 138 [2018-10-02 12:12:45,224 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:12:45,224 INFO L480 AbstractCegarLoop]: Abstraction has 143 states and 143 transitions. [2018-10-02 12:12:45,224 INFO L481 AbstractCegarLoop]: Interpolant automaton has 71 states. [2018-10-02 12:12:45,224 INFO L276 IsEmpty]: Start isEmpty. Operand 143 states and 143 transitions. [2018-10-02 12:12:45,225 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 143 [2018-10-02 12:12:45,225 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:12:45,225 INFO L375 BasicCegarLoop]: trace histogram [70, 69, 1, 1, 1] [2018-10-02 12:12:45,225 INFO L423 AbstractCegarLoop]: === Iteration 36 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:12:45,225 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:12:45,225 INFO L82 PathProgramCache]: Analyzing trace with hash -1260451351, now seen corresponding path program 35 times [2018-10-02 12:12:45,225 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:12:45,225 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:12:45,226 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:12:45,226 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:12:45,226 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:12:45,487 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:12:49,296 INFO L134 CoverageAnalysis]: Checked inductivity of 4830 backedges. 0 proven. 4830 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:12:49,297 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:12:49,297 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 36 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 36 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:12:49,304 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-10-02 12:12:49,728 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 70 check-sat command(s) [2018-10-02 12:12:49,728 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:12:49,796 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:12:50,343 INFO L134 CoverageAnalysis]: Checked inductivity of 4830 backedges. 0 proven. 4830 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:12:50,363 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:12:50,363 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [71, 71] total 72 [2018-10-02 12:12:50,364 INFO L459 AbstractCegarLoop]: Interpolant automaton has 73 states [2018-10-02 12:12:50,364 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 73 interpolants. [2018-10-02 12:12:50,364 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:12:50,364 INFO L87 Difference]: Start difference. First operand 143 states and 143 transitions. Second operand 73 states. [2018-10-02 12:13:01,937 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:13:01,937 INFO L93 Difference]: Finished difference Result 149 states and 150 transitions. [2018-10-02 12:13:01,937 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 73 states. [2018-10-02 12:13:01,938 INFO L78 Accepts]: Start accepts. Automaton has 73 states. Word has length 142 [2018-10-02 12:13:01,938 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:13:01,939 INFO L225 Difference]: With dead ends: 149 [2018-10-02 12:13:01,939 INFO L226 Difference]: Without dead ends: 147 [2018-10-02 12:13:01,939 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 281 GetRequests, 141 SyntacticMatches, 0 SemanticMatches, 140 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 14.6s Time 13.1s impTime [2018-10-02 12:13:01,940 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 147 states. [2018-10-02 12:13:01,976 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 147 to 147. [2018-10-02 12:13:01,977 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 147 states. [2018-10-02 12:13:01,977 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 147 states to 147 states and 147 transitions. [2018-10-02 12:13:01,977 INFO L78 Accepts]: Start accepts. Automaton has 147 states and 147 transitions. Word has length 142 [2018-10-02 12:13:01,978 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:13:01,978 INFO L480 AbstractCegarLoop]: Abstraction has 147 states and 147 transitions. [2018-10-02 12:13:01,978 INFO L481 AbstractCegarLoop]: Interpolant automaton has 73 states. [2018-10-02 12:13:01,978 INFO L276 IsEmpty]: Start isEmpty. Operand 147 states and 147 transitions. [2018-10-02 12:13:01,978 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 147 [2018-10-02 12:13:01,979 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:13:01,979 INFO L375 BasicCegarLoop]: trace histogram [72, 71, 1, 1, 1] [2018-10-02 12:13:01,979 INFO L423 AbstractCegarLoop]: === Iteration 37 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:13:01,979 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:13:01,979 INFO L82 PathProgramCache]: Analyzing trace with hash -1140683299, now seen corresponding path program 36 times [2018-10-02 12:13:01,979 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:13:01,980 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:13:01,980 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:13:01,980 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:13:01,980 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:13:02,300 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:13:06,160 INFO L134 CoverageAnalysis]: Checked inductivity of 5112 backedges. 0 proven. 5112 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:13:06,161 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:13:06,161 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 37 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 37 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:13:06,168 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-10-02 12:13:06,248 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 72 check-sat command(s) [2018-10-02 12:13:06,248 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-02 12:13:06,258 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:13:06,724 INFO L134 CoverageAnalysis]: Checked inductivity of 5112 backedges. 0 proven. 5112 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:13:06,744 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:13:06,744 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [73, 73] total 74 [2018-10-02 12:13:06,745 INFO L459 AbstractCegarLoop]: Interpolant automaton has 75 states [2018-10-02 12:13:06,745 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 75 interpolants. [2018-10-02 12:13:06,745 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:13:06,746 INFO L87 Difference]: Start difference. First operand 147 states and 147 transitions. Second operand 75 states. [2018-10-02 12:13:19,755 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:13:19,755 INFO L93 Difference]: Finished difference Result 153 states and 154 transitions. [2018-10-02 12:13:19,756 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 75 states. [2018-10-02 12:13:19,756 INFO L78 Accepts]: Start accepts. Automaton has 75 states. Word has length 146 [2018-10-02 12:13:19,756 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:13:19,757 INFO L225 Difference]: With dead ends: 153 [2018-10-02 12:13:19,757 INFO L226 Difference]: Without dead ends: 151 [2018-10-02 12:13:19,757 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 289 GetRequests, 145 SyntacticMatches, 0 SemanticMatches, 144 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 15.9s Time 14.6s impTime [2018-10-02 12:13:19,758 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 151 states. [2018-10-02 12:13:19,797 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 151 to 151. [2018-10-02 12:13:19,797 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 151 states. [2018-10-02 12:13:19,798 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 151 states to 151 states and 151 transitions. [2018-10-02 12:13:19,798 INFO L78 Accepts]: Start accepts. Automaton has 151 states and 151 transitions. Word has length 146 [2018-10-02 12:13:19,798 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:13:19,798 INFO L480 AbstractCegarLoop]: Abstraction has 151 states and 151 transitions. [2018-10-02 12:13:19,798 INFO L481 AbstractCegarLoop]: Interpolant automaton has 75 states. [2018-10-02 12:13:19,799 INFO L276 IsEmpty]: Start isEmpty. Operand 151 states and 151 transitions. [2018-10-02 12:13:19,799 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 151 [2018-10-02 12:13:19,799 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:13:19,799 INFO L375 BasicCegarLoop]: trace histogram [74, 73, 1, 1, 1] [2018-10-02 12:13:19,800 INFO L423 AbstractCegarLoop]: === Iteration 38 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:13:19,800 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:13:19,800 INFO L82 PathProgramCache]: Analyzing trace with hash -1122306095, now seen corresponding path program 37 times [2018-10-02 12:13:19,800 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:13:19,800 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:13:19,801 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:13:19,801 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-02 12:13:19,801 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:13:20,280 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:13:23,973 INFO L134 CoverageAnalysis]: Checked inductivity of 5402 backedges. 0 proven. 5402 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:13:23,973 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-02 12:13:23,973 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 38 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 38 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-02 12:13:23,981 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-02 12:13:24,892 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-02 12:13:25,246 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-02 12:13:25,609 INFO L134 CoverageAnalysis]: Checked inductivity of 5402 backedges. 0 proven. 5402 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-02 12:13:25,632 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-02 12:13:25,632 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [75, 75] total 76 [2018-10-02 12:13:25,633 INFO L459 AbstractCegarLoop]: Interpolant automaton has 77 states [2018-10-02 12:13:25,633 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 77 interpolants. [2018-10-02 12:13:25,633 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-02 12:13:25,633 INFO L87 Difference]: Start difference. First operand 151 states and 151 transitions. Second operand 77 states. [2018-10-02 12:13:41,436 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-02 12:13:41,437 INFO L93 Difference]: Finished difference Result 157 states and 158 transitions. [2018-10-02 12:13:41,437 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 77 states. [2018-10-02 12:13:41,437 INFO L78 Accepts]: Start accepts. Automaton has 77 states. Word has length 150 [2018-10-02 12:13:41,437 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-02 12:13:41,438 INFO L225 Difference]: With dead ends: 157 [2018-10-02 12:13:41,438 INFO L226 Difference]: Without dead ends: 155 [2018-10-02 12:13:41,438 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 297 GetRequests, 149 SyntacticMatches, 0 SemanticMatches, 148 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 18.0s Time 16.8s impTime [2018-10-02 12:13:41,439 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 155 states. [2018-10-02 12:13:41,466 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 155 to 155. [2018-10-02 12:13:41,467 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 155 states. [2018-10-02 12:13:41,467 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 155 states to 155 states and 155 transitions. [2018-10-02 12:13:41,467 INFO L78 Accepts]: Start accepts. Automaton has 155 states and 155 transitions. Word has length 150 [2018-10-02 12:13:41,467 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-02 12:13:41,468 INFO L480 AbstractCegarLoop]: Abstraction has 155 states and 155 transitions. [2018-10-02 12:13:41,468 INFO L481 AbstractCegarLoop]: Interpolant automaton has 77 states. [2018-10-02 12:13:41,468 INFO L276 IsEmpty]: Start isEmpty. Operand 155 states and 155 transitions. [2018-10-02 12:13:41,468 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 155 [2018-10-02 12:13:41,468 INFO L367 BasicCegarLoop]: Found error trace [2018-10-02 12:13:41,468 INFO L375 BasicCegarLoop]: trace histogram [76, 75, 1, 1, 1] [2018-10-02 12:13:41,469 INFO L423 AbstractCegarLoop]: === Iteration 39 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-02 12:13:41,469 INFO L103 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-02 12:13:41,469 INFO L82 PathProgramCache]: Analyzing trace with hash 1195722693, now seen corresponding path program 38 times [2018-10-02 12:13:41,469 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-02 12:13:41,469 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-02 12:13:41,470 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:13:41,470 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-02 12:13:41,470 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-02 12:13:41,805 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat Received shutdown request... [2018-10-02 12:13:44,931 WARN L549 AbstractCegarLoop]: Verification canceled [2018-10-02 12:13:44,935 WARN L205 ceAbstractionStarter]: Timeout [2018-10-02 12:13:44,935 INFO L202 PluginConnector]: Adding new model count_by_k.i_3.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 02.10 12:13:44 BoogieIcfgContainer [2018-10-02 12:13:44,935 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-10-02 12:13:44,936 INFO L168 Benchmark]: Toolchain (without parser) took 255050.28 ms. Allocated memory was 1.5 GB in the beginning and 1.4 GB in the end (delta: -120.1 MB). Free memory was 1.5 GB in the beginning and 1.4 GB in the end (delta: 90.7 MB). Peak memory consumption was 456.6 MB. Max. memory is 7.1 GB. [2018-10-02 12:13:44,939 INFO L168 Benchmark]: Boogie PL CUP Parser took 0.22 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-10-02 12:13:44,939 INFO L168 Benchmark]: Boogie Procedure Inliner took 41.10 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-10-02 12:13:44,940 INFO L168 Benchmark]: Boogie Preprocessor took 22.86 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-10-02 12:13:44,940 INFO L168 Benchmark]: RCFGBuilder took 325.46 ms. Allocated memory is still 1.5 GB. Free memory was 1.5 GB in the beginning and 1.5 GB in the end (delta: 21.1 MB). Peak memory consumption was 21.1 MB. Max. memory is 7.1 GB. [2018-10-02 12:13:44,941 INFO L168 Benchmark]: TraceAbstraction took 254655.04 ms. Allocated memory was 1.5 GB in the beginning and 1.4 GB in the end (delta: -120.1 MB). Free memory was 1.5 GB in the beginning and 1.4 GB in the end (delta: 69.5 MB). Peak memory consumption was 435.5 MB. Max. memory is 7.1 GB. [2018-10-02 12:13:44,945 INFO L336 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * Boogie PL CUP Parser took 0.22 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. * Boogie Procedure Inliner took 41.10 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. * Boogie Preprocessor took 22.86 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. * RCFGBuilder took 325.46 ms. Allocated memory is still 1.5 GB. Free memory was 1.5 GB in the beginning and 1.5 GB in the end (delta: 21.1 MB). Peak memory consumption was 21.1 MB. Max. memory is 7.1 GB. * TraceAbstraction took 254655.04 ms. Allocated memory was 1.5 GB in the beginning and 1.4 GB in the end (delta: -120.1 MB). Free memory was 1.5 GB in the beginning and 1.4 GB in the end (delta: 69.5 MB). Peak memory consumption was 435.5 MB. Max. memory is 7.1 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 38]: Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 38). Cancelled while BasicCegarLoop was analyzing trace of length 155 with TraceHistMax 76, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while NestedInterpolantsBuilder was constructing predicates for 153 interpolants. - StatisticsResult: Ultimate Automizer benchmark data CFG has 1 procedures, 7 locations, 1 error locations. TIMEOUT Result, 254.5s OverallTime, 39 OverallIterations, 76 TraceHistogramMax, 174.3s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 189 SDtfs, 0 SDslu, 2909 SDs, 0 SdLazy, 3058 SolverSat, 1369 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 7.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 5662 GetRequests, 2850 SyntacticMatches, 0 SemanticMatches, 2812 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 211.2s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=155occurred in iteration=38, 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.6s AutomataMinimizationTime, 38 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 8.2s SatisfiabilityAnalysisTime, 65.8s InterpolantComputationTime, 5776 NumberOfCodeBlocks, 5776 NumberOfCodeBlocksAsserted, 777 NumberOfCheckSat, 5701 ConstructedInterpolants, 0 QuantifiedInterpolants, 2857315 SizeOfPredicates, 74 NumberOfNonLiveVariables, 6105 ConjunctsInSsa, 1480 ConjunctsInUnsatCore, 75 InterpolantComputations, 1 PerfectInterpolantSequences, 0/137788 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/repos/ultimate/releaseScripts/default/UAutomizer-linux/csv/count_by_k.i_3.bpl_svcomp-Reach-32bit-Automizer_Default_PUPT.epf_AutomizerBplInline.xml/Csv-Benchmark-0-2018-10-02_12-13-44-956.csv Written .csv to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/csv/count_by_k.i_3.bpl_svcomp-Reach-32bit-Automizer_Default_PUPT.epf_AutomizerBplInline.xml/Csv-TraceAbstractionBenchmarks-0-2018-10-02_12-13-44-956.csv Completed graceful shutdown