java -Xmx8000000000 -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data --generate-csv --csv-dir csv -tc ../../../trunk/examples/toolchains/AutomizerBplInline.xml -s ../../../trunk/examples/settings/pu-bench/svcomp-Reach-32bit-Automizer_Default.epf -i ../../../trunk/examples/programs/toy/tooDifficultLoopInvariant/AnnoyingVillain.bpl -------------------------------------------------------------------------------- This is Ultimate 0.1.23-4eac566 [2018-09-23 19:45:42,892 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-09-23 19:45:42,894 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-09-23 19:45:42,912 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-09-23 19:45:42,912 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-09-23 19:45:42,913 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-09-23 19:45:42,914 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-09-23 19:45:42,916 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-09-23 19:45:42,918 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-09-23 19:45:42,919 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-09-23 19:45:42,919 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-09-23 19:45:42,920 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-09-23 19:45:42,921 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-09-23 19:45:42,922 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-09-23 19:45:42,923 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-09-23 19:45:42,924 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-09-23 19:45:42,924 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-09-23 19:45:42,926 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-09-23 19:45:42,928 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-09-23 19:45:42,930 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-09-23 19:45:42,931 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-09-23 19:45:42,934 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-09-23 19:45:42,939 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-09-23 19:45:42,940 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-09-23 19:45:42,940 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-09-23 19:45:42,941 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-09-23 19:45:42,942 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-09-23 19:45:42,944 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-09-23 19:45:42,945 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-09-23 19:45:42,946 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-09-23 19:45:42,947 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-09-23 19:45:42,948 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-09-23 19:45:42,948 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-09-23 19:45:42,948 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-09-23 19:45:42,950 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-09-23 19:45:42,951 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-09-23 19:45:42,951 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/pu-bench/svcomp-Reach-32bit-Automizer_Default.epf [2018-09-23 19:45:42,980 INFO L110 SettingsManager]: Loading preferences was successful [2018-09-23 19:45:42,981 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-09-23 19:45:42,981 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-09-23 19:45:42,982 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-09-23 19:45:42,982 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-09-23 19:45:42,982 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-09-23 19:45:42,983 INFO L133 SettingsManager]: * Use SBE=true [2018-09-23 19:45:42,983 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-09-23 19:45:42,983 INFO L133 SettingsManager]: * sizeof long=4 [2018-09-23 19:45:42,983 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-09-23 19:45:42,985 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-09-23 19:45:42,985 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-09-23 19:45:42,985 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-09-23 19:45:42,985 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-09-23 19:45:42,985 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-09-23 19:45:42,985 INFO L133 SettingsManager]: * sizeof long double=12 [2018-09-23 19:45:42,986 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-09-23 19:45:42,986 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-09-23 19:45:42,986 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-09-23 19:45:42,986 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-09-23 19:45:42,988 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-09-23 19:45:42,988 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-09-23 19:45:42,988 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-09-23 19:45:42,988 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-09-23 19:45:42,988 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-09-23 19:45:42,989 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-09-23 19:45:42,989 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-09-23 19:45:42,989 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-09-23 19:45:42,989 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-09-23 19:45:42,990 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-09-23 19:45:43,046 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-09-23 19:45:43,059 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-09-23 19:45:43,062 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-09-23 19:45:43,064 INFO L271 PluginConnector]: Initializing Boogie PL CUP Parser... [2018-09-23 19:45:43,064 INFO L276 PluginConnector]: Boogie PL CUP Parser initialized [2018-09-23 19:45:43,065 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/toy/tooDifficultLoopInvariant/AnnoyingVillain.bpl [2018-09-23 19:45:43,065 INFO L111 BoogieParser]: Parsing: '/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/toy/tooDifficultLoopInvariant/AnnoyingVillain.bpl' [2018-09-23 19:45:43,111 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-09-23 19:45:43,114 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-09-23 19:45:43,115 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2018-09-23 19:45:43,115 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2018-09-23 19:45:43,115 INFO L276 PluginConnector]: Boogie Procedure Inliner initialized [2018-09-23 19:45:43,135 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 23.09 07:45:43" (1/1) ... [2018-09-23 19:45:43,147 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 23.09 07:45:43" (1/1) ... [2018-09-23 19:45:43,151 WARN L165 Inliner]: Program contained no entry procedure! [2018-09-23 19:45:43,152 WARN L168 Inliner]: Missing entry procedures: [ULTIMATE.start] [2018-09-23 19:45:43,152 WARN L175 Inliner]: Fallback enabled. All procedures will be processed. [2018-09-23 19:45:43,154 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2018-09-23 19:45:43,155 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-09-23 19:45:43,155 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-09-23 19:45:43,155 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-09-23 19:45:43,166 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 23.09 07:45:43" (1/1) ... [2018-09-23 19:45:43,167 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 23.09 07:45:43" (1/1) ... [2018-09-23 19:45:43,167 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 23.09 07:45:43" (1/1) ... [2018-09-23 19:45:43,167 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 23.09 07:45:43" (1/1) ... [2018-09-23 19:45:43,170 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 23.09 07:45:43" (1/1) ... [2018-09-23 19:45:43,173 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 23.09 07:45:43" (1/1) ... [2018-09-23 19:45:43,174 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 23.09 07:45:43" (1/1) ... [2018-09-23 19:45:43,176 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-09-23 19:45:43,176 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-09-23 19:45:43,176 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-09-23 19:45:43,176 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-09-23 19:45:43,177 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 23.09 07:45:43" (1/1) ... No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-09-23 19:45:43,248 INFO L124 BoogieDeclarations]: Specification and implementation of procedure main given in one single declaration [2018-09-23 19:45:43,248 INFO L130 BoogieDeclarations]: Found specification of procedure main [2018-09-23 19:45:43,248 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2018-09-23 19:45:43,476 INFO L351 CfgBuilder]: Using library mode [2018-09-23 19:45:43,477 INFO L202 PluginConnector]: Adding new model AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.09 07:45:43 BoogieIcfgContainer [2018-09-23 19:45:43,477 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-09-23 19:45:43,478 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-09-23 19:45:43,478 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-09-23 19:45:43,481 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-09-23 19:45:43,481 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 23.09 07:45:43" (1/2) ... [2018-09-23 19:45:43,482 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@70bb21cf and model type AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.09 07:45:43, skipping insertion in model container [2018-09-23 19:45:43,482 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.09 07:45:43" (2/2) ... [2018-09-23 19:45:43,485 INFO L112 eAbstractionObserver]: Analyzing ICFG AnnoyingVillain.bpl [2018-09-23 19:45:43,495 INFO L137 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-09-23 19:45:43,507 INFO L149 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-09-23 19:45:43,556 INFO L133 ementStrategyFactory]: Using default assertion order modulation [2018-09-23 19:45:43,557 INFO L381 AbstractCegarLoop]: Interprodecural is true [2018-09-23 19:45:43,558 INFO L382 AbstractCegarLoop]: Hoare is true [2018-09-23 19:45:43,558 INFO L383 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-09-23 19:45:43,558 INFO L384 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-09-23 19:45:43,558 INFO L385 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-09-23 19:45:43,558 INFO L386 AbstractCegarLoop]: Difference is false [2018-09-23 19:45:43,558 INFO L387 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-09-23 19:45:43,559 INFO L392 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-09-23 19:45:43,572 INFO L276 IsEmpty]: Start isEmpty. Operand 6 states. [2018-09-23 19:45:43,578 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2018-09-23 19:45:43,579 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:45:43,580 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1] [2018-09-23 19:45:43,581 INFO L423 AbstractCegarLoop]: === Iteration 1 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:45:43,587 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:45:43,587 INFO L82 PathProgramCache]: Analyzing trace with hash 30048, now seen corresponding path program 1 times [2018-09-23 19:45:43,589 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:45:43,590 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:45:43,636 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:43,636 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-23 19:45:43,636 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:43,671 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:45:43,725 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:43,727 INFO L313 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-09-23 19:45:43,727 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2018-09-23 19:45:43,731 INFO L459 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-09-23 19:45:43,744 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-09-23 19:45:43,745 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-09-23 19:45:43,747 INFO L87 Difference]: Start difference. First operand 6 states. Second operand 3 states. [2018-09-23 19:45:43,803 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:45:43,803 INFO L93 Difference]: Finished difference Result 11 states and 13 transitions. [2018-09-23 19:45:43,805 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-09-23 19:45:43,806 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 3 [2018-09-23 19:45:43,807 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:45:43,816 INFO L225 Difference]: With dead ends: 11 [2018-09-23 19:45:43,817 INFO L226 Difference]: Without dead ends: 5 [2018-09-23 19:45:43,821 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 1 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-09-23 19:45:43,838 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 5 states. [2018-09-23 19:45:43,853 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 5 to 5. [2018-09-23 19:45:43,854 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5 states. [2018-09-23 19:45:43,855 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 5 transitions. [2018-09-23 19:45:43,856 INFO L78 Accepts]: Start accepts. Automaton has 5 states and 5 transitions. Word has length 3 [2018-09-23 19:45:43,856 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:45:43,856 INFO L480 AbstractCegarLoop]: Abstraction has 5 states and 5 transitions. [2018-09-23 19:45:43,856 INFO L481 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-09-23 19:45:43,857 INFO L276 IsEmpty]: Start isEmpty. Operand 5 states and 5 transitions. [2018-09-23 19:45:43,857 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 5 [2018-09-23 19:45:43,857 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:45:43,857 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1] [2018-09-23 19:45:43,857 INFO L423 AbstractCegarLoop]: === Iteration 2 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:45:43,858 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:45:43,858 INFO L82 PathProgramCache]: Analyzing trace with hash 927622, now seen corresponding path program 1 times [2018-09-23 19:45:43,858 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:45:43,858 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:45:43,859 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:43,859 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-23 19:45:43,859 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:43,872 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:45:44,045 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:44,046 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:45:44,046 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:45:44,056 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-23 19:45:44,077 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:45:44,084 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:45:44,169 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:44,193 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:45:44,194 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [3, 3] total 3 [2018-09-23 19:45:44,194 INFO L459 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-09-23 19:45:44,194 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-09-23 19:45:44,195 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-09-23 19:45:44,195 INFO L87 Difference]: Start difference. First operand 5 states and 5 transitions. Second operand 4 states. [2018-09-23 19:45:44,215 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:45:44,216 INFO L93 Difference]: Finished difference Result 8 states and 8 transitions. [2018-09-23 19:45:44,216 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-09-23 19:45:44,217 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 4 [2018-09-23 19:45:44,217 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:45:44,217 INFO L225 Difference]: With dead ends: 8 [2018-09-23 19:45:44,217 INFO L226 Difference]: Without dead ends: 6 [2018-09-23 19:45:44,218 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 3 SyntacticMatches, 1 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-09-23 19:45:44,219 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 6 states. [2018-09-23 19:45:44,220 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 6 to 6. [2018-09-23 19:45:44,221 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 6 states. [2018-09-23 19:45:44,221 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 6 transitions. [2018-09-23 19:45:44,221 INFO L78 Accepts]: Start accepts. Automaton has 6 states and 6 transitions. Word has length 4 [2018-09-23 19:45:44,221 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:45:44,222 INFO L480 AbstractCegarLoop]: Abstraction has 6 states and 6 transitions. [2018-09-23 19:45:44,222 INFO L481 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-09-23 19:45:44,222 INFO L276 IsEmpty]: Start isEmpty. Operand 6 states and 6 transitions. [2018-09-23 19:45:44,222 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 6 [2018-09-23 19:45:44,222 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:45:44,222 INFO L375 BasicCegarLoop]: trace histogram [2, 1, 1, 1] [2018-09-23 19:45:44,223 INFO L423 AbstractCegarLoop]: === Iteration 3 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:45:44,223 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:45:44,223 INFO L82 PathProgramCache]: Analyzing trace with hash 28752416, now seen corresponding path program 2 times [2018-09-23 19:45:44,223 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:45:44,224 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:45:44,224 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:44,225 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-23 19:45:44,225 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:44,233 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:45:44,382 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:44,383 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:45:44,383 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:45:44,406 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-09-23 19:45:44,427 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-09-23 19:45:44,427 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-23 19:45:44,428 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:45:44,444 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:44,463 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:45:44,463 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 4 [2018-09-23 19:45:44,464 INFO L459 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-09-23 19:45:44,464 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-09-23 19:45:44,464 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-09-23 19:45:44,465 INFO L87 Difference]: Start difference. First operand 6 states and 6 transitions. Second operand 5 states. [2018-09-23 19:45:44,507 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:45:44,507 INFO L93 Difference]: Finished difference Result 9 states and 9 transitions. [2018-09-23 19:45:44,508 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-09-23 19:45:44,508 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 5 [2018-09-23 19:45:44,508 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:45:44,509 INFO L225 Difference]: With dead ends: 9 [2018-09-23 19:45:44,509 INFO L226 Difference]: Without dead ends: 7 [2018-09-23 19:45:44,510 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 4 SyntacticMatches, 1 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-09-23 19:45:44,510 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 7 states. [2018-09-23 19:45:44,512 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 7 to 7. [2018-09-23 19:45:44,512 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 7 states. [2018-09-23 19:45:44,513 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 7 transitions. [2018-09-23 19:45:44,513 INFO L78 Accepts]: Start accepts. Automaton has 7 states and 7 transitions. Word has length 5 [2018-09-23 19:45:44,513 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:45:44,513 INFO L480 AbstractCegarLoop]: Abstraction has 7 states and 7 transitions. [2018-09-23 19:45:44,514 INFO L481 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-09-23 19:45:44,514 INFO L276 IsEmpty]: Start isEmpty. Operand 7 states and 7 transitions. [2018-09-23 19:45:44,514 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2018-09-23 19:45:44,514 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:45:44,515 INFO L375 BasicCegarLoop]: trace histogram [3, 1, 1, 1] [2018-09-23 19:45:44,515 INFO L423 AbstractCegarLoop]: === Iteration 4 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:45:44,515 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:45:44,515 INFO L82 PathProgramCache]: Analyzing trace with hash 891321030, now seen corresponding path program 3 times [2018-09-23 19:45:44,515 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:45:44,516 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:45:44,517 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:44,517 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-23 19:45:44,517 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:44,526 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:45:44,751 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:44,752 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:45:44,752 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:45:44,761 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-09-23 19:45:44,779 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-09-23 19:45:44,779 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-23 19:45:44,780 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:45:44,799 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:44,818 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:45:44,819 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 5 [2018-09-23 19:45:44,819 INFO L459 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-09-23 19:45:44,819 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-09-23 19:45:44,820 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-09-23 19:45:44,820 INFO L87 Difference]: Start difference. First operand 7 states and 7 transitions. Second operand 6 states. [2018-09-23 19:45:45,024 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:45:45,025 INFO L93 Difference]: Finished difference Result 10 states and 10 transitions. [2018-09-23 19:45:45,025 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-09-23 19:45:45,025 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 6 [2018-09-23 19:45:45,026 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:45:45,026 INFO L225 Difference]: With dead ends: 10 [2018-09-23 19:45:45,027 INFO L226 Difference]: Without dead ends: 8 [2018-09-23 19:45:45,027 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 5 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-09-23 19:45:45,028 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 8 states. [2018-09-23 19:45:45,030 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 8 to 8. [2018-09-23 19:45:45,030 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 8 states. [2018-09-23 19:45:45,030 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 8 transitions. [2018-09-23 19:45:45,031 INFO L78 Accepts]: Start accepts. Automaton has 8 states and 8 transitions. Word has length 6 [2018-09-23 19:45:45,031 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:45:45,031 INFO L480 AbstractCegarLoop]: Abstraction has 8 states and 8 transitions. [2018-09-23 19:45:45,031 INFO L481 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-09-23 19:45:45,031 INFO L276 IsEmpty]: Start isEmpty. Operand 8 states and 8 transitions. [2018-09-23 19:45:45,032 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2018-09-23 19:45:45,032 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:45:45,032 INFO L375 BasicCegarLoop]: trace histogram [4, 1, 1, 1] [2018-09-23 19:45:45,033 INFO L423 AbstractCegarLoop]: === Iteration 5 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:45:45,033 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:45:45,033 INFO L82 PathProgramCache]: Analyzing trace with hash 1861144288, now seen corresponding path program 4 times [2018-09-23 19:45:45,033 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:45:45,033 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:45:45,034 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:45,034 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-23 19:45:45,035 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:45,043 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:45:45,172 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:45,172 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:45:45,172 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:45:45,180 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-09-23 19:45:45,189 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-09-23 19:45:45,190 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-23 19:45:45,192 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:45:45,207 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:45,229 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:45:45,229 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 6 [2018-09-23 19:45:45,229 INFO L459 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-09-23 19:45:45,230 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-09-23 19:45:45,230 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-09-23 19:45:45,231 INFO L87 Difference]: Start difference. First operand 8 states and 8 transitions. Second operand 7 states. [2018-09-23 19:45:45,353 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:45:45,353 INFO L93 Difference]: Finished difference Result 11 states and 11 transitions. [2018-09-23 19:45:45,354 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-09-23 19:45:45,354 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 7 [2018-09-23 19:45:45,354 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:45:45,354 INFO L225 Difference]: With dead ends: 11 [2018-09-23 19:45:45,354 INFO L226 Difference]: Without dead ends: 9 [2018-09-23 19:45:45,355 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 6 SyntacticMatches, 1 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-09-23 19:45:45,355 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 9 states. [2018-09-23 19:45:45,357 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-09-23 19:45:45,358 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 9 states. [2018-09-23 19:45:45,358 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-09-23 19:45:45,358 INFO L78 Accepts]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-09-23 19:45:45,358 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:45:45,358 INFO L480 AbstractCegarLoop]: Abstraction has 9 states and 9 transitions. [2018-09-23 19:45:45,359 INFO L481 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-09-23 19:45:45,359 INFO L276 IsEmpty]: Start isEmpty. Operand 9 states and 9 transitions. [2018-09-23 19:45:45,359 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2018-09-23 19:45:45,359 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:45:45,359 INFO L375 BasicCegarLoop]: trace histogram [5, 1, 1, 1] [2018-09-23 19:45:45,359 INFO L423 AbstractCegarLoop]: === Iteration 6 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:45:45,360 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:45:45,360 INFO L82 PathProgramCache]: Analyzing trace with hash 1860894214, now seen corresponding path program 5 times [2018-09-23 19:45:45,360 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:45:45,360 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:45:45,361 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:45,361 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-23 19:45:45,361 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:45,372 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:45:45,571 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:45,571 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:45:45,572 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:45:45,580 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-09-23 19:45:45,590 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-09-23 19:45:45,590 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-23 19:45:45,591 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:45:45,618 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:45,644 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:45:45,644 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 7 [2018-09-23 19:45:45,644 INFO L459 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-09-23 19:45:45,645 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-09-23 19:45:45,645 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2018-09-23 19:45:45,645 INFO L87 Difference]: Start difference. First operand 9 states and 9 transitions. Second operand 8 states. [2018-09-23 19:45:45,726 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:45:45,726 INFO L93 Difference]: Finished difference Result 12 states and 12 transitions. [2018-09-23 19:45:45,726 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-09-23 19:45:45,727 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 8 [2018-09-23 19:45:45,727 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:45:45,727 INFO L225 Difference]: With dead ends: 12 [2018-09-23 19:45:45,728 INFO L226 Difference]: Without dead ends: 10 [2018-09-23 19:45:45,728 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2018-09-23 19:45:45,728 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 10 states. [2018-09-23 19:45:45,731 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-09-23 19:45:45,731 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 10 states. [2018-09-23 19:45:45,732 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-09-23 19:45:45,732 INFO L78 Accepts]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-09-23 19:45:45,732 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:45:45,733 INFO L480 AbstractCegarLoop]: Abstraction has 10 states and 10 transitions. [2018-09-23 19:45:45,733 INFO L481 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-09-23 19:45:45,733 INFO L276 IsEmpty]: Start isEmpty. Operand 10 states and 10 transitions. [2018-09-23 19:45:45,733 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2018-09-23 19:45:45,733 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:45:45,734 INFO L375 BasicCegarLoop]: trace histogram [6, 1, 1, 1] [2018-09-23 19:45:45,734 INFO L423 AbstractCegarLoop]: === Iteration 7 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:45:45,734 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:45:45,734 INFO L82 PathProgramCache]: Analyzing trace with hash 1853141920, now seen corresponding path program 6 times [2018-09-23 19:45:45,734 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:45:45,735 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:45:45,735 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:45,736 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-23 19:45:45,736 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:45,743 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:45:45,939 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:45,940 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:45:45,940 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:45:45,949 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-09-23 19:45:46,017 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2018-09-23 19:45:46,018 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-23 19:45:46,020 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:45:46,080 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:46,115 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:45:46,116 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 8 [2018-09-23 19:45:46,116 INFO L459 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-09-23 19:45:46,116 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-09-23 19:45:46,116 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=57, Unknown=0, NotChecked=0, Total=72 [2018-09-23 19:45:46,117 INFO L87 Difference]: Start difference. First operand 10 states and 10 transitions. Second operand 9 states. [2018-09-23 19:45:46,348 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:45:46,348 INFO L93 Difference]: Finished difference Result 13 states and 13 transitions. [2018-09-23 19:45:46,349 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-09-23 19:45:46,349 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 9 [2018-09-23 19:45:46,350 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:45:46,350 INFO L225 Difference]: With dead ends: 13 [2018-09-23 19:45:46,350 INFO L226 Difference]: Without dead ends: 11 [2018-09-23 19:45:46,351 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 8 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=15, Invalid=57, Unknown=0, NotChecked=0, Total=72 [2018-09-23 19:45:46,351 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 11 states. [2018-09-23 19:45:46,355 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-09-23 19:45:46,355 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 11 states. [2018-09-23 19:45:46,355 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-09-23 19:45:46,356 INFO L78 Accepts]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 9 [2018-09-23 19:45:46,356 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:45:46,356 INFO L480 AbstractCegarLoop]: Abstraction has 11 states and 11 transitions. [2018-09-23 19:45:46,356 INFO L481 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-09-23 19:45:46,356 INFO L276 IsEmpty]: Start isEmpty. Operand 11 states and 11 transitions. [2018-09-23 19:45:46,357 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2018-09-23 19:45:46,357 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:45:46,357 INFO L375 BasicCegarLoop]: trace histogram [7, 1, 1, 1] [2018-09-23 19:45:46,357 INFO L423 AbstractCegarLoop]: === Iteration 8 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:45:46,357 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:45:46,358 INFO L82 PathProgramCache]: Analyzing trace with hash 1612820806, now seen corresponding path program 7 times [2018-09-23 19:45:46,358 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:45:46,358 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:45:46,359 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:46,359 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-23 19:45:46,359 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:46,367 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:45:46,563 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:46,564 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:45:46,564 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:45:46,574 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-23 19:45:46,581 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:45:46,584 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:45:46,607 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:46,627 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:45:46,627 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 9 [2018-09-23 19:45:46,628 INFO L459 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-09-23 19:45:46,628 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-09-23 19:45:46,628 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=73, Unknown=0, NotChecked=0, Total=90 [2018-09-23 19:45:46,629 INFO L87 Difference]: Start difference. First operand 11 states and 11 transitions. Second operand 10 states. [2018-09-23 19:45:46,785 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:45:46,785 INFO L93 Difference]: Finished difference Result 14 states and 14 transitions. [2018-09-23 19:45:46,786 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-09-23 19:45:46,786 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 10 [2018-09-23 19:45:46,786 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:45:46,787 INFO L225 Difference]: With dead ends: 14 [2018-09-23 19:45:46,787 INFO L226 Difference]: Without dead ends: 12 [2018-09-23 19:45:46,787 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 9 SyntacticMatches, 1 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=73, Unknown=0, NotChecked=0, Total=90 [2018-09-23 19:45:46,787 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 12 states. [2018-09-23 19:45:46,789 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-09-23 19:45:46,790 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 12 states. [2018-09-23 19:45:46,790 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-09-23 19:45:46,790 INFO L78 Accepts]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-09-23 19:45:46,790 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:45:46,791 INFO L480 AbstractCegarLoop]: Abstraction has 12 states and 12 transitions. [2018-09-23 19:45:46,791 INFO L481 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-09-23 19:45:46,791 INFO L276 IsEmpty]: Start isEmpty. Operand 12 states and 12 transitions. [2018-09-23 19:45:46,791 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2018-09-23 19:45:46,791 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:45:46,791 INFO L375 BasicCegarLoop]: trace histogram [8, 1, 1, 1] [2018-09-23 19:45:46,792 INFO L423 AbstractCegarLoop]: === Iteration 9 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:45:46,792 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:45:46,792 INFO L82 PathProgramCache]: Analyzing trace with hash -1542166432, now seen corresponding path program 8 times [2018-09-23 19:45:46,792 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:45:46,792 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:45:46,793 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:46,793 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-23 19:45:46,793 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:46,802 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:45:47,063 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:47,063 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:45:47,064 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:45:47,077 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-09-23 19:45:47,094 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-09-23 19:45:47,095 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-23 19:45:47,096 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:45:47,487 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 0 proven. 35 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-09-23 19:45:47,518 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:45:47,518 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 8] total 18 [2018-09-23 19:45:47,518 INFO L459 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-09-23 19:45:47,519 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-09-23 19:45:47,519 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=307, Unknown=0, NotChecked=0, Total=342 [2018-09-23 19:45:47,522 INFO L87 Difference]: Start difference. First operand 12 states and 12 transitions. Second operand 19 states. [2018-09-23 19:45:48,395 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:45:48,396 INFO L93 Difference]: Finished difference Result 35 states and 36 transitions. [2018-09-23 19:45:48,397 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2018-09-23 19:45:48,397 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 11 [2018-09-23 19:45:48,397 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:45:48,399 INFO L225 Difference]: With dead ends: 35 [2018-09-23 19:45:48,399 INFO L226 Difference]: Without dead ends: 32 [2018-09-23 19:45:48,400 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 120 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=99, Invalid=1091, Unknown=0, NotChecked=0, Total=1190 [2018-09-23 19:45:48,400 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2018-09-23 19:45:48,404 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 19. [2018-09-23 19:45:48,405 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 19 states. [2018-09-23 19:45:48,405 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 25 transitions. [2018-09-23 19:45:48,406 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 25 transitions. Word has length 11 [2018-09-23 19:45:48,406 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:45:48,406 INFO L480 AbstractCegarLoop]: Abstraction has 19 states and 25 transitions. [2018-09-23 19:45:48,406 INFO L481 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-09-23 19:45:48,406 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 25 transitions. [2018-09-23 19:45:48,407 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2018-09-23 19:45:48,407 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:45:48,407 INFO L375 BasicCegarLoop]: trace histogram [9, 1, 1, 1] [2018-09-23 19:45:48,407 INFO L423 AbstractCegarLoop]: === Iteration 10 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:45:48,407 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:45:48,408 INFO L82 PathProgramCache]: Analyzing trace with hash -562523002, now seen corresponding path program 9 times [2018-09-23 19:45:48,408 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:45:48,408 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:45:48,409 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:48,409 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-23 19:45:48,410 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:48,418 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:45:48,799 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 0 proven. 45 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:48,799 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:45:48,800 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:45:48,808 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-09-23 19:45:48,832 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2018-09-23 19:45:48,832 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-23 19:45:48,833 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:45:48,860 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 0 proven. 45 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:48,881 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:45:48,881 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 11 [2018-09-23 19:45:48,882 INFO L459 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-09-23 19:45:48,882 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-09-23 19:45:48,882 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=111, Unknown=0, NotChecked=0, Total=132 [2018-09-23 19:45:48,882 INFO L87 Difference]: Start difference. First operand 19 states and 25 transitions. Second operand 12 states. [2018-09-23 19:45:49,046 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:45:49,047 INFO L93 Difference]: Finished difference Result 23 states and 29 transitions. [2018-09-23 19:45:49,047 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-09-23 19:45:49,047 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 12 [2018-09-23 19:45:49,047 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:45:49,049 INFO L225 Difference]: With dead ends: 23 [2018-09-23 19:45:49,049 INFO L226 Difference]: Without dead ends: 21 [2018-09-23 19:45:49,050 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 11 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=21, Invalid=111, Unknown=0, NotChecked=0, Total=132 [2018-09-23 19:45:49,050 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2018-09-23 19:45:49,055 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-09-23 19:45:49,055 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 21 states. [2018-09-23 19:45:49,056 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 27 transitions. [2018-09-23 19:45:49,056 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 27 transitions. Word has length 12 [2018-09-23 19:45:49,056 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:45:49,056 INFO L480 AbstractCegarLoop]: Abstraction has 21 states and 27 transitions. [2018-09-23 19:45:49,056 INFO L481 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-09-23 19:45:49,056 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 27 transitions. [2018-09-23 19:45:49,057 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2018-09-23 19:45:49,057 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:45:49,057 INFO L375 BasicCegarLoop]: trace histogram [10, 1, 1, 1] [2018-09-23 19:45:49,057 INFO L423 AbstractCegarLoop]: === Iteration 11 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:45:49,058 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:45:49,058 INFO L82 PathProgramCache]: Analyzing trace with hash -258347744, now seen corresponding path program 10 times [2018-09-23 19:45:49,058 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:45:49,058 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:45:49,059 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:49,059 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-23 19:45:49,059 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:49,067 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:45:49,323 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 0 proven. 55 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:49,323 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:45:49,324 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:45:49,332 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-09-23 19:45:49,349 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-09-23 19:45:49,350 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-23 19:45:49,351 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:45:49,379 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 0 proven. 55 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:49,404 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:45:49,405 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 12 [2018-09-23 19:45:49,405 INFO L459 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-09-23 19:45:49,405 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-09-23 19:45:49,405 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=133, Unknown=0, NotChecked=0, Total=156 [2018-09-23 19:45:49,406 INFO L87 Difference]: Start difference. First operand 21 states and 27 transitions. Second operand 13 states. [2018-09-23 19:45:49,589 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:45:49,589 INFO L93 Difference]: Finished difference Result 24 states and 30 transitions. [2018-09-23 19:45:49,596 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-09-23 19:45:49,597 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 13 [2018-09-23 19:45:49,597 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:45:49,597 INFO L225 Difference]: With dead ends: 24 [2018-09-23 19:45:49,598 INFO L226 Difference]: Without dead ends: 22 [2018-09-23 19:45:49,598 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 12 SyntacticMatches, 1 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=23, Invalid=133, Unknown=0, NotChecked=0, Total=156 [2018-09-23 19:45:49,598 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2018-09-23 19:45:49,603 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 22. [2018-09-23 19:45:49,603 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 22 states. [2018-09-23 19:45:49,603 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 28 transitions. [2018-09-23 19:45:49,604 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 28 transitions. Word has length 13 [2018-09-23 19:45:49,604 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:45:49,604 INFO L480 AbstractCegarLoop]: Abstraction has 22 states and 28 transitions. [2018-09-23 19:45:49,604 INFO L481 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-09-23 19:45:49,604 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 28 transitions. [2018-09-23 19:45:49,605 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2018-09-23 19:45:49,605 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:45:49,605 INFO L375 BasicCegarLoop]: trace histogram [11, 1, 1, 1] [2018-09-23 19:45:49,606 INFO L423 AbstractCegarLoop]: === Iteration 12 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:45:49,606 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:45:49,606 INFO L82 PathProgramCache]: Analyzing trace with hash 581150662, now seen corresponding path program 11 times [2018-09-23 19:45:49,606 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:45:49,606 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:45:49,607 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:49,607 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-23 19:45:49,607 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:49,614 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:45:49,984 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 0 proven. 66 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:49,985 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:45:49,985 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:45:49,994 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-09-23 19:45:50,007 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 7 check-sat command(s) [2018-09-23 19:45:50,007 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-23 19:45:50,010 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:45:50,040 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 0 proven. 66 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:50,065 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:45:50,065 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 13 [2018-09-23 19:45:50,066 INFO L459 AbstractCegarLoop]: Interpolant automaton has 14 states [2018-09-23 19:45:50,066 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2018-09-23 19:45:50,066 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=157, Unknown=0, NotChecked=0, Total=182 [2018-09-23 19:45:50,067 INFO L87 Difference]: Start difference. First operand 22 states and 28 transitions. Second operand 14 states. [2018-09-23 19:45:50,393 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:45:50,393 INFO L93 Difference]: Finished difference Result 25 states and 31 transitions. [2018-09-23 19:45:50,393 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-09-23 19:45:50,394 INFO L78 Accepts]: Start accepts. Automaton has 14 states. Word has length 14 [2018-09-23 19:45:50,394 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:45:50,394 INFO L225 Difference]: With dead ends: 25 [2018-09-23 19:45:50,394 INFO L226 Difference]: Without dead ends: 23 [2018-09-23 19:45:50,395 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 26 GetRequests, 13 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=25, Invalid=157, Unknown=0, NotChecked=0, Total=182 [2018-09-23 19:45:50,395 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2018-09-23 19:45:50,399 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-09-23 19:45:50,399 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 23 states. [2018-09-23 19:45:50,399 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 29 transitions. [2018-09-23 19:45:50,400 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 29 transitions. Word has length 14 [2018-09-23 19:45:50,400 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:45:50,400 INFO L480 AbstractCegarLoop]: Abstraction has 23 states and 29 transitions. [2018-09-23 19:45:50,400 INFO L481 AbstractCegarLoop]: Interpolant automaton has 14 states. [2018-09-23 19:45:50,400 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 29 transitions. [2018-09-23 19:45:50,401 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-09-23 19:45:50,401 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:45:50,401 INFO L375 BasicCegarLoop]: trace histogram [12, 1, 1, 1] [2018-09-23 19:45:50,401 INFO L423 AbstractCegarLoop]: === Iteration 13 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:45:50,401 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:45:50,401 INFO L82 PathProgramCache]: Analyzing trace with hash 835797472, now seen corresponding path program 12 times [2018-09-23 19:45:50,402 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:45:50,402 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:45:50,402 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:50,403 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-23 19:45:50,403 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:50,409 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:45:50,939 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 0 proven. 78 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:50,940 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:45:50,940 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:45:50,947 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-09-23 19:45:50,961 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-09-23 19:45:50,961 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-23 19:45:50,963 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:45:50,986 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 0 proven. 78 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:51,007 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:45:51,007 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 14 [2018-09-23 19:45:51,008 INFO L459 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-09-23 19:45:51,008 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-09-23 19:45:51,008 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=183, Unknown=0, NotChecked=0, Total=210 [2018-09-23 19:45:51,008 INFO L87 Difference]: Start difference. First operand 23 states and 29 transitions. Second operand 15 states. [2018-09-23 19:45:51,237 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:45:51,237 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2018-09-23 19:45:51,244 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-09-23 19:45:51,245 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 15 [2018-09-23 19:45:51,245 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:45:51,245 INFO L225 Difference]: With dead ends: 26 [2018-09-23 19:45:51,245 INFO L226 Difference]: Without dead ends: 24 [2018-09-23 19:45:51,246 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 14 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=27, Invalid=183, Unknown=0, NotChecked=0, Total=210 [2018-09-23 19:45:51,246 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2018-09-23 19:45:51,254 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2018-09-23 19:45:51,255 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 24 states. [2018-09-23 19:45:51,255 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2018-09-23 19:45:51,256 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 30 transitions. Word has length 15 [2018-09-23 19:45:51,256 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:45:51,256 INFO L480 AbstractCegarLoop]: Abstraction has 24 states and 30 transitions. [2018-09-23 19:45:51,256 INFO L481 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-09-23 19:45:51,256 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 30 transitions. [2018-09-23 19:45:51,259 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-09-23 19:45:51,259 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:45:51,259 INFO L375 BasicCegarLoop]: trace histogram [13, 1, 1, 1] [2018-09-23 19:45:51,260 INFO L423 AbstractCegarLoop]: === Iteration 14 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:45:51,260 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:45:51,260 INFO L82 PathProgramCache]: Analyzing trace with hash 139913990, now seen corresponding path program 13 times [2018-09-23 19:45:51,260 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:45:51,260 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:45:51,261 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:51,261 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-23 19:45:51,261 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:51,274 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:45:51,680 INFO L134 CoverageAnalysis]: Checked inductivity of 91 backedges. 0 proven. 91 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:51,680 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:45:51,680 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:45:51,689 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-23 19:45:51,699 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:45:51,700 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:45:51,711 INFO L134 CoverageAnalysis]: Checked inductivity of 91 backedges. 0 proven. 91 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:51,731 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:45:51,732 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 15 [2018-09-23 19:45:51,732 INFO L459 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-09-23 19:45:51,732 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-09-23 19:45:51,732 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=211, Unknown=0, NotChecked=0, Total=240 [2018-09-23 19:45:51,733 INFO L87 Difference]: Start difference. First operand 24 states and 30 transitions. Second operand 16 states. [2018-09-23 19:45:52,167 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:45:52,168 INFO L93 Difference]: Finished difference Result 27 states and 33 transitions. [2018-09-23 19:45:52,171 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-09-23 19:45:52,172 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 16 [2018-09-23 19:45:52,172 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:45:52,172 INFO L225 Difference]: With dead ends: 27 [2018-09-23 19:45:52,173 INFO L226 Difference]: Without dead ends: 25 [2018-09-23 19:45:52,174 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 15 SyntacticMatches, 1 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=29, Invalid=211, Unknown=0, NotChecked=0, Total=240 [2018-09-23 19:45:52,174 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2018-09-23 19:45:52,177 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-09-23 19:45:52,177 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 25 states. [2018-09-23 19:45:52,178 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 31 transitions. [2018-09-23 19:45:52,178 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 31 transitions. Word has length 16 [2018-09-23 19:45:52,178 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:45:52,179 INFO L480 AbstractCegarLoop]: Abstraction has 25 states and 31 transitions. [2018-09-23 19:45:52,179 INFO L481 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-09-23 19:45:52,179 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 31 transitions. [2018-09-23 19:45:52,179 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2018-09-23 19:45:52,179 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:45:52,179 INFO L375 BasicCegarLoop]: trace histogram [14, 1, 1, 1] [2018-09-23 19:45:52,180 INFO L423 AbstractCegarLoop]: === Iteration 15 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:45:52,180 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:45:52,180 INFO L82 PathProgramCache]: Analyzing trace with hash 42362528, now seen corresponding path program 14 times [2018-09-23 19:45:52,180 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:45:52,180 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:45:52,181 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:52,181 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-23 19:45:52,181 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:52,189 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:45:52,706 INFO L134 CoverageAnalysis]: Checked inductivity of 105 backedges. 0 proven. 105 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:52,707 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:45:52,707 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:45:52,721 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-09-23 19:45:52,739 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-09-23 19:45:52,739 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-23 19:45:52,741 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:45:52,757 INFO L134 CoverageAnalysis]: Checked inductivity of 105 backedges. 0 proven. 105 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:52,777 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:45:52,778 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 16 [2018-09-23 19:45:52,778 INFO L459 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-09-23 19:45:52,778 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-09-23 19:45:52,778 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=241, Unknown=0, NotChecked=0, Total=272 [2018-09-23 19:45:52,779 INFO L87 Difference]: Start difference. First operand 25 states and 31 transitions. Second operand 17 states. [2018-09-23 19:45:53,128 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:45:53,129 INFO L93 Difference]: Finished difference Result 28 states and 34 transitions. [2018-09-23 19:45:53,131 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-09-23 19:45:53,131 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 17 [2018-09-23 19:45:53,131 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:45:53,132 INFO L225 Difference]: With dead ends: 28 [2018-09-23 19:45:53,132 INFO L226 Difference]: Without dead ends: 26 [2018-09-23 19:45:53,132 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 16 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=31, Invalid=241, Unknown=0, NotChecked=0, Total=272 [2018-09-23 19:45:53,133 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2018-09-23 19:45:53,136 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2018-09-23 19:45:53,136 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 26 states. [2018-09-23 19:45:53,137 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 32 transitions. [2018-09-23 19:45:53,137 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 32 transitions. Word has length 17 [2018-09-23 19:45:53,137 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:45:53,137 INFO L480 AbstractCegarLoop]: Abstraction has 26 states and 32 transitions. [2018-09-23 19:45:53,137 INFO L481 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-09-23 19:45:53,137 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 32 transitions. [2018-09-23 19:45:53,138 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2018-09-23 19:45:53,138 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:45:53,138 INFO L375 BasicCegarLoop]: trace histogram [15, 1, 1, 1] [2018-09-23 19:45:53,138 INFO L423 AbstractCegarLoop]: === Iteration 16 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:45:53,138 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:45:53,139 INFO L82 PathProgramCache]: Analyzing trace with hash 1313234502, now seen corresponding path program 15 times [2018-09-23 19:45:53,139 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:45:53,139 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:45:53,139 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:53,139 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-23 19:45:53,140 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:53,145 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:45:53,882 INFO L134 CoverageAnalysis]: Checked inductivity of 120 backedges. 0 proven. 120 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:53,882 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:45:53,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 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:45:53,890 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-09-23 19:45:53,903 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 9 check-sat command(s) [2018-09-23 19:45:53,904 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-23 19:45:53,905 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:45:53,931 INFO L134 CoverageAnalysis]: Checked inductivity of 120 backedges. 0 proven. 120 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:53,959 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:45:53,959 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17] total 17 [2018-09-23 19:45:53,959 INFO L459 AbstractCegarLoop]: Interpolant automaton has 18 states [2018-09-23 19:45:53,959 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2018-09-23 19:45:53,960 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=273, Unknown=0, NotChecked=0, Total=306 [2018-09-23 19:45:53,960 INFO L87 Difference]: Start difference. First operand 26 states and 32 transitions. Second operand 18 states. [2018-09-23 19:45:54,259 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:45:54,259 INFO L93 Difference]: Finished difference Result 29 states and 35 transitions. [2018-09-23 19:45:54,259 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-09-23 19:45:54,260 INFO L78 Accepts]: Start accepts. Automaton has 18 states. Word has length 18 [2018-09-23 19:45:54,260 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:45:54,261 INFO L225 Difference]: With dead ends: 29 [2018-09-23 19:45:54,262 INFO L226 Difference]: Without dead ends: 27 [2018-09-23 19:45:54,262 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 17 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=33, Invalid=273, Unknown=0, NotChecked=0, Total=306 [2018-09-23 19:45:54,263 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2018-09-23 19:45:54,266 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2018-09-23 19:45:54,266 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 27 states. [2018-09-23 19:45:54,267 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 33 transitions. [2018-09-23 19:45:54,267 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 33 transitions. Word has length 18 [2018-09-23 19:45:54,267 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:45:54,267 INFO L480 AbstractCegarLoop]: Abstraction has 27 states and 33 transitions. [2018-09-23 19:45:54,267 INFO L481 AbstractCegarLoop]: Interpolant automaton has 18 states. [2018-09-23 19:45:54,267 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 33 transitions. [2018-09-23 19:45:54,268 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-09-23 19:45:54,268 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:45:54,268 INFO L375 BasicCegarLoop]: trace histogram [17, 1, 1, 1] [2018-09-23 19:45:54,269 INFO L423 AbstractCegarLoop]: === Iteration 17 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:45:54,269 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:45:54,269 INFO L82 PathProgramCache]: Analyzing trace with hash -702152314, now seen corresponding path program 16 times [2018-09-23 19:45:54,269 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:45:54,269 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:45:54,269 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:54,270 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-23 19:45:54,270 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:54,275 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:45:57,023 INFO L134 CoverageAnalysis]: Checked inductivity of 153 backedges. 0 proven. 153 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:57,023 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:45:57,023 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:45:57,032 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-09-23 19:45:57,043 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-09-23 19:45:57,043 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-23 19:45:57,045 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:45:57,068 INFO L134 CoverageAnalysis]: Checked inductivity of 153 backedges. 0 proven. 153 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:45:57,096 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:45:57,097 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19] total 19 [2018-09-23 19:45:57,097 INFO L459 AbstractCegarLoop]: Interpolant automaton has 20 states [2018-09-23 19:45:57,097 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2018-09-23 19:45:57,097 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=342, Unknown=1, NotChecked=0, Total=380 [2018-09-23 19:45:57,098 INFO L87 Difference]: Start difference. First operand 27 states and 33 transitions. Second operand 20 states. [2018-09-23 19:45:59,641 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:45:59,642 INFO L93 Difference]: Finished difference Result 31 states and 37 transitions. [2018-09-23 19:45:59,642 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2018-09-23 19:45:59,642 INFO L78 Accepts]: Start accepts. Automaton has 20 states. Word has length 20 [2018-09-23 19:45:59,642 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:45:59,643 INFO L225 Difference]: With dead ends: 31 [2018-09-23 19:45:59,643 INFO L226 Difference]: Without dead ends: 29 [2018-09-23 19:45:59,644 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 19 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=37, Invalid=342, Unknown=1, NotChecked=0, Total=380 [2018-09-23 19:45:59,644 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2018-09-23 19:45:59,648 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 29. [2018-09-23 19:45:59,649 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 29 states. [2018-09-23 19:45:59,649 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 35 transitions. [2018-09-23 19:45:59,649 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 35 transitions. Word has length 20 [2018-09-23 19:45:59,649 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:45:59,649 INFO L480 AbstractCegarLoop]: Abstraction has 29 states and 35 transitions. [2018-09-23 19:45:59,649 INFO L481 AbstractCegarLoop]: Interpolant automaton has 20 states. [2018-09-23 19:45:59,650 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 35 transitions. [2018-09-23 19:45:59,650 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2018-09-23 19:45:59,650 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:45:59,650 INFO L375 BasicCegarLoop]: trace histogram [18, 1, 1, 1] [2018-09-23 19:45:59,651 INFO L423 AbstractCegarLoop]: === Iteration 18 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:45:59,651 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:45:59,651 INFO L82 PathProgramCache]: Analyzing trace with hash -291889120, now seen corresponding path program 17 times [2018-09-23 19:45:59,651 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:45:59,651 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:45:59,652 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:59,652 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-23 19:45:59,652 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:45:59,658 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:46:02,384 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 0 proven. 170 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:46:02,385 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:46:02,385 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:46:02,393 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-09-23 19:46:02,458 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 10 check-sat command(s) [2018-09-23 19:46:02,458 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-23 19:46:02,460 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:46:02,472 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 0 proven. 170 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:46:02,493 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:46:02,493 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 20 [2018-09-23 19:46:02,493 INFO L459 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-09-23 19:46:02,493 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-09-23 19:46:02,494 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=380, Unknown=1, NotChecked=0, Total=420 [2018-09-23 19:46:02,494 INFO L87 Difference]: Start difference. First operand 29 states and 35 transitions. Second operand 21 states. [2018-09-23 19:46:05,103 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:46:05,104 INFO L93 Difference]: Finished difference Result 32 states and 38 transitions. [2018-09-23 19:46:05,104 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-09-23 19:46:05,105 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 21 [2018-09-23 19:46:05,105 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:46:05,105 INFO L225 Difference]: With dead ends: 32 [2018-09-23 19:46:05,105 INFO L226 Difference]: Without dead ends: 30 [2018-09-23 19:46:05,106 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 20 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=39, Invalid=380, Unknown=1, NotChecked=0, Total=420 [2018-09-23 19:46:05,106 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2018-09-23 19:46:05,110 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2018-09-23 19:46:05,110 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 30 states. [2018-09-23 19:46:05,113 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 36 transitions. [2018-09-23 19:46:05,113 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 36 transitions. Word has length 21 [2018-09-23 19:46:05,113 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:46:05,113 INFO L480 AbstractCegarLoop]: Abstraction has 30 states and 36 transitions. [2018-09-23 19:46:05,113 INFO L481 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-09-23 19:46:05,114 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 36 transitions. [2018-09-23 19:46:05,114 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2018-09-23 19:46:05,114 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:46:05,114 INFO L375 BasicCegarLoop]: trace histogram [19, 1, 1, 1] [2018-09-23 19:46:05,115 INFO L423 AbstractCegarLoop]: === Iteration 19 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:46:05,115 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:46:05,115 INFO L82 PathProgramCache]: Analyzing trace with hash -458631994, now seen corresponding path program 18 times [2018-09-23 19:46:05,115 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:46:05,115 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:46:05,116 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:46:05,116 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-23 19:46:05,116 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:46:05,121 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:46:05,971 INFO L134 CoverageAnalysis]: Checked inductivity of 190 backedges. 0 proven. 190 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:46:05,972 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:46:05,972 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:46:05,986 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-09-23 19:46:06,035 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 11 check-sat command(s) [2018-09-23 19:46:06,036 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-23 19:46:06,038 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:46:06,057 INFO L134 CoverageAnalysis]: Checked inductivity of 190 backedges. 0 proven. 190 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:46:06,078 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:46:06,078 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21] total 21 [2018-09-23 19:46:06,079 INFO L459 AbstractCegarLoop]: Interpolant automaton has 22 states [2018-09-23 19:46:06,079 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2018-09-23 19:46:06,079 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=421, Unknown=0, NotChecked=0, Total=462 [2018-09-23 19:46:06,080 INFO L87 Difference]: Start difference. First operand 30 states and 36 transitions. Second operand 22 states. [2018-09-23 19:46:10,824 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:46:10,824 INFO L93 Difference]: Finished difference Result 33 states and 39 transitions. [2018-09-23 19:46:10,825 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2018-09-23 19:46:10,825 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 22 [2018-09-23 19:46:10,826 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:46:10,827 INFO L225 Difference]: With dead ends: 33 [2018-09-23 19:46:10,827 INFO L226 Difference]: Without dead ends: 31 [2018-09-23 19:46:10,828 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 21 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=41, Invalid=421, Unknown=0, NotChecked=0, Total=462 [2018-09-23 19:46:10,828 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2018-09-23 19:46:10,832 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2018-09-23 19:46:10,832 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 31 states. [2018-09-23 19:46:10,833 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 37 transitions. [2018-09-23 19:46:10,833 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 37 transitions. Word has length 22 [2018-09-23 19:46:10,833 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:46:10,833 INFO L480 AbstractCegarLoop]: Abstraction has 31 states and 37 transitions. [2018-09-23 19:46:10,833 INFO L481 AbstractCegarLoop]: Interpolant automaton has 22 states. [2018-09-23 19:46:10,834 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 37 transitions. [2018-09-23 19:46:10,834 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2018-09-23 19:46:10,834 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:46:10,834 INFO L375 BasicCegarLoop]: trace histogram [20, 1, 1, 1] [2018-09-23 19:46:10,835 INFO L423 AbstractCegarLoop]: === Iteration 20 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:46:10,835 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:46:10,835 INFO L82 PathProgramCache]: Analyzing trace with hash -1332693792, now seen corresponding path program 19 times [2018-09-23 19:46:10,835 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:46:10,835 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:46:10,836 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:46:10,836 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-23 19:46:10,836 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:46:10,843 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:46:14,725 INFO L134 CoverageAnalysis]: Checked inductivity of 210 backedges. 0 proven. 209 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:46:14,726 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:46:14,726 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:46:14,734 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-23 19:46:14,760 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:46:14,763 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:46:14,793 INFO L134 CoverageAnalysis]: Checked inductivity of 210 backedges. 0 proven. 209 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:46:14,813 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:46:14,813 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 22 [2018-09-23 19:46:14,814 INFO L459 AbstractCegarLoop]: Interpolant automaton has 23 states [2018-09-23 19:46:14,814 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2018-09-23 19:46:14,814 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=462, Unknown=1, NotChecked=0, Total=506 [2018-09-23 19:46:14,814 INFO L87 Difference]: Start difference. First operand 31 states and 37 transitions. Second operand 23 states. [2018-09-23 19:46:21,474 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:46:21,474 INFO L93 Difference]: Finished difference Result 34 states and 40 transitions. [2018-09-23 19:46:21,475 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-09-23 19:46:21,476 INFO L78 Accepts]: Start accepts. Automaton has 23 states. Word has length 23 [2018-09-23 19:46:21,476 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:46:21,476 INFO L225 Difference]: With dead ends: 34 [2018-09-23 19:46:21,476 INFO L226 Difference]: Without dead ends: 32 [2018-09-23 19:46:21,477 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 22 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 3.8s TimeCoverageRelationStatistics Valid=43, Invalid=462, Unknown=1, NotChecked=0, Total=506 [2018-09-23 19:46:21,477 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2018-09-23 19:46:21,481 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2018-09-23 19:46:21,481 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 32 states. [2018-09-23 19:46:21,482 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 38 transitions. [2018-09-23 19:46:21,482 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 38 transitions. Word has length 23 [2018-09-23 19:46:21,482 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:46:21,482 INFO L480 AbstractCegarLoop]: Abstraction has 32 states and 38 transitions. [2018-09-23 19:46:21,482 INFO L481 AbstractCegarLoop]: Interpolant automaton has 23 states. [2018-09-23 19:46:21,482 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 38 transitions. [2018-09-23 19:46:21,483 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-09-23 19:46:21,483 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:46:21,483 INFO L375 BasicCegarLoop]: trace histogram [21, 1, 1, 1] [2018-09-23 19:46:21,483 INFO L423 AbstractCegarLoop]: === Iteration 21 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:46:21,484 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:46:21,484 INFO L82 PathProgramCache]: Analyzing trace with hash 1636161542, now seen corresponding path program 20 times [2018-09-23 19:46:21,484 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:46:21,484 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:46:21,485 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:46:21,485 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-23 19:46:21,485 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:46:21,491 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:46:28,788 INFO L134 CoverageAnalysis]: Checked inductivity of 231 backedges. 0 proven. 229 refuted. 2 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:46:28,789 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:46:28,789 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:46:28,797 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-09-23 19:46:28,824 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-09-23 19:46:28,825 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-23 19:46:28,827 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:46:28,886 INFO L134 CoverageAnalysis]: Checked inductivity of 231 backedges. 0 proven. 229 refuted. 2 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:46:28,908 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:46:28,908 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 23] total 23 [2018-09-23 19:46:28,908 INFO L459 AbstractCegarLoop]: Interpolant automaton has 24 states [2018-09-23 19:46:28,908 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2018-09-23 19:46:28,909 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=504, Unknown=3, NotChecked=0, Total=552 [2018-09-23 19:46:28,909 INFO L87 Difference]: Start difference. First operand 32 states and 38 transitions. Second operand 24 states. [2018-09-23 19:46:29,977 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:46:29,978 INFO L93 Difference]: Finished difference Result 35 states and 41 transitions. [2018-09-23 19:46:29,978 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-09-23 19:46:29,978 INFO L78 Accepts]: Start accepts. Automaton has 24 states. Word has length 24 [2018-09-23 19:46:29,979 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:46:29,979 INFO L225 Difference]: With dead ends: 35 [2018-09-23 19:46:29,979 INFO L226 Difference]: Without dead ends: 33 [2018-09-23 19:46:29,980 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 23 SyntacticMatches, 1 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 7.3s TimeCoverageRelationStatistics Valid=45, Invalid=504, Unknown=3, NotChecked=0, Total=552 [2018-09-23 19:46:29,981 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2018-09-23 19:46:29,986 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2018-09-23 19:46:29,986 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 33 states. [2018-09-23 19:46:29,986 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 39 transitions. [2018-09-23 19:46:29,986 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 39 transitions. Word has length 24 [2018-09-23 19:46:29,987 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:46:29,987 INFO L480 AbstractCegarLoop]: Abstraction has 33 states and 39 transitions. [2018-09-23 19:46:29,987 INFO L481 AbstractCegarLoop]: Interpolant automaton has 24 states. [2018-09-23 19:46:29,987 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 39 transitions. [2018-09-23 19:46:29,987 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2018-09-23 19:46:29,987 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:46:29,988 INFO L375 BasicCegarLoop]: trace histogram [22, 1, 1, 1] [2018-09-23 19:46:29,988 INFO L423 AbstractCegarLoop]: === Iteration 22 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:46:29,988 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:46:29,988 INFO L82 PathProgramCache]: Analyzing trace with hash -818603616, now seen corresponding path program 21 times [2018-09-23 19:46:29,988 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:46:29,988 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:46:29,989 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:46:29,989 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-23 19:46:29,989 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:46:29,994 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:46:40,176 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 0 proven. 251 refuted. 2 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:46:40,177 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:46:40,177 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:46:40,184 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-09-23 19:46:40,203 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 12 check-sat command(s) [2018-09-23 19:46:40,203 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-23 19:46:40,206 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:46:40,238 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 0 proven. 251 refuted. 2 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:46:40,268 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:46:40,269 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 24] total 24 [2018-09-23 19:46:40,269 INFO L459 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-09-23 19:46:40,269 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-09-23 19:46:40,269 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=549, Unknown=4, NotChecked=0, Total=600 [2018-09-23 19:46:40,270 INFO L87 Difference]: Start difference. First operand 33 states and 39 transitions. Second operand 25 states. [2018-09-23 19:46:47,619 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:46:47,620 INFO L93 Difference]: Finished difference Result 36 states and 42 transitions. [2018-09-23 19:46:47,621 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2018-09-23 19:46:47,621 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 25 [2018-09-23 19:46:47,621 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:46:47,622 INFO L225 Difference]: With dead ends: 36 [2018-09-23 19:46:47,622 INFO L226 Difference]: Without dead ends: 34 [2018-09-23 19:46:47,623 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 48 GetRequests, 24 SyntacticMatches, 1 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 10.1s TimeCoverageRelationStatistics Valid=47, Invalid=549, Unknown=4, NotChecked=0, Total=600 [2018-09-23 19:46:47,623 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2018-09-23 19:46:47,628 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 34. [2018-09-23 19:46:47,628 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 34 states. [2018-09-23 19:46:47,628 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 40 transitions. [2018-09-23 19:46:47,628 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 40 transitions. Word has length 25 [2018-09-23 19:46:47,629 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:46:47,629 INFO L480 AbstractCegarLoop]: Abstraction has 34 states and 40 transitions. [2018-09-23 19:46:47,629 INFO L481 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-09-23 19:46:47,629 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 40 transitions. [2018-09-23 19:46:47,629 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2018-09-23 19:46:47,629 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:46:47,630 INFO L375 BasicCegarLoop]: trace histogram [23, 1, 1, 1] [2018-09-23 19:46:47,630 INFO L423 AbstractCegarLoop]: === Iteration 23 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:46:47,630 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:46:47,630 INFO L82 PathProgramCache]: Analyzing trace with hash 393087814, now seen corresponding path program 22 times [2018-09-23 19:46:47,630 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:46:47,630 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:46:47,631 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:46:47,631 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-23 19:46:47,631 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:46:47,637 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:46:51,057 INFO L134 CoverageAnalysis]: Checked inductivity of 276 backedges. 0 proven. 275 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:46:51,057 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:46:51,057 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:46:51,065 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-09-23 19:46:51,093 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-09-23 19:46:51,093 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-23 19:46:51,096 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:46:51,165 INFO L134 CoverageAnalysis]: Checked inductivity of 276 backedges. 0 proven. 275 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:46:51,187 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:46:51,187 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 25] total 25 [2018-09-23 19:46:51,188 INFO L459 AbstractCegarLoop]: Interpolant automaton has 26 states [2018-09-23 19:46:51,188 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2018-09-23 19:46:51,188 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=49, Invalid=600, Unknown=1, NotChecked=0, Total=650 [2018-09-23 19:46:51,189 INFO L87 Difference]: Start difference. First operand 34 states and 40 transitions. Second operand 26 states. [2018-09-23 19:46:58,175 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:46:58,175 INFO L93 Difference]: Finished difference Result 37 states and 43 transitions. [2018-09-23 19:46:58,175 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2018-09-23 19:46:58,176 INFO L78 Accepts]: Start accepts. Automaton has 26 states. Word has length 26 [2018-09-23 19:46:58,176 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:46:58,177 INFO L225 Difference]: With dead ends: 37 [2018-09-23 19:46:58,177 INFO L226 Difference]: Without dead ends: 35 [2018-09-23 19:46:58,177 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 50 GetRequests, 25 SyntacticMatches, 1 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 3.4s TimeCoverageRelationStatistics Valid=49, Invalid=600, Unknown=1, NotChecked=0, Total=650 [2018-09-23 19:46:58,178 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2018-09-23 19:46:58,181 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 35. [2018-09-23 19:46:58,182 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 35 states. [2018-09-23 19:46:58,182 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 41 transitions. [2018-09-23 19:46:58,182 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 41 transitions. Word has length 26 [2018-09-23 19:46:58,182 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:46:58,182 INFO L480 AbstractCegarLoop]: Abstraction has 35 states and 41 transitions. [2018-09-23 19:46:58,183 INFO L481 AbstractCegarLoop]: Interpolant automaton has 26 states. [2018-09-23 19:46:58,183 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 41 transitions. [2018-09-23 19:46:58,183 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2018-09-23 19:46:58,183 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:46:58,183 INFO L375 BasicCegarLoop]: trace histogram [25, 1, 1, 1] [2018-09-23 19:46:58,184 INFO L423 AbstractCegarLoop]: === Iteration 24 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:46:58,184 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:46:58,184 INFO L82 PathProgramCache]: Analyzing trace with hash -199856506, now seen corresponding path program 23 times [2018-09-23 19:46:58,184 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:46:58,184 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:46:58,185 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:46:58,185 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-23 19:46:58,185 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:46:58,191 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:47:05,095 INFO L134 CoverageAnalysis]: Checked inductivity of 325 backedges. 0 proven. 323 refuted. 2 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:47:05,096 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:47:05,096 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 24 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 24 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:47:05,104 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-09-23 19:47:05,126 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 14 check-sat command(s) [2018-09-23 19:47:05,127 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-23 19:47:05,129 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:47:05,154 INFO L134 CoverageAnalysis]: Checked inductivity of 325 backedges. 0 proven. 323 refuted. 2 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:47:05,181 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:47:05,181 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [27, 27] total 27 [2018-09-23 19:47:05,181 INFO L459 AbstractCegarLoop]: Interpolant automaton has 28 states [2018-09-23 19:47:05,181 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2018-09-23 19:47:05,182 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=701, Unknown=2, NotChecked=0, Total=756 [2018-09-23 19:47:05,182 INFO L87 Difference]: Start difference. First operand 35 states and 41 transitions. Second operand 28 states. [2018-09-23 19:47:10,503 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:47:10,503 INFO L93 Difference]: Finished difference Result 39 states and 45 transitions. [2018-09-23 19:47:10,504 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2018-09-23 19:47:10,504 INFO L78 Accepts]: Start accepts. Automaton has 28 states. Word has length 28 [2018-09-23 19:47:10,504 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:47:10,505 INFO L225 Difference]: With dead ends: 39 [2018-09-23 19:47:10,505 INFO L226 Difference]: Without dead ends: 37 [2018-09-23 19:47:10,506 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 27 SyntacticMatches, 1 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 6.8s TimeCoverageRelationStatistics Valid=53, Invalid=701, Unknown=2, NotChecked=0, Total=756 [2018-09-23 19:47:10,506 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2018-09-23 19:47:10,511 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 37. [2018-09-23 19:47:10,511 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 37 states. [2018-09-23 19:47:10,512 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 43 transitions. [2018-09-23 19:47:10,512 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 43 transitions. Word has length 28 [2018-09-23 19:47:10,512 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:47:10,512 INFO L480 AbstractCegarLoop]: Abstraction has 37 states and 43 transitions. [2018-09-23 19:47:10,512 INFO L481 AbstractCegarLoop]: Interpolant automaton has 28 states. [2018-09-23 19:47:10,513 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 43 transitions. [2018-09-23 19:47:10,513 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2018-09-23 19:47:10,513 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:47:10,513 INFO L375 BasicCegarLoop]: trace histogram [26, 1, 1, 1] [2018-09-23 19:47:10,514 INFO L423 AbstractCegarLoop]: === Iteration 25 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:47:10,514 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:47:10,514 INFO L82 PathProgramCache]: Analyzing trace with hash -1900588256, now seen corresponding path program 24 times [2018-09-23 19:47:10,514 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:47:10,514 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:47:10,515 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:47:10,515 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-23 19:47:10,515 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:47:10,523 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:47:20,130 INFO L134 CoverageAnalysis]: Checked inductivity of 351 backedges. 0 proven. 350 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:47:20,130 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:47:20,130 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:47:20,137 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-09-23 19:47:20,162 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 14 check-sat command(s) [2018-09-23 19:47:20,162 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-23 19:47:20,164 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:47:20,195 INFO L134 CoverageAnalysis]: Checked inductivity of 351 backedges. 0 proven. 350 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:47:20,215 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:47:20,215 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [28, 28] total 28 [2018-09-23 19:47:20,215 INFO L459 AbstractCegarLoop]: Interpolant automaton has 29 states [2018-09-23 19:47:20,216 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2018-09-23 19:47:20,216 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=753, Unknown=4, NotChecked=0, Total=812 [2018-09-23 19:47:20,216 INFO L87 Difference]: Start difference. First operand 37 states and 43 transitions. Second operand 29 states. [2018-09-23 19:47:29,388 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:47:29,389 INFO L93 Difference]: Finished difference Result 40 states and 46 transitions. [2018-09-23 19:47:29,389 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2018-09-23 19:47:29,389 INFO L78 Accepts]: Start accepts. Automaton has 29 states. Word has length 29 [2018-09-23 19:47:29,389 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:47:29,390 INFO L225 Difference]: With dead ends: 40 [2018-09-23 19:47:29,390 INFO L226 Difference]: Without dead ends: 38 [2018-09-23 19:47:29,391 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 28 SyntacticMatches, 1 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 9.5s TimeCoverageRelationStatistics Valid=55, Invalid=753, Unknown=4, NotChecked=0, Total=812 [2018-09-23 19:47:29,391 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 38 states. [2018-09-23 19:47:29,394 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 38 to 38. [2018-09-23 19:47:29,395 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 38 states. [2018-09-23 19:47:29,395 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 44 transitions. [2018-09-23 19:47:29,395 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 44 transitions. Word has length 29 [2018-09-23 19:47:29,395 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:47:29,395 INFO L480 AbstractCegarLoop]: Abstraction has 38 states and 44 transitions. [2018-09-23 19:47:29,396 INFO L481 AbstractCegarLoop]: Interpolant automaton has 29 states. [2018-09-23 19:47:29,396 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 44 transitions. [2018-09-23 19:47:29,396 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2018-09-23 19:47:29,396 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:47:29,396 INFO L375 BasicCegarLoop]: trace histogram [27, 1, 1, 1] [2018-09-23 19:47:29,397 INFO L423 AbstractCegarLoop]: === Iteration 26 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:47:29,397 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:47:29,397 INFO L82 PathProgramCache]: Analyzing trace with hash 1211302342, now seen corresponding path program 25 times [2018-09-23 19:47:29,397 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:47:29,397 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:47:29,398 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:47:29,398 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-23 19:47:29,398 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:47:29,404 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:47:35,652 INFO L134 CoverageAnalysis]: Checked inductivity of 378 backedges. 0 proven. 378 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:47:35,652 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:47:35,652 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 26 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 26 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:47:35,660 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-23 19:47:35,678 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:47:35,681 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:47:35,719 INFO L134 CoverageAnalysis]: Checked inductivity of 378 backedges. 0 proven. 378 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:47:35,740 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:47:35,740 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [29, 29] total 29 [2018-09-23 19:47:35,740 INFO L459 AbstractCegarLoop]: Interpolant automaton has 30 states [2018-09-23 19:47:35,741 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2018-09-23 19:47:35,741 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=57, Invalid=811, Unknown=2, NotChecked=0, Total=870 [2018-09-23 19:47:35,741 INFO L87 Difference]: Start difference. First operand 38 states and 44 transitions. Second operand 30 states. [2018-09-23 19:47:43,147 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:47:43,147 INFO L93 Difference]: Finished difference Result 41 states and 47 transitions. [2018-09-23 19:47:43,148 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-09-23 19:47:43,148 INFO L78 Accepts]: Start accepts. Automaton has 30 states. Word has length 30 [2018-09-23 19:47:43,148 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:47:43,149 INFO L225 Difference]: With dead ends: 41 [2018-09-23 19:47:43,149 INFO L226 Difference]: Without dead ends: 39 [2018-09-23 19:47:43,150 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 29 SyntacticMatches, 1 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 6.2s TimeCoverageRelationStatistics Valid=57, Invalid=811, Unknown=2, NotChecked=0, Total=870 [2018-09-23 19:47:43,150 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2018-09-23 19:47:43,153 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 39. [2018-09-23 19:47:43,153 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 39 states. [2018-09-23 19:47:43,153 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 45 transitions. [2018-09-23 19:47:43,154 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 45 transitions. Word has length 30 [2018-09-23 19:47:43,154 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:47:43,154 INFO L480 AbstractCegarLoop]: Abstraction has 39 states and 45 transitions. [2018-09-23 19:47:43,154 INFO L481 AbstractCegarLoop]: Interpolant automaton has 30 states. [2018-09-23 19:47:43,154 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 45 transitions. [2018-09-23 19:47:43,154 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2018-09-23 19:47:43,154 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:47:43,155 INFO L375 BasicCegarLoop]: trace histogram [28, 1, 1, 1] [2018-09-23 19:47:43,155 INFO L423 AbstractCegarLoop]: === Iteration 27 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:47:43,155 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:47:43,155 INFO L82 PathProgramCache]: Analyzing trace with hash -1104336928, now seen corresponding path program 26 times [2018-09-23 19:47:43,155 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:47:43,155 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:47:43,156 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:47:43,156 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-23 19:47:43,156 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:47:43,163 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:47:51,051 INFO L134 CoverageAnalysis]: Checked inductivity of 406 backedges. 0 proven. 404 refuted. 2 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:47:51,052 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:47:51,052 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 27 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 27 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:47:51,062 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-09-23 19:47:51,080 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-09-23 19:47:51,080 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-23 19:47:51,082 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:47:51,097 INFO L134 CoverageAnalysis]: Checked inductivity of 406 backedges. 0 proven. 404 refuted. 2 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:47:51,117 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:47:51,118 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [30, 30] total 30 [2018-09-23 19:47:51,118 INFO L459 AbstractCegarLoop]: Interpolant automaton has 31 states [2018-09-23 19:47:51,118 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2018-09-23 19:47:51,119 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=59, Invalid=868, Unknown=3, NotChecked=0, Total=930 [2018-09-23 19:47:51,119 INFO L87 Difference]: Start difference. First operand 39 states and 45 transitions. Second operand 31 states. [2018-09-23 19:48:04,521 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:48:04,521 INFO L93 Difference]: Finished difference Result 42 states and 48 transitions. [2018-09-23 19:48:04,522 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2018-09-23 19:48:04,522 INFO L78 Accepts]: Start accepts. Automaton has 31 states. Word has length 31 [2018-09-23 19:48:04,522 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:48:04,523 INFO L225 Difference]: With dead ends: 42 [2018-09-23 19:48:04,523 INFO L226 Difference]: Without dead ends: 40 [2018-09-23 19:48:04,524 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 30 SyntacticMatches, 1 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 7.8s TimeCoverageRelationStatistics Valid=59, Invalid=868, Unknown=3, NotChecked=0, Total=930 [2018-09-23 19:48:04,524 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2018-09-23 19:48:04,528 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 40. [2018-09-23 19:48:04,528 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 40 states. [2018-09-23 19:48:04,528 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 46 transitions. [2018-09-23 19:48:04,529 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 46 transitions. Word has length 31 [2018-09-23 19:48:04,529 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:48:04,529 INFO L480 AbstractCegarLoop]: Abstraction has 40 states and 46 transitions. [2018-09-23 19:48:04,529 INFO L481 AbstractCegarLoop]: Interpolant automaton has 31 states. [2018-09-23 19:48:04,529 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 46 transitions. [2018-09-23 19:48:04,530 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2018-09-23 19:48:04,530 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:48:04,530 INFO L375 BasicCegarLoop]: trace histogram [29, 1, 1, 1] [2018-09-23 19:48:04,530 INFO L423 AbstractCegarLoop]: === Iteration 28 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:48:04,530 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:48:04,530 INFO L82 PathProgramCache]: Analyzing trace with hash 125289734, now seen corresponding path program 27 times [2018-09-23 19:48:04,530 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:48:04,531 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:48:04,531 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:48:04,531 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-23 19:48:04,531 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:48:04,538 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:48:10,760 INFO L134 CoverageAnalysis]: Checked inductivity of 435 backedges. 0 proven. 434 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:48:10,761 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:48:10,761 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 28 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 28 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:48:10,774 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-09-23 19:48:10,799 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 16 check-sat command(s) [2018-09-23 19:48:10,799 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-23 19:48:10,801 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:48:10,831 INFO L134 CoverageAnalysis]: Checked inductivity of 435 backedges. 0 proven. 434 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:48:10,862 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:48:10,862 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [31, 31] total 31 [2018-09-23 19:48:10,862 INFO L459 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-09-23 19:48:10,863 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-09-23 19:48:10,863 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=61, Invalid=929, Unknown=2, NotChecked=0, Total=992 [2018-09-23 19:48:10,863 INFO L87 Difference]: Start difference. First operand 40 states and 46 transitions. Second operand 32 states. [2018-09-23 19:48:28,592 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:48:28,593 INFO L93 Difference]: Finished difference Result 43 states and 49 transitions. [2018-09-23 19:48:28,594 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2018-09-23 19:48:28,594 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 32 [2018-09-23 19:48:28,594 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:48:28,594 INFO L225 Difference]: With dead ends: 43 [2018-09-23 19:48:28,595 INFO L226 Difference]: Without dead ends: 41 [2018-09-23 19:48:28,595 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 62 GetRequests, 31 SyntacticMatches, 1 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 6.2s TimeCoverageRelationStatistics Valid=61, Invalid=929, Unknown=2, NotChecked=0, Total=992 [2018-09-23 19:48:28,596 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2018-09-23 19:48:28,600 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2018-09-23 19:48:28,600 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 41 states. [2018-09-23 19:48:28,600 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 47 transitions. [2018-09-23 19:48:28,601 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 47 transitions. Word has length 32 [2018-09-23 19:48:28,601 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:48:28,601 INFO L480 AbstractCegarLoop]: Abstraction has 41 states and 47 transitions. [2018-09-23 19:48:28,601 INFO L481 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-09-23 19:48:28,601 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 47 transitions. [2018-09-23 19:48:28,602 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2018-09-23 19:48:28,602 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:48:28,602 INFO L375 BasicCegarLoop]: trace histogram [30, 1, 1, 1] [2018-09-23 19:48:28,602 INFO L423 AbstractCegarLoop]: === Iteration 29 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:48:28,603 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:48:28,603 INFO L82 PathProgramCache]: Analyzing trace with hash -410989408, now seen corresponding path program 28 times [2018-09-23 19:48:28,603 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:48:28,603 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:48:28,604 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:48:28,604 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-23 19:48:28,604 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:48:28,613 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:48:39,165 INFO L134 CoverageAnalysis]: Checked inductivity of 465 backedges. 0 proven. 463 refuted. 2 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:48:39,165 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:48:39,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 29 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 29 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:48:39,174 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-09-23 19:48:39,195 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-09-23 19:48:39,195 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-23 19:48:39,197 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:48:39,225 INFO L134 CoverageAnalysis]: Checked inductivity of 465 backedges. 0 proven. 463 refuted. 2 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:48:39,258 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:48:39,258 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [32, 32] total 32 [2018-09-23 19:48:39,258 INFO L459 AbstractCegarLoop]: Interpolant automaton has 33 states [2018-09-23 19:48:39,259 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2018-09-23 19:48:39,259 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=63, Invalid=989, Unknown=4, NotChecked=0, Total=1056 [2018-09-23 19:48:39,259 INFO L87 Difference]: Start difference. First operand 41 states and 47 transitions. Second operand 33 states. [2018-09-23 19:48:42,581 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:48:42,581 INFO L93 Difference]: Finished difference Result 44 states and 50 transitions. [2018-09-23 19:48:42,582 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-09-23 19:48:42,582 INFO L78 Accepts]: Start accepts. Automaton has 33 states. Word has length 33 [2018-09-23 19:48:42,582 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:48:42,583 INFO L225 Difference]: With dead ends: 44 [2018-09-23 19:48:42,583 INFO L226 Difference]: Without dead ends: 42 [2018-09-23 19:48:42,583 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 64 GetRequests, 32 SyntacticMatches, 1 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 10.5s TimeCoverageRelationStatistics Valid=63, Invalid=989, Unknown=4, NotChecked=0, Total=1056 [2018-09-23 19:48:42,584 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2018-09-23 19:48:42,586 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 42. [2018-09-23 19:48:42,586 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 42 states. [2018-09-23 19:48:42,587 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 48 transitions. [2018-09-23 19:48:42,587 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 48 transitions. Word has length 33 [2018-09-23 19:48:42,587 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:48:42,587 INFO L480 AbstractCegarLoop]: Abstraction has 42 states and 48 transitions. [2018-09-23 19:48:42,587 INFO L481 AbstractCegarLoop]: Interpolant automaton has 33 states. [2018-09-23 19:48:42,587 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 48 transitions. [2018-09-23 19:48:42,588 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2018-09-23 19:48:42,588 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:48:42,588 INFO L375 BasicCegarLoop]: trace histogram [31, 1, 1, 1] [2018-09-23 19:48:42,588 INFO L423 AbstractCegarLoop]: === Iteration 30 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:48:42,588 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:48:42,588 INFO L82 PathProgramCache]: Analyzing trace with hash 144226374, now seen corresponding path program 29 times [2018-09-23 19:48:42,588 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:48:42,589 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:48:42,589 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:48:42,589 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-23 19:48:42,589 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:48:42,596 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:48:48,962 INFO L134 CoverageAnalysis]: Checked inductivity of 496 backedges. 0 proven. 494 refuted. 2 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:48:48,962 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:48:48,962 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 30 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 30 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:48:48,970 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-09-23 19:48:48,995 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 17 check-sat command(s) [2018-09-23 19:48:48,996 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-23 19:48:48,998 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:48:49,012 INFO L134 CoverageAnalysis]: Checked inductivity of 496 backedges. 0 proven. 494 refuted. 2 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:48:49,033 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:48:49,034 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [33, 33] total 33 [2018-09-23 19:48:49,034 INFO L459 AbstractCegarLoop]: Interpolant automaton has 34 states [2018-09-23 19:48:49,034 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2018-09-23 19:48:49,035 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=65, Invalid=1055, Unknown=2, NotChecked=0, Total=1122 [2018-09-23 19:48:49,035 INFO L87 Difference]: Start difference. First operand 42 states and 48 transitions. Second operand 34 states. [2018-09-23 19:48:59,254 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:48:59,254 INFO L93 Difference]: Finished difference Result 45 states and 51 transitions. [2018-09-23 19:48:59,255 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 34 states. [2018-09-23 19:48:59,255 INFO L78 Accepts]: Start accepts. Automaton has 34 states. Word has length 34 [2018-09-23 19:48:59,255 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:48:59,256 INFO L225 Difference]: With dead ends: 45 [2018-09-23 19:48:59,256 INFO L226 Difference]: Without dead ends: 43 [2018-09-23 19:48:59,257 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 66 GetRequests, 33 SyntacticMatches, 1 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 6.3s TimeCoverageRelationStatistics Valid=65, Invalid=1055, Unknown=2, NotChecked=0, Total=1122 [2018-09-23 19:48:59,257 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2018-09-23 19:48:59,260 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2018-09-23 19:48:59,260 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 43 states. [2018-09-23 19:48:59,260 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 49 transitions. [2018-09-23 19:48:59,261 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 49 transitions. Word has length 34 [2018-09-23 19:48:59,261 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:48:59,261 INFO L480 AbstractCegarLoop]: Abstraction has 43 states and 49 transitions. [2018-09-23 19:48:59,261 INFO L481 AbstractCegarLoop]: Interpolant automaton has 34 states. [2018-09-23 19:48:59,261 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 49 transitions. [2018-09-23 19:48:59,261 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2018-09-23 19:48:59,261 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:48:59,262 INFO L375 BasicCegarLoop]: trace histogram [33, 1, 1, 1] [2018-09-23 19:48:59,262 INFO L423 AbstractCegarLoop]: === Iteration 31 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:48:59,262 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:48:59,262 INFO L82 PathProgramCache]: Analyzing trace with hash 1162468230, now seen corresponding path program 30 times [2018-09-23 19:48:59,262 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:48:59,262 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:48:59,263 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:48:59,263 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-23 19:48:59,263 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:48:59,274 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:49:08,552 INFO L134 CoverageAnalysis]: Checked inductivity of 561 backedges. 0 proven. 560 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:49:08,552 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:49:08,552 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 31 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 31 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:49:08,561 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-09-23 19:49:08,595 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 18 check-sat command(s) [2018-09-23 19:49:08,595 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-23 19:49:08,597 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:49:08,613 INFO L134 CoverageAnalysis]: Checked inductivity of 561 backedges. 0 proven. 560 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:49:08,633 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:49:08,633 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [35, 35] total 35 [2018-09-23 19:49:08,634 INFO L459 AbstractCegarLoop]: Interpolant automaton has 36 states [2018-09-23 19:49:08,634 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2018-09-23 19:49:08,634 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=1188, Unknown=3, NotChecked=0, Total=1260 [2018-09-23 19:49:08,634 INFO L87 Difference]: Start difference. First operand 43 states and 49 transitions. Second operand 36 states. [2018-09-23 19:49:14,570 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:49:14,570 INFO L93 Difference]: Finished difference Result 47 states and 53 transitions. [2018-09-23 19:49:14,571 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2018-09-23 19:49:14,571 INFO L78 Accepts]: Start accepts. Automaton has 36 states. Word has length 36 [2018-09-23 19:49:14,572 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:49:14,572 INFO L225 Difference]: With dead ends: 47 [2018-09-23 19:49:14,572 INFO L226 Difference]: Without dead ends: 45 [2018-09-23 19:49:14,573 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 35 SyntacticMatches, 1 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 9.2s TimeCoverageRelationStatistics Valid=69, Invalid=1188, Unknown=3, NotChecked=0, Total=1260 [2018-09-23 19:49:14,574 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2018-09-23 19:49:14,576 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 45. [2018-09-23 19:49:14,576 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 45 states. [2018-09-23 19:49:14,576 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 51 transitions. [2018-09-23 19:49:14,576 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 51 transitions. Word has length 36 [2018-09-23 19:49:14,576 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:49:14,576 INFO L480 AbstractCegarLoop]: Abstraction has 45 states and 51 transitions. [2018-09-23 19:49:14,576 INFO L481 AbstractCegarLoop]: Interpolant automaton has 36 states. [2018-09-23 19:49:14,577 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 51 transitions. [2018-09-23 19:49:14,577 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2018-09-23 19:49:14,577 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:49:14,577 INFO L375 BasicCegarLoop]: trace histogram [34, 1, 1, 1] [2018-09-23 19:49:14,577 INFO L423 AbstractCegarLoop]: === Iteration 32 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:49:14,578 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:49:14,578 INFO L82 PathProgramCache]: Analyzing trace with hash 1676772896, now seen corresponding path program 31 times [2018-09-23 19:49:14,578 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:49:14,578 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:49:14,579 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:49:14,579 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-23 19:49:14,579 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:49:14,586 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:49:26,157 INFO L134 CoverageAnalysis]: Checked inductivity of 595 backedges. 0 proven. 594 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:49:26,157 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:49:26,157 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 32 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 32 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:49:26,164 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-23 19:49:26,186 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:49:26,188 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:49:26,210 INFO L134 CoverageAnalysis]: Checked inductivity of 595 backedges. 0 proven. 594 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:49:26,231 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:49:26,231 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [36, 36] total 36 [2018-09-23 19:49:26,231 INFO L459 AbstractCegarLoop]: Interpolant automaton has 37 states [2018-09-23 19:49:26,231 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2018-09-23 19:49:26,232 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=1257, Unknown=4, NotChecked=0, Total=1332 [2018-09-23 19:49:26,232 INFO L87 Difference]: Start difference. First operand 45 states and 51 transitions. Second operand 37 states. [2018-09-23 19:49:36,703 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:49:36,703 INFO L93 Difference]: Finished difference Result 48 states and 54 transitions. [2018-09-23 19:49:36,703 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 37 states. [2018-09-23 19:49:36,703 INFO L78 Accepts]: Start accepts. Automaton has 37 states. Word has length 37 [2018-09-23 19:49:36,704 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:49:36,704 INFO L225 Difference]: With dead ends: 48 [2018-09-23 19:49:36,704 INFO L226 Difference]: Without dead ends: 46 [2018-09-23 19:49:36,706 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 36 SyntacticMatches, 1 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 11.5s TimeCoverageRelationStatistics Valid=71, Invalid=1257, Unknown=4, NotChecked=0, Total=1332 [2018-09-23 19:49:36,706 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2018-09-23 19:49:36,710 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 46. [2018-09-23 19:49:36,710 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 46 states. [2018-09-23 19:49:36,710 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 52 transitions. [2018-09-23 19:49:36,711 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 52 transitions. Word has length 37 [2018-09-23 19:49:36,711 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:49:36,711 INFO L480 AbstractCegarLoop]: Abstraction has 46 states and 52 transitions. [2018-09-23 19:49:36,711 INFO L481 AbstractCegarLoop]: Interpolant automaton has 37 states. [2018-09-23 19:49:36,711 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 52 transitions. [2018-09-23 19:49:36,711 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2018-09-23 19:49:36,712 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:49:36,712 INFO L375 BasicCegarLoop]: trace histogram [35, 1, 1, 1] [2018-09-23 19:49:36,712 INFO L423 AbstractCegarLoop]: === Iteration 33 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:49:36,712 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:49:36,712 INFO L82 PathProgramCache]: Analyzing trace with hash 440348358, now seen corresponding path program 32 times [2018-09-23 19:49:36,713 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:49:36,713 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:49:36,713 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:49:36,714 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-23 19:49:36,714 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:49:36,723 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-23 19:49:49,738 INFO L134 CoverageAnalysis]: Checked inductivity of 630 backedges. 0 proven. 625 refuted. 5 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:49:49,738 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-23 19:49:49,739 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 33 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 33 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-23 19:49:49,746 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-09-23 19:49:49,768 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-09-23 19:49:49,769 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-23 19:49:49,771 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-23 19:49:49,783 INFO L134 CoverageAnalysis]: Checked inductivity of 630 backedges. 0 proven. 625 refuted. 5 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-23 19:49:49,803 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-23 19:49:49,803 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [37, 37] total 37 [2018-09-23 19:49:49,804 INFO L459 AbstractCegarLoop]: Interpolant automaton has 38 states [2018-09-23 19:49:49,804 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 38 interpolants. [2018-09-23 19:49:49,804 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=1328, Unknown=5, NotChecked=0, Total=1406 [2018-09-23 19:49:49,804 INFO L87 Difference]: Start difference. First operand 46 states and 52 transitions. Second operand 38 states. [2018-09-23 19:50:05,598 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-23 19:50:05,598 INFO L93 Difference]: Finished difference Result 49 states and 55 transitions. [2018-09-23 19:50:05,599 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 38 states. [2018-09-23 19:50:05,599 INFO L78 Accepts]: Start accepts. Automaton has 38 states. Word has length 38 [2018-09-23 19:50:05,599 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-23 19:50:05,599 INFO L225 Difference]: With dead ends: 49 [2018-09-23 19:50:05,600 INFO L226 Difference]: Without dead ends: 47 [2018-09-23 19:50:05,600 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 37 SyntacticMatches, 1 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 12.9s TimeCoverageRelationStatistics Valid=73, Invalid=1328, Unknown=5, NotChecked=0, Total=1406 [2018-09-23 19:50:05,600 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2018-09-23 19:50:05,603 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2018-09-23 19:50:05,603 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 47 states. [2018-09-23 19:50:05,603 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 53 transitions. [2018-09-23 19:50:05,603 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 53 transitions. Word has length 38 [2018-09-23 19:50:05,603 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-23 19:50:05,604 INFO L480 AbstractCegarLoop]: Abstraction has 47 states and 53 transitions. [2018-09-23 19:50:05,604 INFO L481 AbstractCegarLoop]: Interpolant automaton has 38 states. [2018-09-23 19:50:05,604 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 53 transitions. [2018-09-23 19:50:05,604 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2018-09-23 19:50:05,604 INFO L367 BasicCegarLoop]: Found error trace [2018-09-23 19:50:05,604 INFO L375 BasicCegarLoop]: trace histogram [36, 1, 1, 1] [2018-09-23 19:50:05,604 INFO L423 AbstractCegarLoop]: === Iteration 34 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-23 19:50:05,605 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-23 19:50:05,605 INFO L82 PathProgramCache]: Analyzing trace with hash 765893344, now seen corresponding path program 33 times [2018-09-23 19:50:05,605 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-23 19:50:05,605 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-23 19:50:05,605 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:50:05,605 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-23 19:50:05,606 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-23 19:50:05,613 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat Received shutdown request... [2018-09-23 19:50:24,627 WARN L549 AbstractCegarLoop]: Verification canceled [2018-09-23 19:50:24,631 WARN L206 ceAbstractionStarter]: Timeout [2018-09-23 19:50:24,631 INFO L202 PluginConnector]: Adding new model AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 23.09 07:50:24 BoogieIcfgContainer [2018-09-23 19:50:24,631 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-09-23 19:50:24,632 INFO L168 Benchmark]: Toolchain (without parser) took 281520.88 ms. Allocated memory was 1.5 GB in the beginning and 1.7 GB in the end (delta: 141.0 MB). Free memory was 1.5 GB in the beginning and 948.8 MB in the end (delta: 520.0 MB). Peak memory consumption was 661.1 MB. Max. memory is 7.1 GB. [2018-09-23 19:50:24,634 INFO L168 Benchmark]: Boogie PL CUP Parser took 0.19 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-09-23 19:50:24,634 INFO L168 Benchmark]: Boogie Procedure Inliner took 39.48 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-09-23 19:50:24,635 INFO L168 Benchmark]: Boogie Preprocessor took 21.00 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-09-23 19:50:24,635 INFO L168 Benchmark]: RCFGBuilder took 300.74 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-09-23 19:50:24,636 INFO L168 Benchmark]: TraceAbstraction took 281153.77 ms. Allocated memory was 1.5 GB in the beginning and 1.7 GB in the end (delta: 141.0 MB). Free memory was 1.4 GB in the beginning and 948.8 MB in the end (delta: 498.9 MB). Peak memory consumption was 639.9 MB. Max. memory is 7.1 GB. [2018-09-23 19:50:24,639 INFO L336 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * Boogie PL CUP Parser took 0.19 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. * Boogie Procedure Inliner took 39.48 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 21.00 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 300.74 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 281153.77 ms. Allocated memory was 1.5 GB in the beginning and 1.7 GB in the end (delta: 141.0 MB). Free memory was 1.4 GB in the beginning and 948.8 MB in the end (delta: 498.9 MB). Peak memory consumption was 639.9 MB. Max. memory is 7.1 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 24]: Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 24). Cancelled while BasicCegarLoop was analyzing trace of length 40 with TraceHistMax 36, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateComparison was comparing new predicate (quantifier-free) to 38 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 1 procedures, 6 locations, 1 error locations. TIMEOUT Result, 281.0s OverallTime, 34 OverallIterations, 36 TraceHistogramMax, 134.6s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 107 SDtfs, 55 SDslu, 609 SDs, 0 SdLazy, 15546 SolverSat, 40 SolverUnsat, 53 SolverUnknown, 0 SolverNotchecked, 130.7s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1261 GetRequests, 615 SyntacticMatches, 31 SemanticMatches, 615 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 120 ImplicationChecksByTransitivity, 123.8s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=47occurred in iteration=33, 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.1s AutomataMinimizationTime, 33 MinimizatonAttempts, 13 StatesRemovedByMinimization, 1 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.9s SatisfiabilityAnalysisTime, 124.8s InterpolantComputationTime, 1311 NumberOfCodeBlocks, 1311 NumberOfCodeBlocksAsserted, 213 NumberOfCheckSat, 1246 ConstructedInterpolants, 0 QuantifiedInterpolants, 321400 SizeOfPredicates, 31 NumberOfNonLiveVariables, 2520 ConjunctsInSsa, 1180 ConjunctsInUnsatCore, 65 InterpolantComputations, 1 PerfectInterpolantSequences, 1/13612 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/AnnoyingVillain.bpl_svcomp-Reach-32bit-Automizer_Default.epf_AutomizerBplInline.xml/Csv-Benchmark-0-2018-09-23_19-50-24-649.csv Written .csv to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/csv/AnnoyingVillain.bpl_svcomp-Reach-32bit-Automizer_Default.epf_AutomizerBplInline.xml/Csv-TraceAbstractionBenchmarks-0-2018-09-23_19-50-24-649.csv Completed graceful shutdown