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.epf -i ../../../trunk/examples/programs/20170304-DifficultPathPrograms/count_by_k.i_3.bpl -------------------------------------------------------------------------------- This is Ultimate 0.1.23-00a8621 [2018-09-30 10:22:36,876 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-09-30 10:22:36,878 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-09-30 10:22:36,894 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-09-30 10:22:36,894 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-09-30 10:22:36,895 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-09-30 10:22:36,901 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-09-30 10:22:36,904 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-09-30 10:22:36,906 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-09-30 10:22:36,907 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-09-30 10:22:36,908 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-09-30 10:22:36,908 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-09-30 10:22:36,909 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-09-30 10:22:36,910 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-09-30 10:22:36,911 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-09-30 10:22:36,912 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-09-30 10:22:36,913 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-09-30 10:22:36,915 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-09-30 10:22:36,917 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-09-30 10:22:36,919 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-09-30 10:22:36,922 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-09-30 10:22:36,927 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-09-30 10:22:36,932 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-09-30 10:22:36,932 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-09-30 10:22:36,932 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-09-30 10:22:36,934 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-09-30 10:22:36,940 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-09-30 10:22:36,941 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-09-30 10:22:36,942 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-09-30 10:22:36,943 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-09-30 10:22:36,943 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-09-30 10:22:36,947 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-09-30 10:22:36,947 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-09-30 10:22:36,948 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-09-30 10:22:36,951 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-09-30 10:22:36,952 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-09-30 10:22:36,952 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/pu-bench/svcomp-Reach-32bit-Automizer_Default.epf [2018-09-30 10:22:36,981 INFO L110 SettingsManager]: Loading preferences was successful [2018-09-30 10:22:36,984 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-09-30 10:22:36,985 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-09-30 10:22:36,985 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-09-30 10:22:36,986 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-09-30 10:22:36,986 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-09-30 10:22:36,986 INFO L133 SettingsManager]: * Use SBE=true [2018-09-30 10:22:36,987 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-09-30 10:22:36,988 INFO L133 SettingsManager]: * sizeof long=4 [2018-09-30 10:22:36,988 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-09-30 10:22:36,988 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-09-30 10:22:36,988 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-09-30 10:22:36,988 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-09-30 10:22:36,989 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-09-30 10:22:36,989 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-09-30 10:22:36,989 INFO L133 SettingsManager]: * sizeof long double=12 [2018-09-30 10:22:36,989 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-09-30 10:22:36,991 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-09-30 10:22:36,991 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-09-30 10:22:36,991 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-09-30 10:22:36,991 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-09-30 10:22:36,992 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-09-30 10:22:36,992 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-09-30 10:22:36,992 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-09-30 10:22:36,992 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-09-30 10:22:36,993 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-09-30 10:22:36,993 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-09-30 10:22:36,993 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-09-30 10:22:36,993 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-09-30 10:22:36,994 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-09-30 10:22:37,064 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-09-30 10:22:37,080 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-09-30 10:22:37,089 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-09-30 10:22:37,091 INFO L271 PluginConnector]: Initializing Boogie PL CUP Parser... [2018-09-30 10:22:37,092 INFO L276 PluginConnector]: Boogie PL CUP Parser initialized [2018-09-30 10:22:37,092 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-09-30 10:22:37,093 INFO L111 BoogieParser]: Parsing: '/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/20170304-DifficultPathPrograms/count_by_k.i_3.bpl' [2018-09-30 10:22:37,143 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-09-30 10:22:37,146 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-09-30 10:22:37,147 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2018-09-30 10:22:37,147 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2018-09-30 10:22:37,148 INFO L276 PluginConnector]: Boogie Procedure Inliner initialized [2018-09-30 10:22:37,168 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 30.09 10:22:37" (1/1) ... [2018-09-30 10:22:37,180 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 30.09 10:22:37" (1/1) ... [2018-09-30 10:22:37,187 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2018-09-30 10:22:37,188 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-09-30 10:22:37,188 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-09-30 10:22:37,188 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-09-30 10:22:37,198 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 30.09 10:22:37" (1/1) ... [2018-09-30 10:22:37,198 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 30.09 10:22:37" (1/1) ... [2018-09-30 10:22:37,199 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 30.09 10:22:37" (1/1) ... [2018-09-30 10:22:37,200 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 30.09 10:22:37" (1/1) ... [2018-09-30 10:22:37,202 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 30.09 10:22:37" (1/1) ... [2018-09-30 10:22:37,204 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 30.09 10:22:37" (1/1) ... [2018-09-30 10:22:37,205 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 30.09 10:22:37" (1/1) ... [2018-09-30 10:22:37,207 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-09-30 10:22:37,207 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-09-30 10:22:37,207 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-09-30 10:22:37,208 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-09-30 10:22:37,209 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 30.09 10:22:37" (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-09-30 10:22:37,282 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-09-30 10:22:37,282 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-09-30 10:22:37,519 INFO L348 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-09-30 10:22:37,520 INFO L202 PluginConnector]: Adding new model count_by_k.i_3.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 30.09 10:22:37 BoogieIcfgContainer [2018-09-30 10:22:37,520 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-09-30 10:22:37,521 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-09-30 10:22:37,521 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-09-30 10:22:37,525 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-09-30 10:22:37,525 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 30.09 10:22:37" (1/2) ... [2018-09-30 10:22:37,526 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@71a649e1 and model type count_by_k.i_3.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 30.09 10:22:37, skipping insertion in model container [2018-09-30 10:22:37,527 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 30.09 10:22:37" (2/2) ... [2018-09-30 10:22:37,530 INFO L112 eAbstractionObserver]: Analyzing ICFG count_by_k.i_3.bpl [2018-09-30 10:22:37,541 INFO L137 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-09-30 10:22:37,552 INFO L149 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-09-30 10:22:37,603 INFO L133 ementStrategyFactory]: Using default assertion order modulation [2018-09-30 10:22:37,604 INFO L381 AbstractCegarLoop]: Interprodecural is true [2018-09-30 10:22:37,604 INFO L382 AbstractCegarLoop]: Hoare is true [2018-09-30 10:22:37,604 INFO L383 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-09-30 10:22:37,605 INFO L384 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-09-30 10:22:37,605 INFO L385 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-09-30 10:22:37,605 INFO L386 AbstractCegarLoop]: Difference is false [2018-09-30 10:22:37,605 INFO L387 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-09-30 10:22:37,605 INFO L392 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-09-30 10:22:37,620 INFO L276 IsEmpty]: Start isEmpty. Operand 7 states. [2018-09-30 10:22:37,626 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 5 [2018-09-30 10:22:37,626 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:22:37,627 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1] [2018-09-30 10:22:37,629 INFO L423 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:22:37,639 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:22:37,640 INFO L82 PathProgramCache]: Analyzing trace with hash 925639, now seen corresponding path program 1 times [2018-09-30 10:22:37,642 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:22:37,644 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:22:37,690 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:37,691 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-30 10:22:37,691 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:37,730 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:22:37,832 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:22:37,834 INFO L313 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-09-30 10:22:37,834 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-09-30 10:22:37,838 INFO L459 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-09-30 10:22:37,849 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-09-30 10:22:37,850 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-09-30 10:22:37,852 INFO L87 Difference]: Start difference. First operand 7 states. Second operand 3 states. [2018-09-30 10:22:37,903 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:22:37,904 INFO L93 Difference]: Finished difference Result 11 states and 12 transitions. [2018-09-30 10:22:37,905 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-09-30 10:22:37,906 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 4 [2018-09-30 10:22:37,907 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:22:37,918 INFO L225 Difference]: With dead ends: 11 [2018-09-30 10:22:37,918 INFO L226 Difference]: Without dead ends: 7 [2018-09-30 10:22:37,925 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-09-30 10:22:37,957 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 7 states. [2018-09-30 10:22:37,983 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 7 to 7. [2018-09-30 10:22:37,985 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 7 states. [2018-09-30 10:22:37,986 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 7 transitions. [2018-09-30 10:22:37,988 INFO L78 Accepts]: Start accepts. Automaton has 7 states and 7 transitions. Word has length 4 [2018-09-30 10:22:37,989 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:22:37,989 INFO L480 AbstractCegarLoop]: Abstraction has 7 states and 7 transitions. [2018-09-30 10:22:37,989 INFO L481 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-09-30 10:22:37,990 INFO L276 IsEmpty]: Start isEmpty. Operand 7 states and 7 transitions. [2018-09-30 10:22:37,990 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2018-09-30 10:22:37,990 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:22:37,991 INFO L375 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1] [2018-09-30 10:22:37,991 INFO L423 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:22:37,991 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:22:37,992 INFO L82 PathProgramCache]: Analyzing trace with hash 889591169, now seen corresponding path program 1 times [2018-09-30 10:22:37,992 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:22:37,992 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:22:37,993 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:37,994 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-30 10:22:37,994 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:38,006 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:22:38,095 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:22:38,095 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:22:38,095 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-09-30 10:22:38,105 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-30 10:22:38,129 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:22:38,137 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:22:38,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-09-30 10:22:38,227 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:22:38,228 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [3, 3] total 4 [2018-09-30 10:22:38,228 INFO L459 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-09-30 10:22:38,229 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-09-30 10:22:38,229 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-09-30 10:22:38,229 INFO L87 Difference]: Start difference. First operand 7 states and 7 transitions. Second operand 5 states. [2018-09-30 10:22:38,281 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:22:38,281 INFO L93 Difference]: Finished difference Result 13 states and 14 transitions. [2018-09-30 10:22:38,281 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-09-30 10:22:38,281 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 6 [2018-09-30 10:22:38,282 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:22:38,282 INFO L225 Difference]: With dead ends: 13 [2018-09-30 10:22:38,282 INFO L226 Difference]: Without dead ends: 11 [2018-09-30 10:22:38,284 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-09-30 10:22:38,284 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 11 states. [2018-09-30 10:22:38,288 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-09-30 10:22:38,288 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 11 states. [2018-09-30 10:22:38,289 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-09-30 10:22:38,289 INFO L78 Accepts]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 6 [2018-09-30 10:22:38,289 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:22:38,289 INFO L480 AbstractCegarLoop]: Abstraction has 11 states and 11 transitions. [2018-09-30 10:22:38,289 INFO L481 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-09-30 10:22:38,290 INFO L276 IsEmpty]: Start isEmpty. Operand 11 states and 11 transitions. [2018-09-30 10:22:38,290 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2018-09-30 10:22:38,290 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:22:38,290 INFO L375 BasicCegarLoop]: trace histogram [4, 3, 1, 1, 1] [2018-09-30 10:22:38,291 INFO L423 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:22:38,291 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:22:38,291 INFO L82 PathProgramCache]: Analyzing trace with hash 1946815861, now seen corresponding path program 2 times [2018-09-30 10:22:38,291 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:22:38,292 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:22:38,293 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:38,293 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-30 10:22:38,293 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:38,309 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:22:38,451 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:22:38,452 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:22:38,452 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-09-30 10:22:38,469 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-09-30 10:22:38,483 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-09-30 10:22:38,484 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:22:38,486 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:22:38,554 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:22:38,583 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:22:38,584 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 6 [2018-09-30 10:22:38,584 INFO L459 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-09-30 10:22:38,584 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-09-30 10:22:38,585 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2018-09-30 10:22:38,585 INFO L87 Difference]: Start difference. First operand 11 states and 11 transitions. Second operand 7 states. [2018-09-30 10:22:38,754 WARN L178 SmtUtils]: Spent 103.00 ms on a formula simplification. DAG size of input: 9 DAG size of output: 8 [2018-09-30 10:22:39,087 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:22:39,087 INFO L93 Difference]: Finished difference Result 17 states and 18 transitions. [2018-09-30 10:22:39,088 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-09-30 10:22:39,088 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 10 [2018-09-30 10:22:39,088 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:22:39,089 INFO L225 Difference]: With dead ends: 17 [2018-09-30 10:22:39,089 INFO L226 Difference]: Without dead ends: 15 [2018-09-30 10:22:39,089 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=29, Invalid=61, Unknown=0, NotChecked=0, Total=90 [2018-09-30 10:22:39,090 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 15 states. [2018-09-30 10:22:39,094 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-09-30 10:22:39,095 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 15 states. [2018-09-30 10:22:39,095 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 15 transitions. [2018-09-30 10:22:39,096 INFO L78 Accepts]: Start accepts. Automaton has 15 states and 15 transitions. Word has length 10 [2018-09-30 10:22:39,096 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:22:39,096 INFO L480 AbstractCegarLoop]: Abstraction has 15 states and 15 transitions. [2018-09-30 10:22:39,096 INFO L481 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-09-30 10:22:39,097 INFO L276 IsEmpty]: Start isEmpty. Operand 15 states and 15 transitions. [2018-09-30 10:22:39,097 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2018-09-30 10:22:39,097 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:22:39,097 INFO L375 BasicCegarLoop]: trace histogram [6, 5, 1, 1, 1] [2018-09-30 10:22:39,098 INFO L423 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:22:39,098 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:22:39,098 INFO L82 PathProgramCache]: Analyzing trace with hash 531164009, now seen corresponding path program 3 times [2018-09-30 10:22:39,099 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:22:39,099 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:22:39,100 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:39,100 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:22:39,101 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:39,122 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:22:39,274 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 0 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:22:39,274 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:22:39,275 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-09-30 10:22:39,293 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-09-30 10:22:39,309 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2018-09-30 10:22:39,309 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:22:39,312 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:22:39,441 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 0 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:22:39,465 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:22:39,465 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 8 [2018-09-30 10:22:39,465 INFO L459 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-09-30 10:22:39,466 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-09-30 10:22:39,466 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=56, Unknown=0, NotChecked=0, Total=72 [2018-09-30 10:22:39,467 INFO L87 Difference]: Start difference. First operand 15 states and 15 transitions. Second operand 9 states. [2018-09-30 10:22:39,723 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:22:39,724 INFO L93 Difference]: Finished difference Result 21 states and 22 transitions. [2018-09-30 10:22:39,724 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-09-30 10:22:39,725 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 14 [2018-09-30 10:22:39,725 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:22:39,725 INFO L225 Difference]: With dead ends: 21 [2018-09-30 10:22:39,725 INFO L226 Difference]: Without dead ends: 19 [2018-09-30 10:22:39,726 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 25 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=55, Invalid=127, Unknown=0, NotChecked=0, Total=182 [2018-09-30 10:22:39,726 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2018-09-30 10:22:39,731 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-09-30 10:22:39,732 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 19 states. [2018-09-30 10:22:39,732 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 19 transitions. [2018-09-30 10:22:39,733 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 19 transitions. Word has length 14 [2018-09-30 10:22:39,733 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:22:39,733 INFO L480 AbstractCegarLoop]: Abstraction has 19 states and 19 transitions. [2018-09-30 10:22:39,733 INFO L481 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-09-30 10:22:39,734 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 19 transitions. [2018-09-30 10:22:39,734 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2018-09-30 10:22:39,734 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:22:39,734 INFO L375 BasicCegarLoop]: trace histogram [8, 7, 1, 1, 1] [2018-09-30 10:22:39,735 INFO L423 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:22:39,735 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:22:39,735 INFO L82 PathProgramCache]: Analyzing trace with hash 67088221, now seen corresponding path program 4 times [2018-09-30 10:22:39,735 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:22:39,736 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:22:39,736 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:39,737 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:22:39,737 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:39,765 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:22:40,505 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 0 proven. 56 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:22:40,506 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:22:40,506 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-09-30 10:22:40,522 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-09-30 10:22:40,539 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-09-30 10:22:40,540 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:22:40,543 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:22:40,616 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 0 proven. 56 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:22:40,637 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:22:40,637 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 10 [2018-09-30 10:22:40,638 INFO L459 AbstractCegarLoop]: Interpolant automaton has 11 states [2018-09-30 10:22:40,638 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2018-09-30 10:22:40,638 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=90, Unknown=0, NotChecked=0, Total=110 [2018-09-30 10:22:40,639 INFO L87 Difference]: Start difference. First operand 19 states and 19 transitions. Second operand 11 states. [2018-09-30 10:22:40,915 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:22:40,915 INFO L93 Difference]: Finished difference Result 25 states and 26 transitions. [2018-09-30 10:22:40,917 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-09-30 10:22:40,917 INFO L78 Accepts]: Start accepts. Automaton has 11 states. Word has length 18 [2018-09-30 10:22:40,918 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:22:40,918 INFO L225 Difference]: With dead ends: 25 [2018-09-30 10:22:40,918 INFO L226 Difference]: Without dead ends: 23 [2018-09-30 10:22:40,919 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=89, Invalid=217, Unknown=0, NotChecked=0, Total=306 [2018-09-30 10:22:40,919 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2018-09-30 10:22:40,924 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-09-30 10:22:40,925 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 23 states. [2018-09-30 10:22:40,925 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 23 transitions. [2018-09-30 10:22:40,926 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 23 transitions. Word has length 18 [2018-09-30 10:22:40,926 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:22:40,926 INFO L480 AbstractCegarLoop]: Abstraction has 23 states and 23 transitions. [2018-09-30 10:22:40,926 INFO L481 AbstractCegarLoop]: Interpolant automaton has 11 states. [2018-09-30 10:22:40,927 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 23 transitions. [2018-09-30 10:22:40,927 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2018-09-30 10:22:40,927 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:22:40,928 INFO L375 BasicCegarLoop]: trace histogram [10, 9, 1, 1, 1] [2018-09-30 10:22:40,928 INFO L423 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:22:40,928 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:22:40,928 INFO L82 PathProgramCache]: Analyzing trace with hash -1767155375, now seen corresponding path program 5 times [2018-09-30 10:22:40,929 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:22:40,929 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:22:40,930 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:40,930 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:22:40,930 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:40,950 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:22:41,413 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 0 proven. 90 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:22:41,414 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:22:41,414 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-09-30 10:22:41,433 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-09-30 10:22:41,471 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 10 check-sat command(s) [2018-09-30 10:22:41,471 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:22:41,473 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:22:41,526 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 0 proven. 90 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:22:41,547 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:22:41,548 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 12 [2018-09-30 10:22:41,548 INFO L459 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-09-30 10:22:41,549 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-09-30 10:22:41,549 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=132, Unknown=0, NotChecked=0, Total=156 [2018-09-30 10:22:41,549 INFO L87 Difference]: Start difference. First operand 23 states and 23 transitions. Second operand 13 states. [2018-09-30 10:22:42,023 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:22:42,024 INFO L93 Difference]: Finished difference Result 29 states and 30 transitions. [2018-09-30 10:22:42,024 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-09-30 10:22:42,024 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 22 [2018-09-30 10:22:42,025 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:22:42,026 INFO L225 Difference]: With dead ends: 29 [2018-09-30 10:22:42,027 INFO L226 Difference]: Without dead ends: 27 [2018-09-30 10:22:42,028 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 37 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=131, Invalid=331, Unknown=0, NotChecked=0, Total=462 [2018-09-30 10:22:42,028 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2018-09-30 10:22:42,033 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2018-09-30 10:22:42,034 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 27 states. [2018-09-30 10:22:42,034 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 27 transitions. [2018-09-30 10:22:42,035 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 27 transitions. Word has length 22 [2018-09-30 10:22:42,035 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:22:42,035 INFO L480 AbstractCegarLoop]: Abstraction has 27 states and 27 transitions. [2018-09-30 10:22:42,035 INFO L481 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-09-30 10:22:42,035 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 27 transitions. [2018-09-30 10:22:42,036 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2018-09-30 10:22:42,036 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:22:42,036 INFO L375 BasicCegarLoop]: trace histogram [12, 11, 1, 1, 1] [2018-09-30 10:22:42,037 INFO L423 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:22:42,037 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:22:42,037 INFO L82 PathProgramCache]: Analyzing trace with hash 919136581, now seen corresponding path program 6 times [2018-09-30 10:22:42,037 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:22:42,038 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:22:42,039 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:42,039 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:22:42,039 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:42,058 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:22:42,294 INFO L134 CoverageAnalysis]: Checked inductivity of 132 backedges. 0 proven. 132 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:22:42,295 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:22:42,295 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-09-30 10:22:42,308 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-09-30 10:22:42,323 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 12 check-sat command(s) [2018-09-30 10:22:42,323 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:22:42,325 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:22:42,382 INFO L134 CoverageAnalysis]: Checked inductivity of 132 backedges. 0 proven. 132 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:22:42,403 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:22:42,403 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 14 [2018-09-30 10:22:42,403 INFO L459 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-09-30 10:22:42,404 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-09-30 10:22:42,404 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=182, Unknown=0, NotChecked=0, Total=210 [2018-09-30 10:22:42,404 INFO L87 Difference]: Start difference. First operand 27 states and 27 transitions. Second operand 15 states. [2018-09-30 10:22:43,065 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:22:43,065 INFO L93 Difference]: Finished difference Result 33 states and 34 transitions. [2018-09-30 10:22:43,066 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-09-30 10:22:43,067 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 26 [2018-09-30 10:22:43,067 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:22:43,068 INFO L225 Difference]: With dead ends: 33 [2018-09-30 10:22:43,068 INFO L226 Difference]: Without dead ends: 31 [2018-09-30 10:22:43,069 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 56 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=181, Invalid=469, Unknown=0, NotChecked=0, Total=650 [2018-09-30 10:22:43,069 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2018-09-30 10:22:43,076 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2018-09-30 10:22:43,076 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 31 states. [2018-09-30 10:22:43,077 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 31 transitions. [2018-09-30 10:22:43,077 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 31 transitions. Word has length 26 [2018-09-30 10:22:43,077 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:22:43,078 INFO L480 AbstractCegarLoop]: Abstraction has 31 states and 31 transitions. [2018-09-30 10:22:43,078 INFO L481 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-09-30 10:22:43,078 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 31 transitions. [2018-09-30 10:22:43,079 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2018-09-30 10:22:43,079 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:22:43,079 INFO L375 BasicCegarLoop]: trace histogram [14, 13, 1, 1, 1] [2018-09-30 10:22:43,080 INFO L423 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:22:43,080 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:22:43,080 INFO L82 PathProgramCache]: Analyzing trace with hash 1828020025, now seen corresponding path program 7 times [2018-09-30 10:22:43,080 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:22:43,080 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:22:43,081 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:43,081 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:22:43,081 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:43,121 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:22:43,630 INFO L134 CoverageAnalysis]: Checked inductivity of 182 backedges. 0 proven. 182 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:22:43,630 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:22:43,630 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-09-30 10:22:43,643 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-30 10:22:43,659 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:22:43,664 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:22:43,715 INFO L134 CoverageAnalysis]: Checked inductivity of 182 backedges. 0 proven. 182 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:22:43,735 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:22:43,736 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 16 [2018-09-30 10:22:43,736 INFO L459 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-09-30 10:22:43,736 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-09-30 10:22:43,737 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=240, Unknown=0, NotChecked=0, Total=272 [2018-09-30 10:22:43,737 INFO L87 Difference]: Start difference. First operand 31 states and 31 transitions. Second operand 17 states. [2018-09-30 10:22:44,538 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:22:44,538 INFO L93 Difference]: Finished difference Result 37 states and 38 transitions. [2018-09-30 10:22:44,540 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-09-30 10:22:44,540 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 30 [2018-09-30 10:22:44,541 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:22:44,541 INFO L225 Difference]: With dead ends: 37 [2018-09-30 10:22:44,541 INFO L226 Difference]: Without dead ends: 35 [2018-09-30 10:22:44,542 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 79 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=239, Invalid=631, Unknown=0, NotChecked=0, Total=870 [2018-09-30 10:22:44,542 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2018-09-30 10:22:44,548 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 35. [2018-09-30 10:22:44,549 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 35 states. [2018-09-30 10:22:44,549 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 35 transitions. [2018-09-30 10:22:44,550 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 35 transitions. Word has length 30 [2018-09-30 10:22:44,550 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:22:44,550 INFO L480 AbstractCegarLoop]: Abstraction has 35 states and 35 transitions. [2018-09-30 10:22:44,550 INFO L481 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-09-30 10:22:44,551 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 35 transitions. [2018-09-30 10:22:44,551 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2018-09-30 10:22:44,552 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:22:44,552 INFO L375 BasicCegarLoop]: trace histogram [16, 15, 1, 1, 1] [2018-09-30 10:22:44,552 INFO L423 AbstractCegarLoop]: === Iteration 9 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:22:44,552 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:22:44,553 INFO L82 PathProgramCache]: Analyzing trace with hash 726514477, now seen corresponding path program 8 times [2018-09-30 10:22:44,553 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:22:44,553 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:22:44,554 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:44,554 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-30 10:22:44,554 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:44,574 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:22:44,878 INFO L134 CoverageAnalysis]: Checked inductivity of 240 backedges. 0 proven. 240 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:22:44,878 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:22:44,879 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-09-30 10:22:44,896 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-09-30 10:22:44,930 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-09-30 10:22:44,930 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:22:44,936 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:22:44,992 INFO L134 CoverageAnalysis]: Checked inductivity of 240 backedges. 0 proven. 240 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:22:45,013 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:22:45,014 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17] total 18 [2018-09-30 10:22:45,014 INFO L459 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-09-30 10:22:45,015 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-09-30 10:22:45,015 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=306, Unknown=0, NotChecked=0, Total=342 [2018-09-30 10:22:45,015 INFO L87 Difference]: Start difference. First operand 35 states and 35 transitions. Second operand 19 states. [2018-09-30 10:22:45,240 WARN L178 SmtUtils]: Spent 109.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 9 [2018-09-30 10:22:45,917 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:22:45,918 INFO L93 Difference]: Finished difference Result 41 states and 42 transitions. [2018-09-30 10:22:45,922 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-09-30 10:22:45,922 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 34 [2018-09-30 10:22:45,923 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:22:45,923 INFO L225 Difference]: With dead ends: 41 [2018-09-30 10:22:45,923 INFO L226 Difference]: Without dead ends: 39 [2018-09-30 10:22:45,924 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 106 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=305, Invalid=817, Unknown=0, NotChecked=0, Total=1122 [2018-09-30 10:22:45,925 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2018-09-30 10:22:45,930 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 39. [2018-09-30 10:22:45,931 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 39 states. [2018-09-30 10:22:45,931 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 39 transitions. [2018-09-30 10:22:45,932 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 39 transitions. Word has length 34 [2018-09-30 10:22:45,932 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:22:45,932 INFO L480 AbstractCegarLoop]: Abstraction has 39 states and 39 transitions. [2018-09-30 10:22:45,932 INFO L481 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-09-30 10:22:45,932 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 39 transitions. [2018-09-30 10:22:45,933 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2018-09-30 10:22:45,933 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:22:45,934 INFO L375 BasicCegarLoop]: trace histogram [18, 17, 1, 1, 1] [2018-09-30 10:22:45,934 INFO L423 AbstractCegarLoop]: === Iteration 10 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:22:45,934 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:22:45,934 INFO L82 PathProgramCache]: Analyzing trace with hash 225377569, now seen corresponding path program 9 times [2018-09-30 10:22:45,934 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:22:45,935 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:22:45,935 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:45,935 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:22:45,936 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:45,955 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:22:46,298 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 0 proven. 306 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:22:46,299 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:22:46,299 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-09-30 10:22:46,308 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-09-30 10:22:46,343 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 18 check-sat command(s) [2018-09-30 10:22:46,343 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:22:46,346 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:22:46,482 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 0 proven. 306 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:22:46,502 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:22:46,503 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19] total 20 [2018-09-30 10:22:46,504 INFO L459 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-09-30 10:22:46,504 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-09-30 10:22:46,505 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=380, Unknown=0, NotChecked=0, Total=420 [2018-09-30 10:22:46,506 INFO L87 Difference]: Start difference. First operand 39 states and 39 transitions. Second operand 21 states. [2018-09-30 10:22:46,954 WARN L178 SmtUtils]: Spent 236.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 11 [2018-09-30 10:22:47,630 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:22:47,630 INFO L93 Difference]: Finished difference Result 45 states and 46 transitions. [2018-09-30 10:22:47,631 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-09-30 10:22:47,631 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 38 [2018-09-30 10:22:47,632 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:22:47,632 INFO L225 Difference]: With dead ends: 45 [2018-09-30 10:22:47,632 INFO L226 Difference]: Without dead ends: 43 [2018-09-30 10:22:47,634 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 37 SyntacticMatches, 0 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 137 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=379, Invalid=1027, Unknown=0, NotChecked=0, Total=1406 [2018-09-30 10:22:47,634 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2018-09-30 10:22:47,641 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2018-09-30 10:22:47,641 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 43 states. [2018-09-30 10:22:47,642 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 43 transitions. [2018-09-30 10:22:47,642 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 43 transitions. Word has length 38 [2018-09-30 10:22:47,642 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:22:47,642 INFO L480 AbstractCegarLoop]: Abstraction has 43 states and 43 transitions. [2018-09-30 10:22:47,642 INFO L481 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-09-30 10:22:47,643 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 43 transitions. [2018-09-30 10:22:47,644 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2018-09-30 10:22:47,644 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:22:47,644 INFO L375 BasicCegarLoop]: trace histogram [20, 19, 1, 1, 1] [2018-09-30 10:22:47,644 INFO L423 AbstractCegarLoop]: === Iteration 11 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:22:47,644 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:22:47,645 INFO L82 PathProgramCache]: Analyzing trace with hash -1737087723, now seen corresponding path program 10 times [2018-09-30 10:22:47,645 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:22:47,645 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:22:47,646 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:47,646 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:22:47,646 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:47,666 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:22:47,971 INFO L134 CoverageAnalysis]: Checked inductivity of 380 backedges. 0 proven. 380 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:22:47,972 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:22:47,972 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-09-30 10:22:47,980 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-09-30 10:22:47,995 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-09-30 10:22:47,995 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:22:47,998 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:22:48,098 INFO L134 CoverageAnalysis]: Checked inductivity of 380 backedges. 0 proven. 380 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:22:48,119 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:22:48,119 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21] total 22 [2018-09-30 10:22:48,119 INFO L459 AbstractCegarLoop]: Interpolant automaton has 23 states [2018-09-30 10:22:48,120 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2018-09-30 10:22:48,120 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=462, Unknown=0, NotChecked=0, Total=506 [2018-09-30 10:22:48,120 INFO L87 Difference]: Start difference. First operand 43 states and 43 transitions. Second operand 23 states. [2018-09-30 10:22:49,332 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:22:49,332 INFO L93 Difference]: Finished difference Result 49 states and 50 transitions. [2018-09-30 10:22:49,333 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-09-30 10:22:49,333 INFO L78 Accepts]: Start accepts. Automaton has 23 states. Word has length 42 [2018-09-30 10:22:49,333 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:22:49,334 INFO L225 Difference]: With dead ends: 49 [2018-09-30 10:22:49,334 INFO L226 Difference]: Without dead ends: 47 [2018-09-30 10:22:49,335 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 41 SyntacticMatches, 0 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 172 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=461, Invalid=1261, Unknown=0, NotChecked=0, Total=1722 [2018-09-30 10:22:49,335 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2018-09-30 10:22:49,343 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2018-09-30 10:22:49,343 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 47 states. [2018-09-30 10:22:49,344 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 47 transitions. [2018-09-30 10:22:49,344 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 47 transitions. Word has length 42 [2018-09-30 10:22:49,344 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:22:49,344 INFO L480 AbstractCegarLoop]: Abstraction has 47 states and 47 transitions. [2018-09-30 10:22:49,344 INFO L481 AbstractCegarLoop]: Interpolant automaton has 23 states. [2018-09-30 10:22:49,345 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 47 transitions. [2018-09-30 10:22:49,345 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2018-09-30 10:22:49,345 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:22:49,346 INFO L375 BasicCegarLoop]: trace histogram [22, 21, 1, 1, 1] [2018-09-30 10:22:49,346 INFO L423 AbstractCegarLoop]: === Iteration 12 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:22:49,346 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:22:49,346 INFO L82 PathProgramCache]: Analyzing trace with hash 2063610633, now seen corresponding path program 11 times [2018-09-30 10:22:49,346 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:22:49,347 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:22:49,347 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:49,348 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:22:49,348 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:49,376 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:22:49,771 INFO L134 CoverageAnalysis]: Checked inductivity of 462 backedges. 0 proven. 462 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:22:49,772 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:22:49,772 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-09-30 10:22:49,793 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-09-30 10:22:49,834 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 22 check-sat command(s) [2018-09-30 10:22:49,835 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:22:49,840 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:22:49,895 INFO L134 CoverageAnalysis]: Checked inductivity of 462 backedges. 0 proven. 462 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:22:49,915 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:22:49,916 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 23] total 24 [2018-09-30 10:22:49,916 INFO L459 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-09-30 10:22:49,916 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-09-30 10:22:49,917 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=552, Unknown=0, NotChecked=0, Total=600 [2018-09-30 10:22:49,917 INFO L87 Difference]: Start difference. First operand 47 states and 47 transitions. Second operand 25 states. [2018-09-30 10:22:50,386 WARN L178 SmtUtils]: Spent 301.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 11 [2018-09-30 10:22:50,869 WARN L178 SmtUtils]: Spent 360.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 11 [2018-09-30 10:22:51,814 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:22:51,815 INFO L93 Difference]: Finished difference Result 53 states and 54 transitions. [2018-09-30 10:22:51,816 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2018-09-30 10:22:51,816 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 46 [2018-09-30 10:22:51,816 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:22:51,817 INFO L225 Difference]: With dead ends: 53 [2018-09-30 10:22:51,817 INFO L226 Difference]: Without dead ends: 51 [2018-09-30 10:22:51,818 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 89 GetRequests, 45 SyntacticMatches, 0 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 211 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=551, Invalid=1519, Unknown=0, NotChecked=0, Total=2070 [2018-09-30 10:22:51,818 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2018-09-30 10:22:51,824 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2018-09-30 10:22:51,825 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 51 states. [2018-09-30 10:22:51,825 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 51 transitions. [2018-09-30 10:22:51,825 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 51 transitions. Word has length 46 [2018-09-30 10:22:51,826 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:22:51,826 INFO L480 AbstractCegarLoop]: Abstraction has 51 states and 51 transitions. [2018-09-30 10:22:51,826 INFO L481 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-09-30 10:22:51,826 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 51 transitions. [2018-09-30 10:22:51,827 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2018-09-30 10:22:51,827 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:22:51,827 INFO L375 BasicCegarLoop]: trace histogram [24, 23, 1, 1, 1] [2018-09-30 10:22:51,827 INFO L423 AbstractCegarLoop]: === Iteration 13 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:22:51,827 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:22:51,827 INFO L82 PathProgramCache]: Analyzing trace with hash -852875523, now seen corresponding path program 12 times [2018-09-30 10:22:51,828 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:22:51,828 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:22:51,829 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:51,829 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:22:51,829 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:51,853 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:22:52,259 INFO L134 CoverageAnalysis]: Checked inductivity of 552 backedges. 0 proven. 552 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:22:52,259 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:22:52,259 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-09-30 10:22:52,266 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-09-30 10:22:52,294 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 24 check-sat command(s) [2018-09-30 10:22:52,294 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:22:52,297 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:22:52,370 INFO L134 CoverageAnalysis]: Checked inductivity of 552 backedges. 0 proven. 552 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:22:52,391 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:22:52,391 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 25] total 26 [2018-09-30 10:22:52,392 INFO L459 AbstractCegarLoop]: Interpolant automaton has 27 states [2018-09-30 10:22:52,392 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2018-09-30 10:22:52,392 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=650, Unknown=0, NotChecked=0, Total=702 [2018-09-30 10:22:52,393 INFO L87 Difference]: Start difference. First operand 51 states and 51 transitions. Second operand 27 states. [2018-09-30 10:22:53,810 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:22:53,810 INFO L93 Difference]: Finished difference Result 57 states and 58 transitions. [2018-09-30 10:22:53,810 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2018-09-30 10:22:53,810 INFO L78 Accepts]: Start accepts. Automaton has 27 states. Word has length 50 [2018-09-30 10:22:53,811 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:22:53,811 INFO L225 Difference]: With dead ends: 57 [2018-09-30 10:22:53,811 INFO L226 Difference]: Without dead ends: 55 [2018-09-30 10:22:53,812 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 97 GetRequests, 49 SyntacticMatches, 0 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 254 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=649, Invalid=1801, Unknown=0, NotChecked=0, Total=2450 [2018-09-30 10:22:53,812 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2018-09-30 10:22:53,819 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2018-09-30 10:22:53,819 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 55 states. [2018-09-30 10:22:53,820 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 55 transitions. [2018-09-30 10:22:53,820 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 55 transitions. Word has length 50 [2018-09-30 10:22:53,820 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:22:53,820 INFO L480 AbstractCegarLoop]: Abstraction has 55 states and 55 transitions. [2018-09-30 10:22:53,820 INFO L481 AbstractCegarLoop]: Interpolant automaton has 27 states. [2018-09-30 10:22:53,821 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 55 transitions. [2018-09-30 10:22:53,821 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2018-09-30 10:22:53,821 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:22:53,821 INFO L375 BasicCegarLoop]: trace histogram [26, 25, 1, 1, 1] [2018-09-30 10:22:53,822 INFO L423 AbstractCegarLoop]: === Iteration 14 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:22:53,822 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:22:53,822 INFO L82 PathProgramCache]: Analyzing trace with hash 1351680241, now seen corresponding path program 13 times [2018-09-30 10:22:53,822 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:22:53,822 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:22:53,823 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:53,823 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:22:53,823 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:53,853 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:22:54,756 INFO L134 CoverageAnalysis]: Checked inductivity of 650 backedges. 0 proven. 650 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:22:54,757 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:22:54,757 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-09-30 10:22:54,766 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-30 10:22:54,806 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:22:54,823 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:22:54,944 INFO L134 CoverageAnalysis]: Checked inductivity of 650 backedges. 0 proven. 650 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:22:54,964 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:22:54,965 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [27, 27] total 28 [2018-09-30 10:22:54,965 INFO L459 AbstractCegarLoop]: Interpolant automaton has 29 states [2018-09-30 10:22:54,966 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2018-09-30 10:22:54,966 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=56, Invalid=756, Unknown=0, NotChecked=0, Total=812 [2018-09-30 10:22:54,966 INFO L87 Difference]: Start difference. First operand 55 states and 55 transitions. Second operand 29 states. [2018-09-30 10:22:55,300 WARN L178 SmtUtils]: Spent 168.00 ms on a formula simplification. DAG size of input: 80 DAG size of output: 11 [2018-09-30 10:22:56,545 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:22:56,545 INFO L93 Difference]: Finished difference Result 61 states and 62 transitions. [2018-09-30 10:22:56,545 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2018-09-30 10:22:56,546 INFO L78 Accepts]: Start accepts. Automaton has 29 states. Word has length 54 [2018-09-30 10:22:56,546 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:22:56,547 INFO L225 Difference]: With dead ends: 61 [2018-09-30 10:22:56,547 INFO L226 Difference]: Without dead ends: 59 [2018-09-30 10:22:56,549 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 53 SyntacticMatches, 0 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 301 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=755, Invalid=2107, Unknown=0, NotChecked=0, Total=2862 [2018-09-30 10:22:56,549 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2018-09-30 10:22:56,555 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 59. [2018-09-30 10:22:56,555 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 59 states. [2018-09-30 10:22:56,556 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 59 transitions. [2018-09-30 10:22:56,556 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 59 transitions. Word has length 54 [2018-09-30 10:22:56,557 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:22:56,557 INFO L480 AbstractCegarLoop]: Abstraction has 59 states and 59 transitions. [2018-09-30 10:22:56,557 INFO L481 AbstractCegarLoop]: Interpolant automaton has 29 states. [2018-09-30 10:22:56,557 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 59 transitions. [2018-09-30 10:22:56,558 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2018-09-30 10:22:56,558 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:22:56,558 INFO L375 BasicCegarLoop]: trace histogram [28, 27, 1, 1, 1] [2018-09-30 10:22:56,558 INFO L423 AbstractCegarLoop]: === Iteration 15 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:22:56,558 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:22:56,559 INFO L82 PathProgramCache]: Analyzing trace with hash -1336819483, now seen corresponding path program 14 times [2018-09-30 10:22:56,559 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:22:56,559 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:22:56,560 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:56,560 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-30 10:22:56,560 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:56,594 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:22:57,075 INFO L134 CoverageAnalysis]: Checked inductivity of 756 backedges. 0 proven. 756 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:22:57,075 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:22:57,075 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-09-30 10:22:57,083 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-09-30 10:22:57,131 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-09-30 10:22:57,131 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:22:57,153 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:22:57,303 INFO L134 CoverageAnalysis]: Checked inductivity of 756 backedges. 0 proven. 756 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:22:57,326 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:22:57,326 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [29, 29] total 30 [2018-09-30 10:22:57,327 INFO L459 AbstractCegarLoop]: Interpolant automaton has 31 states [2018-09-30 10:22:57,327 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2018-09-30 10:22:57,327 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=870, Unknown=0, NotChecked=0, Total=930 [2018-09-30 10:22:57,327 INFO L87 Difference]: Start difference. First operand 59 states and 59 transitions. Second operand 31 states. [2018-09-30 10:22:58,518 WARN L178 SmtUtils]: Spent 211.00 ms on a formula simplification. DAG size of input: 59 DAG size of output: 11 [2018-09-30 10:22:59,867 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:22:59,867 INFO L93 Difference]: Finished difference Result 65 states and 66 transitions. [2018-09-30 10:22:59,868 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2018-09-30 10:22:59,868 INFO L78 Accepts]: Start accepts. Automaton has 31 states. Word has length 58 [2018-09-30 10:22:59,868 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:22:59,869 INFO L225 Difference]: With dead ends: 65 [2018-09-30 10:22:59,869 INFO L226 Difference]: Without dead ends: 63 [2018-09-30 10:22:59,871 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 113 GetRequests, 57 SyntacticMatches, 0 SemanticMatches, 56 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 352 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=869, Invalid=2437, Unknown=0, NotChecked=0, Total=3306 [2018-09-30 10:22:59,872 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2018-09-30 10:22:59,878 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 63. [2018-09-30 10:22:59,879 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 63 states. [2018-09-30 10:22:59,879 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 63 transitions. [2018-09-30 10:22:59,880 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 63 transitions. Word has length 58 [2018-09-30 10:22:59,880 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:22:59,880 INFO L480 AbstractCegarLoop]: Abstraction has 63 states and 63 transitions. [2018-09-30 10:22:59,880 INFO L481 AbstractCegarLoop]: Interpolant automaton has 31 states. [2018-09-30 10:22:59,880 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 63 transitions. [2018-09-30 10:22:59,881 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2018-09-30 10:22:59,881 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:22:59,881 INFO L375 BasicCegarLoop]: trace histogram [30, 29, 1, 1, 1] [2018-09-30 10:22:59,882 INFO L423 AbstractCegarLoop]: === Iteration 16 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:22:59,882 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:22:59,882 INFO L82 PathProgramCache]: Analyzing trace with hash -1056348455, now seen corresponding path program 15 times [2018-09-30 10:22:59,882 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:22:59,882 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:22:59,883 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:59,883 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:22:59,883 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:22:59,923 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:23:00,843 INFO L134 CoverageAnalysis]: Checked inductivity of 870 backedges. 0 proven. 870 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:23:00,843 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:23:00,843 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-09-30 10:23:00,852 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-09-30 10:23:00,882 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 30 check-sat command(s) [2018-09-30 10:23:00,882 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:23:00,887 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:23:00,982 INFO L134 CoverageAnalysis]: Checked inductivity of 870 backedges. 0 proven. 870 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:23:01,008 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:23:01,009 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [31, 31] total 32 [2018-09-30 10:23:01,009 INFO L459 AbstractCegarLoop]: Interpolant automaton has 33 states [2018-09-30 10:23:01,009 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2018-09-30 10:23:01,010 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=992, Unknown=0, NotChecked=0, Total=1056 [2018-09-30 10:23:01,010 INFO L87 Difference]: Start difference. First operand 63 states and 63 transitions. Second operand 33 states. [2018-09-30 10:23:03,191 WARN L178 SmtUtils]: Spent 249.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 11 [2018-09-30 10:23:03,713 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:23:03,713 INFO L93 Difference]: Finished difference Result 69 states and 70 transitions. [2018-09-30 10:23:03,713 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-09-30 10:23:03,714 INFO L78 Accepts]: Start accepts. Automaton has 33 states. Word has length 62 [2018-09-30 10:23:03,714 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:23:03,714 INFO L225 Difference]: With dead ends: 69 [2018-09-30 10:23:03,715 INFO L226 Difference]: Without dead ends: 67 [2018-09-30 10:23:03,717 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 121 GetRequests, 61 SyntacticMatches, 0 SemanticMatches, 60 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 407 ImplicationChecksByTransitivity, 3.4s TimeCoverageRelationStatistics Valid=991, Invalid=2791, Unknown=0, NotChecked=0, Total=3782 [2018-09-30 10:23:03,717 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2018-09-30 10:23:03,723 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 67. [2018-09-30 10:23:03,723 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 67 states. [2018-09-30 10:23:03,724 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 67 transitions. [2018-09-30 10:23:03,724 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 67 transitions. Word has length 62 [2018-09-30 10:23:03,725 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:23:03,725 INFO L480 AbstractCegarLoop]: Abstraction has 67 states and 67 transitions. [2018-09-30 10:23:03,725 INFO L481 AbstractCegarLoop]: Interpolant automaton has 33 states. [2018-09-30 10:23:03,725 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 67 transitions. [2018-09-30 10:23:03,726 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2018-09-30 10:23:03,726 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:23:03,726 INFO L375 BasicCegarLoop]: trace histogram [32, 31, 1, 1, 1] [2018-09-30 10:23:03,726 INFO L423 AbstractCegarLoop]: === Iteration 17 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:23:03,726 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:23:03,727 INFO L82 PathProgramCache]: Analyzing trace with hash -1059786035, now seen corresponding path program 16 times [2018-09-30 10:23:03,727 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:23:03,727 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:23:03,728 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:23:03,728 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:23:03,728 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:23:03,775 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:23:05,179 INFO L134 CoverageAnalysis]: Checked inductivity of 992 backedges. 0 proven. 992 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:23:05,179 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:23:05,179 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-09-30 10:23:05,187 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-09-30 10:23:05,272 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-09-30 10:23:05,272 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:23:05,303 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:23:05,386 INFO L134 CoverageAnalysis]: Checked inductivity of 992 backedges. 0 proven. 992 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:23:05,409 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:23:05,409 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [33, 33] total 34 [2018-09-30 10:23:05,409 INFO L459 AbstractCegarLoop]: Interpolant automaton has 35 states [2018-09-30 10:23:05,410 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2018-09-30 10:23:05,410 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=1122, Unknown=0, NotChecked=0, Total=1190 [2018-09-30 10:23:05,410 INFO L87 Difference]: Start difference. First operand 67 states and 67 transitions. Second operand 35 states. [2018-09-30 10:23:07,522 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:23:07,522 INFO L93 Difference]: Finished difference Result 73 states and 74 transitions. [2018-09-30 10:23:07,522 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2018-09-30 10:23:07,523 INFO L78 Accepts]: Start accepts. Automaton has 35 states. Word has length 66 [2018-09-30 10:23:07,523 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:23:07,524 INFO L225 Difference]: With dead ends: 73 [2018-09-30 10:23:07,524 INFO L226 Difference]: Without dead ends: 71 [2018-09-30 10:23:07,526 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 65 SyntacticMatches, 0 SemanticMatches, 64 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 466 ImplicationChecksByTransitivity, 3.4s TimeCoverageRelationStatistics Valid=1121, Invalid=3169, Unknown=0, NotChecked=0, Total=4290 [2018-09-30 10:23:07,526 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2018-09-30 10:23:07,533 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 71. [2018-09-30 10:23:07,533 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 71 states. [2018-09-30 10:23:07,534 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 71 transitions. [2018-09-30 10:23:07,534 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 71 transitions. Word has length 66 [2018-09-30 10:23:07,534 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:23:07,534 INFO L480 AbstractCegarLoop]: Abstraction has 71 states and 71 transitions. [2018-09-30 10:23:07,534 INFO L481 AbstractCegarLoop]: Interpolant automaton has 35 states. [2018-09-30 10:23:07,535 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 71 transitions. [2018-09-30 10:23:07,535 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2018-09-30 10:23:07,536 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:23:07,536 INFO L375 BasicCegarLoop]: trace histogram [34, 33, 1, 1, 1] [2018-09-30 10:23:07,536 INFO L423 AbstractCegarLoop]: === Iteration 18 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:23:07,536 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:23:07,536 INFO L82 PathProgramCache]: Analyzing trace with hash -1756273471, now seen corresponding path program 17 times [2018-09-30 10:23:07,536 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:23:07,536 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:23:07,537 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:23:07,537 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:23:07,538 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:23:07,588 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:23:08,304 INFO L134 CoverageAnalysis]: Checked inductivity of 1122 backedges. 0 proven. 1122 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:23:08,304 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:23:08,304 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-09-30 10:23:08,313 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-09-30 10:23:08,384 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 34 check-sat command(s) [2018-09-30 10:23:08,384 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:23:08,395 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:23:08,462 INFO L134 CoverageAnalysis]: Checked inductivity of 1122 backedges. 0 proven. 1122 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:23:08,483 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:23:08,483 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [35, 35] total 36 [2018-09-30 10:23:08,483 INFO L459 AbstractCegarLoop]: Interpolant automaton has 37 states [2018-09-30 10:23:08,483 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2018-09-30 10:23:08,484 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=72, Invalid=1260, Unknown=0, NotChecked=0, Total=1332 [2018-09-30 10:23:08,484 INFO L87 Difference]: Start difference. First operand 71 states and 71 transitions. Second operand 37 states. [2018-09-30 10:23:10,983 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:23:10,983 INFO L93 Difference]: Finished difference Result 77 states and 78 transitions. [2018-09-30 10:23:10,983 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 37 states. [2018-09-30 10:23:10,984 INFO L78 Accepts]: Start accepts. Automaton has 37 states. Word has length 70 [2018-09-30 10:23:10,984 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:23:10,985 INFO L225 Difference]: With dead ends: 77 [2018-09-30 10:23:10,985 INFO L226 Difference]: Without dead ends: 75 [2018-09-30 10:23:10,987 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 137 GetRequests, 69 SyntacticMatches, 0 SemanticMatches, 68 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 529 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=1259, Invalid=3571, Unknown=0, NotChecked=0, Total=4830 [2018-09-30 10:23:10,987 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 75 states. [2018-09-30 10:23:10,992 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 75 to 75. [2018-09-30 10:23:10,993 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 75 states. [2018-09-30 10:23:10,993 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 75 transitions. [2018-09-30 10:23:10,993 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 75 transitions. Word has length 70 [2018-09-30 10:23:10,994 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:23:10,994 INFO L480 AbstractCegarLoop]: Abstraction has 75 states and 75 transitions. [2018-09-30 10:23:10,994 INFO L481 AbstractCegarLoop]: Interpolant automaton has 37 states. [2018-09-30 10:23:10,994 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 75 transitions. [2018-09-30 10:23:10,995 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2018-09-30 10:23:10,995 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:23:10,995 INFO L375 BasicCegarLoop]: trace histogram [36, 35, 1, 1, 1] [2018-09-30 10:23:10,996 INFO L423 AbstractCegarLoop]: === Iteration 19 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:23:10,996 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:23:10,996 INFO L82 PathProgramCache]: Analyzing trace with hash 362527925, now seen corresponding path program 18 times [2018-09-30 10:23:10,996 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:23:10,996 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:23:10,997 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:23:10,997 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:23:10,997 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:23:11,055 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:23:11,778 INFO L134 CoverageAnalysis]: Checked inductivity of 1260 backedges. 0 proven. 1260 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:23:11,778 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:23:11,778 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-09-30 10:23:11,785 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-09-30 10:23:11,828 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 36 check-sat command(s) [2018-09-30 10:23:11,828 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:23:11,834 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:23:11,932 INFO L134 CoverageAnalysis]: Checked inductivity of 1260 backedges. 0 proven. 1260 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:23:11,953 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:23:11,953 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [37, 37] total 38 [2018-09-30 10:23:11,953 INFO L459 AbstractCegarLoop]: Interpolant automaton has 39 states [2018-09-30 10:23:11,954 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 39 interpolants. [2018-09-30 10:23:11,954 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=76, Invalid=1406, Unknown=0, NotChecked=0, Total=1482 [2018-09-30 10:23:11,954 INFO L87 Difference]: Start difference. First operand 75 states and 75 transitions. Second operand 39 states. [2018-09-30 10:23:14,908 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:23:14,908 INFO L93 Difference]: Finished difference Result 81 states and 82 transitions. [2018-09-30 10:23:14,908 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 39 states. [2018-09-30 10:23:14,908 INFO L78 Accepts]: Start accepts. Automaton has 39 states. Word has length 74 [2018-09-30 10:23:14,908 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:23:14,909 INFO L225 Difference]: With dead ends: 81 [2018-09-30 10:23:14,909 INFO L226 Difference]: Without dead ends: 79 [2018-09-30 10:23:14,911 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 145 GetRequests, 73 SyntacticMatches, 0 SemanticMatches, 72 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 596 ImplicationChecksByTransitivity, 3.5s TimeCoverageRelationStatistics Valid=1405, Invalid=3997, Unknown=0, NotChecked=0, Total=5402 [2018-09-30 10:23:14,912 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 79 states. [2018-09-30 10:23:14,918 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 79 to 79. [2018-09-30 10:23:14,918 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 79 states. [2018-09-30 10:23:14,919 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 79 transitions. [2018-09-30 10:23:14,919 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 79 transitions. Word has length 74 [2018-09-30 10:23:14,919 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:23:14,919 INFO L480 AbstractCegarLoop]: Abstraction has 79 states and 79 transitions. [2018-09-30 10:23:14,919 INFO L481 AbstractCegarLoop]: Interpolant automaton has 39 states. [2018-09-30 10:23:14,920 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 79 transitions. [2018-09-30 10:23:14,920 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2018-09-30 10:23:14,921 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:23:14,921 INFO L375 BasicCegarLoop]: trace histogram [38, 37, 1, 1, 1] [2018-09-30 10:23:14,921 INFO L423 AbstractCegarLoop]: === Iteration 20 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:23:14,921 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:23:14,921 INFO L82 PathProgramCache]: Analyzing trace with hash 911276713, now seen corresponding path program 19 times [2018-09-30 10:23:14,922 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:23:14,922 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:23:14,922 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:23:14,923 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:23:14,923 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:23:14,994 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:23:15,778 INFO L134 CoverageAnalysis]: Checked inductivity of 1406 backedges. 0 proven. 1406 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:23:15,778 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:23:15,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 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-09-30 10:23:15,786 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-30 10:23:15,876 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:23:15,924 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:23:16,014 INFO L134 CoverageAnalysis]: Checked inductivity of 1406 backedges. 0 proven. 1406 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:23:16,034 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:23:16,034 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [39, 39] total 40 [2018-09-30 10:23:16,034 INFO L459 AbstractCegarLoop]: Interpolant automaton has 41 states [2018-09-30 10:23:16,035 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 41 interpolants. [2018-09-30 10:23:16,035 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=80, Invalid=1560, Unknown=0, NotChecked=0, Total=1640 [2018-09-30 10:23:16,035 INFO L87 Difference]: Start difference. First operand 79 states and 79 transitions. Second operand 41 states. [2018-09-30 10:23:19,178 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:23:19,179 INFO L93 Difference]: Finished difference Result 85 states and 86 transitions. [2018-09-30 10:23:19,179 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2018-09-30 10:23:19,179 INFO L78 Accepts]: Start accepts. Automaton has 41 states. Word has length 78 [2018-09-30 10:23:19,180 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:23:19,181 INFO L225 Difference]: With dead ends: 85 [2018-09-30 10:23:19,181 INFO L226 Difference]: Without dead ends: 83 [2018-09-30 10:23:19,183 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 153 GetRequests, 77 SyntacticMatches, 0 SemanticMatches, 76 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 667 ImplicationChecksByTransitivity, 3.8s TimeCoverageRelationStatistics Valid=1559, Invalid=4447, Unknown=0, NotChecked=0, Total=6006 [2018-09-30 10:23:19,184 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 83 states. [2018-09-30 10:23:19,189 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 83 to 83. [2018-09-30 10:23:19,190 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 83 states. [2018-09-30 10:23:19,190 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 83 states to 83 states and 83 transitions. [2018-09-30 10:23:19,190 INFO L78 Accepts]: Start accepts. Automaton has 83 states and 83 transitions. Word has length 78 [2018-09-30 10:23:19,191 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:23:19,191 INFO L480 AbstractCegarLoop]: Abstraction has 83 states and 83 transitions. [2018-09-30 10:23:19,191 INFO L481 AbstractCegarLoop]: Interpolant automaton has 41 states. [2018-09-30 10:23:19,191 INFO L276 IsEmpty]: Start isEmpty. Operand 83 states and 83 transitions. [2018-09-30 10:23:19,192 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2018-09-30 10:23:19,192 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:23:19,192 INFO L375 BasicCegarLoop]: trace histogram [40, 39, 1, 1, 1] [2018-09-30 10:23:19,192 INFO L423 AbstractCegarLoop]: === Iteration 21 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:23:19,193 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:23:19,193 INFO L82 PathProgramCache]: Analyzing trace with hash 1569595037, now seen corresponding path program 20 times [2018-09-30 10:23:19,193 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:23:19,193 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:23:19,194 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:23:19,194 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-30 10:23:19,194 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:23:19,262 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:23:20,409 INFO L134 CoverageAnalysis]: Checked inductivity of 1560 backedges. 0 proven. 1560 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:23:20,410 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:23:20,410 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-09-30 10:23:20,420 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-09-30 10:23:20,523 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-09-30 10:23:20,524 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:23:20,579 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:23:20,665 INFO L134 CoverageAnalysis]: Checked inductivity of 1560 backedges. 0 proven. 1560 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:23:20,685 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:23:20,685 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [41, 41] total 42 [2018-09-30 10:23:20,685 INFO L459 AbstractCegarLoop]: Interpolant automaton has 43 states [2018-09-30 10:23:20,686 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 43 interpolants. [2018-09-30 10:23:20,686 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=84, Invalid=1722, Unknown=0, NotChecked=0, Total=1806 [2018-09-30 10:23:20,686 INFO L87 Difference]: Start difference. First operand 83 states and 83 transitions. Second operand 43 states. [2018-09-30 10:23:24,253 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:23:24,254 INFO L93 Difference]: Finished difference Result 89 states and 90 transitions. [2018-09-30 10:23:24,254 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 43 states. [2018-09-30 10:23:24,254 INFO L78 Accepts]: Start accepts. Automaton has 43 states. Word has length 82 [2018-09-30 10:23:24,255 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:23:24,255 INFO L225 Difference]: With dead ends: 89 [2018-09-30 10:23:24,256 INFO L226 Difference]: Without dead ends: 87 [2018-09-30 10:23:24,258 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 161 GetRequests, 81 SyntacticMatches, 0 SemanticMatches, 80 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 742 ImplicationChecksByTransitivity, 4.5s TimeCoverageRelationStatistics Valid=1721, Invalid=4921, Unknown=0, NotChecked=0, Total=6642 [2018-09-30 10:23:24,258 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 87 states. [2018-09-30 10:23:24,266 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 87 to 87. [2018-09-30 10:23:24,266 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 87 states. [2018-09-30 10:23:24,266 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 87 states to 87 states and 87 transitions. [2018-09-30 10:23:24,267 INFO L78 Accepts]: Start accepts. Automaton has 87 states and 87 transitions. Word has length 82 [2018-09-30 10:23:24,267 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:23:24,267 INFO L480 AbstractCegarLoop]: Abstraction has 87 states and 87 transitions. [2018-09-30 10:23:24,267 INFO L481 AbstractCegarLoop]: Interpolant automaton has 43 states. [2018-09-30 10:23:24,267 INFO L276 IsEmpty]: Start isEmpty. Operand 87 states and 87 transitions. [2018-09-30 10:23:24,268 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2018-09-30 10:23:24,268 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:23:24,269 INFO L375 BasicCegarLoop]: trace histogram [42, 41, 1, 1, 1] [2018-09-30 10:23:24,269 INFO L423 AbstractCegarLoop]: === Iteration 22 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:23:24,269 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:23:24,273 INFO L82 PathProgramCache]: Analyzing trace with hash -1729091439, now seen corresponding path program 21 times [2018-09-30 10:23:24,273 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:23:24,274 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:23:24,275 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:23:24,275 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:23:24,275 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:23:24,403 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:23:25,559 INFO L134 CoverageAnalysis]: Checked inductivity of 1722 backedges. 0 proven. 1722 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:23:25,560 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:23:25,560 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-09-30 10:23:25,568 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-09-30 10:23:25,672 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 42 check-sat command(s) [2018-09-30 10:23:25,672 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:23:25,676 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:23:25,749 INFO L134 CoverageAnalysis]: Checked inductivity of 1722 backedges. 0 proven. 1722 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:23:25,770 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:23:25,770 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [43, 43] total 44 [2018-09-30 10:23:25,770 INFO L459 AbstractCegarLoop]: Interpolant automaton has 45 states [2018-09-30 10:23:25,771 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2018-09-30 10:23:25,771 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=1892, Unknown=0, NotChecked=0, Total=1980 [2018-09-30 10:23:25,771 INFO L87 Difference]: Start difference. First operand 87 states and 87 transitions. Second operand 45 states. [2018-09-30 10:23:29,802 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:23:29,802 INFO L93 Difference]: Finished difference Result 93 states and 94 transitions. [2018-09-30 10:23:29,806 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2018-09-30 10:23:29,806 INFO L78 Accepts]: Start accepts. Automaton has 45 states. Word has length 86 [2018-09-30 10:23:29,807 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:23:29,807 INFO L225 Difference]: With dead ends: 93 [2018-09-30 10:23:29,807 INFO L226 Difference]: Without dead ends: 91 [2018-09-30 10:23:29,808 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 169 GetRequests, 85 SyntacticMatches, 0 SemanticMatches, 84 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 821 ImplicationChecksByTransitivity, 5.0s TimeCoverageRelationStatistics Valid=1891, Invalid=5419, Unknown=0, NotChecked=0, Total=7310 [2018-09-30 10:23:29,808 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2018-09-30 10:23:29,812 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 91. [2018-09-30 10:23:29,813 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 91 states. [2018-09-30 10:23:29,813 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 91 transitions. [2018-09-30 10:23:29,813 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 91 transitions. Word has length 86 [2018-09-30 10:23:29,813 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:23:29,813 INFO L480 AbstractCegarLoop]: Abstraction has 91 states and 91 transitions. [2018-09-30 10:23:29,813 INFO L481 AbstractCegarLoop]: Interpolant automaton has 45 states. [2018-09-30 10:23:29,813 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 91 transitions. [2018-09-30 10:23:29,814 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2018-09-30 10:23:29,814 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:23:29,814 INFO L375 BasicCegarLoop]: trace histogram [44, 43, 1, 1, 1] [2018-09-30 10:23:29,815 INFO L423 AbstractCegarLoop]: === Iteration 23 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:23:29,815 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:23:29,815 INFO L82 PathProgramCache]: Analyzing trace with hash -543942523, now seen corresponding path program 22 times [2018-09-30 10:23:29,815 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:23:29,815 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:23:29,816 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:23:29,816 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:23:29,816 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:23:29,913 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:23:31,183 INFO L134 CoverageAnalysis]: Checked inductivity of 1892 backedges. 0 proven. 1892 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:23:31,183 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:23:31,183 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-09-30 10:23:31,191 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-09-30 10:23:31,225 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-09-30 10:23:31,226 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:23:31,231 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:23:31,350 INFO L134 CoverageAnalysis]: Checked inductivity of 1892 backedges. 0 proven. 1892 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:23:31,370 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:23:31,371 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [45, 45] total 46 [2018-09-30 10:23:31,371 INFO L459 AbstractCegarLoop]: Interpolant automaton has 47 states [2018-09-30 10:23:31,371 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 47 interpolants. [2018-09-30 10:23:31,372 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=92, Invalid=2070, Unknown=0, NotChecked=0, Total=2162 [2018-09-30 10:23:31,372 INFO L87 Difference]: Start difference. First operand 91 states and 91 transitions. Second operand 47 states. [2018-09-30 10:23:36,005 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:23:36,005 INFO L93 Difference]: Finished difference Result 97 states and 98 transitions. [2018-09-30 10:23:36,005 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 47 states. [2018-09-30 10:23:36,006 INFO L78 Accepts]: Start accepts. Automaton has 47 states. Word has length 90 [2018-09-30 10:23:36,006 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:23:36,007 INFO L225 Difference]: With dead ends: 97 [2018-09-30 10:23:36,007 INFO L226 Difference]: Without dead ends: 95 [2018-09-30 10:23:36,008 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 177 GetRequests, 89 SyntacticMatches, 0 SemanticMatches, 88 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 904 ImplicationChecksByTransitivity, 5.7s TimeCoverageRelationStatistics Valid=2069, Invalid=5941, Unknown=0, NotChecked=0, Total=8010 [2018-09-30 10:23:36,008 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2018-09-30 10:23:36,014 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 95. [2018-09-30 10:23:36,014 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 95 states. [2018-09-30 10:23:36,015 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 95 transitions. [2018-09-30 10:23:36,015 INFO L78 Accepts]: Start accepts. Automaton has 95 states and 95 transitions. Word has length 90 [2018-09-30 10:23:36,015 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:23:36,015 INFO L480 AbstractCegarLoop]: Abstraction has 95 states and 95 transitions. [2018-09-30 10:23:36,015 INFO L481 AbstractCegarLoop]: Interpolant automaton has 47 states. [2018-09-30 10:23:36,015 INFO L276 IsEmpty]: Start isEmpty. Operand 95 states and 95 transitions. [2018-09-30 10:23:36,016 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 95 [2018-09-30 10:23:36,016 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:23:36,016 INFO L375 BasicCegarLoop]: trace histogram [46, 45, 1, 1, 1] [2018-09-30 10:23:36,016 INFO L423 AbstractCegarLoop]: === Iteration 24 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:23:36,016 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:23:36,017 INFO L82 PathProgramCache]: Analyzing trace with hash 1377234553, now seen corresponding path program 23 times [2018-09-30 10:23:36,017 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:23:36,017 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:23:36,018 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:23:36,018 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:23:36,018 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:23:36,127 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:23:37,266 INFO L134 CoverageAnalysis]: Checked inductivity of 2070 backedges. 0 proven. 2070 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:23:37,266 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:23:37,266 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-09-30 10:23:37,274 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-09-30 10:23:37,444 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 46 check-sat command(s) [2018-09-30 10:23:37,444 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:23:37,464 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:23:37,566 INFO L134 CoverageAnalysis]: Checked inductivity of 2070 backedges. 0 proven. 2070 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:23:37,586 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:23:37,586 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [47, 47] total 48 [2018-09-30 10:23:37,587 INFO L459 AbstractCegarLoop]: Interpolant automaton has 49 states [2018-09-30 10:23:37,587 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 49 interpolants. [2018-09-30 10:23:37,587 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=96, Invalid=2256, Unknown=0, NotChecked=0, Total=2352 [2018-09-30 10:23:37,587 INFO L87 Difference]: Start difference. First operand 95 states and 95 transitions. Second operand 49 states. [2018-09-30 10:23:42,490 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:23:42,490 INFO L93 Difference]: Finished difference Result 101 states and 102 transitions. [2018-09-30 10:23:42,490 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 49 states. [2018-09-30 10:23:42,491 INFO L78 Accepts]: Start accepts. Automaton has 49 states. Word has length 94 [2018-09-30 10:23:42,491 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:23:42,492 INFO L225 Difference]: With dead ends: 101 [2018-09-30 10:23:42,492 INFO L226 Difference]: Without dead ends: 99 [2018-09-30 10:23:42,493 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 185 GetRequests, 93 SyntacticMatches, 0 SemanticMatches, 92 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 991 ImplicationChecksByTransitivity, 5.8s TimeCoverageRelationStatistics Valid=2255, Invalid=6487, Unknown=0, NotChecked=0, Total=8742 [2018-09-30 10:23:42,493 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states. [2018-09-30 10:23:42,501 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 99. [2018-09-30 10:23:42,501 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 99 states. [2018-09-30 10:23:42,501 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 99 transitions. [2018-09-30 10:23:42,501 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 99 transitions. Word has length 94 [2018-09-30 10:23:42,501 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:23:42,501 INFO L480 AbstractCegarLoop]: Abstraction has 99 states and 99 transitions. [2018-09-30 10:23:42,502 INFO L481 AbstractCegarLoop]: Interpolant automaton has 49 states. [2018-09-30 10:23:42,502 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 99 transitions. [2018-09-30 10:23:42,502 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2018-09-30 10:23:42,502 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:23:42,502 INFO L375 BasicCegarLoop]: trace histogram [48, 47, 1, 1, 1] [2018-09-30 10:23:42,502 INFO L423 AbstractCegarLoop]: === Iteration 25 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:23:42,503 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:23:42,503 INFO L82 PathProgramCache]: Analyzing trace with hash 2056628845, now seen corresponding path program 24 times [2018-09-30 10:23:42,503 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:23:42,503 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:23:42,503 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:23:42,503 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:23:42,504 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:23:42,628 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:23:44,375 INFO L134 CoverageAnalysis]: Checked inductivity of 2256 backedges. 0 proven. 2256 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:23:44,376 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:23:44,376 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-09-30 10:23:44,383 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-09-30 10:23:44,433 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 48 check-sat command(s) [2018-09-30 10:23:44,433 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:23:44,438 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:23:45,579 INFO L134 CoverageAnalysis]: Checked inductivity of 2256 backedges. 0 proven. 2256 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:23:45,600 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:23:45,600 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [49, 49] total 50 [2018-09-30 10:23:45,600 INFO L459 AbstractCegarLoop]: Interpolant automaton has 51 states [2018-09-30 10:23:45,600 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 51 interpolants. [2018-09-30 10:23:45,601 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=2450, Unknown=0, NotChecked=0, Total=2550 [2018-09-30 10:23:45,601 INFO L87 Difference]: Start difference. First operand 99 states and 99 transitions. Second operand 51 states. [2018-09-30 10:23:45,771 WARN L178 SmtUtils]: Spent 112.00 ms on a formula simplification. DAG size of input: 141 DAG size of output: 8 [2018-09-30 10:23:45,887 WARN L178 SmtUtils]: Spent 104.00 ms on a formula simplification. DAG size of input: 147 DAG size of output: 9 [2018-09-30 10:23:46,007 WARN L178 SmtUtils]: Spent 103.00 ms on a formula simplification. DAG size of input: 146 DAG size of output: 11 [2018-09-30 10:23:46,250 WARN L178 SmtUtils]: Spent 100.00 ms on a formula simplification. DAG size of input: 140 DAG size of output: 11 [2018-09-30 10:23:51,234 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:23:51,235 INFO L93 Difference]: Finished difference Result 105 states and 106 transitions. [2018-09-30 10:23:51,235 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 51 states. [2018-09-30 10:23:51,235 INFO L78 Accepts]: Start accepts. Automaton has 51 states. Word has length 98 [2018-09-30 10:23:51,236 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:23:51,237 INFO L225 Difference]: With dead ends: 105 [2018-09-30 10:23:51,237 INFO L226 Difference]: Without dead ends: 103 [2018-09-30 10:23:51,239 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 193 GetRequests, 97 SyntacticMatches, 0 SemanticMatches, 96 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1082 ImplicationChecksByTransitivity, 8.2s TimeCoverageRelationStatistics Valid=2449, Invalid=7057, Unknown=0, NotChecked=0, Total=9506 [2018-09-30 10:23:51,239 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states. [2018-09-30 10:23:51,246 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 103. [2018-09-30 10:23:51,246 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 103 states. [2018-09-30 10:23:51,247 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 103 transitions. [2018-09-30 10:23:51,247 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 103 transitions. Word has length 98 [2018-09-30 10:23:51,247 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:23:51,247 INFO L480 AbstractCegarLoop]: Abstraction has 103 states and 103 transitions. [2018-09-30 10:23:51,247 INFO L481 AbstractCegarLoop]: Interpolant automaton has 51 states. [2018-09-30 10:23:51,247 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 103 transitions. [2018-09-30 10:23:51,248 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 103 [2018-09-30 10:23:51,248 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:23:51,248 INFO L375 BasicCegarLoop]: trace histogram [50, 49, 1, 1, 1] [2018-09-30 10:23:51,248 INFO L423 AbstractCegarLoop]: === Iteration 26 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:23:51,248 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:23:51,249 INFO L82 PathProgramCache]: Analyzing trace with hash -1934799775, now seen corresponding path program 25 times [2018-09-30 10:23:51,249 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:23:51,249 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:23:51,250 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:23:51,250 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:23:51,250 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:23:51,358 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:23:52,624 INFO L134 CoverageAnalysis]: Checked inductivity of 2450 backedges. 0 proven. 2450 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:23:52,624 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:23:52,624 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-09-30 10:23:52,633 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-30 10:23:52,821 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:23:52,925 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:23:53,015 INFO L134 CoverageAnalysis]: Checked inductivity of 2450 backedges. 0 proven. 2450 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:23:53,036 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:23:53,036 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [51, 51] total 52 [2018-09-30 10:23:53,036 INFO L459 AbstractCegarLoop]: Interpolant automaton has 53 states [2018-09-30 10:23:53,036 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 53 interpolants. [2018-09-30 10:23:53,037 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=104, Invalid=2652, Unknown=0, NotChecked=0, Total=2756 [2018-09-30 10:23:53,037 INFO L87 Difference]: Start difference. First operand 103 states and 103 transitions. Second operand 53 states. [2018-09-30 10:23:53,165 WARN L178 SmtUtils]: Spent 101.00 ms on a formula simplification. DAG size of input: 147 DAG size of output: 8 [2018-09-30 10:23:53,284 WARN L178 SmtUtils]: Spent 107.00 ms on a formula simplification. DAG size of input: 153 DAG size of output: 9 [2018-09-30 10:23:53,412 WARN L178 SmtUtils]: Spent 110.00 ms on a formula simplification. DAG size of input: 152 DAG size of output: 11 [2018-09-30 10:23:53,537 WARN L178 SmtUtils]: Spent 104.00 ms on a formula simplification. DAG size of input: 149 DAG size of output: 11 [2018-09-30 10:23:53,667 WARN L178 SmtUtils]: Spent 104.00 ms on a formula simplification. DAG size of input: 146 DAG size of output: 11 [2018-09-30 10:23:53,798 WARN L178 SmtUtils]: Spent 101.00 ms on a formula simplification. DAG size of input: 143 DAG size of output: 11 [2018-09-30 10:23:58,951 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:23:58,951 INFO L93 Difference]: Finished difference Result 109 states and 110 transitions. [2018-09-30 10:23:58,952 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 53 states. [2018-09-30 10:23:58,952 INFO L78 Accepts]: Start accepts. Automaton has 53 states. Word has length 102 [2018-09-30 10:23:58,952 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:23:58,953 INFO L225 Difference]: With dead ends: 109 [2018-09-30 10:23:58,953 INFO L226 Difference]: Without dead ends: 107 [2018-09-30 10:23:58,955 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 201 GetRequests, 101 SyntacticMatches, 0 SemanticMatches, 100 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1177 ImplicationChecksByTransitivity, 6.9s TimeCoverageRelationStatistics Valid=2651, Invalid=7651, Unknown=0, NotChecked=0, Total=10302 [2018-09-30 10:23:58,955 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 107 states. [2018-09-30 10:23:58,962 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 107 to 107. [2018-09-30 10:23:58,962 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 107 states. [2018-09-30 10:23:58,963 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 107 transitions. [2018-09-30 10:23:58,963 INFO L78 Accepts]: Start accepts. Automaton has 107 states and 107 transitions. Word has length 102 [2018-09-30 10:23:58,963 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:23:58,964 INFO L480 AbstractCegarLoop]: Abstraction has 107 states and 107 transitions. [2018-09-30 10:23:58,964 INFO L481 AbstractCegarLoop]: Interpolant automaton has 53 states. [2018-09-30 10:23:58,964 INFO L276 IsEmpty]: Start isEmpty. Operand 107 states and 107 transitions. [2018-09-30 10:23:58,964 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 107 [2018-09-30 10:23:58,964 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:23:58,964 INFO L375 BasicCegarLoop]: trace histogram [52, 51, 1, 1, 1] [2018-09-30 10:23:58,965 INFO L423 AbstractCegarLoop]: === Iteration 27 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:23:58,965 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:23:58,965 INFO L82 PathProgramCache]: Analyzing trace with hash -1518676907, now seen corresponding path program 26 times [2018-09-30 10:23:58,965 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:23:58,965 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:23:58,966 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:23:58,966 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-30 10:23:58,966 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:23:59,088 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:24:00,460 INFO L134 CoverageAnalysis]: Checked inductivity of 2652 backedges. 0 proven. 2652 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:24:00,461 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:24:00,461 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-09-30 10:24:00,471 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-09-30 10:24:00,679 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-09-30 10:24:00,680 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:24:00,804 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:24:00,970 INFO L134 CoverageAnalysis]: Checked inductivity of 2652 backedges. 0 proven. 2652 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:24:00,991 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:24:00,991 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [53, 53] total 54 [2018-09-30 10:24:00,992 INFO L459 AbstractCegarLoop]: Interpolant automaton has 55 states [2018-09-30 10:24:00,992 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 55 interpolants. [2018-09-30 10:24:00,992 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=108, Invalid=2862, Unknown=0, NotChecked=0, Total=2970 [2018-09-30 10:24:00,992 INFO L87 Difference]: Start difference. First operand 107 states and 107 transitions. Second operand 55 states. [2018-09-30 10:24:01,177 WARN L178 SmtUtils]: Spent 118.00 ms on a formula simplification. DAG size of input: 153 DAG size of output: 8 [2018-09-30 10:24:01,317 WARN L178 SmtUtils]: Spent 128.00 ms on a formula simplification. DAG size of input: 159 DAG size of output: 9 [2018-09-30 10:24:01,476 WARN L178 SmtUtils]: Spent 140.00 ms on a formula simplification. DAG size of input: 158 DAG size of output: 11 [2018-09-30 10:24:01,627 WARN L178 SmtUtils]: Spent 112.00 ms on a formula simplification. DAG size of input: 155 DAG size of output: 11 [2018-09-30 10:24:01,765 WARN L178 SmtUtils]: Spent 112.00 ms on a formula simplification. DAG size of input: 152 DAG size of output: 11 [2018-09-30 10:24:01,900 WARN L178 SmtUtils]: Spent 100.00 ms on a formula simplification. DAG size of input: 149 DAG size of output: 11 [2018-09-30 10:24:02,037 WARN L178 SmtUtils]: Spent 100.00 ms on a formula simplification. DAG size of input: 146 DAG size of output: 11 [2018-09-30 10:24:07,629 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:24:07,630 INFO L93 Difference]: Finished difference Result 113 states and 114 transitions. [2018-09-30 10:24:07,630 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 55 states. [2018-09-30 10:24:07,630 INFO L78 Accepts]: Start accepts. Automaton has 55 states. Word has length 106 [2018-09-30 10:24:07,631 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:24:07,631 INFO L225 Difference]: With dead ends: 113 [2018-09-30 10:24:07,631 INFO L226 Difference]: Without dead ends: 111 [2018-09-30 10:24:07,633 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 209 GetRequests, 105 SyntacticMatches, 0 SemanticMatches, 104 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1276 ImplicationChecksByTransitivity, 7.8s TimeCoverageRelationStatistics Valid=2861, Invalid=8269, Unknown=0, NotChecked=0, Total=11130 [2018-09-30 10:24:07,633 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 111 states. [2018-09-30 10:24:07,639 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 111 to 111. [2018-09-30 10:24:07,639 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 111 states. [2018-09-30 10:24:07,640 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 111 states to 111 states and 111 transitions. [2018-09-30 10:24:07,640 INFO L78 Accepts]: Start accepts. Automaton has 111 states and 111 transitions. Word has length 106 [2018-09-30 10:24:07,640 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:24:07,640 INFO L480 AbstractCegarLoop]: Abstraction has 111 states and 111 transitions. [2018-09-30 10:24:07,641 INFO L481 AbstractCegarLoop]: Interpolant automaton has 55 states. [2018-09-30 10:24:07,641 INFO L276 IsEmpty]: Start isEmpty. Operand 111 states and 111 transitions. [2018-09-30 10:24:07,641 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 111 [2018-09-30 10:24:07,641 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:24:07,641 INFO L375 BasicCegarLoop]: trace histogram [54, 53, 1, 1, 1] [2018-09-30 10:24:07,642 INFO L423 AbstractCegarLoop]: === Iteration 28 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:24:07,642 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:24:07,642 INFO L82 PathProgramCache]: Analyzing trace with hash 194724425, now seen corresponding path program 27 times [2018-09-30 10:24:07,642 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:24:07,642 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:24:07,643 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:24:07,643 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:24:07,643 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:24:07,789 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:24:09,336 INFO L134 CoverageAnalysis]: Checked inductivity of 2862 backedges. 0 proven. 2862 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:24:09,336 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:24:09,336 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-09-30 10:24:09,345 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-09-30 10:24:09,405 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 54 check-sat command(s) [2018-09-30 10:24:09,406 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:24:09,412 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:24:09,535 INFO L134 CoverageAnalysis]: Checked inductivity of 2862 backedges. 0 proven. 2862 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:24:09,557 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:24:09,557 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [55, 55] total 56 [2018-09-30 10:24:09,557 INFO L459 AbstractCegarLoop]: Interpolant automaton has 57 states [2018-09-30 10:24:09,558 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 57 interpolants. [2018-09-30 10:24:09,558 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=112, Invalid=3080, Unknown=0, NotChecked=0, Total=3192 [2018-09-30 10:24:09,558 INFO L87 Difference]: Start difference. First operand 111 states and 111 transitions. Second operand 57 states. [2018-09-30 10:24:09,716 WARN L178 SmtUtils]: Spent 113.00 ms on a formula simplification. DAG size of input: 159 DAG size of output: 8 [2018-09-30 10:24:09,871 WARN L178 SmtUtils]: Spent 122.00 ms on a formula simplification. DAG size of input: 165 DAG size of output: 9 [2018-09-30 10:24:10,017 WARN L178 SmtUtils]: Spent 125.00 ms on a formula simplification. DAG size of input: 164 DAG size of output: 11 [2018-09-30 10:24:10,157 WARN L178 SmtUtils]: Spent 118.00 ms on a formula simplification. DAG size of input: 161 DAG size of output: 11 [2018-09-30 10:24:10,297 WARN L178 SmtUtils]: Spent 113.00 ms on a formula simplification. DAG size of input: 158 DAG size of output: 11 [2018-09-30 10:24:10,437 WARN L178 SmtUtils]: Spent 105.00 ms on a formula simplification. DAG size of input: 155 DAG size of output: 11 [2018-09-30 10:24:10,583 WARN L178 SmtUtils]: Spent 104.00 ms on a formula simplification. DAG size of input: 152 DAG size of output: 11 [2018-09-30 10:24:10,868 WARN L178 SmtUtils]: Spent 100.00 ms on a formula simplification. DAG size of input: 146 DAG size of output: 11 [2018-09-30 10:24:11,032 WARN L178 SmtUtils]: Spent 113.00 ms on a formula simplification. DAG size of input: 143 DAG size of output: 11 [2018-09-30 10:24:11,355 WARN L178 SmtUtils]: Spent 102.00 ms on a formula simplification. DAG size of input: 137 DAG size of output: 11 [2018-09-30 10:24:16,816 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:24:16,817 INFO L93 Difference]: Finished difference Result 117 states and 118 transitions. [2018-09-30 10:24:16,817 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 57 states. [2018-09-30 10:24:16,817 INFO L78 Accepts]: Start accepts. Automaton has 57 states. Word has length 110 [2018-09-30 10:24:16,818 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:24:16,818 INFO L225 Difference]: With dead ends: 117 [2018-09-30 10:24:16,819 INFO L226 Difference]: Without dead ends: 115 [2018-09-30 10:24:16,820 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 217 GetRequests, 109 SyntacticMatches, 0 SemanticMatches, 108 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1379 ImplicationChecksByTransitivity, 8.6s TimeCoverageRelationStatistics Valid=3079, Invalid=8911, Unknown=0, NotChecked=0, Total=11990 [2018-09-30 10:24:16,820 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 115 states. [2018-09-30 10:24:16,826 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 115 to 115. [2018-09-30 10:24:16,826 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 115 states. [2018-09-30 10:24:16,827 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 115 states to 115 states and 115 transitions. [2018-09-30 10:24:16,827 INFO L78 Accepts]: Start accepts. Automaton has 115 states and 115 transitions. Word has length 110 [2018-09-30 10:24:16,827 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:24:16,827 INFO L480 AbstractCegarLoop]: Abstraction has 115 states and 115 transitions. [2018-09-30 10:24:16,827 INFO L481 AbstractCegarLoop]: Interpolant automaton has 57 states. [2018-09-30 10:24:16,827 INFO L276 IsEmpty]: Start isEmpty. Operand 115 states and 115 transitions. [2018-09-30 10:24:16,827 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 115 [2018-09-30 10:24:16,827 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:24:16,828 INFO L375 BasicCegarLoop]: trace histogram [56, 55, 1, 1, 1] [2018-09-30 10:24:16,828 INFO L423 AbstractCegarLoop]: === Iteration 29 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:24:16,828 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:24:16,828 INFO L82 PathProgramCache]: Analyzing trace with hash 1865127485, now seen corresponding path program 28 times [2018-09-30 10:24:16,828 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:24:16,828 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:24:16,829 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:24:16,829 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:24:16,829 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:24:16,983 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:24:18,504 INFO L134 CoverageAnalysis]: Checked inductivity of 3080 backedges. 0 proven. 3080 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:24:18,505 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:24:18,505 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-09-30 10:24:18,514 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-09-30 10:24:18,764 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-09-30 10:24:18,765 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:24:18,913 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:24:19,012 INFO L134 CoverageAnalysis]: Checked inductivity of 3080 backedges. 0 proven. 3080 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:24:19,042 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:24:19,042 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [57, 57] total 58 [2018-09-30 10:24:19,043 INFO L459 AbstractCegarLoop]: Interpolant automaton has 59 states [2018-09-30 10:24:19,043 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 59 interpolants. [2018-09-30 10:24:19,043 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=116, Invalid=3306, Unknown=0, NotChecked=0, Total=3422 [2018-09-30 10:24:19,043 INFO L87 Difference]: Start difference. First operand 115 states and 115 transitions. Second operand 59 states. [2018-09-30 10:24:19,201 WARN L178 SmtUtils]: Spent 115.00 ms on a formula simplification. DAG size of input: 165 DAG size of output: 8 [2018-09-30 10:24:19,340 WARN L178 SmtUtils]: Spent 125.00 ms on a formula simplification. DAG size of input: 171 DAG size of output: 9 [2018-09-30 10:24:19,492 WARN L178 SmtUtils]: Spent 131.00 ms on a formula simplification. DAG size of input: 170 DAG size of output: 11 [2018-09-30 10:24:19,633 WARN L178 SmtUtils]: Spent 118.00 ms on a formula simplification. DAG size of input: 167 DAG size of output: 11 [2018-09-30 10:24:19,784 WARN L178 SmtUtils]: Spent 124.00 ms on a formula simplification. DAG size of input: 164 DAG size of output: 11 [2018-09-30 10:24:19,924 WARN L178 SmtUtils]: Spent 108.00 ms on a formula simplification. DAG size of input: 161 DAG size of output: 11 [2018-09-30 10:24:20,070 WARN L178 SmtUtils]: Spent 110.00 ms on a formula simplification. DAG size of input: 158 DAG size of output: 11 [2018-09-30 10:24:20,216 WARN L178 SmtUtils]: Spent 105.00 ms on a formula simplification. DAG size of input: 155 DAG size of output: 11 [2018-09-30 10:24:20,368 WARN L178 SmtUtils]: Spent 103.00 ms on a formula simplification. DAG size of input: 152 DAG size of output: 11 [2018-09-30 10:24:20,530 WARN L178 SmtUtils]: Spent 109.00 ms on a formula simplification. DAG size of input: 149 DAG size of output: 11 [2018-09-30 10:24:27,172 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:24:27,172 INFO L93 Difference]: Finished difference Result 121 states and 122 transitions. [2018-09-30 10:24:27,175 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 59 states. [2018-09-30 10:24:27,175 INFO L78 Accepts]: Start accepts. Automaton has 59 states. Word has length 114 [2018-09-30 10:24:27,175 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:24:27,176 INFO L225 Difference]: With dead ends: 121 [2018-09-30 10:24:27,176 INFO L226 Difference]: Without dead ends: 119 [2018-09-30 10:24:27,177 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 225 GetRequests, 113 SyntacticMatches, 0 SemanticMatches, 112 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1486 ImplicationChecksByTransitivity, 9.4s TimeCoverageRelationStatistics Valid=3305, Invalid=9577, Unknown=0, NotChecked=0, Total=12882 [2018-09-30 10:24:27,177 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 119 states. [2018-09-30 10:24:27,184 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 119 to 119. [2018-09-30 10:24:27,184 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 119 states. [2018-09-30 10:24:27,185 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 119 states to 119 states and 119 transitions. [2018-09-30 10:24:27,185 INFO L78 Accepts]: Start accepts. Automaton has 119 states and 119 transitions. Word has length 114 [2018-09-30 10:24:27,185 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:24:27,185 INFO L480 AbstractCegarLoop]: Abstraction has 119 states and 119 transitions. [2018-09-30 10:24:27,185 INFO L481 AbstractCegarLoop]: Interpolant automaton has 59 states. [2018-09-30 10:24:27,186 INFO L276 IsEmpty]: Start isEmpty. Operand 119 states and 119 transitions. [2018-09-30 10:24:27,186 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 119 [2018-09-30 10:24:27,186 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:24:27,186 INFO L375 BasicCegarLoop]: trace histogram [58, 57, 1, 1, 1] [2018-09-30 10:24:27,187 INFO L423 AbstractCegarLoop]: === Iteration 30 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:24:27,187 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:24:27,187 INFO L82 PathProgramCache]: Analyzing trace with hash 701026353, now seen corresponding path program 29 times [2018-09-30 10:24:27,187 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:24:27,187 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:24:27,188 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:24:27,188 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:24:27,188 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:24:27,335 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:24:29,002 INFO L134 CoverageAnalysis]: Checked inductivity of 3306 backedges. 0 proven. 3306 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:24:29,002 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:24:29,002 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-09-30 10:24:29,010 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-09-30 10:24:29,263 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 58 check-sat command(s) [2018-09-30 10:24:29,263 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:24:29,301 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:24:29,406 INFO L134 CoverageAnalysis]: Checked inductivity of 3306 backedges. 0 proven. 3306 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:24:29,428 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:24:29,428 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [59, 59] total 60 [2018-09-30 10:24:29,429 INFO L459 AbstractCegarLoop]: Interpolant automaton has 61 states [2018-09-30 10:24:29,429 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 61 interpolants. [2018-09-30 10:24:29,429 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=120, Invalid=3540, Unknown=0, NotChecked=0, Total=3660 [2018-09-30 10:24:29,429 INFO L87 Difference]: Start difference. First operand 119 states and 119 transitions. Second operand 61 states. [2018-09-30 10:24:29,590 WARN L178 SmtUtils]: Spent 122.00 ms on a formula simplification. DAG size of input: 171 DAG size of output: 8 [2018-09-30 10:24:29,741 WARN L178 SmtUtils]: Spent 139.00 ms on a formula simplification. DAG size of input: 177 DAG size of output: 9 [2018-09-30 10:24:29,899 WARN L178 SmtUtils]: Spent 138.00 ms on a formula simplification. DAG size of input: 176 DAG size of output: 11 [2018-09-30 10:24:30,043 WARN L178 SmtUtils]: Spent 120.00 ms on a formula simplification. DAG size of input: 173 DAG size of output: 11 [2018-09-30 10:24:30,194 WARN L178 SmtUtils]: Spent 122.00 ms on a formula simplification. DAG size of input: 170 DAG size of output: 11 [2018-09-30 10:24:30,338 WARN L178 SmtUtils]: Spent 110.00 ms on a formula simplification. DAG size of input: 167 DAG size of output: 11 [2018-09-30 10:24:30,492 WARN L178 SmtUtils]: Spent 117.00 ms on a formula simplification. DAG size of input: 164 DAG size of output: 11 [2018-09-30 10:24:30,647 WARN L178 SmtUtils]: Spent 114.00 ms on a formula simplification. DAG size of input: 161 DAG size of output: 11 [2018-09-30 10:24:30,810 WARN L178 SmtUtils]: Spent 114.00 ms on a formula simplification. DAG size of input: 158 DAG size of output: 11 [2018-09-30 10:24:30,971 WARN L178 SmtUtils]: Spent 109.00 ms on a formula simplification. DAG size of input: 155 DAG size of output: 11 [2018-09-30 10:24:31,130 WARN L178 SmtUtils]: Spent 102.00 ms on a formula simplification. DAG size of input: 152 DAG size of output: 11 [2018-09-30 10:24:31,292 WARN L178 SmtUtils]: Spent 101.00 ms on a formula simplification. DAG size of input: 149 DAG size of output: 11 [2018-09-30 10:24:31,464 WARN L178 SmtUtils]: Spent 105.00 ms on a formula simplification. DAG size of input: 146 DAG size of output: 11 [2018-09-30 10:24:31,649 WARN L178 SmtUtils]: Spent 108.00 ms on a formula simplification. DAG size of input: 143 DAG size of output: 11 [2018-09-30 10:24:31,847 WARN L178 SmtUtils]: Spent 106.00 ms on a formula simplification. DAG size of input: 140 DAG size of output: 11 [2018-09-30 10:24:38,102 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:24:38,102 INFO L93 Difference]: Finished difference Result 125 states and 126 transitions. [2018-09-30 10:24:38,103 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 61 states. [2018-09-30 10:24:38,103 INFO L78 Accepts]: Start accepts. Automaton has 61 states. Word has length 118 [2018-09-30 10:24:38,103 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:24:38,104 INFO L225 Difference]: With dead ends: 125 [2018-09-30 10:24:38,105 INFO L226 Difference]: Without dead ends: 123 [2018-09-30 10:24:38,106 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 233 GetRequests, 117 SyntacticMatches, 0 SemanticMatches, 116 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1597 ImplicationChecksByTransitivity, 10.1s TimeCoverageRelationStatistics Valid=3539, Invalid=10267, Unknown=0, NotChecked=0, Total=13806 [2018-09-30 10:24:38,106 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 123 states. [2018-09-30 10:24:38,114 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 123 to 123. [2018-09-30 10:24:38,114 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 123 states. [2018-09-30 10:24:38,114 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 123 states to 123 states and 123 transitions. [2018-09-30 10:24:38,115 INFO L78 Accepts]: Start accepts. Automaton has 123 states and 123 transitions. Word has length 118 [2018-09-30 10:24:38,115 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:24:38,115 INFO L480 AbstractCegarLoop]: Abstraction has 123 states and 123 transitions. [2018-09-30 10:24:38,115 INFO L481 AbstractCegarLoop]: Interpolant automaton has 61 states. [2018-09-30 10:24:38,115 INFO L276 IsEmpty]: Start isEmpty. Operand 123 states and 123 transitions. [2018-09-30 10:24:38,116 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 123 [2018-09-30 10:24:38,116 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:24:38,116 INFO L375 BasicCegarLoop]: trace histogram [60, 59, 1, 1, 1] [2018-09-30 10:24:38,116 INFO L423 AbstractCegarLoop]: === Iteration 31 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:24:38,116 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:24:38,117 INFO L82 PathProgramCache]: Analyzing trace with hash 2123362341, now seen corresponding path program 30 times [2018-09-30 10:24:38,117 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:24:38,117 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:24:38,117 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:24:38,118 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:24:38,118 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:24:38,301 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:24:40,524 INFO L134 CoverageAnalysis]: Checked inductivity of 3540 backedges. 0 proven. 3540 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:24:40,525 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:24:40,525 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-09-30 10:24:40,534 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-09-30 10:24:40,610 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 60 check-sat command(s) [2018-09-30 10:24:40,611 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:24:40,618 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:24:40,752 INFO L134 CoverageAnalysis]: Checked inductivity of 3540 backedges. 0 proven. 3540 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:24:40,780 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:24:40,781 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [61, 61] total 62 [2018-09-30 10:24:40,781 INFO L459 AbstractCegarLoop]: Interpolant automaton has 63 states [2018-09-30 10:24:40,781 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 63 interpolants. [2018-09-30 10:24:40,781 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=124, Invalid=3782, Unknown=0, NotChecked=0, Total=3906 [2018-09-30 10:24:40,782 INFO L87 Difference]: Start difference. First operand 123 states and 123 transitions. Second operand 63 states. [2018-09-30 10:24:40,954 WARN L178 SmtUtils]: Spent 126.00 ms on a formula simplification. DAG size of input: 177 DAG size of output: 8 [2018-09-30 10:24:41,105 WARN L178 SmtUtils]: Spent 138.00 ms on a formula simplification. DAG size of input: 183 DAG size of output: 9 [2018-09-30 10:24:41,263 WARN L178 SmtUtils]: Spent 136.00 ms on a formula simplification. DAG size of input: 182 DAG size of output: 11 [2018-09-30 10:24:41,418 WARN L178 SmtUtils]: Spent 130.00 ms on a formula simplification. DAG size of input: 179 DAG size of output: 11 [2018-09-30 10:24:41,587 WARN L178 SmtUtils]: Spent 141.00 ms on a formula simplification. DAG size of input: 176 DAG size of output: 11 [2018-09-30 10:24:41,763 WARN L178 SmtUtils]: Spent 140.00 ms on a formula simplification. DAG size of input: 173 DAG size of output: 11 [2018-09-30 10:24:41,949 WARN L178 SmtUtils]: Spent 141.00 ms on a formula simplification. DAG size of input: 170 DAG size of output: 11 [2018-09-30 10:24:42,130 WARN L178 SmtUtils]: Spent 128.00 ms on a formula simplification. DAG size of input: 167 DAG size of output: 11 [2018-09-30 10:24:42,297 WARN L178 SmtUtils]: Spent 120.00 ms on a formula simplification. DAG size of input: 164 DAG size of output: 11 [2018-09-30 10:24:42,517 WARN L178 SmtUtils]: Spent 113.00 ms on a formula simplification. DAG size of input: 161 DAG size of output: 11 [2018-09-30 10:24:42,689 WARN L178 SmtUtils]: Spent 113.00 ms on a formula simplification. DAG size of input: 158 DAG size of output: 11 [2018-09-30 10:24:42,863 WARN L178 SmtUtils]: Spent 114.00 ms on a formula simplification. DAG size of input: 155 DAG size of output: 11 [2018-09-30 10:24:43,198 WARN L178 SmtUtils]: Spent 101.00 ms on a formula simplification. DAG size of input: 149 DAG size of output: 11 [2018-09-30 10:24:43,380 WARN L178 SmtUtils]: Spent 106.00 ms on a formula simplification. DAG size of input: 146 DAG size of output: 11 [2018-09-30 10:24:50,002 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:24:50,002 INFO L93 Difference]: Finished difference Result 129 states and 130 transitions. [2018-09-30 10:24:50,003 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 63 states. [2018-09-30 10:24:50,003 INFO L78 Accepts]: Start accepts. Automaton has 63 states. Word has length 122 [2018-09-30 10:24:50,003 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:24:50,004 INFO L225 Difference]: With dead ends: 129 [2018-09-30 10:24:50,004 INFO L226 Difference]: Without dead ends: 127 [2018-09-30 10:24:50,005 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 241 GetRequests, 121 SyntacticMatches, 0 SemanticMatches, 120 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1712 ImplicationChecksByTransitivity, 11.2s TimeCoverageRelationStatistics Valid=3781, Invalid=10981, Unknown=0, NotChecked=0, Total=14762 [2018-09-30 10:24:50,005 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states. [2018-09-30 10:24:50,010 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 127. [2018-09-30 10:24:50,011 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 127 states. [2018-09-30 10:24:50,011 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 127 transitions. [2018-09-30 10:24:50,011 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 127 transitions. Word has length 122 [2018-09-30 10:24:50,011 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:24:50,011 INFO L480 AbstractCegarLoop]: Abstraction has 127 states and 127 transitions. [2018-09-30 10:24:50,011 INFO L481 AbstractCegarLoop]: Interpolant automaton has 63 states. [2018-09-30 10:24:50,012 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 127 transitions. [2018-09-30 10:24:50,012 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 127 [2018-09-30 10:24:50,012 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:24:50,012 INFO L375 BasicCegarLoop]: trace histogram [62, 61, 1, 1, 1] [2018-09-30 10:24:50,012 INFO L423 AbstractCegarLoop]: === Iteration 32 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:24:50,013 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:24:50,013 INFO L82 PathProgramCache]: Analyzing trace with hash -635570663, now seen corresponding path program 31 times [2018-09-30 10:24:50,013 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:24:50,013 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:24:50,013 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:24:50,014 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:24:50,014 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:24:50,197 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:24:52,501 INFO L134 CoverageAnalysis]: Checked inductivity of 3782 backedges. 0 proven. 3782 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:24:52,501 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:24:52,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 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-09-30 10:24:52,508 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-30 10:24:52,842 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:24:53,039 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:24:53,144 INFO L134 CoverageAnalysis]: Checked inductivity of 3782 backedges. 0 proven. 3782 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:24:53,165 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:24:53,166 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [63, 63] total 64 [2018-09-30 10:24:53,166 INFO L459 AbstractCegarLoop]: Interpolant automaton has 65 states [2018-09-30 10:24:53,166 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 65 interpolants. [2018-09-30 10:24:53,167 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=128, Invalid=4032, Unknown=0, NotChecked=0, Total=4160 [2018-09-30 10:24:53,167 INFO L87 Difference]: Start difference. First operand 127 states and 127 transitions. Second operand 65 states. [2018-09-30 10:24:53,340 WARN L178 SmtUtils]: Spent 138.00 ms on a formula simplification. DAG size of input: 183 DAG size of output: 8 [2018-09-30 10:24:53,504 WARN L178 SmtUtils]: Spent 151.00 ms on a formula simplification. DAG size of input: 189 DAG size of output: 9 [2018-09-30 10:24:53,675 WARN L178 SmtUtils]: Spent 151.00 ms on a formula simplification. DAG size of input: 188 DAG size of output: 11 [2018-09-30 10:24:53,847 WARN L178 SmtUtils]: Spent 147.00 ms on a formula simplification. DAG size of input: 185 DAG size of output: 11 [2018-09-30 10:24:54,021 WARN L178 SmtUtils]: Spent 143.00 ms on a formula simplification. DAG size of input: 182 DAG size of output: 11 [2018-09-30 10:24:54,182 WARN L178 SmtUtils]: Spent 125.00 ms on a formula simplification. DAG size of input: 179 DAG size of output: 11 [2018-09-30 10:24:54,354 WARN L178 SmtUtils]: Spent 129.00 ms on a formula simplification. DAG size of input: 176 DAG size of output: 11 [2018-09-30 10:24:54,530 WARN L178 SmtUtils]: Spent 127.00 ms on a formula simplification. DAG size of input: 173 DAG size of output: 11 [2018-09-30 10:24:54,702 WARN L178 SmtUtils]: Spent 122.00 ms on a formula simplification. DAG size of input: 170 DAG size of output: 11 [2018-09-30 10:24:54,882 WARN L178 SmtUtils]: Spent 126.00 ms on a formula simplification. DAG size of input: 167 DAG size of output: 11 [2018-09-30 10:24:55,056 WARN L178 SmtUtils]: Spent 116.00 ms on a formula simplification. DAG size of input: 164 DAG size of output: 11 [2018-09-30 10:24:55,229 WARN L178 SmtUtils]: Spent 112.00 ms on a formula simplification. DAG size of input: 161 DAG size of output: 11 [2018-09-30 10:24:55,402 WARN L178 SmtUtils]: Spent 107.00 ms on a formula simplification. DAG size of input: 158 DAG size of output: 11 [2018-09-30 10:24:55,587 WARN L178 SmtUtils]: Spent 112.00 ms on a formula simplification. DAG size of input: 155 DAG size of output: 11 [2018-09-30 10:24:55,777 WARN L178 SmtUtils]: Spent 109.00 ms on a formula simplification. DAG size of input: 152 DAG size of output: 11 [2018-09-30 10:25:03,035 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:25:03,035 INFO L93 Difference]: Finished difference Result 133 states and 134 transitions. [2018-09-30 10:25:03,035 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 65 states. [2018-09-30 10:25:03,035 INFO L78 Accepts]: Start accepts. Automaton has 65 states. Word has length 126 [2018-09-30 10:25:03,036 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:25:03,037 INFO L225 Difference]: With dead ends: 133 [2018-09-30 10:25:03,037 INFO L226 Difference]: Without dead ends: 131 [2018-09-30 10:25:03,038 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 249 GetRequests, 125 SyntacticMatches, 0 SemanticMatches, 124 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1831 ImplicationChecksByTransitivity, 11.9s TimeCoverageRelationStatistics Valid=4031, Invalid=11719, Unknown=0, NotChecked=0, Total=15750 [2018-09-30 10:25:03,038 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 131 states. [2018-09-30 10:25:03,044 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 131 to 131. [2018-09-30 10:25:03,045 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 131 states. [2018-09-30 10:25:03,045 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 131 states to 131 states and 131 transitions. [2018-09-30 10:25:03,045 INFO L78 Accepts]: Start accepts. Automaton has 131 states and 131 transitions. Word has length 126 [2018-09-30 10:25:03,046 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:25:03,046 INFO L480 AbstractCegarLoop]: Abstraction has 131 states and 131 transitions. [2018-09-30 10:25:03,046 INFO L481 AbstractCegarLoop]: Interpolant automaton has 65 states. [2018-09-30 10:25:03,046 INFO L276 IsEmpty]: Start isEmpty. Operand 131 states and 131 transitions. [2018-09-30 10:25:03,046 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 131 [2018-09-30 10:25:03,047 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:25:03,047 INFO L375 BasicCegarLoop]: trace histogram [64, 63, 1, 1, 1] [2018-09-30 10:25:03,047 INFO L423 AbstractCegarLoop]: === Iteration 33 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:25:03,047 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:25:03,047 INFO L82 PathProgramCache]: Analyzing trace with hash 311419405, now seen corresponding path program 32 times [2018-09-30 10:25:03,047 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:25:03,048 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:25:03,048 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:25:03,048 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-30 10:25:03,049 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:25:03,342 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:25:05,395 INFO L134 CoverageAnalysis]: Checked inductivity of 4032 backedges. 0 proven. 4032 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:25:05,395 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:25:05,395 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-09-30 10:25:05,404 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-09-30 10:25:05,776 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-09-30 10:25:05,776 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:25:05,996 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:25:06,183 INFO L134 CoverageAnalysis]: Checked inductivity of 4032 backedges. 0 proven. 4032 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:25:06,203 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:25:06,203 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [65, 65] total 66 [2018-09-30 10:25:06,203 INFO L459 AbstractCegarLoop]: Interpolant automaton has 67 states [2018-09-30 10:25:06,203 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 67 interpolants. [2018-09-30 10:25:06,204 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=132, Invalid=4290, Unknown=0, NotChecked=0, Total=4422 [2018-09-30 10:25:06,204 INFO L87 Difference]: Start difference. First operand 131 states and 131 transitions. Second operand 67 states. [2018-09-30 10:25:06,409 WARN L178 SmtUtils]: Spent 137.00 ms on a formula simplification. DAG size of input: 189 DAG size of output: 8 [2018-09-30 10:25:06,568 WARN L178 SmtUtils]: Spent 145.00 ms on a formula simplification. DAG size of input: 195 DAG size of output: 9 [2018-09-30 10:25:06,738 WARN L178 SmtUtils]: Spent 151.00 ms on a formula simplification. DAG size of input: 194 DAG size of output: 11 [2018-09-30 10:25:06,913 WARN L178 SmtUtils]: Spent 150.00 ms on a formula simplification. DAG size of input: 191 DAG size of output: 11 [2018-09-30 10:25:07,094 WARN L178 SmtUtils]: Spent 147.00 ms on a formula simplification. DAG size of input: 188 DAG size of output: 11 [2018-09-30 10:25:07,261 WARN L178 SmtUtils]: Spent 130.00 ms on a formula simplification. DAG size of input: 185 DAG size of output: 11 [2018-09-30 10:25:07,457 WARN L178 SmtUtils]: Spent 149.00 ms on a formula simplification. DAG size of input: 182 DAG size of output: 11 [2018-09-30 10:25:07,650 WARN L178 SmtUtils]: Spent 149.00 ms on a formula simplification. DAG size of input: 179 DAG size of output: 11 [2018-09-30 10:25:07,850 WARN L178 SmtUtils]: Spent 141.00 ms on a formula simplification. DAG size of input: 176 DAG size of output: 11 [2018-09-30 10:25:08,034 WARN L178 SmtUtils]: Spent 127.00 ms on a formula simplification. DAG size of input: 173 DAG size of output: 11 [2018-09-30 10:25:08,227 WARN L178 SmtUtils]: Spent 132.00 ms on a formula simplification. DAG size of input: 170 DAG size of output: 11 [2018-09-30 10:25:08,408 WARN L178 SmtUtils]: Spent 115.00 ms on a formula simplification. DAG size of input: 167 DAG size of output: 11 [2018-09-30 10:25:08,595 WARN L178 SmtUtils]: Spent 118.00 ms on a formula simplification. DAG size of input: 164 DAG size of output: 11 [2018-09-30 10:25:08,774 WARN L178 SmtUtils]: Spent 108.00 ms on a formula simplification. DAG size of input: 161 DAG size of output: 11 [2018-09-30 10:25:08,972 WARN L178 SmtUtils]: Spent 110.00 ms on a formula simplification. DAG size of input: 158 DAG size of output: 11 [2018-09-30 10:25:13,282 WARN L178 SmtUtils]: Spent 116.00 ms on a formula simplification. DAG size of input: 92 DAG size of output: 11 [2018-09-30 10:25:16,826 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:25:16,827 INFO L93 Difference]: Finished difference Result 137 states and 138 transitions. [2018-09-30 10:25:16,827 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 67 states. [2018-09-30 10:25:16,827 INFO L78 Accepts]: Start accepts. Automaton has 67 states. Word has length 130 [2018-09-30 10:25:16,828 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:25:16,828 INFO L225 Difference]: With dead ends: 137 [2018-09-30 10:25:16,829 INFO L226 Difference]: Without dead ends: 135 [2018-09-30 10:25:16,830 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 257 GetRequests, 129 SyntacticMatches, 0 SemanticMatches, 128 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1954 ImplicationChecksByTransitivity, 12.4s TimeCoverageRelationStatistics Valid=4289, Invalid=12481, Unknown=0, NotChecked=0, Total=16770 [2018-09-30 10:25:16,830 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 135 states. [2018-09-30 10:25:16,836 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 135 to 135. [2018-09-30 10:25:16,836 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 135 states. [2018-09-30 10:25:16,837 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 135 states to 135 states and 135 transitions. [2018-09-30 10:25:16,837 INFO L78 Accepts]: Start accepts. Automaton has 135 states and 135 transitions. Word has length 130 [2018-09-30 10:25:16,837 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:25:16,837 INFO L480 AbstractCegarLoop]: Abstraction has 135 states and 135 transitions. [2018-09-30 10:25:16,837 INFO L481 AbstractCegarLoop]: Interpolant automaton has 67 states. [2018-09-30 10:25:16,838 INFO L276 IsEmpty]: Start isEmpty. Operand 135 states and 135 transitions. [2018-09-30 10:25:16,838 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 135 [2018-09-30 10:25:16,838 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:25:16,838 INFO L375 BasicCegarLoop]: trace histogram [66, 65, 1, 1, 1] [2018-09-30 10:25:16,838 INFO L423 AbstractCegarLoop]: === Iteration 34 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:25:16,838 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:25:16,839 INFO L82 PathProgramCache]: Analyzing trace with hash -1484606463, now seen corresponding path program 33 times [2018-09-30 10:25:16,839 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:25:16,839 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:25:16,839 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:25:16,839 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:25:16,839 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:25:17,130 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:25:20,239 INFO L134 CoverageAnalysis]: Checked inductivity of 4290 backedges. 0 proven. 4290 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:25:20,239 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:25:20,239 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-09-30 10:25:20,246 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-09-30 10:25:20,316 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 66 check-sat command(s) [2018-09-30 10:25:20,316 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:25:20,323 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:25:20,562 INFO L134 CoverageAnalysis]: Checked inductivity of 4290 backedges. 0 proven. 4290 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:25:20,593 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:25:20,594 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [67, 67] total 68 [2018-09-30 10:25:20,594 INFO L459 AbstractCegarLoop]: Interpolant automaton has 69 states [2018-09-30 10:25:20,594 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 69 interpolants. [2018-09-30 10:25:20,595 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=136, Invalid=4556, Unknown=0, NotChecked=0, Total=4692 [2018-09-30 10:25:20,595 INFO L87 Difference]: Start difference. First operand 135 states and 135 transitions. Second operand 69 states. [2018-09-30 10:25:20,855 WARN L178 SmtUtils]: Spent 155.00 ms on a formula simplification. DAG size of input: 195 DAG size of output: 8 [2018-09-30 10:25:21,037 WARN L178 SmtUtils]: Spent 162.00 ms on a formula simplification. DAG size of input: 201 DAG size of output: 9 [2018-09-30 10:25:21,217 WARN L178 SmtUtils]: Spent 160.00 ms on a formula simplification. DAG size of input: 200 DAG size of output: 11 [2018-09-30 10:25:21,411 WARN L178 SmtUtils]: Spent 168.00 ms on a formula simplification. DAG size of input: 197 DAG size of output: 11 [2018-09-30 10:25:21,603 WARN L178 SmtUtils]: Spent 162.00 ms on a formula simplification. DAG size of input: 194 DAG size of output: 11 [2018-09-30 10:25:21,790 WARN L178 SmtUtils]: Spent 147.00 ms on a formula simplification. DAG size of input: 191 DAG size of output: 11 [2018-09-30 10:25:21,980 WARN L178 SmtUtils]: Spent 150.00 ms on a formula simplification. DAG size of input: 188 DAG size of output: 11 [2018-09-30 10:25:22,176 WARN L178 SmtUtils]: Spent 146.00 ms on a formula simplification. DAG size of input: 185 DAG size of output: 11 [2018-09-30 10:25:22,372 WARN L178 SmtUtils]: Spent 142.00 ms on a formula simplification. DAG size of input: 182 DAG size of output: 11 [2018-09-30 10:25:22,568 WARN L178 SmtUtils]: Spent 141.00 ms on a formula simplification. DAG size of input: 179 DAG size of output: 11 [2018-09-30 10:25:22,784 WARN L178 SmtUtils]: Spent 148.00 ms on a formula simplification. DAG size of input: 176 DAG size of output: 11 [2018-09-30 10:25:23,008 WARN L178 SmtUtils]: Spent 148.00 ms on a formula simplification. DAG size of input: 173 DAG size of output: 11 [2018-09-30 10:25:23,215 WARN L178 SmtUtils]: Spent 136.00 ms on a formula simplification. DAG size of input: 170 DAG size of output: 11 [2018-09-30 10:25:23,409 WARN L178 SmtUtils]: Spent 122.00 ms on a formula simplification. DAG size of input: 167 DAG size of output: 11 [2018-09-30 10:25:23,610 WARN L178 SmtUtils]: Spent 115.00 ms on a formula simplification. DAG size of input: 164 DAG size of output: 11 [2018-09-30 10:25:23,819 WARN L178 SmtUtils]: Spent 109.00 ms on a formula simplification. DAG size of input: 161 DAG size of output: 11 [2018-09-30 10:25:24,024 WARN L178 SmtUtils]: Spent 103.00 ms on a formula simplification. DAG size of input: 158 DAG size of output: 11 [2018-09-30 10:25:24,238 WARN L178 SmtUtils]: Spent 109.00 ms on a formula simplification. DAG size of input: 155 DAG size of output: 11 [2018-09-30 10:25:24,458 WARN L178 SmtUtils]: Spent 104.00 ms on a formula simplification. DAG size of input: 152 DAG size of output: 11 [2018-09-30 10:25:24,663 WARN L178 SmtUtils]: Spent 105.00 ms on a formula simplification. DAG size of input: 149 DAG size of output: 11 [2018-09-30 10:25:24,878 WARN L178 SmtUtils]: Spent 107.00 ms on a formula simplification. DAG size of input: 146 DAG size of output: 11 [2018-09-30 10:25:25,090 WARN L178 SmtUtils]: Spent 100.00 ms on a formula simplification. DAG size of input: 143 DAG size of output: 11 [2018-09-30 10:25:32,193 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:25:32,193 INFO L93 Difference]: Finished difference Result 141 states and 142 transitions. [2018-09-30 10:25:32,194 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 69 states. [2018-09-30 10:25:32,194 INFO L78 Accepts]: Start accepts. Automaton has 69 states. Word has length 134 [2018-09-30 10:25:32,194 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:25:32,195 INFO L225 Difference]: With dead ends: 141 [2018-09-30 10:25:32,195 INFO L226 Difference]: Without dead ends: 139 [2018-09-30 10:25:32,196 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 265 GetRequests, 133 SyntacticMatches, 0 SemanticMatches, 132 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2081 ImplicationChecksByTransitivity, 14.5s TimeCoverageRelationStatistics Valid=4555, Invalid=13267, Unknown=0, NotChecked=0, Total=17822 [2018-09-30 10:25:32,197 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 139 states. [2018-09-30 10:25:32,203 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 139 to 139. [2018-09-30 10:25:32,203 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 139 states. [2018-09-30 10:25:32,203 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 139 transitions. [2018-09-30 10:25:32,203 INFO L78 Accepts]: Start accepts. Automaton has 139 states and 139 transitions. Word has length 134 [2018-09-30 10:25:32,203 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:25:32,204 INFO L480 AbstractCegarLoop]: Abstraction has 139 states and 139 transitions. [2018-09-30 10:25:32,204 INFO L481 AbstractCegarLoop]: Interpolant automaton has 69 states. [2018-09-30 10:25:32,204 INFO L276 IsEmpty]: Start isEmpty. Operand 139 states and 139 transitions. [2018-09-30 10:25:32,204 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 139 [2018-09-30 10:25:32,204 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:25:32,205 INFO L375 BasicCegarLoop]: trace histogram [68, 67, 1, 1, 1] [2018-09-30 10:25:32,205 INFO L423 AbstractCegarLoop]: === Iteration 35 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:25:32,205 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:25:32,205 INFO L82 PathProgramCache]: Analyzing trace with hash 34827253, now seen corresponding path program 34 times [2018-09-30 10:25:32,205 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:25:32,205 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:25:32,206 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:25:32,206 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:25:32,206 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:25:32,437 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:25:35,079 INFO L134 CoverageAnalysis]: Checked inductivity of 4556 backedges. 0 proven. 4556 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:25:35,080 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:25:35,080 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-09-30 10:25:35,088 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-09-30 10:25:35,129 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-09-30 10:25:35,130 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:25:35,133 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:25:35,273 INFO L134 CoverageAnalysis]: Checked inductivity of 4556 backedges. 0 proven. 4556 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:25:35,304 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:25:35,304 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [69, 69] total 70 [2018-09-30 10:25:35,304 INFO L459 AbstractCegarLoop]: Interpolant automaton has 71 states [2018-09-30 10:25:35,305 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 71 interpolants. [2018-09-30 10:25:35,305 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=140, Invalid=4830, Unknown=0, NotChecked=0, Total=4970 [2018-09-30 10:25:35,305 INFO L87 Difference]: Start difference. First operand 139 states and 139 transitions. Second operand 71 states. [2018-09-30 10:25:35,570 WARN L178 SmtUtils]: Spent 160.00 ms on a formula simplification. DAG size of input: 201 DAG size of output: 8 [2018-09-30 10:25:35,763 WARN L178 SmtUtils]: Spent 180.00 ms on a formula simplification. DAG size of input: 207 DAG size of output: 9 [2018-09-30 10:25:35,960 WARN L178 SmtUtils]: Spent 173.00 ms on a formula simplification. DAG size of input: 206 DAG size of output: 11 [2018-09-30 10:25:36,157 WARN L178 SmtUtils]: Spent 170.00 ms on a formula simplification. DAG size of input: 203 DAG size of output: 11 [2018-09-30 10:25:36,360 WARN L178 SmtUtils]: Spent 169.00 ms on a formula simplification. DAG size of input: 200 DAG size of output: 11 [2018-09-30 10:25:36,554 WARN L178 SmtUtils]: Spent 156.00 ms on a formula simplification. DAG size of input: 197 DAG size of output: 11 [2018-09-30 10:25:36,747 WARN L178 SmtUtils]: Spent 147.00 ms on a formula simplification. DAG size of input: 194 DAG size of output: 11 [2018-09-30 10:25:36,945 WARN L178 SmtUtils]: Spent 148.00 ms on a formula simplification. DAG size of input: 191 DAG size of output: 11 [2018-09-30 10:25:37,149 WARN L178 SmtUtils]: Spent 149.00 ms on a formula simplification. DAG size of input: 188 DAG size of output: 11 [2018-09-30 10:25:37,354 WARN L178 SmtUtils]: Spent 145.00 ms on a formula simplification. DAG size of input: 185 DAG size of output: 11 [2018-09-30 10:25:37,561 WARN L178 SmtUtils]: Spent 139.00 ms on a formula simplification. DAG size of input: 182 DAG size of output: 11 [2018-09-30 10:25:37,775 WARN L178 SmtUtils]: Spent 140.00 ms on a formula simplification. DAG size of input: 179 DAG size of output: 11 [2018-09-30 10:25:37,975 WARN L178 SmtUtils]: Spent 125.00 ms on a formula simplification. DAG size of input: 176 DAG size of output: 11 [2018-09-30 10:25:38,200 WARN L178 SmtUtils]: Spent 136.00 ms on a formula simplification. DAG size of input: 173 DAG size of output: 11 [2018-09-30 10:25:38,431 WARN L178 SmtUtils]: Spent 137.00 ms on a formula simplification. DAG size of input: 170 DAG size of output: 11 [2018-09-30 10:25:38,652 WARN L178 SmtUtils]: Spent 119.00 ms on a formula simplification. DAG size of input: 167 DAG size of output: 11 [2018-09-30 10:25:38,870 WARN L178 SmtUtils]: Spent 115.00 ms on a formula simplification. DAG size of input: 164 DAG size of output: 11 [2018-09-30 10:25:39,095 WARN L178 SmtUtils]: Spent 116.00 ms on a formula simplification. DAG size of input: 161 DAG size of output: 11 [2018-09-30 10:25:39,320 WARN L178 SmtUtils]: Spent 110.00 ms on a formula simplification. DAG size of input: 158 DAG size of output: 11 [2018-09-30 10:25:39,553 WARN L178 SmtUtils]: Spent 117.00 ms on a formula simplification. DAG size of input: 155 DAG size of output: 11 [2018-09-30 10:25:39,776 WARN L178 SmtUtils]: Spent 109.00 ms on a formula simplification. DAG size of input: 152 DAG size of output: 11 [2018-09-30 10:25:39,994 WARN L178 SmtUtils]: Spent 102.00 ms on a formula simplification. DAG size of input: 149 DAG size of output: 11 [2018-09-30 10:25:40,213 WARN L178 SmtUtils]: Spent 103.00 ms on a formula simplification. DAG size of input: 146 DAG size of output: 11 [2018-09-30 10:25:47,775 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:25:47,775 INFO L93 Difference]: Finished difference Result 145 states and 146 transitions. [2018-09-30 10:25:47,776 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 71 states. [2018-09-30 10:25:47,776 INFO L78 Accepts]: Start accepts. Automaton has 71 states. Word has length 138 [2018-09-30 10:25:47,776 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:25:47,777 INFO L225 Difference]: With dead ends: 145 [2018-09-30 10:25:47,777 INFO L226 Difference]: Without dead ends: 143 [2018-09-30 10:25:47,778 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 273 GetRequests, 137 SyntacticMatches, 0 SemanticMatches, 136 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2212 ImplicationChecksByTransitivity, 14.8s TimeCoverageRelationStatistics Valid=4829, Invalid=14077, Unknown=0, NotChecked=0, Total=18906 [2018-09-30 10:25:47,779 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 143 states. [2018-09-30 10:25:47,786 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 143 to 143. [2018-09-30 10:25:47,787 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 143 states. [2018-09-30 10:25:47,787 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 143 states to 143 states and 143 transitions. [2018-09-30 10:25:47,787 INFO L78 Accepts]: Start accepts. Automaton has 143 states and 143 transitions. Word has length 138 [2018-09-30 10:25:47,788 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:25:47,788 INFO L480 AbstractCegarLoop]: Abstraction has 143 states and 143 transitions. [2018-09-30 10:25:47,788 INFO L481 AbstractCegarLoop]: Interpolant automaton has 71 states. [2018-09-30 10:25:47,788 INFO L276 IsEmpty]: Start isEmpty. Operand 143 states and 143 transitions. [2018-09-30 10:25:47,789 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 143 [2018-09-30 10:25:47,789 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:25:47,789 INFO L375 BasicCegarLoop]: trace histogram [70, 69, 1, 1, 1] [2018-09-30 10:25:47,789 INFO L423 AbstractCegarLoop]: === Iteration 36 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:25:47,789 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:25:47,789 INFO L82 PathProgramCache]: Analyzing trace with hash -1260451351, now seen corresponding path program 35 times [2018-09-30 10:25:47,789 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:25:47,790 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:25:47,790 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:25:47,790 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:25:47,790 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:25:48,029 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:25:50,687 INFO L134 CoverageAnalysis]: Checked inductivity of 4830 backedges. 0 proven. 4830 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:25:50,688 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:25:50,688 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-09-30 10:25:50,694 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-09-30 10:25:51,111 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 70 check-sat command(s) [2018-09-30 10:25:51,111 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:25:51,170 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:25:51,294 INFO L134 CoverageAnalysis]: Checked inductivity of 4830 backedges. 0 proven. 4830 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:25:51,313 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:25:51,313 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [71, 71] total 72 [2018-09-30 10:25:51,314 INFO L459 AbstractCegarLoop]: Interpolant automaton has 73 states [2018-09-30 10:25:51,314 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 73 interpolants. [2018-09-30 10:25:51,314 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=144, Invalid=5112, Unknown=0, NotChecked=0, Total=5256 [2018-09-30 10:25:51,314 INFO L87 Difference]: Start difference. First operand 143 states and 143 transitions. Second operand 73 states. [2018-09-30 10:25:51,505 WARN L178 SmtUtils]: Spent 157.00 ms on a formula simplification. DAG size of input: 207 DAG size of output: 8 [2018-09-30 10:25:51,693 WARN L178 SmtUtils]: Spent 173.00 ms on a formula simplification. DAG size of input: 213 DAG size of output: 9 [2018-09-30 10:25:51,885 WARN L178 SmtUtils]: Spent 170.00 ms on a formula simplification. DAG size of input: 212 DAG size of output: 11 [2018-09-30 10:25:52,082 WARN L178 SmtUtils]: Spent 167.00 ms on a formula simplification. DAG size of input: 209 DAG size of output: 11 [2018-09-30 10:25:52,291 WARN L178 SmtUtils]: Spent 170.00 ms on a formula simplification. DAG size of input: 206 DAG size of output: 11 [2018-09-30 10:25:52,487 WARN L178 SmtUtils]: Spent 153.00 ms on a formula simplification. DAG size of input: 203 DAG size of output: 11 [2018-09-30 10:25:52,696 WARN L178 SmtUtils]: Spent 163.00 ms on a formula simplification. DAG size of input: 200 DAG size of output: 11 [2018-09-30 10:25:52,891 WARN L178 SmtUtils]: Spent 147.00 ms on a formula simplification. DAG size of input: 197 DAG size of output: 11 [2018-09-30 10:25:53,102 WARN L178 SmtUtils]: Spent 154.00 ms on a formula simplification. DAG size of input: 194 DAG size of output: 11 [2018-09-30 10:25:53,322 WARN L178 SmtUtils]: Spent 157.00 ms on a formula simplification. DAG size of input: 191 DAG size of output: 11 [2018-09-30 10:25:53,556 WARN L178 SmtUtils]: Spent 160.00 ms on a formula simplification. DAG size of input: 188 DAG size of output: 11 [2018-09-30 10:25:53,787 WARN L178 SmtUtils]: Spent 150.00 ms on a formula simplification. DAG size of input: 185 DAG size of output: 11 [2018-09-30 10:25:54,006 WARN L178 SmtUtils]: Spent 144.00 ms on a formula simplification. DAG size of input: 182 DAG size of output: 11 [2018-09-30 10:25:54,207 WARN L178 SmtUtils]: Spent 126.00 ms on a formula simplification. DAG size of input: 179 DAG size of output: 11 [2018-09-30 10:25:54,431 WARN L178 SmtUtils]: Spent 131.00 ms on a formula simplification. DAG size of input: 176 DAG size of output: 11 [2018-09-30 10:25:54,654 WARN L178 SmtUtils]: Spent 115.00 ms on a formula simplification. DAG size of input: 173 DAG size of output: 11 [2018-09-30 10:25:54,874 WARN L178 SmtUtils]: Spent 113.00 ms on a formula simplification. DAG size of input: 170 DAG size of output: 11 [2018-09-30 10:25:55,098 WARN L178 SmtUtils]: Spent 115.00 ms on a formula simplification. DAG size of input: 167 DAG size of output: 11 [2018-09-30 10:25:55,327 WARN L178 SmtUtils]: Spent 113.00 ms on a formula simplification. DAG size of input: 164 DAG size of output: 11 [2018-09-30 10:25:55,562 WARN L178 SmtUtils]: Spent 122.00 ms on a formula simplification. DAG size of input: 161 DAG size of output: 11 [2018-09-30 10:25:55,793 WARN L178 SmtUtils]: Spent 108.00 ms on a formula simplification. DAG size of input: 158 DAG size of output: 11 [2018-09-30 10:25:56,025 WARN L178 SmtUtils]: Spent 104.00 ms on a formula simplification. DAG size of input: 155 DAG size of output: 11 [2018-09-30 10:25:56,253 WARN L178 SmtUtils]: Spent 101.00 ms on a formula simplification. DAG size of input: 152 DAG size of output: 11 [2018-09-30 10:26:04,644 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:26:04,644 INFO L93 Difference]: Finished difference Result 149 states and 150 transitions. [2018-09-30 10:26:04,645 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 73 states. [2018-09-30 10:26:04,645 INFO L78 Accepts]: Start accepts. Automaton has 73 states. Word has length 142 [2018-09-30 10:26:04,645 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:26:04,647 INFO L225 Difference]: With dead ends: 149 [2018-09-30 10:26:04,647 INFO L226 Difference]: Without dead ends: 147 [2018-09-30 10:26:04,648 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 281 GetRequests, 141 SyntacticMatches, 0 SemanticMatches, 140 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2347 ImplicationChecksByTransitivity, 15.7s TimeCoverageRelationStatistics Valid=5111, Invalid=14911, Unknown=0, NotChecked=0, Total=20022 [2018-09-30 10:26:04,648 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 147 states. [2018-09-30 10:26:04,656 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 147 to 147. [2018-09-30 10:26:04,656 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 147 states. [2018-09-30 10:26:04,657 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 147 states to 147 states and 147 transitions. [2018-09-30 10:26:04,657 INFO L78 Accepts]: Start accepts. Automaton has 147 states and 147 transitions. Word has length 142 [2018-09-30 10:26:04,657 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:26:04,657 INFO L480 AbstractCegarLoop]: Abstraction has 147 states and 147 transitions. [2018-09-30 10:26:04,657 INFO L481 AbstractCegarLoop]: Interpolant automaton has 73 states. [2018-09-30 10:26:04,658 INFO L276 IsEmpty]: Start isEmpty. Operand 147 states and 147 transitions. [2018-09-30 10:26:04,658 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 147 [2018-09-30 10:26:04,658 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:26:04,658 INFO L375 BasicCegarLoop]: trace histogram [72, 71, 1, 1, 1] [2018-09-30 10:26:04,659 INFO L423 AbstractCegarLoop]: === Iteration 37 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:26:04,659 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:26:04,659 INFO L82 PathProgramCache]: Analyzing trace with hash -1140683299, now seen corresponding path program 36 times [2018-09-30 10:26:04,659 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:26:04,659 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:26:04,660 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:26:04,660 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:26:04,660 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:26:05,083 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:26:08,052 INFO L134 CoverageAnalysis]: Checked inductivity of 5112 backedges. 0 proven. 5112 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:26:08,052 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:26:08,052 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-09-30 10:26:08,059 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-09-30 10:26:08,151 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 72 check-sat command(s) [2018-09-30 10:26:08,152 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-30 10:26:08,161 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:26:08,312 INFO L134 CoverageAnalysis]: Checked inductivity of 5112 backedges. 0 proven. 5112 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:26:08,332 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:26:08,332 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [73, 73] total 74 [2018-09-30 10:26:08,332 INFO L459 AbstractCegarLoop]: Interpolant automaton has 75 states [2018-09-30 10:26:08,333 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 75 interpolants. [2018-09-30 10:26:08,333 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=148, Invalid=5402, Unknown=0, NotChecked=0, Total=5550 [2018-09-30 10:26:08,333 INFO L87 Difference]: Start difference. First operand 147 states and 147 transitions. Second operand 75 states. [2018-09-30 10:26:08,644 WARN L178 SmtUtils]: Spent 169.00 ms on a formula simplification. DAG size of input: 213 DAG size of output: 8 [2018-09-30 10:26:08,861 WARN L178 SmtUtils]: Spent 202.00 ms on a formula simplification. DAG size of input: 219 DAG size of output: 9 [2018-09-30 10:26:09,082 WARN L178 SmtUtils]: Spent 202.00 ms on a formula simplification. DAG size of input: 218 DAG size of output: 11 [2018-09-30 10:26:09,290 WARN L178 SmtUtils]: Spent 179.00 ms on a formula simplification. DAG size of input: 215 DAG size of output: 11 [2018-09-30 10:26:09,501 WARN L178 SmtUtils]: Spent 174.00 ms on a formula simplification. DAG size of input: 212 DAG size of output: 11 [2018-09-30 10:26:09,704 WARN L178 SmtUtils]: Spent 164.00 ms on a formula simplification. DAG size of input: 209 DAG size of output: 11 [2018-09-30 10:26:09,914 WARN L178 SmtUtils]: Spent 165.00 ms on a formula simplification. DAG size of input: 206 DAG size of output: 11 [2018-09-30 10:26:10,124 WARN L178 SmtUtils]: Spent 156.00 ms on a formula simplification. DAG size of input: 203 DAG size of output: 11 [2018-09-30 10:26:10,338 WARN L178 SmtUtils]: Spent 158.00 ms on a formula simplification. DAG size of input: 200 DAG size of output: 11 [2018-09-30 10:26:10,561 WARN L178 SmtUtils]: Spent 160.00 ms on a formula simplification. DAG size of input: 197 DAG size of output: 11 [2018-09-30 10:26:10,781 WARN L178 SmtUtils]: Spent 146.00 ms on a formula simplification. DAG size of input: 194 DAG size of output: 11 [2018-09-30 10:26:11,009 WARN L178 SmtUtils]: Spent 149.00 ms on a formula simplification. DAG size of input: 191 DAG size of output: 11 [2018-09-30 10:26:11,231 WARN L178 SmtUtils]: Spent 139.00 ms on a formula simplification. DAG size of input: 188 DAG size of output: 11 [2018-09-30 10:26:11,453 WARN L178 SmtUtils]: Spent 139.00 ms on a formula simplification. DAG size of input: 185 DAG size of output: 11 [2018-09-30 10:26:11,692 WARN L178 SmtUtils]: Spent 137.00 ms on a formula simplification. DAG size of input: 182 DAG size of output: 11 [2018-09-30 10:26:11,931 WARN L178 SmtUtils]: Spent 130.00 ms on a formula simplification. DAG size of input: 179 DAG size of output: 11 [2018-09-30 10:26:12,160 WARN L178 SmtUtils]: Spent 118.00 ms on a formula simplification. DAG size of input: 176 DAG size of output: 11 [2018-09-30 10:26:12,388 WARN L178 SmtUtils]: Spent 121.00 ms on a formula simplification. DAG size of input: 173 DAG size of output: 11 [2018-09-30 10:26:12,625 WARN L178 SmtUtils]: Spent 116.00 ms on a formula simplification. DAG size of input: 170 DAG size of output: 11 [2018-09-30 10:26:12,879 WARN L178 SmtUtils]: Spent 124.00 ms on a formula simplification. DAG size of input: 167 DAG size of output: 11 [2018-09-30 10:26:13,128 WARN L178 SmtUtils]: Spent 116.00 ms on a formula simplification. DAG size of input: 164 DAG size of output: 11 [2018-09-30 10:26:13,361 WARN L178 SmtUtils]: Spent 106.00 ms on a formula simplification. DAG size of input: 161 DAG size of output: 11 [2018-09-30 10:26:13,603 WARN L178 SmtUtils]: Spent 104.00 ms on a formula simplification. DAG size of input: 158 DAG size of output: 11 [2018-09-30 10:26:13,841 WARN L178 SmtUtils]: Spent 103.00 ms on a formula simplification. DAG size of input: 155 DAG size of output: 11 [2018-09-30 10:26:14,105 WARN L178 SmtUtils]: Spent 115.00 ms on a formula simplification. DAG size of input: 152 DAG size of output: 11 [2018-09-30 10:26:14,339 WARN L178 SmtUtils]: Spent 104.00 ms on a formula simplification. DAG size of input: 149 DAG size of output: 11 [2018-09-30 10:26:22,696 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:26:22,696 INFO L93 Difference]: Finished difference Result 153 states and 154 transitions. [2018-09-30 10:26:22,696 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 75 states. [2018-09-30 10:26:22,697 INFO L78 Accepts]: Start accepts. Automaton has 75 states. Word has length 146 [2018-09-30 10:26:22,697 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:26:22,698 INFO L225 Difference]: With dead ends: 153 [2018-09-30 10:26:22,698 INFO L226 Difference]: Without dead ends: 151 [2018-09-30 10:26:22,700 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 289 GetRequests, 145 SyntacticMatches, 0 SemanticMatches, 144 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2486 ImplicationChecksByTransitivity, 17.0s TimeCoverageRelationStatistics Valid=5401, Invalid=15769, Unknown=0, NotChecked=0, Total=21170 [2018-09-30 10:26:22,700 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 151 states. [2018-09-30 10:26:22,708 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 151 to 151. [2018-09-30 10:26:22,709 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 151 states. [2018-09-30 10:26:22,709 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 151 states to 151 states and 151 transitions. [2018-09-30 10:26:22,709 INFO L78 Accepts]: Start accepts. Automaton has 151 states and 151 transitions. Word has length 146 [2018-09-30 10:26:22,710 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:26:22,710 INFO L480 AbstractCegarLoop]: Abstraction has 151 states and 151 transitions. [2018-09-30 10:26:22,710 INFO L481 AbstractCegarLoop]: Interpolant automaton has 75 states. [2018-09-30 10:26:22,710 INFO L276 IsEmpty]: Start isEmpty. Operand 151 states and 151 transitions. [2018-09-30 10:26:22,711 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 151 [2018-09-30 10:26:22,711 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:26:22,711 INFO L375 BasicCegarLoop]: trace histogram [74, 73, 1, 1, 1] [2018-09-30 10:26:22,711 INFO L423 AbstractCegarLoop]: === Iteration 38 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:26:22,711 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:26:22,712 INFO L82 PathProgramCache]: Analyzing trace with hash -1122306095, now seen corresponding path program 37 times [2018-09-30 10:26:22,712 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:26:22,712 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:26:22,712 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:26:22,713 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-30 10:26:22,713 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:26:23,093 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:26:26,673 INFO L134 CoverageAnalysis]: Checked inductivity of 5402 backedges. 0 proven. 5402 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:26:26,673 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-30 10:26:26,673 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-09-30 10:26:26,680 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-30 10:26:27,361 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-30 10:26:27,702 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-30 10:26:27,834 INFO L134 CoverageAnalysis]: Checked inductivity of 5402 backedges. 0 proven. 5402 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-30 10:26:27,854 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-30 10:26:27,855 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [75, 75] total 76 [2018-09-30 10:26:27,855 INFO L459 AbstractCegarLoop]: Interpolant automaton has 77 states [2018-09-30 10:26:27,855 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 77 interpolants. [2018-09-30 10:26:27,855 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=152, Invalid=5700, Unknown=0, NotChecked=0, Total=5852 [2018-09-30 10:26:27,856 INFO L87 Difference]: Start difference. First operand 151 states and 151 transitions. Second operand 77 states. [2018-09-30 10:26:28,079 WARN L178 SmtUtils]: Spent 185.00 ms on a formula simplification. DAG size of input: 219 DAG size of output: 8 [2018-09-30 10:26:28,293 WARN L178 SmtUtils]: Spent 200.00 ms on a formula simplification. DAG size of input: 225 DAG size of output: 9 [2018-09-30 10:26:28,514 WARN L178 SmtUtils]: Spent 197.00 ms on a formula simplification. DAG size of input: 224 DAG size of output: 11 [2018-09-30 10:26:28,730 WARN L178 SmtUtils]: Spent 188.00 ms on a formula simplification. DAG size of input: 221 DAG size of output: 11 [2018-09-30 10:26:28,951 WARN L178 SmtUtils]: Spent 187.00 ms on a formula simplification. DAG size of input: 218 DAG size of output: 11 [2018-09-30 10:26:29,169 WARN L178 SmtUtils]: Spent 175.00 ms on a formula simplification. DAG size of input: 215 DAG size of output: 11 [2018-09-30 10:26:29,418 WARN L178 SmtUtils]: Spent 199.00 ms on a formula simplification. DAG size of input: 212 DAG size of output: 11 [2018-09-30 10:26:29,656 WARN L178 SmtUtils]: Spent 185.00 ms on a formula simplification. DAG size of input: 209 DAG size of output: 11 [2018-09-30 10:26:29,896 WARN L178 SmtUtils]: Spent 174.00 ms on a formula simplification. DAG size of input: 206 DAG size of output: 11 [2018-09-30 10:26:30,138 WARN L178 SmtUtils]: Spent 177.00 ms on a formula simplification. DAG size of input: 203 DAG size of output: 11 [2018-09-30 10:26:30,375 WARN L178 SmtUtils]: Spent 167.00 ms on a formula simplification. DAG size of input: 200 DAG size of output: 11 [2018-09-30 10:26:30,615 WARN L178 SmtUtils]: Spent 158.00 ms on a formula simplification. DAG size of input: 197 DAG size of output: 11 [2018-09-30 10:26:30,847 WARN L178 SmtUtils]: Spent 150.00 ms on a formula simplification. DAG size of input: 194 DAG size of output: 11 [2018-09-30 10:26:31,074 WARN L178 SmtUtils]: Spent 147.00 ms on a formula simplification. DAG size of input: 191 DAG size of output: 11 [2018-09-30 10:26:31,318 WARN L178 SmtUtils]: Spent 151.00 ms on a formula simplification. DAG size of input: 188 DAG size of output: 11 [2018-09-30 10:26:31,577 WARN L178 SmtUtils]: Spent 143.00 ms on a formula simplification. DAG size of input: 185 DAG size of output: 11 [2018-09-30 10:26:31,830 WARN L178 SmtUtils]: Spent 136.00 ms on a formula simplification. DAG size of input: 182 DAG size of output: 11 [2018-09-30 10:26:32,082 WARN L178 SmtUtils]: Spent 134.00 ms on a formula simplification. DAG size of input: 179 DAG size of output: 11 [2018-09-30 10:26:32,338 WARN L178 SmtUtils]: Spent 134.00 ms on a formula simplification. DAG size of input: 176 DAG size of output: 11 [2018-09-30 10:26:32,601 WARN L178 SmtUtils]: Spent 134.00 ms on a formula simplification. DAG size of input: 173 DAG size of output: 11 [2018-09-30 10:26:32,862 WARN L178 SmtUtils]: Spent 131.00 ms on a formula simplification. DAG size of input: 170 DAG size of output: 11 [2018-09-30 10:26:33,116 WARN L178 SmtUtils]: Spent 116.00 ms on a formula simplification. DAG size of input: 167 DAG size of output: 11 [2018-09-30 10:26:33,368 WARN L178 SmtUtils]: Spent 116.00 ms on a formula simplification. DAG size of input: 164 DAG size of output: 11 [2018-09-30 10:26:33,622 WARN L178 SmtUtils]: Spent 116.00 ms on a formula simplification. DAG size of input: 161 DAG size of output: 11 [2018-09-30 10:26:33,876 WARN L178 SmtUtils]: Spent 109.00 ms on a formula simplification. DAG size of input: 158 DAG size of output: 11 [2018-09-30 10:26:34,145 WARN L178 SmtUtils]: Spent 112.00 ms on a formula simplification. DAG size of input: 155 DAG size of output: 11 [2018-09-30 10:26:34,422 WARN L178 SmtUtils]: Spent 120.00 ms on a formula simplification. DAG size of input: 152 DAG size of output: 11 [2018-09-30 10:26:34,683 WARN L178 SmtUtils]: Spent 106.00 ms on a formula simplification. DAG size of input: 149 DAG size of output: 11 [2018-09-30 10:26:34,941 WARN L178 SmtUtils]: Spent 105.00 ms on a formula simplification. DAG size of input: 146 DAG size of output: 11 [2018-09-30 10:26:43,494 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-30 10:26:43,494 INFO L93 Difference]: Finished difference Result 157 states and 158 transitions. [2018-09-30 10:26:43,494 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 77 states. [2018-09-30 10:26:43,494 INFO L78 Accepts]: Start accepts. Automaton has 77 states. Word has length 150 [2018-09-30 10:26:43,495 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-30 10:26:43,496 INFO L225 Difference]: With dead ends: 157 [2018-09-30 10:26:43,496 INFO L226 Difference]: Without dead ends: 155 [2018-09-30 10:26:43,497 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 297 GetRequests, 149 SyntacticMatches, 0 SemanticMatches, 148 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2629 ImplicationChecksByTransitivity, 18.9s TimeCoverageRelationStatistics Valid=5699, Invalid=16651, Unknown=0, NotChecked=0, Total=22350 [2018-09-30 10:26:43,497 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 155 states. [2018-09-30 10:26:43,506 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 155 to 155. [2018-09-30 10:26:43,506 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 155 states. [2018-09-30 10:26:43,507 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 155 states to 155 states and 155 transitions. [2018-09-30 10:26:43,507 INFO L78 Accepts]: Start accepts. Automaton has 155 states and 155 transitions. Word has length 150 [2018-09-30 10:26:43,507 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-30 10:26:43,507 INFO L480 AbstractCegarLoop]: Abstraction has 155 states and 155 transitions. [2018-09-30 10:26:43,507 INFO L481 AbstractCegarLoop]: Interpolant automaton has 77 states. [2018-09-30 10:26:43,508 INFO L276 IsEmpty]: Start isEmpty. Operand 155 states and 155 transitions. [2018-09-30 10:26:43,508 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 155 [2018-09-30 10:26:43,508 INFO L367 BasicCegarLoop]: Found error trace [2018-09-30 10:26:43,508 INFO L375 BasicCegarLoop]: trace histogram [76, 75, 1, 1, 1] [2018-09-30 10:26:43,509 INFO L423 AbstractCegarLoop]: === Iteration 39 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-09-30 10:26:43,509 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-30 10:26:43,509 INFO L82 PathProgramCache]: Analyzing trace with hash 1195722693, now seen corresponding path program 38 times [2018-09-30 10:26:43,509 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-30 10:26:43,509 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-30 10:26:43,510 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:26:43,510 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-30 10:26:43,510 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-30 10:26:43,971 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat Received shutdown request... [2018-09-30 10:26:46,214 WARN L549 AbstractCegarLoop]: Verification canceled [2018-09-30 10:26:46,219 WARN L206 ceAbstractionStarter]: Timeout [2018-09-30 10:26:46,220 INFO L202 PluginConnector]: Adding new model count_by_k.i_3.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 30.09 10:26:46 BoogieIcfgContainer [2018-09-30 10:26:46,220 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-09-30 10:26:46,221 INFO L168 Benchmark]: Toolchain (without parser) took 249077.61 ms. Allocated memory was 1.5 GB in the beginning and 1.4 GB in the end (delta: -159.4 MB). Free memory was 1.4 GB in the beginning and 1.1 GB in the end (delta: 364.3 MB). Peak memory consumption was 204.9 MB. Max. memory is 7.1 GB. [2018-09-30 10:26:46,222 INFO L168 Benchmark]: Boogie PL CUP Parser took 0.19 ms. Allocated memory is still 1.5 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-09-30 10:26:46,223 INFO L168 Benchmark]: Boogie Procedure Inliner took 39.99 ms. Allocated memory is still 1.5 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-09-30 10:26:46,223 INFO L168 Benchmark]: Boogie Preprocessor took 19.22 ms. Allocated memory is still 1.5 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-09-30 10:26:46,223 INFO L168 Benchmark]: RCFGBuilder took 313.35 ms. Allocated memory is still 1.5 GB. Free memory was 1.4 GB in the beginning and 1.4 GB in the end (delta: 21.1 MB). Peak memory consumption was 21.1 MB. Max. memory is 7.1 GB. [2018-09-30 10:26:46,224 INFO L168 Benchmark]: TraceAbstraction took 248698.58 ms. Allocated memory was 1.5 GB in the beginning and 1.4 GB in the end (delta: -159.4 MB). Free memory was 1.4 GB in the beginning and 1.1 GB in the end (delta: 343.1 MB). Peak memory consumption was 183.7 MB. Max. memory is 7.1 GB. [2018-09-30 10:26:46,226 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.19 ms. Allocated memory is still 1.5 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. * Boogie Procedure Inliner took 39.99 ms. Allocated memory is still 1.5 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. * Boogie Preprocessor took 19.22 ms. Allocated memory is still 1.5 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. * RCFGBuilder took 313.35 ms. Allocated memory is still 1.5 GB. Free memory was 1.4 GB in the beginning and 1.4 GB in the end (delta: 21.1 MB). Peak memory consumption was 21.1 MB. Max. memory is 7.1 GB. * TraceAbstraction took 248698.58 ms. Allocated memory was 1.5 GB in the beginning and 1.4 GB in the end (delta: -159.4 MB). Free memory was 1.4 GB in the beginning and 1.1 GB in the end (delta: 343.1 MB). Peak memory consumption was 183.7 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 PredicateComparison was comparing new predicate (quantifier-free) to 65 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 1 procedures, 7 locations, 1 error locations. TIMEOUT Result, 248.6s OverallTime, 39 OverallIterations, 76 TraceHistogramMax, 183.8s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 189 SDtfs, 0 SDslu, 2893 SDs, 0 SdLazy, 3042 SolverSat, 1369 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 4.9s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 5662 GetRequests, 2850 SyntacticMatches, 0 SemanticMatches, 2812 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 33114 ImplicationChecksByTransitivity, 224.4s 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.3s AutomataMinimizationTime, 38 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 8.0s SatisfiabilityAnalysisTime, 51.6s InterpolantComputationTime, 5776 NumberOfCodeBlocks, 5776 NumberOfCodeBlocksAsserted, 777 NumberOfCheckSat, 5701 ConstructedInterpolants, 0 QuantifiedInterpolants, 2857279 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.epf_AutomizerBplInline.xml/Csv-Benchmark-0-2018-09-30_10-26-46-239.csv Written .csv to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/csv/count_by_k.i_3.bpl_svcomp-Reach-32bit-Automizer_Default.epf_AutomizerBplInline.xml/Csv-TraceAbstractionBenchmarks-0-2018-09-30_10-26-46-239.csv Completed graceful shutdown