java -Xmx8000000000 -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data --generate-csv --csv-dir csv -tc ../../../trunk/examples/toolchains/AutomizerBplInline.xml -s ../../../trunk/examples/settings/pu-bench/svcomp-Reach-32bit-Automizer_Default_PUPT.epf -i ../../../trunk/examples/programs/20170319-ConjunctivePathPrograms/count_by_k.i_3.bplTransformedIcfg_BEv2_3.bpl -------------------------------------------------------------------------------- This is Ultimate 0.1.23-9f4048f-m [2018-10-04 14:20:30,285 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-10-04 14:20:30,287 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-10-04 14:20:30,299 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-10-04 14:20:30,299 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-10-04 14:20:30,300 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-10-04 14:20:30,306 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-10-04 14:20:30,308 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-10-04 14:20:30,309 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-10-04 14:20:30,310 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-10-04 14:20:30,311 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-10-04 14:20:30,315 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-10-04 14:20:30,316 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-10-04 14:20:30,319 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-10-04 14:20:30,324 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-10-04 14:20:30,325 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-10-04 14:20:30,329 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-10-04 14:20:30,330 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-10-04 14:20:30,334 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-10-04 14:20:30,339 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-10-04 14:20:30,340 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-10-04 14:20:30,343 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-10-04 14:20:30,350 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-10-04 14:20:30,350 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-10-04 14:20:30,350 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-10-04 14:20:30,351 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-10-04 14:20:30,352 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-10-04 14:20:30,353 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-10-04 14:20:30,354 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-10-04 14:20:30,358 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-10-04 14:20:30,360 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-10-04 14:20:30,360 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-10-04 14:20:30,362 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-10-04 14:20:30,363 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-10-04 14:20:30,365 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-10-04 14:20:30,366 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-10-04 14:20:30,366 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/pu-bench/svcomp-Reach-32bit-Automizer_Default_PUPT.epf [2018-10-04 14:20:30,391 INFO L110 SettingsManager]: Loading preferences was successful [2018-10-04 14:20:30,391 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-10-04 14:20:30,393 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-10-04 14:20:30,393 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-10-04 14:20:30,394 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-10-04 14:20:30,394 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-10-04 14:20:30,394 INFO L133 SettingsManager]: * Use SBE=true [2018-10-04 14:20:30,394 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-10-04 14:20:30,394 INFO L133 SettingsManager]: * sizeof long=4 [2018-10-04 14:20:30,398 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-10-04 14:20:30,398 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-10-04 14:20:30,398 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-10-04 14:20:30,398 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-10-04 14:20:30,399 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-10-04 14:20:30,399 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-10-04 14:20:30,399 INFO L133 SettingsManager]: * sizeof long double=12 [2018-10-04 14:20:30,399 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-10-04 14:20:30,399 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-10-04 14:20:30,400 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-10-04 14:20:30,401 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-10-04 14:20:30,401 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-10-04 14:20:30,402 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-10-04 14:20:30,402 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-10-04 14:20:30,402 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-10-04 14:20:30,402 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-10-04 14:20:30,402 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-10-04 14:20:30,403 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-10-04 14:20:30,403 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-10-04 14:20:30,403 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-10-04 14:20:30,403 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-10-04 14:20:30,403 INFO L133 SettingsManager]: * Use predicate trie based predicate unification=true [2018-10-04 14:20:30,471 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-10-04 14:20:30,487 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-10-04 14:20:30,494 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-10-04 14:20:30,496 INFO L271 PluginConnector]: Initializing Boogie PL CUP Parser... [2018-10-04 14:20:30,497 INFO L276 PluginConnector]: Boogie PL CUP Parser initialized [2018-10-04 14:20:30,498 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/20170319-ConjunctivePathPrograms/count_by_k.i_3.bplTransformedIcfg_BEv2_3.bpl [2018-10-04 14:20:30,498 INFO L111 BoogieParser]: Parsing: '/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/20170319-ConjunctivePathPrograms/count_by_k.i_3.bplTransformedIcfg_BEv2_3.bpl' [2018-10-04 14:20:30,548 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-10-04 14:20:30,553 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-10-04 14:20:30,553 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2018-10-04 14:20:30,554 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2018-10-04 14:20:30,554 INFO L276 PluginConnector]: Boogie Procedure Inliner initialized [2018-10-04 14:20:30,575 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "count_by_k.i_3.bplTransformedIcfg_BEv2_3.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 04.10 02:20:30" (1/1) ... [2018-10-04 14:20:30,587 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "count_by_k.i_3.bplTransformedIcfg_BEv2_3.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 04.10 02:20:30" (1/1) ... [2018-10-04 14:20:30,594 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2018-10-04 14:20:30,595 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-10-04 14:20:30,595 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-10-04 14:20:30,596 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-10-04 14:20:30,607 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "count_by_k.i_3.bplTransformedIcfg_BEv2_3.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 04.10 02:20:30" (1/1) ... [2018-10-04 14:20:30,608 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "count_by_k.i_3.bplTransformedIcfg_BEv2_3.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 04.10 02:20:30" (1/1) ... [2018-10-04 14:20:30,608 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "count_by_k.i_3.bplTransformedIcfg_BEv2_3.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 04.10 02:20:30" (1/1) ... [2018-10-04 14:20:30,609 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "count_by_k.i_3.bplTransformedIcfg_BEv2_3.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 04.10 02:20:30" (1/1) ... [2018-10-04 14:20:30,611 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "count_by_k.i_3.bplTransformedIcfg_BEv2_3.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 04.10 02:20:30" (1/1) ... [2018-10-04 14:20:30,613 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "count_by_k.i_3.bplTransformedIcfg_BEv2_3.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 04.10 02:20:30" (1/1) ... [2018-10-04 14:20:30,614 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "count_by_k.i_3.bplTransformedIcfg_BEv2_3.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 04.10 02:20:30" (1/1) ... [2018-10-04 14:20:30,616 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-10-04 14:20:30,616 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-10-04 14:20:30,616 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-10-04 14:20:30,617 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-10-04 14:20:30,618 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "count_by_k.i_3.bplTransformedIcfg_BEv2_3.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 04.10 02:20:30" (1/1) ... No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-10-04 14:20:30,694 INFO L124 BoogieDeclarations]: Specification and implementation of procedure ULTIMATE.start given in one single declaration [2018-10-04 14:20:30,694 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-10-04 14:20:30,694 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-10-04 14:20:30,908 INFO L341 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-10-04 14:20:30,909 INFO L202 PluginConnector]: Adding new model count_by_k.i_3.bplTransformedIcfg_BEv2_3.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 04.10 02:20:30 BoogieIcfgContainer [2018-10-04 14:20:30,909 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-10-04 14:20:30,910 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-10-04 14:20:30,910 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-10-04 14:20:30,914 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-10-04 14:20:30,914 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "count_by_k.i_3.bplTransformedIcfg_BEv2_3.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 04.10 02:20:30" (1/2) ... [2018-10-04 14:20:30,915 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2708617d and model type count_by_k.i_3.bplTransformedIcfg_BEv2_3.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 04.10 02:20:30, skipping insertion in model container [2018-10-04 14:20:30,915 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "count_by_k.i_3.bplTransformedIcfg_BEv2_3.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 04.10 02:20:30" (2/2) ... [2018-10-04 14:20:30,917 INFO L112 eAbstractionObserver]: Analyzing ICFG count_by_k.i_3.bplTransformedIcfg_BEv2_3.bpl [2018-10-04 14:20:30,927 INFO L136 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-10-04 14:20:30,934 INFO L148 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-10-04 14:20:30,983 INFO L133 ementStrategyFactory]: Using default assertion order modulation [2018-10-04 14:20:30,984 INFO L381 AbstractCegarLoop]: Interprodecural is true [2018-10-04 14:20:30,984 INFO L382 AbstractCegarLoop]: Hoare is true [2018-10-04 14:20:30,985 INFO L383 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-10-04 14:20:30,985 INFO L384 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-10-04 14:20:30,985 INFO L385 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-10-04 14:20:30,985 INFO L386 AbstractCegarLoop]: Difference is false [2018-10-04 14:20:30,985 INFO L387 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-10-04 14:20:30,986 INFO L392 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-10-04 14:20:31,001 INFO L276 IsEmpty]: Start isEmpty. Operand 6 states. [2018-10-04 14:20:31,007 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2018-10-04 14:20:31,007 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:20:31,008 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1] [2018-10-04 14:20:31,009 INFO L423 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:20:31,016 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:20:31,017 INFO L82 PathProgramCache]: Analyzing trace with hash 30017, now seen corresponding path program 1 times [2018-10-04 14:20:31,019 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:20:31,020 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:20:31,069 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:31,070 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-04 14:20:31,070 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:31,107 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:20:31,180 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:31,182 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-04 14:20:31,182 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-10-04 14:20:31,186 INFO L459 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-10-04 14:20:31,198 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-10-04 14:20:31,198 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:20:31,200 INFO L87 Difference]: Start difference. First operand 6 states. Second operand 3 states. [2018-10-04 14:20:31,228 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:20:31,229 INFO L93 Difference]: Finished difference Result 9 states and 10 transitions. [2018-10-04 14:20:31,230 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-10-04 14:20:31,231 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 3 [2018-10-04 14:20:31,231 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:20:31,243 INFO L225 Difference]: With dead ends: 9 [2018-10-04 14:20:31,243 INFO L226 Difference]: Without dead ends: 5 [2018-10-04 14:20:31,246 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s Time 0.0s impTime 1 [2018-10-04 14:20:31,261 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 5 states. [2018-10-04 14:20:31,273 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 5 to 5. [2018-10-04 14:20:31,275 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5 states. [2018-10-04 14:20:31,275 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 5 transitions. [2018-10-04 14:20:31,277 INFO L78 Accepts]: Start accepts. Automaton has 5 states and 5 transitions. Word has length 3 [2018-10-04 14:20:31,277 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:20:31,277 INFO L480 AbstractCegarLoop]: Abstraction has 5 states and 5 transitions. [2018-10-04 14:20:31,277 INFO L481 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-10-04 14:20:31,278 INFO L276 IsEmpty]: Start isEmpty. Operand 5 states and 5 transitions. [2018-10-04 14:20:31,278 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 5 [2018-10-04 14:20:31,278 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:20:31,278 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1] [2018-10-04 14:20:31,279 INFO L423 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:20:31,279 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:20:31,279 INFO L82 PathProgramCache]: Analyzing trace with hash 928552, now seen corresponding path program 1 times [2018-10-04 14:20:31,279 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:20:31,279 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:20:31,280 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:31,281 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-04 14:20:31,281 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:31,289 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:20:31,415 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:31,415 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:20:31,415 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:20:31,435 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-04 14:20:31,463 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:20:31,470 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:20:31,586 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:31,608 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:20:31,608 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [3, 3] total 4 [2018-10-04 14:20:31,608 INFO L459 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-10-04 14:20:31,609 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-10-04 14:20:31,609 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:20:31,609 INFO L87 Difference]: Start difference. First operand 5 states and 5 transitions. Second operand 5 states. [2018-10-04 14:20:31,659 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:20:31,660 INFO L93 Difference]: Finished difference Result 9 states and 10 transitions. [2018-10-04 14:20:31,660 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-10-04 14:20:31,660 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 4 [2018-10-04 14:20:31,661 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:20:31,661 INFO L225 Difference]: With dead ends: 9 [2018-10-04 14:20:31,661 INFO L226 Difference]: Without dead ends: 7 [2018-10-04 14:20:31,662 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s Time 0.0s impTime 3 [2018-10-04 14:20:31,662 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 7 states. [2018-10-04 14:20:31,664 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 7 to 7. [2018-10-04 14:20:31,665 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 7 states. [2018-10-04 14:20:31,665 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 7 transitions. [2018-10-04 14:20:31,665 INFO L78 Accepts]: Start accepts. Automaton has 7 states and 7 transitions. Word has length 4 [2018-10-04 14:20:31,666 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:20:31,666 INFO L480 AbstractCegarLoop]: Abstraction has 7 states and 7 transitions. [2018-10-04 14:20:31,666 INFO L481 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-10-04 14:20:31,666 INFO L276 IsEmpty]: Start isEmpty. Operand 7 states and 7 transitions. [2018-10-04 14:20:31,666 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2018-10-04 14:20:31,667 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:20:31,667 INFO L375 BasicCegarLoop]: trace histogram [3, 1, 1, 1] [2018-10-04 14:20:31,667 INFO L423 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:20:31,667 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:20:31,667 INFO L82 PathProgramCache]: Analyzing trace with hash 892275272, now seen corresponding path program 2 times [2018-10-04 14:20:31,668 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:20:31,668 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:20:31,669 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:31,669 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-04 14:20:31,669 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:31,683 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:20:31,822 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:31,823 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:20:31,823 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:20:31,840 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-10-04 14:20:31,874 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-10-04 14:20:31,875 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:20:31,876 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:20:31,948 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:31,968 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:20:31,968 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 6 [2018-10-04 14:20:31,969 INFO L459 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-10-04 14:20:31,969 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-10-04 14:20:31,969 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:20:31,969 INFO L87 Difference]: Start difference. First operand 7 states and 7 transitions. Second operand 7 states. [2018-10-04 14:20:32,256 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:20:32,256 INFO L93 Difference]: Finished difference Result 11 states and 12 transitions. [2018-10-04 14:20:32,256 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-10-04 14:20:32,257 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 6 [2018-10-04 14:20:32,257 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:20:32,257 INFO L225 Difference]: With dead ends: 11 [2018-10-04 14:20:32,258 INFO L226 Difference]: Without dead ends: 9 [2018-10-04 14:20:32,258 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s Time 0.2s impTime 6 [2018-10-04 14:20:32,258 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 9 states. [2018-10-04 14:20:32,261 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-10-04 14:20:32,262 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 9 states. [2018-10-04 14:20:32,262 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-10-04 14:20:32,263 INFO L78 Accepts]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 6 [2018-10-04 14:20:32,263 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:20:32,263 INFO L480 AbstractCegarLoop]: Abstraction has 9 states and 9 transitions. [2018-10-04 14:20:32,263 INFO L481 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-10-04 14:20:32,263 INFO L276 IsEmpty]: Start isEmpty. Operand 9 states and 9 transitions. [2018-10-04 14:20:32,264 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2018-10-04 14:20:32,264 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:20:32,264 INFO L375 BasicCegarLoop]: trace histogram [5, 1, 1, 1] [2018-10-04 14:20:32,264 INFO L423 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:20:32,265 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:20:32,265 INFO L82 PathProgramCache]: Analyzing trace with hash -1516986008, now seen corresponding path program 3 times [2018-10-04 14:20:32,265 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:20:32,265 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:20:32,267 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:32,267 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:20:32,267 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:32,286 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:20:32,488 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:32,489 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:20:32,489 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:20:32,499 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-04 14:20:32,518 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-10-04 14:20:32,518 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:20:32,520 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:20:32,654 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:32,676 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:20:32,676 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 8 [2018-10-04 14:20:32,676 INFO L459 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-10-04 14:20:32,677 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-10-04 14:20:32,677 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:20:32,677 INFO L87 Difference]: Start difference. First operand 9 states and 9 transitions. Second operand 9 states. [2018-10-04 14:20:32,941 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:20:32,942 INFO L93 Difference]: Finished difference Result 13 states and 14 transitions. [2018-10-04 14:20:32,942 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-10-04 14:20:32,943 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 8 [2018-10-04 14:20:32,943 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:20:32,943 INFO L225 Difference]: With dead ends: 13 [2018-10-04 14:20:32,944 INFO L226 Difference]: Without dead ends: 11 [2018-10-04 14:20:32,944 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.4s Time 0.2s impTime 8 [2018-10-04 14:20:32,945 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 11 states. [2018-10-04 14:20:32,948 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-10-04 14:20:32,948 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 11 states. [2018-10-04 14:20:32,949 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-10-04 14:20:32,949 INFO L78 Accepts]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 8 [2018-10-04 14:20:32,949 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:20:32,949 INFO L480 AbstractCegarLoop]: Abstraction has 11 states and 11 transitions. [2018-10-04 14:20:32,949 INFO L481 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-10-04 14:20:32,950 INFO L276 IsEmpty]: Start isEmpty. Operand 11 states and 11 transitions. [2018-10-04 14:20:32,950 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2018-10-04 14:20:32,950 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:20:32,950 INFO L375 BasicCegarLoop]: trace histogram [7, 1, 1, 1] [2018-10-04 14:20:32,950 INFO L423 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:20:32,951 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:20:32,951 INFO L82 PathProgramCache]: Analyzing trace with hash -1829703544, now seen corresponding path program 4 times [2018-10-04 14:20:32,951 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:20:32,951 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:20:32,952 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:32,952 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:20:32,952 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:32,973 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:20:33,310 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:33,311 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:20:33,311 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:20:33,320 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-04 14:20:33,346 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-04 14:20:33,346 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:20:33,348 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:20:33,540 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:33,571 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:20:33,571 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 10 [2018-10-04 14:20:33,572 INFO L459 AbstractCegarLoop]: Interpolant automaton has 11 states [2018-10-04 14:20:33,572 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2018-10-04 14:20:33,572 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:20:33,572 INFO L87 Difference]: Start difference. First operand 11 states and 11 transitions. Second operand 11 states. [2018-10-04 14:20:34,168 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:20:34,168 INFO L93 Difference]: Finished difference Result 15 states and 16 transitions. [2018-10-04 14:20:34,168 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-10-04 14:20:34,169 INFO L78 Accepts]: Start accepts. Automaton has 11 states. Word has length 10 [2018-10-04 14:20:34,169 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:20:34,170 INFO L225 Difference]: With dead ends: 15 [2018-10-04 14:20:34,170 INFO L226 Difference]: Without dead ends: 13 [2018-10-04 14:20:34,170 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 25 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.9s Time 0.5s impTime 10 [2018-10-04 14:20:34,171 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 13 states. [2018-10-04 14:20:34,174 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-10-04 14:20:34,174 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 13 states. [2018-10-04 14:20:34,175 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13 states to 13 states and 13 transitions. [2018-10-04 14:20:34,175 INFO L78 Accepts]: Start accepts. Automaton has 13 states and 13 transitions. Word has length 10 [2018-10-04 14:20:34,175 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:20:34,175 INFO L480 AbstractCegarLoop]: Abstraction has 13 states and 13 transitions. [2018-10-04 14:20:34,176 INFO L481 AbstractCegarLoop]: Interpolant automaton has 11 states. [2018-10-04 14:20:34,176 INFO L276 IsEmpty]: Start isEmpty. Operand 13 states and 13 transitions. [2018-10-04 14:20:34,176 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2018-10-04 14:20:34,176 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:20:34,176 INFO L375 BasicCegarLoop]: trace histogram [9, 1, 1, 1] [2018-10-04 14:20:34,177 INFO L423 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:20:34,177 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:20:34,177 INFO L82 PathProgramCache]: Analyzing trace with hash -1703544920, now seen corresponding path program 5 times [2018-10-04 14:20:34,177 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:20:34,177 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:20:34,178 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:34,178 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:20:34,178 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:34,208 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:20:34,709 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 0 proven. 45 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:34,710 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:20:34,710 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:20:34,718 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-10-04 14:20:34,736 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-10-04 14:20:34,737 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:20:34,739 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:20:34,951 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 0 proven. 45 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:34,971 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:20:34,972 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 12 [2018-10-04 14:20:34,972 INFO L459 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-10-04 14:20:34,972 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-10-04 14:20:34,973 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:20:34,973 INFO L87 Difference]: Start difference. First operand 13 states and 13 transitions. Second operand 13 states. [2018-10-04 14:20:35,341 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:20:35,341 INFO L93 Difference]: Finished difference Result 17 states and 18 transitions. [2018-10-04 14:20:35,342 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-10-04 14:20:35,342 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 12 [2018-10-04 14:20:35,343 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:20:35,343 INFO L225 Difference]: With dead ends: 17 [2018-10-04 14:20:35,344 INFO L226 Difference]: Without dead ends: 15 [2018-10-04 14:20:35,344 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 31 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.9s Time 0.5s impTime 12 [2018-10-04 14:20:35,344 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 15 states. [2018-10-04 14:20:35,348 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-10-04 14:20:35,348 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 15 states. [2018-10-04 14:20:35,348 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 15 transitions. [2018-10-04 14:20:35,349 INFO L78 Accepts]: Start accepts. Automaton has 15 states and 15 transitions. Word has length 12 [2018-10-04 14:20:35,349 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:20:35,349 INFO L480 AbstractCegarLoop]: Abstraction has 15 states and 15 transitions. [2018-10-04 14:20:35,349 INFO L481 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-10-04 14:20:35,349 INFO L276 IsEmpty]: Start isEmpty. Operand 15 states and 15 transitions. [2018-10-04 14:20:35,350 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2018-10-04 14:20:35,350 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:20:35,350 INFO L375 BasicCegarLoop]: trace histogram [11, 1, 1, 1] [2018-10-04 14:20:35,350 INFO L423 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:20:35,351 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:20:35,351 INFO L82 PathProgramCache]: Analyzing trace with hash -724191544, now seen corresponding path program 6 times [2018-10-04 14:20:35,351 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:20:35,351 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:20:35,353 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:35,353 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:20:35,353 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:35,386 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:20:35,681 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 0 proven. 66 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:35,682 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:20:35,682 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:20:35,693 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-10-04 14:20:35,705 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-10-04 14:20:35,705 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:20:35,707 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:20:35,794 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 0 proven. 66 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:35,815 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:20:35,815 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 14 [2018-10-04 14:20:35,816 INFO L459 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-10-04 14:20:35,816 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-10-04 14:20:35,816 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:20:35,816 INFO L87 Difference]: Start difference. First operand 15 states and 15 transitions. Second operand 15 states. [2018-10-04 14:20:36,377 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:20:36,378 INFO L93 Difference]: Finished difference Result 19 states and 20 transitions. [2018-10-04 14:20:36,379 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-10-04 14:20:36,379 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 14 [2018-10-04 14:20:36,379 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:20:36,379 INFO L225 Difference]: With dead ends: 19 [2018-10-04 14:20:36,380 INFO L226 Difference]: Without dead ends: 17 [2018-10-04 14:20:36,380 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 37 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.7s Time 0.5s impTime 14 [2018-10-04 14:20:36,380 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 17 states. [2018-10-04 14:20:36,384 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-10-04 14:20:36,384 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 17 states. [2018-10-04 14:20:36,385 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 17 transitions. [2018-10-04 14:20:36,385 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 17 transitions. Word has length 14 [2018-10-04 14:20:36,385 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:20:36,385 INFO L480 AbstractCegarLoop]: Abstraction has 17 states and 17 transitions. [2018-10-04 14:20:36,385 INFO L481 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-10-04 14:20:36,385 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 17 transitions. [2018-10-04 14:20:36,386 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-10-04 14:20:36,386 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:20:36,386 INFO L375 BasicCegarLoop]: trace histogram [13, 1, 1, 1] [2018-10-04 14:20:36,386 INFO L423 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:20:36,387 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:20:36,387 INFO L82 PathProgramCache]: Analyzing trace with hash -163435032, now seen corresponding path program 7 times [2018-10-04 14:20:36,387 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:20:36,387 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:20:36,388 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:36,388 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:20:36,388 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:36,406 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:20:36,914 INFO L134 CoverageAnalysis]: Checked inductivity of 91 backedges. 0 proven. 91 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:36,914 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:20:36,914 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:20:36,922 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-04 14:20:36,939 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:20:36,943 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:20:37,179 INFO L134 CoverageAnalysis]: Checked inductivity of 91 backedges. 0 proven. 91 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:37,208 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:20:37,208 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 16 [2018-10-04 14:20:37,208 INFO L459 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-10-04 14:20:37,209 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-10-04 14:20:37,209 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:20:37,209 INFO L87 Difference]: Start difference. First operand 17 states and 17 transitions. Second operand 17 states. [2018-10-04 14:20:37,982 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:20:37,983 INFO L93 Difference]: Finished difference Result 21 states and 22 transitions. [2018-10-04 14:20:37,983 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-10-04 14:20:37,984 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 16 [2018-10-04 14:20:37,984 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:20:37,985 INFO L225 Difference]: With dead ends: 21 [2018-10-04 14:20:37,985 INFO L226 Difference]: Without dead ends: 19 [2018-10-04 14:20:37,986 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 1.3s Time 0.8s impTime 16 [2018-10-04 14:20:37,986 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2018-10-04 14:20:37,991 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-10-04 14:20:37,991 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 19 states. [2018-10-04 14:20:37,992 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 19 transitions. [2018-10-04 14:20:37,992 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 19 transitions. Word has length 16 [2018-10-04 14:20:37,992 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:20:37,992 INFO L480 AbstractCegarLoop]: Abstraction has 19 states and 19 transitions. [2018-10-04 14:20:37,993 INFO L481 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-10-04 14:20:37,993 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 19 transitions. [2018-10-04 14:20:37,993 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2018-10-04 14:20:37,993 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:20:37,993 INFO L375 BasicCegarLoop]: trace histogram [15, 1, 1, 1] [2018-10-04 14:20:37,994 INFO L423 AbstractCegarLoop]: === Iteration 9 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:20:37,994 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:20:37,994 INFO L82 PathProgramCache]: Analyzing trace with hash 1852661000, now seen corresponding path program 8 times [2018-10-04 14:20:37,994 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:20:37,994 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:20:37,995 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:37,995 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-04 14:20:37,995 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:38,015 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:20:38,388 INFO L134 CoverageAnalysis]: Checked inductivity of 120 backedges. 0 proven. 120 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:38,388 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:20:38,388 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:20:38,398 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-10-04 14:20:38,416 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-10-04 14:20:38,417 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:20:38,422 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:20:38,519 INFO L134 CoverageAnalysis]: Checked inductivity of 120 backedges. 0 proven. 120 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:38,539 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:20:38,540 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17] total 18 [2018-10-04 14:20:38,540 INFO L459 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-10-04 14:20:38,540 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-10-04 14:20:38,541 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:20:38,541 INFO L87 Difference]: Start difference. First operand 19 states and 19 transitions. Second operand 19 states. [2018-10-04 14:20:40,538 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:20:40,538 INFO L93 Difference]: Finished difference Result 23 states and 24 transitions. [2018-10-04 14:20:40,542 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-10-04 14:20:40,542 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 18 [2018-10-04 14:20:40,542 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:20:40,542 INFO L225 Difference]: With dead ends: 23 [2018-10-04 14:20:40,543 INFO L226 Difference]: Without dead ends: 21 [2018-10-04 14:20:40,543 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 2.2s Time 1.8s impTime 18 [2018-10-04 14:20:40,543 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2018-10-04 14:20:40,546 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-10-04 14:20:40,546 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 21 states. [2018-10-04 14:20:40,547 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 21 transitions. [2018-10-04 14:20:40,547 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 21 transitions. Word has length 18 [2018-10-04 14:20:40,547 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:20:40,547 INFO L480 AbstractCegarLoop]: Abstraction has 21 states and 21 transitions. [2018-10-04 14:20:40,548 INFO L481 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-10-04 14:20:40,548 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 21 transitions. [2018-10-04 14:20:40,548 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-10-04 14:20:40,548 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:20:40,548 INFO L375 BasicCegarLoop]: trace histogram [17, 1, 1, 1] [2018-10-04 14:20:40,549 INFO L423 AbstractCegarLoop]: === Iteration 10 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:20:40,549 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:20:40,549 INFO L82 PathProgramCache]: Analyzing trace with hash -2004270040, now seen corresponding path program 9 times [2018-10-04 14:20:40,549 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:20:40,549 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:20:40,550 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:40,550 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:20:40,550 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:40,571 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:20:40,937 INFO L134 CoverageAnalysis]: Checked inductivity of 153 backedges. 0 proven. 153 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:40,938 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:20:40,938 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:20:40,947 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-04 14:20:40,961 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2018-10-04 14:20:40,962 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:20:40,964 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:20:41,258 INFO L134 CoverageAnalysis]: Checked inductivity of 153 backedges. 0 proven. 153 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:41,279 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:20:41,279 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19] total 20 [2018-10-04 14:20:41,279 INFO L459 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-10-04 14:20:41,280 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-10-04 14:20:41,280 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:20:41,280 INFO L87 Difference]: Start difference. First operand 21 states and 21 transitions. Second operand 21 states. [2018-10-04 14:20:42,101 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:20:42,102 INFO L93 Difference]: Finished difference Result 25 states and 26 transitions. [2018-10-04 14:20:42,102 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-10-04 14:20:42,102 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 20 [2018-10-04 14:20:42,103 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:20:42,104 INFO L225 Difference]: With dead ends: 25 [2018-10-04 14:20:42,104 INFO L226 Difference]: Without dead ends: 23 [2018-10-04 14:20:42,104 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 55 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 1.2s Time 0.9s impTime 20 [2018-10-04 14:20:42,105 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2018-10-04 14:20:42,109 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-10-04 14:20:42,109 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 23 states. [2018-10-04 14:20:42,110 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 23 transitions. [2018-10-04 14:20:42,110 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 23 transitions. Word has length 20 [2018-10-04 14:20:42,110 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:20:42,110 INFO L480 AbstractCegarLoop]: Abstraction has 23 states and 23 transitions. [2018-10-04 14:20:42,110 INFO L481 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-10-04 14:20:42,111 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 23 transitions. [2018-10-04 14:20:42,111 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2018-10-04 14:20:42,111 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:20:42,111 INFO L375 BasicCegarLoop]: trace histogram [19, 1, 1, 1] [2018-10-04 14:20:42,112 INFO L423 AbstractCegarLoop]: === Iteration 11 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:20:42,112 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:20:42,112 INFO L82 PathProgramCache]: Analyzing trace with hash -1958223032, now seen corresponding path program 10 times [2018-10-04 14:20:42,112 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:20:42,112 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:20:42,113 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:42,113 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:20:42,113 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:42,133 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:20:42,518 INFO L134 CoverageAnalysis]: Checked inductivity of 190 backedges. 0 proven. 190 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:42,519 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:20:42,519 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:20:42,528 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-04 14:20:42,561 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-04 14:20:42,561 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:20:42,572 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:20:42,692 INFO L134 CoverageAnalysis]: Checked inductivity of 190 backedges. 0 proven. 190 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:42,712 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:20:42,712 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21] total 22 [2018-10-04 14:20:42,712 INFO L459 AbstractCegarLoop]: Interpolant automaton has 23 states [2018-10-04 14:20:42,713 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2018-10-04 14:20:42,713 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:20:42,713 INFO L87 Difference]: Start difference. First operand 23 states and 23 transitions. Second operand 23 states. [2018-10-04 14:20:43,604 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:20:43,604 INFO L93 Difference]: Finished difference Result 27 states and 28 transitions. [2018-10-04 14:20:43,605 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-10-04 14:20:43,605 INFO L78 Accepts]: Start accepts. Automaton has 23 states. Word has length 22 [2018-10-04 14:20:43,605 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:20:43,606 INFO L225 Difference]: With dead ends: 27 [2018-10-04 14:20:43,606 INFO L226 Difference]: Without dead ends: 25 [2018-10-04 14:20:43,606 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 61 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 1.2s Time 0.9s impTime 22 [2018-10-04 14:20:43,606 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2018-10-04 14:20:43,611 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-10-04 14:20:43,611 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 25 states. [2018-10-04 14:20:43,611 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 25 transitions. [2018-10-04 14:20:43,612 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 25 transitions. Word has length 22 [2018-10-04 14:20:43,612 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:20:43,612 INFO L480 AbstractCegarLoop]: Abstraction has 25 states and 25 transitions. [2018-10-04 14:20:43,612 INFO L481 AbstractCegarLoop]: Interpolant automaton has 23 states. [2018-10-04 14:20:43,612 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 25 transitions. [2018-10-04 14:20:43,612 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-10-04 14:20:43,613 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:20:43,613 INFO L375 BasicCegarLoop]: trace histogram [21, 1, 1, 1] [2018-10-04 14:20:43,613 INFO L423 AbstractCegarLoop]: === Iteration 12 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:20:43,613 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:20:43,613 INFO L82 PathProgramCache]: Analyzing trace with hash -656721304, now seen corresponding path program 11 times [2018-10-04 14:20:43,613 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:20:43,613 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:20:43,614 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:43,614 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:20:43,614 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:43,641 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:20:44,074 INFO L134 CoverageAnalysis]: Checked inductivity of 231 backedges. 0 proven. 231 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:44,074 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:20:44,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 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:20:44,091 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-10-04 14:20:44,141 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 12 check-sat command(s) [2018-10-04 14:20:44,142 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:20:44,146 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:20:44,251 INFO L134 CoverageAnalysis]: Checked inductivity of 231 backedges. 0 proven. 231 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:44,271 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:20:44,271 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 23] total 24 [2018-10-04 14:20:44,272 INFO L459 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-10-04 14:20:44,272 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-10-04 14:20:44,272 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:20:44,272 INFO L87 Difference]: Start difference. First operand 25 states and 25 transitions. Second operand 25 states. [2018-10-04 14:20:45,178 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:20:45,178 INFO L93 Difference]: Finished difference Result 29 states and 30 transitions. [2018-10-04 14:20:45,179 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2018-10-04 14:20:45,179 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 24 [2018-10-04 14:20:45,179 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:20:45,180 INFO L225 Difference]: With dead ends: 29 [2018-10-04 14:20:45,180 INFO L226 Difference]: Without dead ends: 27 [2018-10-04 14:20:45,180 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 67 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 1.2s Time 1.0s impTime 24 [2018-10-04 14:20:45,181 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2018-10-04 14:20:45,186 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2018-10-04 14:20:45,187 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 27 states. [2018-10-04 14:20:45,187 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 27 transitions. [2018-10-04 14:20:45,188 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 27 transitions. Word has length 24 [2018-10-04 14:20:45,188 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:20:45,188 INFO L480 AbstractCegarLoop]: Abstraction has 27 states and 27 transitions. [2018-10-04 14:20:45,188 INFO L481 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-10-04 14:20:45,188 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 27 transitions. [2018-10-04 14:20:45,189 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2018-10-04 14:20:45,189 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:20:45,189 INFO L375 BasicCegarLoop]: trace histogram [23, 1, 1, 1] [2018-10-04 14:20:45,190 INFO L423 AbstractCegarLoop]: === Iteration 13 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:20:45,190 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:20:45,190 INFO L82 PathProgramCache]: Analyzing trace with hash 250956168, now seen corresponding path program 12 times [2018-10-04 14:20:45,190 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:20:45,190 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:20:45,191 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:45,191 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:20:45,191 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:45,225 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:20:45,739 INFO L134 CoverageAnalysis]: Checked inductivity of 276 backedges. 0 proven. 276 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:45,739 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:20:45,740 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:20:45,749 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-10-04 14:20:45,831 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 13 check-sat command(s) [2018-10-04 14:20:45,831 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:20:45,834 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:20:45,936 INFO L134 CoverageAnalysis]: Checked inductivity of 276 backedges. 0 proven. 276 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:45,965 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:20:45,966 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 25] total 26 [2018-10-04 14:20:45,966 INFO L459 AbstractCegarLoop]: Interpolant automaton has 27 states [2018-10-04 14:20:45,966 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2018-10-04 14:20:45,966 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:20:45,966 INFO L87 Difference]: Start difference. First operand 27 states and 27 transitions. Second operand 27 states. [2018-10-04 14:20:47,022 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:20:47,022 INFO L93 Difference]: Finished difference Result 31 states and 32 transitions. [2018-10-04 14:20:47,023 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2018-10-04 14:20:47,023 INFO L78 Accepts]: Start accepts. Automaton has 27 states. Word has length 26 [2018-10-04 14:20:47,023 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:20:47,023 INFO L225 Difference]: With dead ends: 31 [2018-10-04 14:20:47,024 INFO L226 Difference]: Without dead ends: 29 [2018-10-04 14:20:47,024 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 1.4s Time 1.2s impTime 26 [2018-10-04 14:20:47,024 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2018-10-04 14:20:47,032 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 29. [2018-10-04 14:20:47,032 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 29 states. [2018-10-04 14:20:47,032 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 29 transitions. [2018-10-04 14:20:47,033 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 29 transitions. Word has length 26 [2018-10-04 14:20:47,033 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:20:47,033 INFO L480 AbstractCegarLoop]: Abstraction has 29 states and 29 transitions. [2018-10-04 14:20:47,033 INFO L481 AbstractCegarLoop]: Interpolant automaton has 27 states. [2018-10-04 14:20:47,033 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 29 transitions. [2018-10-04 14:20:47,034 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2018-10-04 14:20:47,034 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:20:47,034 INFO L375 BasicCegarLoop]: trace histogram [25, 1, 1, 1] [2018-10-04 14:20:47,034 INFO L423 AbstractCegarLoop]: === Iteration 14 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:20:47,034 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:20:47,035 INFO L82 PathProgramCache]: Analyzing trace with hash 650645672, now seen corresponding path program 13 times [2018-10-04 14:20:47,035 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:20:47,035 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:20:47,036 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:47,036 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:20:47,036 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:47,079 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:20:47,611 INFO L134 CoverageAnalysis]: Checked inductivity of 325 backedges. 0 proven. 325 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:47,612 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:20:47,612 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:20:47,620 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-04 14:20:47,660 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:20:47,675 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:20:47,785 INFO L134 CoverageAnalysis]: Checked inductivity of 325 backedges. 0 proven. 325 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:47,808 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:20:47,808 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [27, 27] total 28 [2018-10-04 14:20:47,808 INFO L459 AbstractCegarLoop]: Interpolant automaton has 29 states [2018-10-04 14:20:47,808 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2018-10-04 14:20:47,808 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:20:47,809 INFO L87 Difference]: Start difference. First operand 29 states and 29 transitions. Second operand 29 states. [2018-10-04 14:20:48,960 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:20:48,960 INFO L93 Difference]: Finished difference Result 33 states and 34 transitions. [2018-10-04 14:20:48,961 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2018-10-04 14:20:48,961 INFO L78 Accepts]: Start accepts. Automaton has 29 states. Word has length 28 [2018-10-04 14:20:48,961 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:20:48,961 INFO L225 Difference]: With dead ends: 33 [2018-10-04 14:20:48,961 INFO L226 Difference]: Without dead ends: 31 [2018-10-04 14:20:48,962 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 1.5s Time 1.2s impTime 28 [2018-10-04 14:20:48,962 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2018-10-04 14:20:48,968 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2018-10-04 14:20:48,969 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 31 states. [2018-10-04 14:20:48,969 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 31 transitions. [2018-10-04 14:20:48,969 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 31 transitions. Word has length 28 [2018-10-04 14:20:48,970 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:20:48,970 INFO L480 AbstractCegarLoop]: Abstraction has 31 states and 31 transitions. [2018-10-04 14:20:48,970 INFO L481 AbstractCegarLoop]: Interpolant automaton has 29 states. [2018-10-04 14:20:48,970 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 31 transitions. [2018-10-04 14:20:48,970 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2018-10-04 14:20:48,971 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:20:48,971 INFO L375 BasicCegarLoop]: trace histogram [27, 1, 1, 1] [2018-10-04 14:20:48,971 INFO L423 AbstractCegarLoop]: === Iteration 15 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:20:48,971 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:20:48,971 INFO L82 PathProgramCache]: Analyzing trace with hash -1794797624, now seen corresponding path program 14 times [2018-10-04 14:20:48,971 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:20:48,972 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:20:48,972 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:48,972 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-04 14:20:48,972 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:49,004 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:20:49,781 INFO L134 CoverageAnalysis]: Checked inductivity of 378 backedges. 0 proven. 378 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:49,782 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:20:49,782 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:20:49,790 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-10-04 14:20:49,846 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-10-04 14:20:49,847 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:20:49,868 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:20:50,011 INFO L134 CoverageAnalysis]: Checked inductivity of 378 backedges. 0 proven. 378 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:50,032 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:20:50,032 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [29, 29] total 30 [2018-10-04 14:20:50,032 INFO L459 AbstractCegarLoop]: Interpolant automaton has 31 states [2018-10-04 14:20:50,032 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2018-10-04 14:20:50,032 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:20:50,032 INFO L87 Difference]: Start difference. First operand 31 states and 31 transitions. Second operand 31 states. [2018-10-04 14:20:51,393 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:20:51,394 INFO L93 Difference]: Finished difference Result 35 states and 36 transitions. [2018-10-04 14:20:51,394 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2018-10-04 14:20:51,394 INFO L78 Accepts]: Start accepts. Automaton has 31 states. Word has length 30 [2018-10-04 14:20:51,394 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:20:51,395 INFO L225 Difference]: With dead ends: 35 [2018-10-04 14:20:51,395 INFO L226 Difference]: Without dead ends: 33 [2018-10-04 14:20:51,396 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 85 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 56 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 2.1s Time 1.7s impTime 30 [2018-10-04 14:20:51,396 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2018-10-04 14:20:51,403 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2018-10-04 14:20:51,403 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 33 states. [2018-10-04 14:20:51,404 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 33 transitions. [2018-10-04 14:20:51,404 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 33 transitions. Word has length 30 [2018-10-04 14:20:51,404 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:20:51,405 INFO L480 AbstractCegarLoop]: Abstraction has 33 states and 33 transitions. [2018-10-04 14:20:51,405 INFO L481 AbstractCegarLoop]: Interpolant automaton has 31 states. [2018-10-04 14:20:51,405 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 33 transitions. [2018-10-04 14:20:51,405 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2018-10-04 14:20:51,406 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:20:51,406 INFO L375 BasicCegarLoop]: trace histogram [29, 1, 1, 1] [2018-10-04 14:20:51,406 INFO L423 AbstractCegarLoop]: === Iteration 16 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:20:51,406 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:20:51,406 INFO L82 PathProgramCache]: Analyzing trace with hash 1776273128, now seen corresponding path program 15 times [2018-10-04 14:20:51,406 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:20:51,407 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:20:51,407 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:51,407 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:20:51,407 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:51,445 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:20:52,112 INFO L134 CoverageAnalysis]: Checked inductivity of 435 backedges. 0 proven. 435 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:52,113 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:20:52,113 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:20:52,120 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-04 14:20:52,145 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 16 check-sat command(s) [2018-10-04 14:20:52,145 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:20:52,147 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:20:52,302 INFO L134 CoverageAnalysis]: Checked inductivity of 435 backedges. 0 proven. 435 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:52,322 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:20:52,322 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [31, 31] total 32 [2018-10-04 14:20:52,322 INFO L459 AbstractCegarLoop]: Interpolant automaton has 33 states [2018-10-04 14:20:52,322 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2018-10-04 14:20:52,322 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:20:52,323 INFO L87 Difference]: Start difference. First operand 33 states and 33 transitions. Second operand 33 states. [2018-10-04 14:20:54,719 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:20:54,719 INFO L93 Difference]: Finished difference Result 37 states and 38 transitions. [2018-10-04 14:20:54,720 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-10-04 14:20:54,720 INFO L78 Accepts]: Start accepts. Automaton has 33 states. Word has length 32 [2018-10-04 14:20:54,720 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:20:54,720 INFO L225 Difference]: With dead ends: 37 [2018-10-04 14:20:54,721 INFO L226 Difference]: Without dead ends: 35 [2018-10-04 14:20:54,721 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 91 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 60 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 2.9s Time 2.5s impTime 32 [2018-10-04 14:20:54,721 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2018-10-04 14:20:54,728 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 35. [2018-10-04 14:20:54,728 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 35 states. [2018-10-04 14:20:54,729 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 35 transitions. [2018-10-04 14:20:54,729 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 35 transitions. Word has length 32 [2018-10-04 14:20:54,729 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:20:54,729 INFO L480 AbstractCegarLoop]: Abstraction has 35 states and 35 transitions. [2018-10-04 14:20:54,729 INFO L481 AbstractCegarLoop]: Interpolant automaton has 33 states. [2018-10-04 14:20:54,730 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 35 transitions. [2018-10-04 14:20:54,730 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2018-10-04 14:20:54,730 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:20:54,730 INFO L375 BasicCegarLoop]: trace histogram [31, 1, 1, 1] [2018-10-04 14:20:54,731 INFO L423 AbstractCegarLoop]: === Iteration 17 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:20:54,731 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:20:54,731 INFO L82 PathProgramCache]: Analyzing trace with hash 1896396296, now seen corresponding path program 16 times [2018-10-04 14:20:54,731 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:20:54,731 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:20:54,732 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:54,732 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:20:54,732 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:54,770 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:20:56,043 INFO L134 CoverageAnalysis]: Checked inductivity of 496 backedges. 0 proven. 496 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:56,043 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:20:56,043 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:20:56,050 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-04 14:20:56,110 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-04 14:20:56,110 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:20:56,140 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:20:56,268 INFO L134 CoverageAnalysis]: Checked inductivity of 496 backedges. 0 proven. 496 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:20:56,288 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:20:56,289 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [33, 33] total 34 [2018-10-04 14:20:56,289 INFO L459 AbstractCegarLoop]: Interpolant automaton has 35 states [2018-10-04 14:20:56,289 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2018-10-04 14:20:56,289 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:20:56,289 INFO L87 Difference]: Start difference. First operand 35 states and 35 transitions. Second operand 35 states. [2018-10-04 14:20:59,198 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:20:59,198 INFO L93 Difference]: Finished difference Result 39 states and 40 transitions. [2018-10-04 14:20:59,198 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2018-10-04 14:20:59,199 INFO L78 Accepts]: Start accepts. Automaton has 35 states. Word has length 34 [2018-10-04 14:20:59,199 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:20:59,200 INFO L225 Difference]: With dead ends: 39 [2018-10-04 14:20:59,200 INFO L226 Difference]: Without dead ends: 37 [2018-10-04 14:20:59,200 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 97 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 64 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 4.0s Time 3.3s impTime 34 [2018-10-04 14:20:59,200 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2018-10-04 14:20:59,206 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 37. [2018-10-04 14:20:59,206 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 37 states. [2018-10-04 14:20:59,206 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 37 transitions. [2018-10-04 14:20:59,206 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 37 transitions. Word has length 34 [2018-10-04 14:20:59,207 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:20:59,207 INFO L480 AbstractCegarLoop]: Abstraction has 37 states and 37 transitions. [2018-10-04 14:20:59,207 INFO L481 AbstractCegarLoop]: Interpolant automaton has 35 states. [2018-10-04 14:20:59,207 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 37 transitions. [2018-10-04 14:20:59,207 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2018-10-04 14:20:59,207 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:20:59,207 INFO L375 BasicCegarLoop]: trace histogram [33, 1, 1, 1] [2018-10-04 14:20:59,208 INFO L423 AbstractCegarLoop]: === Iteration 18 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:20:59,208 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:20:59,208 INFO L82 PathProgramCache]: Analyzing trace with hash 1370643752, now seen corresponding path program 17 times [2018-10-04 14:20:59,208 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:20:59,208 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:20:59,208 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:59,209 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:20:59,209 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:20:59,256 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:21:00,297 INFO L134 CoverageAnalysis]: Checked inductivity of 561 backedges. 0 proven. 561 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:21:00,298 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:21:00,298 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:21:00,306 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-10-04 14:21:00,368 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 18 check-sat command(s) [2018-10-04 14:21:00,368 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:21:00,380 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:21:00,495 INFO L134 CoverageAnalysis]: Checked inductivity of 561 backedges. 0 proven. 561 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:21:00,515 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:21:00,515 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [35, 35] total 36 [2018-10-04 14:21:00,515 INFO L459 AbstractCegarLoop]: Interpolant automaton has 37 states [2018-10-04 14:21:00,516 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2018-10-04 14:21:00,516 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:21:00,516 INFO L87 Difference]: Start difference. First operand 37 states and 37 transitions. Second operand 37 states. [2018-10-04 14:21:03,114 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:21:03,114 INFO L93 Difference]: Finished difference Result 41 states and 42 transitions. [2018-10-04 14:21:03,116 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 37 states. [2018-10-04 14:21:03,116 INFO L78 Accepts]: Start accepts. Automaton has 37 states. Word has length 36 [2018-10-04 14:21:03,116 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:21:03,117 INFO L225 Difference]: With dead ends: 41 [2018-10-04 14:21:03,117 INFO L226 Difference]: Without dead ends: 39 [2018-10-04 14:21:03,117 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 103 GetRequests, 35 SyntacticMatches, 0 SemanticMatches, 68 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 3.5s Time 3.1s impTime 36 [2018-10-04 14:21:03,118 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2018-10-04 14:21:03,126 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 39. [2018-10-04 14:21:03,127 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 39 states. [2018-10-04 14:21:03,127 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 39 transitions. [2018-10-04 14:21:03,127 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 39 transitions. Word has length 36 [2018-10-04 14:21:03,128 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:21:03,128 INFO L480 AbstractCegarLoop]: Abstraction has 39 states and 39 transitions. [2018-10-04 14:21:03,128 INFO L481 AbstractCegarLoop]: Interpolant automaton has 37 states. [2018-10-04 14:21:03,128 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 39 transitions. [2018-10-04 14:21:03,128 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2018-10-04 14:21:03,128 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:21:03,129 INFO L375 BasicCegarLoop]: trace histogram [35, 1, 1, 1] [2018-10-04 14:21:03,129 INFO L423 AbstractCegarLoop]: === Iteration 19 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:21:03,129 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:21:03,129 INFO L82 PathProgramCache]: Analyzing trace with hash -1366377400, now seen corresponding path program 18 times [2018-10-04 14:21:03,129 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:21:03,129 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:21:03,130 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:21:03,130 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:21:03,130 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:21:03,190 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:21:04,881 INFO L134 CoverageAnalysis]: Checked inductivity of 630 backedges. 0 proven. 630 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:21:04,881 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:21:04,882 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:21:04,889 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-10-04 14:21:04,915 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 19 check-sat command(s) [2018-10-04 14:21:04,915 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:21:04,918 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:21:05,118 INFO L134 CoverageAnalysis]: Checked inductivity of 630 backedges. 0 proven. 630 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:21:05,138 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:21:05,138 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [37, 37] total 38 [2018-10-04 14:21:05,138 INFO L459 AbstractCegarLoop]: Interpolant automaton has 39 states [2018-10-04 14:21:05,139 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 39 interpolants. [2018-10-04 14:21:05,139 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:21:05,139 INFO L87 Difference]: Start difference. First operand 39 states and 39 transitions. Second operand 39 states. [2018-10-04 14:21:07,520 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:21:07,521 INFO L93 Difference]: Finished difference Result 43 states and 44 transitions. [2018-10-04 14:21:07,521 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 39 states. [2018-10-04 14:21:07,521 INFO L78 Accepts]: Start accepts. Automaton has 39 states. Word has length 38 [2018-10-04 14:21:07,522 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:21:07,522 INFO L225 Difference]: With dead ends: 43 [2018-10-04 14:21:07,522 INFO L226 Difference]: Without dead ends: 41 [2018-10-04 14:21:07,523 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 37 SyntacticMatches, 0 SemanticMatches, 72 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 4.0s Time 3.3s impTime 38 [2018-10-04 14:21:07,523 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2018-10-04 14:21:07,532 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2018-10-04 14:21:07,532 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 41 states. [2018-10-04 14:21:07,533 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 41 transitions. [2018-10-04 14:21:07,533 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 41 transitions. Word has length 38 [2018-10-04 14:21:07,533 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:21:07,533 INFO L480 AbstractCegarLoop]: Abstraction has 41 states and 41 transitions. [2018-10-04 14:21:07,533 INFO L481 AbstractCegarLoop]: Interpolant automaton has 39 states. [2018-10-04 14:21:07,534 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 41 transitions. [2018-10-04 14:21:07,534 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2018-10-04 14:21:07,534 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:21:07,534 INFO L375 BasicCegarLoop]: trace histogram [37, 1, 1, 1] [2018-10-04 14:21:07,535 INFO L423 AbstractCegarLoop]: === Iteration 20 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:21:07,535 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:21:07,535 INFO L82 PathProgramCache]: Analyzing trace with hash 1171247976, now seen corresponding path program 19 times [2018-10-04 14:21:07,535 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:21:07,535 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:21:07,536 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:21:07,536 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:21:07,536 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:21:07,601 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:21:09,028 INFO L134 CoverageAnalysis]: Checked inductivity of 703 backedges. 0 proven. 703 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:21:09,029 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:21:09,029 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:21:09,037 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-04 14:21:09,126 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:21:09,173 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:21:09,306 INFO L134 CoverageAnalysis]: Checked inductivity of 703 backedges. 0 proven. 703 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:21:09,327 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:21:09,328 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [39, 39] total 40 [2018-10-04 14:21:09,328 INFO L459 AbstractCegarLoop]: Interpolant automaton has 41 states [2018-10-04 14:21:09,328 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 41 interpolants. [2018-10-04 14:21:09,328 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:21:09,328 INFO L87 Difference]: Start difference. First operand 41 states and 41 transitions. Second operand 41 states. [2018-10-04 14:21:12,424 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:21:12,424 INFO L93 Difference]: Finished difference Result 45 states and 46 transitions. [2018-10-04 14:21:12,424 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2018-10-04 14:21:12,425 INFO L78 Accepts]: Start accepts. Automaton has 41 states. Word has length 40 [2018-10-04 14:21:12,425 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:21:12,425 INFO L225 Difference]: With dead ends: 45 [2018-10-04 14:21:12,426 INFO L226 Difference]: Without dead ends: 43 [2018-10-04 14:21:12,426 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 115 GetRequests, 39 SyntacticMatches, 0 SemanticMatches, 76 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 4.4s Time 3.8s impTime 40 [2018-10-04 14:21:12,426 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2018-10-04 14:21:12,436 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2018-10-04 14:21:12,437 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 43 states. [2018-10-04 14:21:12,437 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 43 transitions. [2018-10-04 14:21:12,437 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 43 transitions. Word has length 40 [2018-10-04 14:21:12,438 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:21:12,438 INFO L480 AbstractCegarLoop]: Abstraction has 43 states and 43 transitions. [2018-10-04 14:21:12,438 INFO L481 AbstractCegarLoop]: Interpolant automaton has 41 states. [2018-10-04 14:21:12,438 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 43 transitions. [2018-10-04 14:21:12,439 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2018-10-04 14:21:12,439 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:21:12,439 INFO L375 BasicCegarLoop]: trace histogram [39, 1, 1, 1] [2018-10-04 14:21:12,439 INFO L423 AbstractCegarLoop]: === Iteration 21 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:21:12,439 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:21:12,440 INFO L82 PathProgramCache]: Analyzing trace with hash 287810184, now seen corresponding path program 20 times [2018-10-04 14:21:12,440 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:21:12,440 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:21:12,441 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:21:12,441 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-04 14:21:12,441 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:21:12,525 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:21:13,621 INFO L134 CoverageAnalysis]: Checked inductivity of 780 backedges. 0 proven. 780 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:21:13,621 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:21:13,621 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:21:13,629 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-10-04 14:21:13,729 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-10-04 14:21:13,729 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:21:13,786 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:21:13,936 INFO L134 CoverageAnalysis]: Checked inductivity of 780 backedges. 0 proven. 780 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:21:13,958 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:21:13,958 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [41, 41] total 42 [2018-10-04 14:21:13,958 INFO L459 AbstractCegarLoop]: Interpolant automaton has 43 states [2018-10-04 14:21:13,958 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 43 interpolants. [2018-10-04 14:21:13,958 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:21:13,959 INFO L87 Difference]: Start difference. First operand 43 states and 43 transitions. Second operand 43 states. [2018-10-04 14:21:17,398 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:21:17,398 INFO L93 Difference]: Finished difference Result 47 states and 48 transitions. [2018-10-04 14:21:17,405 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 43 states. [2018-10-04 14:21:17,405 INFO L78 Accepts]: Start accepts. Automaton has 43 states. Word has length 42 [2018-10-04 14:21:17,405 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:21:17,406 INFO L225 Difference]: With dead ends: 47 [2018-10-04 14:21:17,406 INFO L226 Difference]: Without dead ends: 45 [2018-10-04 14:21:17,406 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 121 GetRequests, 41 SyntacticMatches, 0 SemanticMatches, 80 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 4.4s Time 3.9s impTime 42 [2018-10-04 14:21:17,406 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2018-10-04 14:21:17,417 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 45. [2018-10-04 14:21:17,417 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 45 states. [2018-10-04 14:21:17,418 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 45 transitions. [2018-10-04 14:21:17,418 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 45 transitions. Word has length 42 [2018-10-04 14:21:17,418 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:21:17,418 INFO L480 AbstractCegarLoop]: Abstraction has 45 states and 45 transitions. [2018-10-04 14:21:17,418 INFO L481 AbstractCegarLoop]: Interpolant automaton has 43 states. [2018-10-04 14:21:17,418 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 45 transitions. [2018-10-04 14:21:17,419 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2018-10-04 14:21:17,419 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:21:17,419 INFO L375 BasicCegarLoop]: trace histogram [41, 1, 1, 1] [2018-10-04 14:21:17,419 INFO L423 AbstractCegarLoop]: === Iteration 22 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:21:17,420 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:21:17,420 INFO L82 PathProgramCache]: Analyzing trace with hash 1707616680, now seen corresponding path program 21 times [2018-10-04 14:21:17,420 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:21:17,420 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:21:17,421 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:21:17,421 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:21:17,421 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:21:17,488 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:21:18,759 INFO L134 CoverageAnalysis]: Checked inductivity of 861 backedges. 0 proven. 861 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:21:18,760 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:21:18,760 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:21:18,775 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-04 14:21:18,801 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 22 check-sat command(s) [2018-10-04 14:21:18,802 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:21:18,804 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:21:18,946 INFO L134 CoverageAnalysis]: Checked inductivity of 861 backedges. 0 proven. 861 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:21:18,966 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:21:18,966 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [43, 43] total 44 [2018-10-04 14:21:18,966 INFO L459 AbstractCegarLoop]: Interpolant automaton has 45 states [2018-10-04 14:21:18,967 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2018-10-04 14:21:18,967 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:21:18,967 INFO L87 Difference]: Start difference. First operand 45 states and 45 transitions. Second operand 45 states. [2018-10-04 14:21:22,858 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:21:22,859 INFO L93 Difference]: Finished difference Result 49 states and 50 transitions. [2018-10-04 14:21:22,861 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2018-10-04 14:21:22,861 INFO L78 Accepts]: Start accepts. Automaton has 45 states. Word has length 44 [2018-10-04 14:21:22,862 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:21:22,862 INFO L225 Difference]: With dead ends: 49 [2018-10-04 14:21:22,862 INFO L226 Difference]: Without dead ends: 47 [2018-10-04 14:21:22,863 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 127 GetRequests, 43 SyntacticMatches, 0 SemanticMatches, 84 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 5.0s Time 4.5s impTime 44 [2018-10-04 14:21:22,863 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2018-10-04 14:21:22,873 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2018-10-04 14:21:22,873 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 47 states. [2018-10-04 14:21:22,873 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 47 transitions. [2018-10-04 14:21:22,874 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 47 transitions. Word has length 44 [2018-10-04 14:21:22,874 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:21:22,874 INFO L480 AbstractCegarLoop]: Abstraction has 47 states and 47 transitions. [2018-10-04 14:21:22,874 INFO L481 AbstractCegarLoop]: Interpolant automaton has 45 states. [2018-10-04 14:21:22,874 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 47 transitions. [2018-10-04 14:21:22,875 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2018-10-04 14:21:22,875 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:21:22,875 INFO L375 BasicCegarLoop]: trace histogram [43, 1, 1, 1] [2018-10-04 14:21:22,875 INFO L423 AbstractCegarLoop]: === Iteration 23 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:21:22,875 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:21:22,875 INFO L82 PathProgramCache]: Analyzing trace with hash 342059208, now seen corresponding path program 22 times [2018-10-04 14:21:22,875 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:21:22,876 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:21:22,876 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:21:22,876 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:21:22,876 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:21:22,973 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:21:24,225 INFO L134 CoverageAnalysis]: Checked inductivity of 946 backedges. 0 proven. 946 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:21:24,226 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:21:24,226 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:21:24,233 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-04 14:21:24,362 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-04 14:21:24,362 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:21:24,435 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:21:24,568 INFO L134 CoverageAnalysis]: Checked inductivity of 946 backedges. 0 proven. 946 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:21:24,588 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:21:24,588 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [45, 45] total 46 [2018-10-04 14:21:24,588 INFO L459 AbstractCegarLoop]: Interpolant automaton has 47 states [2018-10-04 14:21:24,588 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 47 interpolants. [2018-10-04 14:21:24,589 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:21:24,589 INFO L87 Difference]: Start difference. First operand 47 states and 47 transitions. Second operand 47 states. [2018-10-04 14:21:28,369 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:21:28,370 INFO L93 Difference]: Finished difference Result 51 states and 52 transitions. [2018-10-04 14:21:28,370 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 47 states. [2018-10-04 14:21:28,370 INFO L78 Accepts]: Start accepts. Automaton has 47 states. Word has length 46 [2018-10-04 14:21:28,371 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:21:28,371 INFO L225 Difference]: With dead ends: 51 [2018-10-04 14:21:28,371 INFO L226 Difference]: Without dead ends: 49 [2018-10-04 14:21:28,371 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 133 GetRequests, 45 SyntacticMatches, 0 SemanticMatches, 88 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 4.9s Time 4.4s impTime 46 [2018-10-04 14:21:28,372 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2018-10-04 14:21:28,381 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 49. [2018-10-04 14:21:28,381 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 49 states. [2018-10-04 14:21:28,381 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 49 transitions. [2018-10-04 14:21:28,381 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 49 transitions. Word has length 46 [2018-10-04 14:21:28,382 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:21:28,382 INFO L480 AbstractCegarLoop]: Abstraction has 49 states and 49 transitions. [2018-10-04 14:21:28,382 INFO L481 AbstractCegarLoop]: Interpolant automaton has 47 states. [2018-10-04 14:21:28,382 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 49 transitions. [2018-10-04 14:21:28,382 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2018-10-04 14:21:28,382 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:21:28,382 INFO L375 BasicCegarLoop]: trace histogram [45, 1, 1, 1] [2018-10-04 14:21:28,383 INFO L423 AbstractCegarLoop]: === Iteration 24 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:21:28,383 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:21:28,383 INFO L82 PathProgramCache]: Analyzing trace with hash -1993646104, now seen corresponding path program 23 times [2018-10-04 14:21:28,383 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:21:28,383 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:21:28,383 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:21:28,384 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:21:28,384 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:21:28,490 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:21:30,136 INFO L134 CoverageAnalysis]: Checked inductivity of 1035 backedges. 0 proven. 1035 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:21:30,136 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:21:30,136 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 24 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 24 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:21:30,143 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-10-04 14:21:30,267 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 24 check-sat command(s) [2018-10-04 14:21:30,267 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:21:30,288 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:21:30,938 INFO L134 CoverageAnalysis]: Checked inductivity of 1035 backedges. 0 proven. 1035 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:21:30,962 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:21:30,963 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [47, 47] total 48 [2018-10-04 14:21:30,963 INFO L459 AbstractCegarLoop]: Interpolant automaton has 49 states [2018-10-04 14:21:30,963 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 49 interpolants. [2018-10-04 14:21:30,963 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:21:30,963 INFO L87 Difference]: Start difference. First operand 49 states and 49 transitions. Second operand 49 states. [2018-10-04 14:21:35,106 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:21:35,106 INFO L93 Difference]: Finished difference Result 53 states and 54 transitions. [2018-10-04 14:21:35,106 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 49 states. [2018-10-04 14:21:35,107 INFO L78 Accepts]: Start accepts. Automaton has 49 states. Word has length 48 [2018-10-04 14:21:35,107 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:21:35,107 INFO L225 Difference]: With dead ends: 53 [2018-10-04 14:21:35,108 INFO L226 Difference]: Without dead ends: 51 [2018-10-04 14:21:35,108 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 139 GetRequests, 47 SyntacticMatches, 0 SemanticMatches, 92 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 6.1s Time 4.9s impTime 48 [2018-10-04 14:21:35,108 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2018-10-04 14:21:35,119 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2018-10-04 14:21:35,119 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 51 states. [2018-10-04 14:21:35,120 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 51 transitions. [2018-10-04 14:21:35,120 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 51 transitions. Word has length 48 [2018-10-04 14:21:35,120 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:21:35,121 INFO L480 AbstractCegarLoop]: Abstraction has 51 states and 51 transitions. [2018-10-04 14:21:35,121 INFO L481 AbstractCegarLoop]: Interpolant automaton has 49 states. [2018-10-04 14:21:35,121 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 51 transitions. [2018-10-04 14:21:35,121 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2018-10-04 14:21:35,121 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:21:35,121 INFO L375 BasicCegarLoop]: trace histogram [47, 1, 1, 1] [2018-10-04 14:21:35,122 INFO L423 AbstractCegarLoop]: === Iteration 25 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:21:35,122 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:21:35,122 INFO L82 PathProgramCache]: Analyzing trace with hash -338555128, now seen corresponding path program 24 times [2018-10-04 14:21:35,122 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:21:35,122 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:21:35,123 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:21:35,123 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:21:35,123 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:21:35,245 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:21:37,015 INFO L134 CoverageAnalysis]: Checked inductivity of 1128 backedges. 0 proven. 1128 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:21:37,015 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:21:37,015 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:21:37,022 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-10-04 14:21:37,054 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 25 check-sat command(s) [2018-10-04 14:21:37,054 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:21:37,056 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:21:37,206 INFO L134 CoverageAnalysis]: Checked inductivity of 1128 backedges. 0 proven. 1128 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:21:37,226 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:21:37,227 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [49, 49] total 50 [2018-10-04 14:21:37,227 INFO L459 AbstractCegarLoop]: Interpolant automaton has 51 states [2018-10-04 14:21:37,227 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 51 interpolants. [2018-10-04 14:21:37,227 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:21:37,227 INFO L87 Difference]: Start difference. First operand 51 states and 51 transitions. Second operand 51 states. [2018-10-04 14:21:41,543 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:21:41,543 INFO L93 Difference]: Finished difference Result 55 states and 56 transitions. [2018-10-04 14:21:41,543 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 51 states. [2018-10-04 14:21:41,544 INFO L78 Accepts]: Start accepts. Automaton has 51 states. Word has length 50 [2018-10-04 14:21:41,544 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:21:41,544 INFO L225 Difference]: With dead ends: 55 [2018-10-04 14:21:41,544 INFO L226 Difference]: Without dead ends: 53 [2018-10-04 14:21:41,545 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 145 GetRequests, 49 SyntacticMatches, 0 SemanticMatches, 96 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 5.9s Time 5.3s impTime 50 [2018-10-04 14:21:41,545 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2018-10-04 14:21:41,554 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 53. [2018-10-04 14:21:41,554 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 53 states. [2018-10-04 14:21:41,554 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 53 transitions. [2018-10-04 14:21:41,554 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 53 transitions. Word has length 50 [2018-10-04 14:21:41,554 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:21:41,555 INFO L480 AbstractCegarLoop]: Abstraction has 53 states and 53 transitions. [2018-10-04 14:21:41,555 INFO L481 AbstractCegarLoop]: Interpolant automaton has 51 states. [2018-10-04 14:21:41,555 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 53 transitions. [2018-10-04 14:21:41,555 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2018-10-04 14:21:41,555 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:21:41,555 INFO L375 BasicCegarLoop]: trace histogram [49, 1, 1, 1] [2018-10-04 14:21:41,555 INFO L423 AbstractCegarLoop]: === Iteration 26 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:21:41,555 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:21:41,556 INFO L82 PathProgramCache]: Analyzing trace with hash 1065973288, now seen corresponding path program 25 times [2018-10-04 14:21:41,556 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:21:41,556 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:21:41,556 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:21:41,556 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:21:41,557 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:21:41,663 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:21:43,327 INFO L134 CoverageAnalysis]: Checked inductivity of 1225 backedges. 0 proven. 1225 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:21:43,327 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:21:43,327 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 26 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 26 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:21:43,334 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-04 14:21:43,517 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:21:43,625 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:21:43,777 INFO L134 CoverageAnalysis]: Checked inductivity of 1225 backedges. 0 proven. 1225 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:21:43,797 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:21:43,797 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [51, 51] total 52 [2018-10-04 14:21:43,797 INFO L459 AbstractCegarLoop]: Interpolant automaton has 53 states [2018-10-04 14:21:43,797 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 53 interpolants. [2018-10-04 14:21:43,798 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:21:43,798 INFO L87 Difference]: Start difference. First operand 53 states and 53 transitions. Second operand 53 states. [2018-10-04 14:21:49,466 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:21:49,467 INFO L93 Difference]: Finished difference Result 57 states and 58 transitions. [2018-10-04 14:21:49,467 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 53 states. [2018-10-04 14:21:49,467 INFO L78 Accepts]: Start accepts. Automaton has 53 states. Word has length 52 [2018-10-04 14:21:49,467 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:21:49,468 INFO L225 Difference]: With dead ends: 57 [2018-10-04 14:21:49,468 INFO L226 Difference]: Without dead ends: 55 [2018-10-04 14:21:49,468 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 151 GetRequests, 51 SyntacticMatches, 0 SemanticMatches, 100 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 7.1s Time 6.5s impTime 52 [2018-10-04 14:21:49,469 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2018-10-04 14:21:49,479 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2018-10-04 14:21:49,479 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 55 states. [2018-10-04 14:21:49,480 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 55 transitions. [2018-10-04 14:21:49,480 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 55 transitions. Word has length 52 [2018-10-04 14:21:49,480 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:21:49,480 INFO L480 AbstractCegarLoop]: Abstraction has 55 states and 55 transitions. [2018-10-04 14:21:49,480 INFO L481 AbstractCegarLoop]: Interpolant automaton has 53 states. [2018-10-04 14:21:49,480 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 55 transitions. [2018-10-04 14:21:49,481 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2018-10-04 14:21:49,481 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:21:49,481 INFO L375 BasicCegarLoop]: trace histogram [51, 1, 1, 1] [2018-10-04 14:21:49,481 INFO L423 AbstractCegarLoop]: === Iteration 27 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:21:49,482 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:21:49,482 INFO L82 PathProgramCache]: Analyzing trace with hash -2096917176, now seen corresponding path program 26 times [2018-10-04 14:21:49,482 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:21:49,482 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:21:49,483 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:21:49,483 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-04 14:21:49,483 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:21:49,628 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:21:51,564 INFO L134 CoverageAnalysis]: Checked inductivity of 1326 backedges. 0 proven. 1326 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:21:51,565 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:21:51,565 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 27 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 27 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:21:51,574 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-10-04 14:21:51,782 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-10-04 14:21:51,782 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:21:51,900 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:21:52,058 INFO L134 CoverageAnalysis]: Checked inductivity of 1326 backedges. 0 proven. 1326 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:21:52,078 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:21:52,078 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [53, 53] total 54 [2018-10-04 14:21:52,079 INFO L459 AbstractCegarLoop]: Interpolant automaton has 55 states [2018-10-04 14:21:52,079 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 55 interpolants. [2018-10-04 14:21:52,079 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:21:52,079 INFO L87 Difference]: Start difference. First operand 55 states and 55 transitions. Second operand 55 states. [2018-10-04 14:21:57,533 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:21:57,533 INFO L93 Difference]: Finished difference Result 59 states and 60 transitions. [2018-10-04 14:21:57,533 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 55 states. [2018-10-04 14:21:57,533 INFO L78 Accepts]: Start accepts. Automaton has 55 states. Word has length 54 [2018-10-04 14:21:57,534 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:21:57,534 INFO L225 Difference]: With dead ends: 59 [2018-10-04 14:21:57,534 INFO L226 Difference]: Without dead ends: 57 [2018-10-04 14:21:57,535 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 157 GetRequests, 53 SyntacticMatches, 0 SemanticMatches, 104 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 7.2s Time 6.5s impTime 54 [2018-10-04 14:21:57,535 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2018-10-04 14:21:57,546 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 57. [2018-10-04 14:21:57,546 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 57 states. [2018-10-04 14:21:57,547 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 57 transitions. [2018-10-04 14:21:57,547 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 57 transitions. Word has length 54 [2018-10-04 14:21:57,547 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:21:57,547 INFO L480 AbstractCegarLoop]: Abstraction has 57 states and 57 transitions. [2018-10-04 14:21:57,547 INFO L481 AbstractCegarLoop]: Interpolant automaton has 55 states. [2018-10-04 14:21:57,547 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 57 transitions. [2018-10-04 14:21:57,548 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2018-10-04 14:21:57,548 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:21:57,548 INFO L375 BasicCegarLoop]: trace histogram [53, 1, 1, 1] [2018-10-04 14:21:57,548 INFO L423 AbstractCegarLoop]: === Iteration 28 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:21:57,549 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:21:57,549 INFO L82 PathProgramCache]: Analyzing trace with hash -797807512, now seen corresponding path program 27 times [2018-10-04 14:21:57,549 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:21:57,549 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:21:57,550 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:21:57,550 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:21:57,550 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:21:57,701 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:21:59,623 INFO L134 CoverageAnalysis]: Checked inductivity of 1431 backedges. 0 proven. 1431 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:21:59,623 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:21:59,623 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 28 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 28 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:21:59,632 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-04 14:21:59,666 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 28 check-sat command(s) [2018-10-04 14:21:59,666 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:21:59,669 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:21:59,855 INFO L134 CoverageAnalysis]: Checked inductivity of 1431 backedges. 0 proven. 1431 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:21:59,876 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:21:59,876 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [55, 55] total 56 [2018-10-04 14:21:59,876 INFO L459 AbstractCegarLoop]: Interpolant automaton has 57 states [2018-10-04 14:21:59,877 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 57 interpolants. [2018-10-04 14:21:59,877 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:21:59,877 INFO L87 Difference]: Start difference. First operand 57 states and 57 transitions. Second operand 57 states. [2018-10-04 14:22:07,122 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:22:07,122 INFO L93 Difference]: Finished difference Result 61 states and 62 transitions. [2018-10-04 14:22:07,123 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 57 states. [2018-10-04 14:22:07,123 INFO L78 Accepts]: Start accepts. Automaton has 57 states. Word has length 56 [2018-10-04 14:22:07,123 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:22:07,124 INFO L225 Difference]: With dead ends: 61 [2018-10-04 14:22:07,124 INFO L226 Difference]: Without dead ends: 59 [2018-10-04 14:22:07,124 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 163 GetRequests, 55 SyntacticMatches, 0 SemanticMatches, 108 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 8.9s Time 8.3s impTime 56 [2018-10-04 14:22:07,124 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2018-10-04 14:22:07,133 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 59. [2018-10-04 14:22:07,133 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 59 states. [2018-10-04 14:22:07,134 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 59 transitions. [2018-10-04 14:22:07,134 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 59 transitions. Word has length 56 [2018-10-04 14:22:07,134 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:22:07,134 INFO L480 AbstractCegarLoop]: Abstraction has 59 states and 59 transitions. [2018-10-04 14:22:07,134 INFO L481 AbstractCegarLoop]: Interpolant automaton has 57 states. [2018-10-04 14:22:07,134 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 59 transitions. [2018-10-04 14:22:07,134 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2018-10-04 14:22:07,135 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:22:07,135 INFO L375 BasicCegarLoop]: trace histogram [55, 1, 1, 1] [2018-10-04 14:22:07,135 INFO L423 AbstractCegarLoop]: === Iteration 29 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:22:07,135 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:22:07,135 INFO L82 PathProgramCache]: Analyzing trace with hash 2106063752, now seen corresponding path program 28 times [2018-10-04 14:22:07,135 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:22:07,135 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:22:07,136 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:22:07,136 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:22:07,136 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:22:07,284 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:22:09,463 INFO L134 CoverageAnalysis]: Checked inductivity of 1540 backedges. 0 proven. 1540 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:22:09,463 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:22:09,463 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 29 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 29 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:22:09,471 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-04 14:22:09,721 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-04 14:22:09,721 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:22:09,868 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:22:10,065 INFO L134 CoverageAnalysis]: Checked inductivity of 1540 backedges. 0 proven. 1540 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:22:10,085 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:22:10,085 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [57, 57] total 58 [2018-10-04 14:22:10,085 INFO L459 AbstractCegarLoop]: Interpolant automaton has 59 states [2018-10-04 14:22:10,085 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 59 interpolants. [2018-10-04 14:22:10,085 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:22:10,085 INFO L87 Difference]: Start difference. First operand 59 states and 59 transitions. Second operand 59 states. [2018-10-04 14:22:17,193 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:22:17,193 INFO L93 Difference]: Finished difference Result 63 states and 64 transitions. [2018-10-04 14:22:17,194 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 59 states. [2018-10-04 14:22:17,194 INFO L78 Accepts]: Start accepts. Automaton has 59 states. Word has length 58 [2018-10-04 14:22:17,194 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:22:17,195 INFO L225 Difference]: With dead ends: 63 [2018-10-04 14:22:17,195 INFO L226 Difference]: Without dead ends: 61 [2018-10-04 14:22:17,195 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 169 GetRequests, 57 SyntacticMatches, 0 SemanticMatches, 112 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 9.1s Time 8.3s impTime 58 [2018-10-04 14:22:17,195 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 61 states. [2018-10-04 14:22:17,206 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 61 to 61. [2018-10-04 14:22:17,206 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 61 states. [2018-10-04 14:22:17,206 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 61 transitions. [2018-10-04 14:22:17,207 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 61 transitions. Word has length 58 [2018-10-04 14:22:17,207 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:22:17,207 INFO L480 AbstractCegarLoop]: Abstraction has 61 states and 61 transitions. [2018-10-04 14:22:17,207 INFO L481 AbstractCegarLoop]: Interpolant automaton has 59 states. [2018-10-04 14:22:17,207 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 61 transitions. [2018-10-04 14:22:17,207 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2018-10-04 14:22:17,207 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:22:17,207 INFO L375 BasicCegarLoop]: trace histogram [57, 1, 1, 1] [2018-10-04 14:22:17,208 INFO L423 AbstractCegarLoop]: === Iteration 30 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:22:17,208 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:22:17,208 INFO L82 PathProgramCache]: Analyzing trace with hash 997606056, now seen corresponding path program 29 times [2018-10-04 14:22:17,208 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:22:17,208 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:22:17,209 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:22:17,209 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:22:17,209 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:22:17,356 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:22:19,529 INFO L134 CoverageAnalysis]: Checked inductivity of 1653 backedges. 0 proven. 1653 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:22:19,529 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:22:19,529 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 30 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 30 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:22:19,536 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-10-04 14:22:19,763 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 30 check-sat command(s) [2018-10-04 14:22:19,763 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:22:19,798 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:22:19,993 INFO L134 CoverageAnalysis]: Checked inductivity of 1653 backedges. 0 proven. 1653 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:22:20,014 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:22:20,014 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [59, 59] total 60 [2018-10-04 14:22:20,014 INFO L459 AbstractCegarLoop]: Interpolant automaton has 61 states [2018-10-04 14:22:20,015 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 61 interpolants. [2018-10-04 14:22:20,015 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:22:20,015 INFO L87 Difference]: Start difference. First operand 61 states and 61 transitions. Second operand 61 states. [2018-10-04 14:22:31,255 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:22:31,256 INFO L93 Difference]: Finished difference Result 65 states and 66 transitions. [2018-10-04 14:22:31,256 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 61 states. [2018-10-04 14:22:31,256 INFO L78 Accepts]: Start accepts. Automaton has 61 states. Word has length 60 [2018-10-04 14:22:31,257 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:22:31,257 INFO L225 Difference]: With dead ends: 65 [2018-10-04 14:22:31,257 INFO L226 Difference]: Without dead ends: 63 [2018-10-04 14:22:31,258 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 175 GetRequests, 59 SyntacticMatches, 0 SemanticMatches, 116 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 13.2s Time 12.4s impTime 60 [2018-10-04 14:22:31,258 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2018-10-04 14:22:31,268 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 63. [2018-10-04 14:22:31,269 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 63 states. [2018-10-04 14:22:31,269 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 63 transitions. [2018-10-04 14:22:31,269 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 63 transitions. Word has length 60 [2018-10-04 14:22:31,269 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:22:31,269 INFO L480 AbstractCegarLoop]: Abstraction has 63 states and 63 transitions. [2018-10-04 14:22:31,269 INFO L481 AbstractCegarLoop]: Interpolant automaton has 61 states. [2018-10-04 14:22:31,269 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 63 transitions. [2018-10-04 14:22:31,270 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2018-10-04 14:22:31,270 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:22:31,270 INFO L375 BasicCegarLoop]: trace histogram [59, 1, 1, 1] [2018-10-04 14:22:31,270 INFO L423 AbstractCegarLoop]: === Iteration 31 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:22:31,270 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:22:31,270 INFO L82 PathProgramCache]: Analyzing trace with hash 921649608, now seen corresponding path program 30 times [2018-10-04 14:22:31,271 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:22:31,271 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:22:31,271 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:22:31,272 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:22:31,272 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:22:31,452 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:22:33,987 INFO L134 CoverageAnalysis]: Checked inductivity of 1770 backedges. 0 proven. 1770 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:22:33,987 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:22:33,987 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 31 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 31 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:22:33,998 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-10-04 14:22:34,044 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 31 check-sat command(s) [2018-10-04 14:22:34,044 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:22:34,047 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:22:34,245 INFO L134 CoverageAnalysis]: Checked inductivity of 1770 backedges. 0 proven. 1770 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:22:34,266 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:22:34,266 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [61, 61] total 62 [2018-10-04 14:22:34,266 INFO L459 AbstractCegarLoop]: Interpolant automaton has 63 states [2018-10-04 14:22:34,266 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 63 interpolants. [2018-10-04 14:22:34,266 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:22:34,266 INFO L87 Difference]: Start difference. First operand 63 states and 63 transitions. Second operand 63 states. [2018-10-04 14:22:43,460 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:22:43,461 INFO L93 Difference]: Finished difference Result 67 states and 68 transitions. [2018-10-04 14:22:43,461 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 63 states. [2018-10-04 14:22:43,461 INFO L78 Accepts]: Start accepts. Automaton has 63 states. Word has length 62 [2018-10-04 14:22:43,461 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:22:43,462 INFO L225 Difference]: With dead ends: 67 [2018-10-04 14:22:43,462 INFO L226 Difference]: Without dead ends: 65 [2018-10-04 14:22:43,463 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 181 GetRequests, 61 SyntacticMatches, 0 SemanticMatches, 120 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 11.5s Time 10.7s impTime 62 [2018-10-04 14:22:43,463 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2018-10-04 14:22:43,475 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 65. [2018-10-04 14:22:43,475 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 65 states. [2018-10-04 14:22:43,476 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 65 states to 65 states and 65 transitions. [2018-10-04 14:22:43,476 INFO L78 Accepts]: Start accepts. Automaton has 65 states and 65 transitions. Word has length 62 [2018-10-04 14:22:43,476 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:22:43,476 INFO L480 AbstractCegarLoop]: Abstraction has 65 states and 65 transitions. [2018-10-04 14:22:43,476 INFO L481 AbstractCegarLoop]: Interpolant automaton has 63 states. [2018-10-04 14:22:43,476 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 65 transitions. [2018-10-04 14:22:43,476 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2018-10-04 14:22:43,476 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:22:43,477 INFO L375 BasicCegarLoop]: trace histogram [61, 1, 1, 1] [2018-10-04 14:22:43,477 INFO L423 AbstractCegarLoop]: === Iteration 32 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:22:43,477 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:22:43,477 INFO L82 PathProgramCache]: Analyzing trace with hash 941947112, now seen corresponding path program 31 times [2018-10-04 14:22:43,477 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:22:43,477 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:22:43,478 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:22:43,478 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:22:43,478 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:22:43,665 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:22:46,178 INFO L134 CoverageAnalysis]: Checked inductivity of 1891 backedges. 0 proven. 1891 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:22:46,178 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:22:46,178 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 32 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 32 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:22:46,186 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-04 14:22:46,518 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:22:46,727 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:22:46,933 INFO L134 CoverageAnalysis]: Checked inductivity of 1891 backedges. 0 proven. 1891 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:22:46,953 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:22:46,953 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [63, 63] total 64 [2018-10-04 14:22:46,954 INFO L459 AbstractCegarLoop]: Interpolant automaton has 65 states [2018-10-04 14:22:46,954 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 65 interpolants. [2018-10-04 14:22:46,954 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:22:46,954 INFO L87 Difference]: Start difference. First operand 65 states and 65 transitions. Second operand 65 states. [2018-10-04 14:22:54,759 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:22:54,760 INFO L93 Difference]: Finished difference Result 69 states and 70 transitions. [2018-10-04 14:22:54,760 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 65 states. [2018-10-04 14:22:54,760 INFO L78 Accepts]: Start accepts. Automaton has 65 states. Word has length 64 [2018-10-04 14:22:54,760 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:22:54,761 INFO L225 Difference]: With dead ends: 69 [2018-10-04 14:22:54,761 INFO L226 Difference]: Without dead ends: 67 [2018-10-04 14:22:54,761 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 187 GetRequests, 63 SyntacticMatches, 0 SemanticMatches, 124 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 10.0s Time 9.2s impTime 64 [2018-10-04 14:22:54,761 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2018-10-04 14:22:54,775 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 67. [2018-10-04 14:22:54,776 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 67 states. [2018-10-04 14:22:54,776 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 67 transitions. [2018-10-04 14:22:54,776 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 67 transitions. Word has length 64 [2018-10-04 14:22:54,777 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:22:54,777 INFO L480 AbstractCegarLoop]: Abstraction has 67 states and 67 transitions. [2018-10-04 14:22:54,777 INFO L481 AbstractCegarLoop]: Interpolant automaton has 65 states. [2018-10-04 14:22:54,777 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 67 transitions. [2018-10-04 14:22:54,777 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2018-10-04 14:22:54,777 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:22:54,778 INFO L375 BasicCegarLoop]: trace histogram [63, 1, 1, 1] [2018-10-04 14:22:54,778 INFO L423 AbstractCegarLoop]: === Iteration 33 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:22:54,778 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:22:54,778 INFO L82 PathProgramCache]: Analyzing trace with hash -1026988024, now seen corresponding path program 32 times [2018-10-04 14:22:54,778 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:22:54,778 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:22:54,779 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:22:54,779 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-04 14:22:54,779 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:22:54,991 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:22:57,637 INFO L134 CoverageAnalysis]: Checked inductivity of 2016 backedges. 0 proven. 2016 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:22:57,638 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:22:57,638 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 33 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 33 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:22:57,644 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-10-04 14:22:58,000 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-10-04 14:22:58,001 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:22:58,230 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:22:58,630 INFO L134 CoverageAnalysis]: Checked inductivity of 2016 backedges. 0 proven. 2016 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:22:58,651 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:22:58,651 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [65, 65] total 66 [2018-10-04 14:22:58,651 INFO L459 AbstractCegarLoop]: Interpolant automaton has 67 states [2018-10-04 14:22:58,652 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 67 interpolants. [2018-10-04 14:22:58,652 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:22:58,652 INFO L87 Difference]: Start difference. First operand 67 states and 67 transitions. Second operand 67 states. [2018-10-04 14:23:11,274 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:23:11,274 INFO L93 Difference]: Finished difference Result 71 states and 72 transitions. [2018-10-04 14:23:11,275 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 67 states. [2018-10-04 14:23:11,275 INFO L78 Accepts]: Start accepts. Automaton has 67 states. Word has length 66 [2018-10-04 14:23:11,275 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:23:11,276 INFO L225 Difference]: With dead ends: 71 [2018-10-04 14:23:11,276 INFO L226 Difference]: Without dead ends: 69 [2018-10-04 14:23:11,276 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 193 GetRequests, 65 SyntacticMatches, 0 SemanticMatches, 128 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 15.2s Time 14.1s impTime 66 [2018-10-04 14:23:11,276 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 69 states. [2018-10-04 14:23:11,288 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 69 to 69. [2018-10-04 14:23:11,289 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 69 states. [2018-10-04 14:23:11,289 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 69 transitions. [2018-10-04 14:23:11,289 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 69 transitions. Word has length 66 [2018-10-04 14:23:11,289 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:23:11,289 INFO L480 AbstractCegarLoop]: Abstraction has 69 states and 69 transitions. [2018-10-04 14:23:11,290 INFO L481 AbstractCegarLoop]: Interpolant automaton has 67 states. [2018-10-04 14:23:11,290 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 69 transitions. [2018-10-04 14:23:11,290 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2018-10-04 14:23:11,290 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:23:11,290 INFO L375 BasicCegarLoop]: trace histogram [65, 1, 1, 1] [2018-10-04 14:23:11,291 INFO L423 AbstractCegarLoop]: === Iteration 34 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:23:11,291 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:23:11,291 INFO L82 PathProgramCache]: Analyzing trace with hash 906923816, now seen corresponding path program 33 times [2018-10-04 14:23:11,291 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:23:11,291 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:23:11,291 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:23:11,291 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:23:11,292 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:23:11,510 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:23:14,626 INFO L134 CoverageAnalysis]: Checked inductivity of 2145 backedges. 0 proven. 2145 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:23:14,627 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:23:14,627 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 34 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 34 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:23:14,636 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-04 14:23:14,680 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 34 check-sat command(s) [2018-10-04 14:23:14,680 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:23:14,683 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:23:14,890 INFO L134 CoverageAnalysis]: Checked inductivity of 2145 backedges. 0 proven. 2145 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:23:14,910 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:23:14,911 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [67, 67] total 68 [2018-10-04 14:23:14,911 INFO L459 AbstractCegarLoop]: Interpolant automaton has 69 states [2018-10-04 14:23:14,911 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 69 interpolants. [2018-10-04 14:23:14,911 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:23:14,911 INFO L87 Difference]: Start difference. First operand 69 states and 69 transitions. Second operand 69 states. [2018-10-04 14:23:29,886 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:23:29,886 INFO L93 Difference]: Finished difference Result 73 states and 74 transitions. [2018-10-04 14:23:29,886 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 69 states. [2018-10-04 14:23:29,887 INFO L78 Accepts]: Start accepts. Automaton has 69 states. Word has length 68 [2018-10-04 14:23:29,887 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:23:29,887 INFO L225 Difference]: With dead ends: 73 [2018-10-04 14:23:29,887 INFO L226 Difference]: Without dead ends: 71 [2018-10-04 14:23:29,888 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 199 GetRequests, 67 SyntacticMatches, 0 SemanticMatches, 132 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 17.8s Time 16.8s impTime 68 [2018-10-04 14:23:29,888 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2018-10-04 14:23:29,901 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 71. [2018-10-04 14:23:29,902 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 71 states. [2018-10-04 14:23:29,902 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 71 transitions. [2018-10-04 14:23:29,902 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 71 transitions. Word has length 68 [2018-10-04 14:23:29,902 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:23:29,902 INFO L480 AbstractCegarLoop]: Abstraction has 71 states and 71 transitions. [2018-10-04 14:23:29,902 INFO L481 AbstractCegarLoop]: Interpolant automaton has 69 states. [2018-10-04 14:23:29,902 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 71 transitions. [2018-10-04 14:23:29,903 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2018-10-04 14:23:29,903 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:23:29,903 INFO L375 BasicCegarLoop]: trace histogram [67, 1, 1, 1] [2018-10-04 14:23:29,903 INFO L423 AbstractCegarLoop]: === Iteration 35 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:23:29,903 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:23:29,903 INFO L82 PathProgramCache]: Analyzing trace with hash -324637112, now seen corresponding path program 34 times [2018-10-04 14:23:29,904 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:23:29,904 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:23:29,904 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:23:29,904 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:23:29,904 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:23:30,171 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:23:33,076 INFO L134 CoverageAnalysis]: Checked inductivity of 2278 backedges. 0 proven. 2278 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:23:33,076 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:23:33,076 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 35 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 35 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:23:33,083 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-04 14:23:33,513 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-04 14:23:33,513 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:23:33,774 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:23:33,972 INFO L134 CoverageAnalysis]: Checked inductivity of 2278 backedges. 0 proven. 2278 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:23:33,992 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:23:33,992 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [69, 69] total 70 [2018-10-04 14:23:33,993 INFO L459 AbstractCegarLoop]: Interpolant automaton has 71 states [2018-10-04 14:23:33,993 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 71 interpolants. [2018-10-04 14:23:33,993 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:23:33,993 INFO L87 Difference]: Start difference. First operand 71 states and 71 transitions. Second operand 71 states. [2018-10-04 14:23:48,382 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:23:48,383 INFO L93 Difference]: Finished difference Result 75 states and 76 transitions. [2018-10-04 14:23:48,383 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 71 states. [2018-10-04 14:23:48,383 INFO L78 Accepts]: Start accepts. Automaton has 71 states. Word has length 70 [2018-10-04 14:23:48,384 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:23:48,384 INFO L225 Difference]: With dead ends: 75 [2018-10-04 14:23:48,385 INFO L226 Difference]: Without dead ends: 73 [2018-10-04 14:23:48,385 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 205 GetRequests, 69 SyntacticMatches, 0 SemanticMatches, 136 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 17.0s Time 16.0s impTime 70 [2018-10-04 14:23:48,385 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2018-10-04 14:23:48,402 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 73. [2018-10-04 14:23:48,402 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 73 states. [2018-10-04 14:23:48,403 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 73 transitions. [2018-10-04 14:23:48,403 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 73 transitions. Word has length 70 [2018-10-04 14:23:48,403 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:23:48,403 INFO L480 AbstractCegarLoop]: Abstraction has 73 states and 73 transitions. [2018-10-04 14:23:48,403 INFO L481 AbstractCegarLoop]: Interpolant automaton has 71 states. [2018-10-04 14:23:48,403 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 73 transitions. [2018-10-04 14:23:48,404 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2018-10-04 14:23:48,404 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:23:48,404 INFO L375 BasicCegarLoop]: trace histogram [69, 1, 1, 1] [2018-10-04 14:23:48,404 INFO L423 AbstractCegarLoop]: === Iteration 36 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:23:48,404 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:23:48,405 INFO L82 PathProgramCache]: Analyzing trace with hash 1556284776, now seen corresponding path program 35 times [2018-10-04 14:23:48,405 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:23:48,405 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:23:48,405 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:23:48,406 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:23:48,406 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:23:48,653 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:23:51,886 INFO L134 CoverageAnalysis]: Checked inductivity of 2415 backedges. 0 proven. 2415 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:23:51,887 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:23:51,887 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 36 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 36 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:23:51,896 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-10-04 14:23:52,286 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 36 check-sat command(s) [2018-10-04 14:23:52,286 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:23:52,344 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:23:52,556 INFO L134 CoverageAnalysis]: Checked inductivity of 2415 backedges. 0 proven. 2415 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:23:52,577 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:23:52,577 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [71, 71] total 72 [2018-10-04 14:23:52,578 INFO L459 AbstractCegarLoop]: Interpolant automaton has 73 states [2018-10-04 14:23:52,578 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 73 interpolants. [2018-10-04 14:23:52,578 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:23:52,578 INFO L87 Difference]: Start difference. First operand 73 states and 73 transitions. Second operand 73 states. [2018-10-04 14:24:09,087 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:24:09,087 INFO L93 Difference]: Finished difference Result 77 states and 78 transitions. [2018-10-04 14:24:09,087 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 73 states. [2018-10-04 14:24:09,088 INFO L78 Accepts]: Start accepts. Automaton has 73 states. Word has length 72 [2018-10-04 14:24:09,088 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:24:09,088 INFO L225 Difference]: With dead ends: 77 [2018-10-04 14:24:09,089 INFO L226 Difference]: Without dead ends: 75 [2018-10-04 14:24:09,089 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 211 GetRequests, 71 SyntacticMatches, 0 SemanticMatches, 140 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 19.4s Time 18.3s impTime 72 [2018-10-04 14:24:09,089 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 75 states. [2018-10-04 14:24:09,106 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 75 to 75. [2018-10-04 14:24:09,106 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 75 states. [2018-10-04 14:24:09,107 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 75 transitions. [2018-10-04 14:24:09,107 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 75 transitions. Word has length 72 [2018-10-04 14:24:09,107 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:24:09,107 INFO L480 AbstractCegarLoop]: Abstraction has 75 states and 75 transitions. [2018-10-04 14:24:09,107 INFO L481 AbstractCegarLoop]: Interpolant automaton has 73 states. [2018-10-04 14:24:09,107 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 75 transitions. [2018-10-04 14:24:09,108 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2018-10-04 14:24:09,108 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:24:09,108 INFO L375 BasicCegarLoop]: trace histogram [71, 1, 1, 1] [2018-10-04 14:24:09,108 INFO L423 AbstractCegarLoop]: === Iteration 37 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:24:09,108 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:24:09,109 INFO L82 PathProgramCache]: Analyzing trace with hash 940987528, now seen corresponding path program 36 times [2018-10-04 14:24:09,109 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:24:09,109 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:24:09,109 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:24:09,110 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:24:09,110 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:24:09,386 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:24:13,164 INFO L134 CoverageAnalysis]: Checked inductivity of 2556 backedges. 0 proven. 2556 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:24:13,165 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:24:13,165 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 37 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 37 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:24:13,174 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-10-04 14:24:13,223 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 37 check-sat command(s) [2018-10-04 14:24:13,223 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:24:13,227 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:24:13,516 INFO L134 CoverageAnalysis]: Checked inductivity of 2556 backedges. 0 proven. 2556 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:24:13,536 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:24:13,536 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [73, 73] total 74 [2018-10-04 14:24:13,537 INFO L459 AbstractCegarLoop]: Interpolant automaton has 75 states [2018-10-04 14:24:13,537 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 75 interpolants. [2018-10-04 14:24:13,537 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:24:13,537 INFO L87 Difference]: Start difference. First operand 75 states and 75 transitions. Second operand 75 states. [2018-10-04 14:24:29,439 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:24:29,440 INFO L93 Difference]: Finished difference Result 79 states and 80 transitions. [2018-10-04 14:24:29,440 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 75 states. [2018-10-04 14:24:29,440 INFO L78 Accepts]: Start accepts. Automaton has 75 states. Word has length 74 [2018-10-04 14:24:29,440 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:24:29,441 INFO L225 Difference]: With dead ends: 79 [2018-10-04 14:24:29,441 INFO L226 Difference]: Without dead ends: 77 [2018-10-04 14:24:29,441 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 217 GetRequests, 73 SyntacticMatches, 0 SemanticMatches, 144 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 19.2s Time 17.9s impTime 74 [2018-10-04 14:24:29,442 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2018-10-04 14:24:29,461 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 77. [2018-10-04 14:24:29,461 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 77 states. [2018-10-04 14:24:29,461 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 77 transitions. [2018-10-04 14:24:29,462 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 77 transitions. Word has length 74 [2018-10-04 14:24:29,462 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:24:29,462 INFO L480 AbstractCegarLoop]: Abstraction has 77 states and 77 transitions. [2018-10-04 14:24:29,462 INFO L481 AbstractCegarLoop]: Interpolant automaton has 75 states. [2018-10-04 14:24:29,462 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 77 transitions. [2018-10-04 14:24:29,463 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2018-10-04 14:24:29,463 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:24:29,463 INFO L375 BasicCegarLoop]: trace histogram [73, 1, 1, 1] [2018-10-04 14:24:29,463 INFO L423 AbstractCegarLoop]: === Iteration 38 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:24:29,463 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:24:29,463 INFO L82 PathProgramCache]: Analyzing trace with hash -1949148248, now seen corresponding path program 37 times [2018-10-04 14:24:29,463 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:24:29,464 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:24:29,464 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:24:29,464 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 14:24:29,464 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:24:29,770 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:24:33,384 INFO L134 CoverageAnalysis]: Checked inductivity of 2701 backedges. 0 proven. 2701 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:24:33,384 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:24:33,384 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 38 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 38 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:24:33,392 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-04 14:24:33,942 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:24:34,293 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:24:34,510 INFO L134 CoverageAnalysis]: Checked inductivity of 2701 backedges. 0 proven. 2701 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:24:34,530 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 14:24:34,530 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [75, 75] total 76 [2018-10-04 14:24:34,530 INFO L459 AbstractCegarLoop]: Interpolant automaton has 77 states [2018-10-04 14:24:34,531 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 77 interpolants. [2018-10-04 14:24:34,531 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 14:24:34,531 INFO L87 Difference]: Start difference. First operand 77 states and 77 transitions. Second operand 77 states. [2018-10-04 14:24:47,529 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 14:24:47,530 INFO L93 Difference]: Finished difference Result 81 states and 82 transitions. [2018-10-04 14:24:47,530 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 77 states. [2018-10-04 14:24:47,530 INFO L78 Accepts]: Start accepts. Automaton has 77 states. Word has length 76 [2018-10-04 14:24:47,530 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 14:24:47,531 INFO L225 Difference]: With dead ends: 81 [2018-10-04 14:24:47,531 INFO L226 Difference]: Without dead ends: 79 [2018-10-04 14:24:47,532 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 223 GetRequests, 75 SyntacticMatches, 0 SemanticMatches, 148 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 16.2s Time 15.2s impTime 76 [2018-10-04 14:24:47,532 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 79 states. [2018-10-04 14:24:47,547 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 79 to 79. [2018-10-04 14:24:47,547 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 79 states. [2018-10-04 14:24:47,548 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 79 transitions. [2018-10-04 14:24:47,548 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 79 transitions. Word has length 76 [2018-10-04 14:24:47,548 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 14:24:47,548 INFO L480 AbstractCegarLoop]: Abstraction has 79 states and 79 transitions. [2018-10-04 14:24:47,548 INFO L481 AbstractCegarLoop]: Interpolant automaton has 77 states. [2018-10-04 14:24:47,548 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 79 transitions. [2018-10-04 14:24:47,549 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2018-10-04 14:24:47,549 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 14:24:47,549 INFO L375 BasicCegarLoop]: trace histogram [75, 1, 1, 1] [2018-10-04 14:24:47,549 INFO L423 AbstractCegarLoop]: === Iteration 39 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 14:24:47,549 INFO L108 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 14:24:47,549 INFO L82 PathProgramCache]: Analyzing trace with hash -525788472, now seen corresponding path program 38 times [2018-10-04 14:24:47,549 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 14:24:47,550 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 14:24:47,550 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:24:47,550 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-04 14:24:47,550 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 14:24:47,868 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 14:24:51,863 INFO L134 CoverageAnalysis]: Checked inductivity of 2850 backedges. 0 proven. 2850 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 14:24:51,863 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 14:24:51,863 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 39 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 39 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:24:51,870 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 Received shutdown request... [2018-10-04 14:24:52,470 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-10-04 14:24:52,470 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 14:24:52,842 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 14:24:52,852 INFO L177 TraceCheckSpWp]: Timeout while computing interpolants [2018-10-04 14:24:53,053 WARN L521 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 39 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 14:24:53,054 WARN L549 AbstractCegarLoop]: Verification canceled [2018-10-04 14:24:53,059 WARN L205 ceAbstractionStarter]: Timeout [2018-10-04 14:24:53,060 INFO L202 PluginConnector]: Adding new model count_by_k.i_3.bplTransformedIcfg_BEv2_3.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 04.10 02:24:53 BoogieIcfgContainer [2018-10-04 14:24:53,060 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-10-04 14:24:53,061 INFO L168 Benchmark]: Toolchain (without parser) took 262511.37 ms. Allocated memory was 1.5 GB in the beginning and 1.4 GB in the end (delta: -124.3 MB). Free memory was 1.5 GB in the beginning and 1.2 GB in the end (delta: 230.7 MB). Peak memory consumption was 106.4 MB. Max. memory is 7.1 GB. [2018-10-04 14:24:53,063 INFO L168 Benchmark]: Boogie PL CUP Parser took 0.27 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-10-04 14:24:53,063 INFO L168 Benchmark]: Boogie Procedure Inliner took 41.46 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-10-04 14:24:53,064 INFO L168 Benchmark]: Boogie Preprocessor took 20.63 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-10-04 14:24:53,064 INFO L168 Benchmark]: RCFGBuilder took 293.15 ms. Allocated memory is still 1.5 GB. Free memory was 1.5 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-10-04 14:24:53,065 INFO L168 Benchmark]: TraceAbstraction took 262149.51 ms. Allocated memory was 1.5 GB in the beginning and 1.4 GB in the end (delta: -124.3 MB). Free memory was 1.4 GB in the beginning and 1.2 GB in the end (delta: 209.5 MB). Peak memory consumption was 85.3 MB. Max. memory is 7.1 GB. [2018-10-04 14:24:53,069 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.27 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. * Boogie Procedure Inliner took 41.46 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. * Boogie Preprocessor took 20.63 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. * RCFGBuilder took 293.15 ms. Allocated memory is still 1.5 GB. Free memory was 1.5 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 262149.51 ms. Allocated memory was 1.5 GB in the beginning and 1.4 GB in the end (delta: -124.3 MB). Free memory was 1.4 GB in the beginning and 1.2 GB in the end (delta: 209.5 MB). Peak memory consumption was 85.3 MB. Max. memory is 7.1 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 39]: Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 39). Cancelled while BasicCegarLoop was analyzing trace of length 79 with TraceHistMax 75, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 2 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 1 procedures, 6 locations, 1 error locations. TIMEOUT Result, 262.0s OverallTime, 39 OverallIterations, 75 TraceHistogramMax, 185.3s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 114 SDtfs, 0 SDslu, 1429 SDs, 0 SdLazy, 3044 SolverSat, 1369 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 6.7s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 4256 GetRequests, 1444 SyntacticMatches, 0 SemanticMatches, 2812 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 234.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=79occurred 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, 7.7s SatisfiabilityAnalysisTime, 61.4s InterpolantComputationTime, 2963 NumberOfCodeBlocks, 2963 NumberOfCodeBlocksAsserted, 441 NumberOfCheckSat, 2888 ConstructedInterpolants, 0 QuantifiedInterpolants, 722866 SizeOfPredicates, 74 NumberOfNonLiveVariables, 4736 ConjunctsInSsa, 1505 ConjunctsInUnsatCore, 75 InterpolantComputations, 1 PerfectInterpolantSequences, 0/68894 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.bplTransformedIcfg_BEv2_3.bpl_svcomp-Reach-32bit-Automizer_Default_PUPT.epf_AutomizerBplInline.xml/Csv-Benchmark-0-2018-10-04_14-24-53-083.csv Written .csv to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/csv/count_by_k.i_3.bplTransformedIcfg_BEv2_3.bpl_svcomp-Reach-32bit-Automizer_Default_PUPT.epf_AutomizerBplInline.xml/Csv-TraceAbstractionBenchmarks-0-2018-10-04_14-24-53-083.csv Completed graceful shutdown