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 -tc ../../../trunk/examples/toolchains/AutomizerCInline.xml -s ../../../trunk/examples/settings/default/automizer/svcomp-Reach-64bit-Automizer_Default.epf -i ../../../trunk/examples/svcomp/eca-rers2012/Problem11_label45_true-unreach-call.c -------------------------------------------------------------------------------- This is Ultimate 0.1.23-df4b876 [2018-11-06 21:05:04,092 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-11-06 21:05:04,094 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-11-06 21:05:04,110 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-11-06 21:05:04,111 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-11-06 21:05:04,112 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-11-06 21:05:04,114 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-11-06 21:05:04,116 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-11-06 21:05:04,119 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-11-06 21:05:04,120 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-11-06 21:05:04,129 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-11-06 21:05:04,129 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-11-06 21:05:04,130 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-11-06 21:05:04,131 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-11-06 21:05:04,134 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-11-06 21:05:04,134 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-11-06 21:05:04,135 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-11-06 21:05:04,138 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-11-06 21:05:04,140 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-11-06 21:05:04,141 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-11-06 21:05:04,142 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-11-06 21:05:04,144 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-11-06 21:05:04,148 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-11-06 21:05:04,148 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-11-06 21:05:04,148 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-11-06 21:05:04,150 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-11-06 21:05:04,151 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-11-06 21:05:04,151 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-11-06 21:05:04,154 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-11-06 21:05:04,157 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-11-06 21:05:04,157 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-11-06 21:05:04,159 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-11-06 21:05:04,159 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-11-06 21:05:04,159 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-11-06 21:05:04,160 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-11-06 21:05:04,161 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-11-06 21:05:04,162 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/automizer/svcomp-Reach-64bit-Automizer_Default.epf [2018-11-06 21:05:04,183 INFO L110 SettingsManager]: Loading preferences was successful [2018-11-06 21:05:04,184 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-11-06 21:05:04,184 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-11-06 21:05:04,185 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-11-06 21:05:04,186 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-11-06 21:05:04,186 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-11-06 21:05:04,186 INFO L133 SettingsManager]: * Use SBE=true [2018-11-06 21:05:04,188 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-11-06 21:05:04,188 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-11-06 21:05:04,188 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-11-06 21:05:04,188 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-11-06 21:05:04,188 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-11-06 21:05:04,189 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-11-06 21:05:04,189 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-11-06 21:05:04,189 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-11-06 21:05:04,189 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-11-06 21:05:04,189 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-11-06 21:05:04,189 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-11-06 21:05:04,191 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-11-06 21:05:04,191 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-11-06 21:05:04,191 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-11-06 21:05:04,191 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-11-06 21:05:04,191 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-11-06 21:05:04,192 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-11-06 21:05:04,192 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-11-06 21:05:04,192 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-11-06 21:05:04,192 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-11-06 21:05:04,193 INFO L133 SettingsManager]: * To the following directory=dump/ [2018-11-06 21:05:04,238 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-11-06 21:05:04,253 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-11-06 21:05:04,256 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-11-06 21:05:04,258 INFO L271 PluginConnector]: Initializing CDTParser... [2018-11-06 21:05:04,258 INFO L276 PluginConnector]: CDTParser initialized [2018-11-06 21:05:04,259 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/eca-rers2012/Problem11_label45_true-unreach-call.c [2018-11-06 21:05:04,315 INFO L218 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/654f81f27/12d5397bca9345479cdaa12b38ff3406/FLAG906be2b33 [2018-11-06 21:05:04,964 INFO L298 CDTParser]: Found 1 translation units. [2018-11-06 21:05:04,965 INFO L158 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/eca-rers2012/Problem11_label45_true-unreach-call.c [2018-11-06 21:05:04,985 INFO L346 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/654f81f27/12d5397bca9345479cdaa12b38ff3406/FLAG906be2b33 [2018-11-06 21:05:05,007 INFO L354 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/654f81f27/12d5397bca9345479cdaa12b38ff3406 [2018-11-06 21:05:05,019 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-11-06 21:05:05,021 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2018-11-06 21:05:05,022 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-11-06 21:05:05,023 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-11-06 21:05:05,027 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-11-06 21:05:05,028 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.11 09:05:05" (1/1) ... [2018-11-06 21:05:05,032 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5a6bed07 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 09:05:05, skipping insertion in model container [2018-11-06 21:05:05,032 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.11 09:05:05" (1/1) ... [2018-11-06 21:05:05,043 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2018-11-06 21:05:05,137 INFO L174 MainTranslator]: Built tables and reachable declarations [2018-11-06 21:05:05,836 INFO L202 PostProcessor]: Analyzing one entry point: main [2018-11-06 21:05:05,841 INFO L189 MainTranslator]: Completed pre-run [2018-11-06 21:05:06,022 INFO L202 PostProcessor]: Analyzing one entry point: main [2018-11-06 21:05:06,043 INFO L193 MainTranslator]: Completed translation [2018-11-06 21:05:06,044 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 09:05:06 WrapperNode [2018-11-06 21:05:06,044 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-11-06 21:05:06,045 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2018-11-06 21:05:06,045 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2018-11-06 21:05:06,045 INFO L276 PluginConnector]: Boogie Procedure Inliner initialized [2018-11-06 21:05:06,057 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 09:05:06" (1/1) ... [2018-11-06 21:05:06,198 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 09:05:06" (1/1) ... [2018-11-06 21:05:06,304 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2018-11-06 21:05:06,304 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-11-06 21:05:06,305 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-11-06 21:05:06,305 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-11-06 21:05:06,317 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 09:05:06" (1/1) ... [2018-11-06 21:05:06,317 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 09:05:06" (1/1) ... [2018-11-06 21:05:06,329 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 09:05:06" (1/1) ... [2018-11-06 21:05:06,329 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 09:05:06" (1/1) ... [2018-11-06 21:05:06,379 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 09:05:06" (1/1) ... [2018-11-06 21:05:06,405 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 09:05:06" (1/1) ... [2018-11-06 21:05:06,416 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 09:05:06" (1/1) ... [2018-11-06 21:05:06,426 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-11-06 21:05:06,427 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-11-06 21:05:06,427 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-11-06 21:05:06,427 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-11-06 21:05:06,428 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 09:05:06" (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-11-06 21:05:06,492 INFO L130 BoogieDeclarations]: Found specification of procedure exit [2018-11-06 21:05:06,493 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-11-06 21:05:06,493 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-11-06 21:05:11,016 INFO L276 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-11-06 21:05:11,017 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.11 09:05:11 BoogieIcfgContainer [2018-11-06 21:05:11,017 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-11-06 21:05:11,019 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-11-06 21:05:11,019 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-11-06 21:05:11,022 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-11-06 21:05:11,023 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.11 09:05:05" (1/3) ... [2018-11-06 21:05:11,024 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@474a2de4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.11 09:05:11, skipping insertion in model container [2018-11-06 21:05:11,024 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 09:05:06" (2/3) ... [2018-11-06 21:05:11,024 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@474a2de4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.11 09:05:11, skipping insertion in model container [2018-11-06 21:05:11,024 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.11 09:05:11" (3/3) ... [2018-11-06 21:05:11,026 INFO L112 eAbstractionObserver]: Analyzing ICFG Problem11_label45_true-unreach-call.c [2018-11-06 21:05:11,038 INFO L136 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-11-06 21:05:11,051 INFO L148 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-11-06 21:05:11,070 INFO L257 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2018-11-06 21:05:11,112 INFO L135 ementStrategyFactory]: Using default assertion order modulation [2018-11-06 21:05:11,113 INFO L382 AbstractCegarLoop]: Interprodecural is true [2018-11-06 21:05:11,113 INFO L383 AbstractCegarLoop]: Hoare is true [2018-11-06 21:05:11,114 INFO L384 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-11-06 21:05:11,114 INFO L385 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-11-06 21:05:11,114 INFO L386 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-11-06 21:05:11,114 INFO L387 AbstractCegarLoop]: Difference is false [2018-11-06 21:05:11,115 INFO L388 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-11-06 21:05:11,115 INFO L393 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-11-06 21:05:11,141 INFO L276 IsEmpty]: Start isEmpty. Operand 284 states. [2018-11-06 21:05:11,149 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2018-11-06 21:05:11,150 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 21:05:11,151 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 21:05:11,153 INFO L423 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 21:05:11,159 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 21:05:11,160 INFO L82 PathProgramCache]: Analyzing trace with hash 575043410, now seen corresponding path program 1 times [2018-11-06 21:05:11,162 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 21:05:11,163 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 21:05:11,222 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:05:11,222 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:05:11,222 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:05:11,291 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:05:11,608 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-06 21:05:11,611 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-06 21:05:11,612 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-11-06 21:05:11,617 INFO L459 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-11-06 21:05:11,632 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-11-06 21:05:11,633 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-11-06 21:05:11,636 INFO L87 Difference]: Start difference. First operand 284 states. Second operand 4 states. [2018-11-06 21:05:14,966 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 21:05:14,967 INFO L93 Difference]: Finished difference Result 972 states and 1744 transitions. [2018-11-06 21:05:14,968 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-11-06 21:05:14,970 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 33 [2018-11-06 21:05:14,970 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 21:05:14,994 INFO L225 Difference]: With dead ends: 972 [2018-11-06 21:05:14,994 INFO L226 Difference]: Without dead ends: 681 [2018-11-06 21:05:15,000 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-11-06 21:05:15,020 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 681 states. [2018-11-06 21:05:15,078 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 681 to 469. [2018-11-06 21:05:15,080 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 469 states. [2018-11-06 21:05:15,082 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 469 states to 469 states and 728 transitions. [2018-11-06 21:05:15,084 INFO L78 Accepts]: Start accepts. Automaton has 469 states and 728 transitions. Word has length 33 [2018-11-06 21:05:15,084 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 21:05:15,084 INFO L480 AbstractCegarLoop]: Abstraction has 469 states and 728 transitions. [2018-11-06 21:05:15,085 INFO L481 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-11-06 21:05:15,085 INFO L276 IsEmpty]: Start isEmpty. Operand 469 states and 728 transitions. [2018-11-06 21:05:15,088 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 103 [2018-11-06 21:05:15,089 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 21:05:15,089 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 21:05:15,089 INFO L423 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 21:05:15,090 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 21:05:15,090 INFO L82 PathProgramCache]: Analyzing trace with hash -294278150, now seen corresponding path program 1 times [2018-11-06 21:05:15,090 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 21:05:15,090 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 21:05:15,091 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:05:15,091 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:05:15,092 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:05:15,168 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:05:15,379 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 30 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-06 21:05:15,379 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-06 21:05:15,380 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-11-06 21:05:15,386 INFO L459 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-11-06 21:05:15,387 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-11-06 21:05:15,387 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-11-06 21:05:15,387 INFO L87 Difference]: Start difference. First operand 469 states and 728 transitions. Second operand 4 states. [2018-11-06 21:05:18,786 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 21:05:18,787 INFO L93 Difference]: Finished difference Result 1695 states and 2717 transitions. [2018-11-06 21:05:18,787 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-11-06 21:05:18,788 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 102 [2018-11-06 21:05:18,789 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 21:05:18,796 INFO L225 Difference]: With dead ends: 1695 [2018-11-06 21:05:18,796 INFO L226 Difference]: Without dead ends: 1228 [2018-11-06 21:05:18,799 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-11-06 21:05:18,800 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1228 states. [2018-11-06 21:05:18,847 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1228 to 1214. [2018-11-06 21:05:18,848 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1214 states. [2018-11-06 21:05:18,853 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1214 states to 1214 states and 1784 transitions. [2018-11-06 21:05:18,853 INFO L78 Accepts]: Start accepts. Automaton has 1214 states and 1784 transitions. Word has length 102 [2018-11-06 21:05:18,854 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 21:05:18,854 INFO L480 AbstractCegarLoop]: Abstraction has 1214 states and 1784 transitions. [2018-11-06 21:05:18,854 INFO L481 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-11-06 21:05:18,854 INFO L276 IsEmpty]: Start isEmpty. Operand 1214 states and 1784 transitions. [2018-11-06 21:05:18,863 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 106 [2018-11-06 21:05:18,863 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 21:05:18,863 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 21:05:18,864 INFO L423 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 21:05:18,865 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 21:05:18,865 INFO L82 PathProgramCache]: Analyzing trace with hash -263297828, now seen corresponding path program 1 times [2018-11-06 21:05:18,865 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 21:05:18,865 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 21:05:18,866 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:05:18,866 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:05:18,866 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:05:18,906 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:05:19,198 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 30 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-06 21:05:19,199 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-06 21:05:19,199 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-11-06 21:05:19,199 INFO L459 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-11-06 21:05:19,199 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-11-06 21:05:19,200 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-11-06 21:05:19,200 INFO L87 Difference]: Start difference. First operand 1214 states and 1784 transitions. Second operand 4 states. [2018-11-06 21:05:23,401 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 21:05:23,401 INFO L93 Difference]: Finished difference Result 4657 states and 6912 transitions. [2018-11-06 21:05:23,410 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-11-06 21:05:23,410 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 105 [2018-11-06 21:05:23,410 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 21:05:23,426 INFO L225 Difference]: With dead ends: 4657 [2018-11-06 21:05:23,426 INFO L226 Difference]: Without dead ends: 3445 [2018-11-06 21:05:23,429 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-11-06 21:05:23,431 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3445 states. [2018-11-06 21:05:23,485 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3445 to 3445. [2018-11-06 21:05:23,485 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3445 states. [2018-11-06 21:05:23,492 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3445 states to 3445 states and 4375 transitions. [2018-11-06 21:05:23,492 INFO L78 Accepts]: Start accepts. Automaton has 3445 states and 4375 transitions. Word has length 105 [2018-11-06 21:05:23,493 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 21:05:23,493 INFO L480 AbstractCegarLoop]: Abstraction has 3445 states and 4375 transitions. [2018-11-06 21:05:23,493 INFO L481 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-11-06 21:05:23,493 INFO L276 IsEmpty]: Start isEmpty. Operand 3445 states and 4375 transitions. [2018-11-06 21:05:23,497 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 162 [2018-11-06 21:05:23,497 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 21:05:23,497 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 21:05:23,497 INFO L423 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 21:05:23,498 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 21:05:23,498 INFO L82 PathProgramCache]: Analyzing trace with hash 316350140, now seen corresponding path program 1 times [2018-11-06 21:05:23,498 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 21:05:23,498 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 21:05:23,499 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:05:23,499 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:05:23,499 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:05:23,545 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:05:23,813 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 30 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-06 21:05:23,813 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-06 21:05:23,813 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-11-06 21:05:23,814 INFO L459 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-11-06 21:05:23,814 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-11-06 21:05:23,814 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2018-11-06 21:05:23,815 INFO L87 Difference]: Start difference. First operand 3445 states and 4375 transitions. Second operand 5 states. [2018-11-06 21:05:28,958 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 21:05:28,958 INFO L93 Difference]: Finished difference Result 10825 states and 14157 transitions. [2018-11-06 21:05:28,959 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-11-06 21:05:28,959 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 161 [2018-11-06 21:05:28,959 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 21:05:28,991 INFO L225 Difference]: With dead ends: 10825 [2018-11-06 21:05:28,992 INFO L226 Difference]: Without dead ends: 7567 [2018-11-06 21:05:28,996 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2018-11-06 21:05:29,001 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 7567 states. [2018-11-06 21:05:29,113 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 7567 to 7566. [2018-11-06 21:05:29,113 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 7566 states. [2018-11-06 21:05:29,128 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7566 states to 7566 states and 9466 transitions. [2018-11-06 21:05:29,129 INFO L78 Accepts]: Start accepts. Automaton has 7566 states and 9466 transitions. Word has length 161 [2018-11-06 21:05:29,129 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 21:05:29,130 INFO L480 AbstractCegarLoop]: Abstraction has 7566 states and 9466 transitions. [2018-11-06 21:05:29,130 INFO L481 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-11-06 21:05:29,130 INFO L276 IsEmpty]: Start isEmpty. Operand 7566 states and 9466 transitions. [2018-11-06 21:05:29,136 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 229 [2018-11-06 21:05:29,137 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 21:05:29,138 INFO L375 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 21:05:29,138 INFO L423 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 21:05:29,138 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 21:05:29,139 INFO L82 PathProgramCache]: Analyzing trace with hash -2090882901, now seen corresponding path program 1 times [2018-11-06 21:05:29,139 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 21:05:29,139 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 21:05:29,140 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:05:29,140 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:05:29,140 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:05:29,184 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:05:29,579 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 61 proven. 0 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2018-11-06 21:05:29,579 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-06 21:05:29,579 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-11-06 21:05:29,580 INFO L459 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-11-06 21:05:29,580 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-11-06 21:05:29,580 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-11-06 21:05:29,581 INFO L87 Difference]: Start difference. First operand 7566 states and 9466 transitions. Second operand 4 states. [2018-11-06 21:05:31,722 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 21:05:31,722 INFO L93 Difference]: Finished difference Result 14971 states and 18789 transitions. [2018-11-06 21:05:31,723 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-11-06 21:05:31,723 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 228 [2018-11-06 21:05:31,723 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 21:05:31,747 INFO L225 Difference]: With dead ends: 14971 [2018-11-06 21:05:31,747 INFO L226 Difference]: Without dead ends: 7592 [2018-11-06 21:05:31,757 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-11-06 21:05:31,763 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 7592 states. [2018-11-06 21:05:31,872 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 7592 to 7565. [2018-11-06 21:05:31,873 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 7565 states. [2018-11-06 21:05:31,887 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7565 states to 7565 states and 8984 transitions. [2018-11-06 21:05:31,887 INFO L78 Accepts]: Start accepts. Automaton has 7565 states and 8984 transitions. Word has length 228 [2018-11-06 21:05:31,888 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 21:05:31,888 INFO L480 AbstractCegarLoop]: Abstraction has 7565 states and 8984 transitions. [2018-11-06 21:05:31,888 INFO L481 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-11-06 21:05:31,888 INFO L276 IsEmpty]: Start isEmpty. Operand 7565 states and 8984 transitions. [2018-11-06 21:05:31,893 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 230 [2018-11-06 21:05:31,893 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 21:05:31,893 INFO L375 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 21:05:31,894 INFO L423 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 21:05:31,894 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 21:05:31,894 INFO L82 PathProgramCache]: Analyzing trace with hash -506625732, now seen corresponding path program 1 times [2018-11-06 21:05:31,894 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 21:05:31,894 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 21:05:31,895 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:05:31,895 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:05:31,896 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:05:31,933 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:05:32,330 INFO L134 CoverageAnalysis]: Checked inductivity of 128 backedges. 128 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-06 21:05:32,330 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-06 21:05:32,330 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-11-06 21:05:32,331 INFO L459 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-11-06 21:05:32,331 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-11-06 21:05:32,331 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-11-06 21:05:32,332 INFO L87 Difference]: Start difference. First operand 7565 states and 8984 transitions. Second operand 4 states. [2018-11-06 21:05:34,305 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 21:05:34,305 INFO L93 Difference]: Finished difference Result 19035 states and 23078 transitions. [2018-11-06 21:05:34,305 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-11-06 21:05:34,306 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 229 [2018-11-06 21:05:34,306 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 21:05:34,361 INFO L225 Difference]: With dead ends: 19035 [2018-11-06 21:05:34,361 INFO L226 Difference]: Without dead ends: 11657 [2018-11-06 21:05:34,370 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-11-06 21:05:34,381 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 11657 states. [2018-11-06 21:05:34,555 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 11657 to 11080. [2018-11-06 21:05:34,555 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 11080 states. [2018-11-06 21:05:34,575 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11080 states to 11080 states and 13221 transitions. [2018-11-06 21:05:34,575 INFO L78 Accepts]: Start accepts. Automaton has 11080 states and 13221 transitions. Word has length 229 [2018-11-06 21:05:34,576 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 21:05:34,576 INFO L480 AbstractCegarLoop]: Abstraction has 11080 states and 13221 transitions. [2018-11-06 21:05:34,576 INFO L481 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-11-06 21:05:34,576 INFO L276 IsEmpty]: Start isEmpty. Operand 11080 states and 13221 transitions. [2018-11-06 21:05:34,588 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 286 [2018-11-06 21:05:34,588 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 21:05:34,589 INFO L375 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 21:05:34,589 INFO L423 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 21:05:34,589 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 21:05:34,589 INFO L82 PathProgramCache]: Analyzing trace with hash -1732908421, now seen corresponding path program 1 times [2018-11-06 21:05:34,590 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 21:05:34,590 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 21:05:34,591 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:05:34,591 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:05:34,591 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:05:34,752 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:05:34,982 INFO L134 CoverageAnalysis]: Checked inductivity of 297 backedges. 227 proven. 0 refuted. 0 times theorem prover too weak. 70 trivial. 0 not checked. [2018-11-06 21:05:34,982 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-06 21:05:34,982 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-11-06 21:05:34,983 INFO L459 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-11-06 21:05:34,983 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-11-06 21:05:34,983 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-11-06 21:05:34,984 INFO L87 Difference]: Start difference. First operand 11080 states and 13221 transitions. Second operand 3 states. [2018-11-06 21:05:36,665 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 21:05:36,665 INFO L93 Difference]: Finished difference Result 25300 states and 30301 transitions. [2018-11-06 21:05:36,666 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-11-06 21:05:36,666 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 285 [2018-11-06 21:05:36,666 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 21:05:36,690 INFO L225 Difference]: With dead ends: 25300 [2018-11-06 21:05:36,690 INFO L226 Difference]: Without dead ends: 13654 [2018-11-06 21:05:36,700 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-11-06 21:05:36,711 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 13654 states. [2018-11-06 21:05:36,842 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 13654 to 13282. [2018-11-06 21:05:36,843 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 13282 states. [2018-11-06 21:05:36,859 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13282 states to 13282 states and 15179 transitions. [2018-11-06 21:05:36,860 INFO L78 Accepts]: Start accepts. Automaton has 13282 states and 15179 transitions. Word has length 285 [2018-11-06 21:05:36,860 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 21:05:36,861 INFO L480 AbstractCegarLoop]: Abstraction has 13282 states and 15179 transitions. [2018-11-06 21:05:36,861 INFO L481 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-11-06 21:05:36,861 INFO L276 IsEmpty]: Start isEmpty. Operand 13282 states and 15179 transitions. [2018-11-06 21:05:36,874 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 329 [2018-11-06 21:05:36,874 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 21:05:36,875 INFO L375 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 21:05:36,875 INFO L423 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 21:05:36,875 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 21:05:36,875 INFO L82 PathProgramCache]: Analyzing trace with hash -1591903917, now seen corresponding path program 1 times [2018-11-06 21:05:36,875 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 21:05:36,876 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 21:05:36,876 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:05:36,877 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:05:36,877 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:05:36,938 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:05:37,242 INFO L134 CoverageAnalysis]: Checked inductivity of 333 backedges. 258 proven. 0 refuted. 0 times theorem prover too weak. 75 trivial. 0 not checked. [2018-11-06 21:05:37,243 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-06 21:05:37,243 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-11-06 21:05:37,244 INFO L459 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-11-06 21:05:37,244 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-11-06 21:05:37,244 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-11-06 21:05:37,244 INFO L87 Difference]: Start difference. First operand 13282 states and 15179 transitions. Second operand 3 states. [2018-11-06 21:05:38,627 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 21:05:38,627 INFO L93 Difference]: Finished difference Result 27314 states and 31303 transitions. [2018-11-06 21:05:38,628 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-11-06 21:05:38,628 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 328 [2018-11-06 21:05:38,629 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 21:05:38,656 INFO L225 Difference]: With dead ends: 27314 [2018-11-06 21:05:38,656 INFO L226 Difference]: Without dead ends: 12720 [2018-11-06 21:05:38,670 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-11-06 21:05:38,682 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 12720 states. [2018-11-06 21:05:38,808 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 12720 to 12345. [2018-11-06 21:05:38,809 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 12345 states. [2018-11-06 21:05:38,825 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 12345 states to 12345 states and 13968 transitions. [2018-11-06 21:05:38,825 INFO L78 Accepts]: Start accepts. Automaton has 12345 states and 13968 transitions. Word has length 328 [2018-11-06 21:05:38,826 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 21:05:38,826 INFO L480 AbstractCegarLoop]: Abstraction has 12345 states and 13968 transitions. [2018-11-06 21:05:38,826 INFO L481 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-11-06 21:05:38,826 INFO L276 IsEmpty]: Start isEmpty. Operand 12345 states and 13968 transitions. [2018-11-06 21:05:38,839 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 334 [2018-11-06 21:05:38,840 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 21:05:38,840 INFO L375 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 21:05:38,841 INFO L423 AbstractCegarLoop]: === Iteration 9 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 21:05:38,841 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 21:05:38,841 INFO L82 PathProgramCache]: Analyzing trace with hash 326232789, now seen corresponding path program 1 times [2018-11-06 21:05:38,841 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 21:05:38,841 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 21:05:38,842 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:05:38,842 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:05:38,842 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:05:38,902 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:05:39,602 INFO L134 CoverageAnalysis]: Checked inductivity of 186 backedges. 0 proven. 186 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-06 21:05:39,603 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-06 21:05:39,603 INFO L225 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-11-06 21:05:39,614 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:05:39,742 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:05:39,771 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-06 21:05:40,463 INFO L134 CoverageAnalysis]: Checked inductivity of 186 backedges. 61 proven. 125 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-06 21:05:40,501 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-11-06 21:05:40,502 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2018-11-06 21:05:40,503 INFO L459 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-11-06 21:05:40,505 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-11-06 21:05:40,506 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2018-11-06 21:05:40,506 INFO L87 Difference]: Start difference. First operand 12345 states and 13968 transitions. Second operand 9 states. [2018-11-06 21:05:47,699 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 21:05:47,699 INFO L93 Difference]: Finished difference Result 38270 states and 43536 transitions. [2018-11-06 21:05:47,699 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-11-06 21:05:47,700 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 333 [2018-11-06 21:05:47,701 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 21:05:47,757 INFO L225 Difference]: With dead ends: 38270 [2018-11-06 21:05:47,757 INFO L226 Difference]: Without dead ends: 27043 [2018-11-06 21:05:47,773 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 338 GetRequests, 329 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2018-11-06 21:05:47,792 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27043 states. [2018-11-06 21:05:48,190 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27043 to 21838. [2018-11-06 21:05:48,190 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 21838 states. [2018-11-06 21:05:48,453 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21838 states to 21838 states and 24508 transitions. [2018-11-06 21:05:48,454 INFO L78 Accepts]: Start accepts. Automaton has 21838 states and 24508 transitions. Word has length 333 [2018-11-06 21:05:48,454 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 21:05:48,454 INFO L480 AbstractCegarLoop]: Abstraction has 21838 states and 24508 transitions. [2018-11-06 21:05:48,454 INFO L481 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-11-06 21:05:48,455 INFO L276 IsEmpty]: Start isEmpty. Operand 21838 states and 24508 transitions. [2018-11-06 21:05:48,470 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 342 [2018-11-06 21:05:48,470 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 21:05:48,470 INFO L375 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 21:05:48,471 INFO L423 AbstractCegarLoop]: === Iteration 10 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 21:05:48,471 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 21:05:48,471 INFO L82 PathProgramCache]: Analyzing trace with hash -249180895, now seen corresponding path program 1 times [2018-11-06 21:05:48,471 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 21:05:48,471 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 21:05:48,472 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:05:48,473 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:05:48,473 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:05:48,539 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:05:49,067 INFO L134 CoverageAnalysis]: Checked inductivity of 359 backedges. 328 proven. 0 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2018-11-06 21:05:49,067 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-06 21:05:49,067 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-11-06 21:05:49,068 INFO L459 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-11-06 21:05:49,068 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-11-06 21:05:49,069 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2018-11-06 21:05:49,069 INFO L87 Difference]: Start difference. First operand 21838 states and 24508 transitions. Second operand 5 states. [2018-11-06 21:05:51,955 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 21:05:51,955 INFO L93 Difference]: Finished difference Result 55730 states and 62701 transitions. [2018-11-06 21:05:51,955 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-11-06 21:05:51,955 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 341 [2018-11-06 21:05:51,956 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 21:05:52,015 INFO L225 Difference]: With dead ends: 55730 [2018-11-06 21:05:52,015 INFO L226 Difference]: Without dead ends: 34079 [2018-11-06 21:05:52,036 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2018-11-06 21:05:52,060 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34079 states. [2018-11-06 21:05:52,397 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34079 to 31658. [2018-11-06 21:05:52,397 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 31658 states. [2018-11-06 21:05:52,439 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31658 states to 31658 states and 34860 transitions. [2018-11-06 21:05:52,439 INFO L78 Accepts]: Start accepts. Automaton has 31658 states and 34860 transitions. Word has length 341 [2018-11-06 21:05:52,440 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 21:05:52,440 INFO L480 AbstractCegarLoop]: Abstraction has 31658 states and 34860 transitions. [2018-11-06 21:05:52,440 INFO L481 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-11-06 21:05:52,440 INFO L276 IsEmpty]: Start isEmpty. Operand 31658 states and 34860 transitions. [2018-11-06 21:05:52,458 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 345 [2018-11-06 21:05:52,458 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 21:05:52,458 INFO L375 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 21:05:52,459 INFO L423 AbstractCegarLoop]: === Iteration 11 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 21:05:52,459 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 21:05:52,459 INFO L82 PathProgramCache]: Analyzing trace with hash -1530952089, now seen corresponding path program 1 times [2018-11-06 21:05:52,459 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 21:05:52,459 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 21:05:52,460 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:05:52,460 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:05:52,460 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:05:52,512 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:05:53,276 WARN L179 SmtUtils]: Spent 312.00 ms on a formula simplification. DAG size of input: 16 DAG size of output: 11 [2018-11-06 21:05:53,768 WARN L179 SmtUtils]: Spent 388.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 12 [2018-11-06 21:05:53,947 INFO L134 CoverageAnalysis]: Checked inductivity of 379 backedges. 242 proven. 106 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2018-11-06 21:05:53,947 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-06 21:05:53,948 INFO L225 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-11-06 21:05:53,956 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:05:54,045 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:05:54,053 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-06 21:05:54,716 INFO L134 CoverageAnalysis]: Checked inductivity of 379 backedges. 0 proven. 273 refuted. 0 times theorem prover too weak. 106 trivial. 0 not checked. [2018-11-06 21:05:54,736 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-11-06 21:05:54,737 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4] total 8 [2018-11-06 21:05:54,737 INFO L459 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-11-06 21:05:54,738 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-11-06 21:05:54,738 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-11-06 21:05:54,738 INFO L87 Difference]: Start difference. First operand 31658 states and 34860 transitions. Second operand 9 states. [2018-11-06 21:06:05,317 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 21:06:05,317 INFO L93 Difference]: Finished difference Result 72412 states and 79503 transitions. [2018-11-06 21:06:05,317 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-11-06 21:06:05,318 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 344 [2018-11-06 21:06:05,318 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 21:06:05,373 INFO L225 Difference]: With dead ends: 72412 [2018-11-06 21:06:05,374 INFO L226 Difference]: Without dead ends: 34221 [2018-11-06 21:06:05,406 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 361 GetRequests, 341 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 80 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=108, Invalid=354, Unknown=0, NotChecked=0, Total=462 [2018-11-06 21:06:05,432 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34221 states. [2018-11-06 21:06:06,078 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34221 to 32179. [2018-11-06 21:06:06,078 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 32179 states. [2018-11-06 21:06:06,124 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32179 states to 32179 states and 35100 transitions. [2018-11-06 21:06:06,125 INFO L78 Accepts]: Start accepts. Automaton has 32179 states and 35100 transitions. Word has length 344 [2018-11-06 21:06:06,125 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 21:06:06,125 INFO L480 AbstractCegarLoop]: Abstraction has 32179 states and 35100 transitions. [2018-11-06 21:06:06,125 INFO L481 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-11-06 21:06:06,126 INFO L276 IsEmpty]: Start isEmpty. Operand 32179 states and 35100 transitions. [2018-11-06 21:06:06,142 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 360 [2018-11-06 21:06:06,142 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 21:06:06,143 INFO L375 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 21:06:06,143 INFO L423 AbstractCegarLoop]: === Iteration 12 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 21:06:06,144 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 21:06:06,144 INFO L82 PathProgramCache]: Analyzing trace with hash 1571378605, now seen corresponding path program 1 times [2018-11-06 21:06:06,144 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 21:06:06,144 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 21:06:06,146 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:06:06,146 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:06:06,146 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:06:06,190 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:06:06,644 WARN L179 SmtUtils]: Spent 193.00 ms on a formula simplification. DAG size of input: 11 DAG size of output: 8 [2018-11-06 21:06:06,760 INFO L134 CoverageAnalysis]: Checked inductivity of 379 backedges. 348 proven. 0 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2018-11-06 21:06:06,761 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-06 21:06:06,761 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-11-06 21:06:06,762 INFO L459 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-11-06 21:06:06,762 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-11-06 21:06:06,762 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-11-06 21:06:06,763 INFO L87 Difference]: Start difference. First operand 32179 states and 35100 transitions. Second operand 4 states. [2018-11-06 21:06:08,296 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 21:06:08,296 INFO L93 Difference]: Finished difference Result 60855 states and 66436 transitions. [2018-11-06 21:06:08,296 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-11-06 21:06:08,297 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 359 [2018-11-06 21:06:08,298 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 21:06:08,339 INFO L225 Difference]: With dead ends: 60855 [2018-11-06 21:06:08,340 INFO L226 Difference]: Without dead ends: 36118 [2018-11-06 21:06:08,359 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-11-06 21:06:08,385 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36118 states. [2018-11-06 21:06:08,713 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36118 to 32746. [2018-11-06 21:06:08,713 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 32746 states. [2018-11-06 21:06:08,757 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32746 states to 32746 states and 35606 transitions. [2018-11-06 21:06:08,757 INFO L78 Accepts]: Start accepts. Automaton has 32746 states and 35606 transitions. Word has length 359 [2018-11-06 21:06:08,758 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 21:06:08,758 INFO L480 AbstractCegarLoop]: Abstraction has 32746 states and 35606 transitions. [2018-11-06 21:06:08,758 INFO L481 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-11-06 21:06:08,758 INFO L276 IsEmpty]: Start isEmpty. Operand 32746 states and 35606 transitions. [2018-11-06 21:06:08,775 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 410 [2018-11-06 21:06:08,775 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 21:06:08,776 INFO L375 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 21:06:08,776 INFO L423 AbstractCegarLoop]: === Iteration 13 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 21:06:08,776 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 21:06:08,777 INFO L82 PathProgramCache]: Analyzing trace with hash -711972748, now seen corresponding path program 1 times [2018-11-06 21:06:08,777 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 21:06:08,777 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 21:06:08,778 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:06:08,778 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:06:08,778 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:06:08,830 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:06:09,174 INFO L134 CoverageAnalysis]: Checked inductivity of 424 backedges. 290 proven. 103 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2018-11-06 21:06:09,174 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-06 21:06:09,174 INFO L225 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-11-06 21:06:09,186 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:06:09,283 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:06:09,289 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-06 21:06:09,490 INFO L134 CoverageAnalysis]: Checked inductivity of 424 backedges. 290 proven. 103 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2018-11-06 21:06:09,510 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-11-06 21:06:09,510 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 3] total 4 [2018-11-06 21:06:09,511 INFO L459 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-11-06 21:06:09,511 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-11-06 21:06:09,512 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-11-06 21:06:09,512 INFO L87 Difference]: Start difference. First operand 32746 states and 35606 transitions. Second operand 5 states. [2018-11-06 21:06:12,145 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 21:06:12,146 INFO L93 Difference]: Finished difference Result 64186 states and 69601 transitions. [2018-11-06 21:06:12,146 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-11-06 21:06:12,146 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 409 [2018-11-06 21:06:12,147 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 21:06:12,176 INFO L225 Difference]: With dead ends: 64186 [2018-11-06 21:06:12,176 INFO L226 Difference]: Without dead ends: 34596 [2018-11-06 21:06:12,196 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 414 GetRequests, 408 SyntacticMatches, 1 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=18, Invalid=24, Unknown=0, NotChecked=0, Total=42 [2018-11-06 21:06:12,218 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34596 states. [2018-11-06 21:06:12,463 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34596 to 29755. [2018-11-06 21:06:12,463 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 29755 states. [2018-11-06 21:06:12,489 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29755 states to 29755 states and 32017 transitions. [2018-11-06 21:06:12,489 INFO L78 Accepts]: Start accepts. Automaton has 29755 states and 32017 transitions. Word has length 409 [2018-11-06 21:06:12,490 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 21:06:12,490 INFO L480 AbstractCegarLoop]: Abstraction has 29755 states and 32017 transitions. [2018-11-06 21:06:12,490 INFO L481 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-11-06 21:06:12,490 INFO L276 IsEmpty]: Start isEmpty. Operand 29755 states and 32017 transitions. [2018-11-06 21:06:12,505 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 420 [2018-11-06 21:06:12,505 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 21:06:12,505 INFO L375 BasicCegarLoop]: trace histogram [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 21:06:12,506 INFO L423 AbstractCegarLoop]: === Iteration 14 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 21:06:12,506 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 21:06:12,506 INFO L82 PathProgramCache]: Analyzing trace with hash -1562337051, now seen corresponding path program 1 times [2018-11-06 21:06:12,506 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 21:06:12,506 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 21:06:12,507 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:06:12,507 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:06:12,507 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:06:12,563 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:06:13,200 INFO L134 CoverageAnalysis]: Checked inductivity of 638 backedges. 0 proven. 556 refuted. 0 times theorem prover too weak. 82 trivial. 0 not checked. [2018-11-06 21:06:13,201 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-06 21:06:13,201 INFO L225 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-11-06 21:06:13,212 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:06:13,316 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:06:13,323 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-06 21:06:13,726 WARN L179 SmtUtils]: Spent 233.00 ms on a formula simplification. DAG size of input: 161 DAG size of output: 43 [2018-11-06 21:06:15,972 WARN L832 $PredicateComparison]: unable to prove that (or (exists ((v_prenex_16 Int)) (let ((.cse1 (mod v_prenex_16 299846))) (let ((.cse0 (+ (* 10 .cse1) 679640))) (let ((.cse2 (div .cse0 9))) (let ((.cse3 (div .cse2 5))) (and (<= 0 .cse0) (<= (+ v_prenex_16 43) 0) (not (= 0 .cse1)) (< v_prenex_16 0) (< 306 .cse2) (<= (+ c_~a23~0 127612) (div .cse3 5)) (<= 0 .cse2) (<= 0 .cse3))))))) (exists ((v_prenex_20 Int)) (let ((.cse4 (mod v_prenex_20 299846))) (let ((.cse6 (+ (* 10 .cse4) 679640))) (let ((.cse7 (div .cse6 9))) (let ((.cse5 (div .cse7 5))) (and (<= (+ v_prenex_20 43) 0) (< v_prenex_20 0) (not (= 0 .cse4)) (not (= (mod .cse5 5) 0)) (<= (+ c_~a23~0 127611) (div .cse5 5)) (<= 0 .cse6) (< .cse5 0) (< 306 .cse7) (<= 0 .cse7))))))) (exists ((v_prenex_25 Int)) (let ((.cse9 (mod v_prenex_25 299846))) (let ((.cse11 (+ (* 10 .cse9) 3678100))) (let ((.cse8 (div .cse11 9))) (let ((.cse10 (div .cse8 5))) (and (< 306 .cse8) (<= 0 .cse8) (= 0 .cse9) (= 0 (mod .cse10 5)) (<= (+ v_prenex_25 43) 0) (<= 0 .cse11) (<= (+ c_~a23~0 127612) (div .cse10 5)))))))) (exists ((v_prenex_38 Int)) (let ((.cse12 (mod v_prenex_38 299846))) (let ((.cse15 (+ (* 10 .cse12) 679640))) (let ((.cse13 (div .cse15 9))) (let ((.cse14 (div .cse13 5))) (and (not (= 0 .cse12)) (= 0 (mod .cse13 5)) (not (= 0 (mod .cse14 5))) (<= (+ v_prenex_38 43) 0) (<= 0 .cse15) (< v_prenex_38 0) (< 306 .cse13) (< .cse14 0) (<= (+ c_~a23~0 127611) (div .cse14 5)))))))) (exists ((v_prenex_29 Int)) (let ((.cse17 (mod v_prenex_29 299846))) (let ((.cse19 (+ (* 10 .cse17) 679640))) (let ((.cse16 (div .cse19 9))) (let ((.cse18 (div .cse16 5))) (and (<= (+ v_prenex_29 43) 0) (< v_prenex_29 0) (< 306 .cse16) (= (mod .cse16 5) 0) (not (= 0 .cse17)) (<= (+ c_~a23~0 127612) (div .cse18 5)) (= (mod .cse18 5) 0) (<= 0 .cse19))))))) (exists ((v_prenex_6 Int)) (let ((.cse22 (mod v_prenex_6 299846))) (let ((.cse23 (+ (* 10 .cse22) 679640))) (let ((.cse21 (div .cse23 9))) (let ((.cse20 (+ (div .cse21 5) 1))) (and (<= (+ c_~a23~0 127611) (div .cse20 5)) (not (= (mod .cse21 5) 0)) (not (= 0 .cse22)) (<= (+ v_prenex_6 43) 0) (< .cse20 0) (< v_prenex_6 0) (< 306 .cse21) (<= 0 .cse23) (not (= (mod .cse20 5) 0)) (< .cse21 0))))))) (exists ((v_prenex_15 Int)) (let ((.cse27 (mod v_prenex_15 299846))) (let ((.cse26 (+ (* 10 .cse27) 3678100))) (let ((.cse24 (div .cse26 9))) (let ((.cse25 (div .cse24 5))) (and (< 306 .cse24) (not (= (mod .cse25 5) 0)) (<= 0 .cse26) (<= 0 .cse24) (< .cse25 0) (<= (+ c_~a23~0 127611) (div .cse25 5)) (= 0 .cse27) (<= (+ v_prenex_15 43) 0))))))) (exists ((v_prenex_31 Int)) (let ((.cse31 (mod v_prenex_31 299846))) (let ((.cse29 (+ (* 10 .cse31) 679640))) (let ((.cse28 (div .cse29 9))) (let ((.cse30 (+ (div .cse28 5) 1))) (and (< .cse28 0) (<= 0 .cse29) (<= (+ c_~a23~0 127612) (div .cse30 5)) (= 0 (mod .cse30 5)) (<= (+ v_prenex_31 43) 0) (not (= 0 .cse31)) (< 306 .cse28) (not (= (mod .cse28 5) 0)) (< v_prenex_31 0))))))) (exists ((v_prenex_37 Int)) (let ((.cse35 (mod v_prenex_37 299846))) (let ((.cse34 (+ (* 10 .cse35) 3678100))) (let ((.cse32 (div .cse34 9))) (let ((.cse33 (div .cse32 5))) (and (<= (+ v_prenex_37 43) 0) (<= 0 .cse32) (<= 0 .cse33) (<= 0 .cse34) (= 0 .cse35) (<= (+ c_~a23~0 127612) (div .cse33 5)) (< 306 .cse32))))))) (exists ((v_prenex_34 Int)) (let ((.cse37 (mod v_prenex_34 299846))) (let ((.cse39 (+ (* 10 .cse37) 679640))) (let ((.cse38 (div .cse39 9))) (let ((.cse36 (div .cse38 5))) (and (<= (+ c_~a23~0 127612) (div .cse36 5)) (not (= 0 .cse37)) (= 0 (mod .cse38 5)) (<= 0 .cse39) (< v_prenex_34 0) (<= 0 .cse36) (<= (+ v_prenex_34 43) 0) (< 306 .cse38))))))) (exists ((v_prenex_23 Int)) (let ((.cse42 (mod v_prenex_23 299846))) (let ((.cse43 (+ (* 10 .cse42) 679640))) (let ((.cse40 (div .cse43 9))) (let ((.cse41 (div .cse40 5))) (and (< v_prenex_23 0) (< 306 .cse40) (<= (+ c_~a23~0 127612) (div .cse41 5)) (= 0 (mod .cse41 5)) (<= (+ v_prenex_23 43) 0) (<= 0 .cse40) (not (= 0 .cse42)) (<= 0 .cse43))))))) (exists ((v_prenex_8 Int)) (let ((.cse47 (mod v_prenex_8 299846))) (let ((.cse44 (+ (* 10 .cse47) 3678100))) (let ((.cse46 (div .cse44 9))) (let ((.cse45 (div .cse46 5))) (and (<= 0 .cse44) (<= (+ c_~a23~0 127612) (div .cse45 5)) (<= 0 .cse45) (= 0 (mod .cse46 5)) (<= (+ v_prenex_8 43) 0) (< 306 .cse46) (= 0 .cse47))))))) (exists ((v_prenex_41 Int)) (let ((.cse50 (mod v_prenex_41 299846))) (let ((.cse51 (+ (* 10 .cse50) 3678100))) (let ((.cse49 (div .cse51 9))) (let ((.cse48 (div .cse49 5))) (and (not (= 0 (mod .cse48 5))) (< .cse48 0) (< 306 .cse49) (<= (+ c_~a23~0 127611) (div .cse48 5)) (= 0 .cse50) (<= 0 .cse51) (= 0 (mod .cse49 5)) (<= (+ v_prenex_41 43) 0))))))) (exists ((v_prenex_18 Int)) (let ((.cse54 (mod v_prenex_18 299846))) (let ((.cse55 (+ (* 10 .cse54) 679640))) (let ((.cse52 (div .cse55 9))) (let ((.cse53 (+ (div .cse52 5) 1))) (and (< .cse52 0) (<= (+ c_~a23~0 127612) (div .cse53 5)) (not (= 0 .cse54)) (<= (+ v_prenex_18 43) 0) (<= 0 .cse55) (not (= (mod .cse52 5) 0)) (< 306 .cse52) (< v_prenex_18 0) (<= 0 .cse53))))))) (exists ((v_prenex_43 Int)) (let ((.cse59 (mod v_prenex_43 299846))) (let ((.cse57 (+ (* 10 .cse59) 3678100))) (let ((.cse58 (div .cse57 9))) (let ((.cse56 (div .cse58 5))) (and (= (mod .cse56 5) 0) (<= 0 .cse57) (<= (+ c_~a23~0 127612) (div .cse56 5)) (= (mod .cse58 5) 0) (= 0 .cse59) (< 306 .cse58) (<= (+ v_prenex_43 43) 0))))))) (exists ((v_prenex_45 Int)) (let ((.cse63 (mod v_prenex_45 299846))) (let ((.cse62 (+ (* 10 .cse63) 3678100))) (let ((.cse61 (div .cse62 9))) (let ((.cse60 (+ (div .cse61 5) 1))) (and (<= (+ c_~a23~0 127611) (div .cse60 5)) (< .cse61 0) (not (= 0 (mod .cse61 5))) (<= 0 .cse62) (not (= (mod .cse60 5) 0)) (<= (+ v_prenex_45 43) 0) (= 0 .cse63) (< .cse60 0) (< 306 .cse61))))))) (exists ((v_prenex_33 Int)) (let ((.cse65 (mod v_prenex_33 299846))) (let ((.cse64 (+ (* 10 .cse65) 3678100))) (let ((.cse66 (div .cse64 9))) (let ((.cse67 (+ (div .cse66 5) 1))) (and (<= 0 .cse64) (= 0 .cse65) (<= (+ v_prenex_33 43) 0) (not (= 0 (mod .cse66 5))) (< 306 .cse66) (= (mod .cse67 5) 0) (<= (+ c_~a23~0 127612) (div .cse67 5)) (< .cse66 0))))))) (exists ((v_prenex_27 Int)) (let ((.cse70 (mod v_prenex_27 299846))) (let ((.cse71 (+ (* 10 .cse70) 3678100))) (let ((.cse68 (div .cse71 9))) (let ((.cse69 (+ (div .cse68 5) 1))) (and (<= (+ v_prenex_27 43) 0) (< .cse68 0) (not (= (mod .cse68 5) 0)) (<= 0 .cse69) (<= (+ c_~a23~0 127612) (div .cse69 5)) (= 0 .cse70) (< 306 .cse68) (<= 0 .cse71)))))))) is different from false [2018-11-06 21:06:19,460 INFO L134 CoverageAnalysis]: Checked inductivity of 638 backedges. 354 proven. 0 refuted. 0 times theorem prover too weak. 253 trivial. 31 not checked. [2018-11-06 21:06:19,479 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-11-06 21:06:19,480 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 4] total 9 [2018-11-06 21:06:19,480 INFO L459 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-11-06 21:06:19,481 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-11-06 21:06:19,481 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=41, Unknown=1, NotChecked=12, Total=72 [2018-11-06 21:06:19,481 INFO L87 Difference]: Start difference. First operand 29755 states and 32017 transitions. Second operand 9 states. [2018-11-06 21:06:30,559 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 21:06:30,559 INFO L93 Difference]: Finished difference Result 63434 states and 68295 transitions. [2018-11-06 21:06:30,560 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-11-06 21:06:30,560 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 419 [2018-11-06 21:06:30,560 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 21:06:30,596 INFO L225 Difference]: With dead ends: 63434 [2018-11-06 21:06:30,597 INFO L226 Difference]: Without dead ends: 36835 [2018-11-06 21:06:30,615 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 443 GetRequests, 425 SyntacticMatches, 3 SemanticMatches, 15 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 43 ImplicationChecksByTransitivity, 4.4s TimeCoverageRelationStatistics Valid=62, Invalid=181, Unknown=1, NotChecked=28, Total=272 [2018-11-06 21:06:30,640 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36835 states. [2018-11-06 21:06:30,893 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36835 to 28261. [2018-11-06 21:06:30,893 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 28261 states. [2018-11-06 21:06:30,924 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28261 states to 28261 states and 30394 transitions. [2018-11-06 21:06:30,924 INFO L78 Accepts]: Start accepts. Automaton has 28261 states and 30394 transitions. Word has length 419 [2018-11-06 21:06:30,925 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 21:06:30,925 INFO L480 AbstractCegarLoop]: Abstraction has 28261 states and 30394 transitions. [2018-11-06 21:06:30,925 INFO L481 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-11-06 21:06:30,925 INFO L276 IsEmpty]: Start isEmpty. Operand 28261 states and 30394 transitions. [2018-11-06 21:06:30,938 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 453 [2018-11-06 21:06:30,938 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 21:06:30,939 INFO L375 BasicCegarLoop]: trace histogram [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 21:06:30,939 INFO L423 AbstractCegarLoop]: === Iteration 15 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 21:06:30,939 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 21:06:30,939 INFO L82 PathProgramCache]: Analyzing trace with hash 1889678859, now seen corresponding path program 1 times [2018-11-06 21:06:30,940 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 21:06:30,940 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 21:06:30,940 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:06:30,940 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:06:30,940 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:06:30,996 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:06:31,513 WARN L179 SmtUtils]: Spent 102.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2018-11-06 21:06:31,846 WARN L179 SmtUtils]: Spent 247.00 ms on a formula simplification. DAG size of input: 15 DAG size of output: 12 [2018-11-06 21:06:32,074 INFO L134 CoverageAnalysis]: Checked inductivity of 696 backedges. 134 proven. 465 refuted. 0 times theorem prover too weak. 97 trivial. 0 not checked. [2018-11-06 21:06:32,074 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-06 21:06:32,074 INFO L225 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-11-06 21:06:32,082 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:06:32,196 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:06:32,204 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-06 21:06:32,486 WARN L179 SmtUtils]: Spent 120.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-11-06 21:06:33,012 WARN L179 SmtUtils]: Spent 368.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 18 [2018-11-06 21:06:34,019 INFO L134 CoverageAnalysis]: Checked inductivity of 696 backedges. 260 proven. 339 refuted. 0 times theorem prover too weak. 97 trivial. 0 not checked. [2018-11-06 21:06:34,039 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-11-06 21:06:34,040 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 5] total 11 [2018-11-06 21:06:34,041 INFO L459 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-11-06 21:06:34,041 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-11-06 21:06:34,042 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=94, Unknown=0, NotChecked=0, Total=132 [2018-11-06 21:06:34,042 INFO L87 Difference]: Start difference. First operand 28261 states and 30394 transitions. Second operand 12 states. [2018-11-06 21:06:46,248 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 21:06:46,249 INFO L93 Difference]: Finished difference Result 55205 states and 59417 transitions. [2018-11-06 21:06:46,249 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-11-06 21:06:46,249 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 452 [2018-11-06 21:06:46,249 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 21:06:46,276 INFO L225 Difference]: With dead ends: 55205 [2018-11-06 21:06:46,276 INFO L226 Difference]: Without dead ends: 28991 [2018-11-06 21:06:46,292 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 468 GetRequests, 447 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 74 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=160, Invalid=302, Unknown=0, NotChecked=0, Total=462 [2018-11-06 21:06:46,308 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28991 states. [2018-11-06 21:06:46,542 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28991 to 26266. [2018-11-06 21:06:46,543 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 26266 states. [2018-11-06 21:06:46,572 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26266 states to 26266 states and 28122 transitions. [2018-11-06 21:06:46,572 INFO L78 Accepts]: Start accepts. Automaton has 26266 states and 28122 transitions. Word has length 452 [2018-11-06 21:06:46,572 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 21:06:46,573 INFO L480 AbstractCegarLoop]: Abstraction has 26266 states and 28122 transitions. [2018-11-06 21:06:46,573 INFO L481 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-11-06 21:06:46,573 INFO L276 IsEmpty]: Start isEmpty. Operand 26266 states and 28122 transitions. [2018-11-06 21:06:46,586 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 509 [2018-11-06 21:06:46,587 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 21:06:46,587 INFO L375 BasicCegarLoop]: trace histogram [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 21:06:46,588 INFO L423 AbstractCegarLoop]: === Iteration 16 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 21:06:46,588 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 21:06:46,588 INFO L82 PathProgramCache]: Analyzing trace with hash -1264069308, now seen corresponding path program 1 times [2018-11-06 21:06:46,588 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 21:06:46,588 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 21:06:46,589 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:06:46,589 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:06:46,589 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:06:46,650 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:06:47,011 WARN L179 SmtUtils]: Spent 116.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-11-06 21:06:47,509 INFO L134 CoverageAnalysis]: Checked inductivity of 656 backedges. 463 proven. 162 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2018-11-06 21:06:47,509 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-06 21:06:47,510 INFO L225 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-11-06 21:06:47,520 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:06:47,643 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:06:47,651 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-06 21:06:48,074 INFO L134 CoverageAnalysis]: Checked inductivity of 656 backedges. 509 proven. 0 refuted. 0 times theorem prover too weak. 147 trivial. 0 not checked. [2018-11-06 21:06:48,095 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-11-06 21:06:48,095 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [8] total 10 [2018-11-06 21:06:48,096 INFO L459 AbstractCegarLoop]: Interpolant automaton has 11 states [2018-11-06 21:06:48,096 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2018-11-06 21:06:48,096 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=74, Unknown=0, NotChecked=0, Total=110 [2018-11-06 21:06:48,096 INFO L87 Difference]: Start difference. First operand 26266 states and 28122 transitions. Second operand 11 states. [2018-11-06 21:06:55,456 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 21:06:55,457 INFO L93 Difference]: Finished difference Result 64931 states and 69484 transitions. [2018-11-06 21:06:55,457 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-11-06 21:06:55,457 INFO L78 Accepts]: Start accepts. Automaton has 11 states. Word has length 508 [2018-11-06 21:06:55,458 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 21:06:55,495 INFO L225 Difference]: With dead ends: 64931 [2018-11-06 21:06:55,495 INFO L226 Difference]: Without dead ends: 40705 [2018-11-06 21:06:55,513 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 529 GetRequests, 506 SyntacticMatches, 1 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 115 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=197, Invalid=355, Unknown=0, NotChecked=0, Total=552 [2018-11-06 21:06:55,536 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40705 states. [2018-11-06 21:06:55,775 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40705 to 23477. [2018-11-06 21:06:55,775 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 23477 states. [2018-11-06 21:06:55,795 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23477 states to 23477 states and 25101 transitions. [2018-11-06 21:06:55,795 INFO L78 Accepts]: Start accepts. Automaton has 23477 states and 25101 transitions. Word has length 508 [2018-11-06 21:06:55,795 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 21:06:55,795 INFO L480 AbstractCegarLoop]: Abstraction has 23477 states and 25101 transitions. [2018-11-06 21:06:55,795 INFO L481 AbstractCegarLoop]: Interpolant automaton has 11 states. [2018-11-06 21:06:55,795 INFO L276 IsEmpty]: Start isEmpty. Operand 23477 states and 25101 transitions. [2018-11-06 21:06:55,804 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 526 [2018-11-06 21:06:55,805 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 21:06:55,805 INFO L375 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 21:06:55,805 INFO L423 AbstractCegarLoop]: === Iteration 17 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 21:06:55,806 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 21:06:55,806 INFO L82 PathProgramCache]: Analyzing trace with hash 1912565945, now seen corresponding path program 1 times [2018-11-06 21:06:55,806 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 21:06:55,806 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 21:06:55,807 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:06:55,807 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:06:55,807 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:06:55,866 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:06:56,433 WARN L179 SmtUtils]: Spent 136.00 ms on a formula simplification that was a NOOP. DAG size: 16 [2018-11-06 21:06:57,293 INFO L134 CoverageAnalysis]: Checked inductivity of 562 backedges. 92 proven. 319 refuted. 0 times theorem prover too weak. 151 trivial. 0 not checked. [2018-11-06 21:06:57,293 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-06 21:06:57,293 INFO L225 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-11-06 21:06:57,301 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:06:57,428 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:06:57,436 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-06 21:06:58,193 WARN L179 SmtUtils]: Spent 383.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 43 [2018-11-06 21:06:59,320 INFO L134 CoverageAnalysis]: Checked inductivity of 562 backedges. 92 proven. 319 refuted. 0 times theorem prover too weak. 151 trivial. 0 not checked. [2018-11-06 21:06:59,340 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-11-06 21:06:59,341 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 5] total 11 [2018-11-06 21:06:59,341 INFO L459 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-11-06 21:06:59,342 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-11-06 21:06:59,342 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=99, Unknown=0, NotChecked=0, Total=132 [2018-11-06 21:06:59,342 INFO L87 Difference]: Start difference. First operand 23477 states and 25101 transitions. Second operand 12 states. [2018-11-06 21:07:00,243 WARN L179 SmtUtils]: Spent 116.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 42 [2018-11-06 21:07:02,689 WARN L179 SmtUtils]: Spent 193.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 46 [2018-11-06 21:07:06,386 WARN L179 SmtUtils]: Spent 104.00 ms on a formula simplification. DAG size of input: 55 DAG size of output: 30 [2018-11-06 21:07:09,683 WARN L179 SmtUtils]: Spent 107.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 32 [2018-11-06 21:07:11,248 WARN L179 SmtUtils]: Spent 188.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 45 [2018-11-06 21:07:11,580 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 21:07:11,581 INFO L93 Difference]: Finished difference Result 48399 states and 51721 transitions. [2018-11-06 21:07:11,582 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2018-11-06 21:07:11,582 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 525 [2018-11-06 21:07:11,583 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 21:07:11,610 INFO L225 Difference]: With dead ends: 48399 [2018-11-06 21:07:11,610 INFO L226 Difference]: Without dead ends: 26776 [2018-11-06 21:07:11,626 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 552 GetRequests, 512 SyntacticMatches, 11 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 257 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=269, Invalid=661, Unknown=0, NotChecked=0, Total=930 [2018-11-06 21:07:11,641 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26776 states. [2018-11-06 21:07:11,847 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26776 to 21419. [2018-11-06 21:07:11,847 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 21419 states. [2018-11-06 21:07:11,865 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21419 states to 21419 states and 22885 transitions. [2018-11-06 21:07:11,866 INFO L78 Accepts]: Start accepts. Automaton has 21419 states and 22885 transitions. Word has length 525 [2018-11-06 21:07:11,866 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 21:07:11,866 INFO L480 AbstractCegarLoop]: Abstraction has 21419 states and 22885 transitions. [2018-11-06 21:07:11,867 INFO L481 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-11-06 21:07:11,867 INFO L276 IsEmpty]: Start isEmpty. Operand 21419 states and 22885 transitions. [2018-11-06 21:07:11,877 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 544 [2018-11-06 21:07:11,877 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 21:07:11,877 INFO L375 BasicCegarLoop]: trace histogram [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 21:07:11,878 INFO L423 AbstractCegarLoop]: === Iteration 18 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 21:07:11,878 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 21:07:11,878 INFO L82 PathProgramCache]: Analyzing trace with hash -1849402497, now seen corresponding path program 1 times [2018-11-06 21:07:11,878 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 21:07:11,878 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 21:07:11,879 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:07:11,879 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:07:11,879 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:07:11,935 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:07:12,529 WARN L179 SmtUtils]: Spent 343.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 11 [2018-11-06 21:07:12,849 INFO L134 CoverageAnalysis]: Checked inductivity of 1072 backedges. 839 proven. 0 refuted. 0 times theorem prover too weak. 233 trivial. 0 not checked. [2018-11-06 21:07:12,849 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-06 21:07:12,849 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-11-06 21:07:12,850 INFO L459 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-11-06 21:07:12,850 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-11-06 21:07:12,850 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-11-06 21:07:12,850 INFO L87 Difference]: Start difference. First operand 21419 states and 22885 transitions. Second operand 4 states. [2018-11-06 21:07:14,393 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 21:07:14,394 INFO L93 Difference]: Finished difference Result 41545 states and 44442 transitions. [2018-11-06 21:07:14,394 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-11-06 21:07:14,394 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 543 [2018-11-06 21:07:14,394 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 21:07:14,414 INFO L225 Difference]: With dead ends: 41545 [2018-11-06 21:07:14,414 INFO L226 Difference]: Without dead ends: 22722 [2018-11-06 21:07:14,425 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-11-06 21:07:14,439 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22722 states. [2018-11-06 21:07:14,628 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22722 to 20861. [2018-11-06 21:07:14,629 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 20861 states. [2018-11-06 21:07:14,647 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20861 states to 20861 states and 22144 transitions. [2018-11-06 21:07:14,647 INFO L78 Accepts]: Start accepts. Automaton has 20861 states and 22144 transitions. Word has length 543 [2018-11-06 21:07:14,647 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 21:07:14,647 INFO L480 AbstractCegarLoop]: Abstraction has 20861 states and 22144 transitions. [2018-11-06 21:07:14,647 INFO L481 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-11-06 21:07:14,647 INFO L276 IsEmpty]: Start isEmpty. Operand 20861 states and 22144 transitions. [2018-11-06 21:07:14,659 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 555 [2018-11-06 21:07:14,659 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 21:07:14,659 INFO L375 BasicCegarLoop]: trace histogram [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 21:07:14,660 INFO L423 AbstractCegarLoop]: === Iteration 19 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 21:07:14,660 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 21:07:14,660 INFO L82 PathProgramCache]: Analyzing trace with hash 956786045, now seen corresponding path program 1 times [2018-11-06 21:07:14,660 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 21:07:14,660 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 21:07:14,661 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:07:14,661 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:07:14,661 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:07:14,724 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:07:15,175 WARN L179 SmtUtils]: Spent 179.00 ms on a formula simplification. DAG size of input: 13 DAG size of output: 9 [2018-11-06 21:07:15,465 WARN L179 SmtUtils]: Spent 228.00 ms on a formula simplification. DAG size of input: 15 DAG size of output: 7 [2018-11-06 21:07:15,707 INFO L134 CoverageAnalysis]: Checked inductivity of 761 backedges. 395 proven. 0 refuted. 0 times theorem prover too weak. 366 trivial. 0 not checked. [2018-11-06 21:07:15,707 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-06 21:07:15,707 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-11-06 21:07:15,708 INFO L459 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-11-06 21:07:15,708 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-11-06 21:07:15,708 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-11-06 21:07:15,708 INFO L87 Difference]: Start difference. First operand 20861 states and 22144 transitions. Second operand 5 states. [2018-11-06 21:07:17,991 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 21:07:17,991 INFO L93 Difference]: Finished difference Result 38757 states and 41176 transitions. [2018-11-06 21:07:17,992 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-11-06 21:07:17,992 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 554 [2018-11-06 21:07:17,992 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 21:07:18,009 INFO L225 Difference]: With dead ends: 38757 [2018-11-06 21:07:18,010 INFO L226 Difference]: Without dead ends: 20864 [2018-11-06 21:07:18,018 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-11-06 21:07:18,028 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20864 states. [2018-11-06 21:07:18,205 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20864 to 19751. [2018-11-06 21:07:18,205 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 19751 states. [2018-11-06 21:07:18,222 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19751 states to 19751 states and 20920 transitions. [2018-11-06 21:07:18,222 INFO L78 Accepts]: Start accepts. Automaton has 19751 states and 20920 transitions. Word has length 554 [2018-11-06 21:07:18,223 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 21:07:18,223 INFO L480 AbstractCegarLoop]: Abstraction has 19751 states and 20920 transitions. [2018-11-06 21:07:18,223 INFO L481 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-11-06 21:07:18,223 INFO L276 IsEmpty]: Start isEmpty. Operand 19751 states and 20920 transitions. [2018-11-06 21:07:18,238 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 641 [2018-11-06 21:07:18,238 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 21:07:18,239 INFO L375 BasicCegarLoop]: trace histogram [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 21:07:18,239 INFO L423 AbstractCegarLoop]: === Iteration 20 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 21:07:18,239 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 21:07:18,240 INFO L82 PathProgramCache]: Analyzing trace with hash -847476356, now seen corresponding path program 1 times [2018-11-06 21:07:18,240 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 21:07:18,240 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 21:07:18,240 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:07:18,241 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:07:18,241 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:07:18,313 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:07:19,004 INFO L134 CoverageAnalysis]: Checked inductivity of 949 backedges. 555 proven. 0 refuted. 0 times theorem prover too weak. 394 trivial. 0 not checked. [2018-11-06 21:07:19,005 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-06 21:07:19,005 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-11-06 21:07:19,005 INFO L459 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-11-06 21:07:19,006 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-11-06 21:07:19,006 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-11-06 21:07:19,006 INFO L87 Difference]: Start difference. First operand 19751 states and 20920 transitions. Second operand 6 states. [2018-11-06 21:07:21,989 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 21:07:21,989 INFO L93 Difference]: Finished difference Result 45071 states and 47716 transitions. [2018-11-06 21:07:21,989 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-11-06 21:07:21,989 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 640 [2018-11-06 21:07:21,990 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 21:07:22,016 INFO L225 Difference]: With dead ends: 45071 [2018-11-06 21:07:22,017 INFO L226 Difference]: Without dead ends: 28288 [2018-11-06 21:07:22,028 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-11-06 21:07:22,043 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28288 states. [2018-11-06 21:07:22,241 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28288 to 19190. [2018-11-06 21:07:22,242 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 19190 states. [2018-11-06 21:07:22,258 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19190 states to 19190 states and 20311 transitions. [2018-11-06 21:07:22,258 INFO L78 Accepts]: Start accepts. Automaton has 19190 states and 20311 transitions. Word has length 640 [2018-11-06 21:07:22,259 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 21:07:22,259 INFO L480 AbstractCegarLoop]: Abstraction has 19190 states and 20311 transitions. [2018-11-06 21:07:22,259 INFO L481 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-11-06 21:07:22,259 INFO L276 IsEmpty]: Start isEmpty. Operand 19190 states and 20311 transitions. [2018-11-06 21:07:22,271 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 648 [2018-11-06 21:07:22,271 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 21:07:22,271 INFO L375 BasicCegarLoop]: trace histogram [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 21:07:22,272 INFO L423 AbstractCegarLoop]: === Iteration 21 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 21:07:22,272 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 21:07:22,272 INFO L82 PathProgramCache]: Analyzing trace with hash -1534956161, now seen corresponding path program 1 times [2018-11-06 21:07:22,272 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 21:07:22,272 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 21:07:22,273 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:07:22,273 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:07:22,273 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:07:22,339 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:07:22,955 INFO L134 CoverageAnalysis]: Checked inductivity of 1189 backedges. 595 proven. 0 refuted. 0 times theorem prover too weak. 594 trivial. 0 not checked. [2018-11-06 21:07:22,955 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-06 21:07:22,955 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-11-06 21:07:22,956 INFO L459 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-11-06 21:07:22,956 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-11-06 21:07:22,956 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-11-06 21:07:22,957 INFO L87 Difference]: Start difference. First operand 19190 states and 20311 transitions. Second operand 6 states. [2018-11-06 21:07:25,949 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 21:07:25,950 INFO L93 Difference]: Finished difference Result 41901 states and 44339 transitions. [2018-11-06 21:07:25,950 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-11-06 21:07:25,950 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 647 [2018-11-06 21:07:25,951 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 21:07:25,973 INFO L225 Difference]: With dead ends: 41901 [2018-11-06 21:07:25,973 INFO L226 Difference]: Without dead ends: 25679 [2018-11-06 21:07:25,984 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-11-06 21:07:25,997 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25679 states. [2018-11-06 21:07:26,188 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25679 to 17700. [2018-11-06 21:07:26,188 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 17700 states. [2018-11-06 21:07:26,202 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17700 states to 17700 states and 18743 transitions. [2018-11-06 21:07:26,203 INFO L78 Accepts]: Start accepts. Automaton has 17700 states and 18743 transitions. Word has length 647 [2018-11-06 21:07:26,203 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 21:07:26,203 INFO L480 AbstractCegarLoop]: Abstraction has 17700 states and 18743 transitions. [2018-11-06 21:07:26,203 INFO L481 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-11-06 21:07:26,203 INFO L276 IsEmpty]: Start isEmpty. Operand 17700 states and 18743 transitions. [2018-11-06 21:07:26,214 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 679 [2018-11-06 21:07:26,214 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 21:07:26,215 INFO L375 BasicCegarLoop]: trace histogram [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 21:07:26,215 INFO L423 AbstractCegarLoop]: === Iteration 22 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 21:07:26,215 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 21:07:26,215 INFO L82 PathProgramCache]: Analyzing trace with hash 725576367, now seen corresponding path program 1 times [2018-11-06 21:07:26,216 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 21:07:26,216 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 21:07:26,216 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:07:26,216 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:07:26,216 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:07:26,285 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:07:27,786 INFO L134 CoverageAnalysis]: Checked inductivity of 1010 backedges. 31 proven. 979 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-06 21:07:27,786 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-06 21:07:27,786 INFO L225 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-11-06 21:07:27,797 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:07:27,969 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:07:27,979 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-06 21:07:29,442 INFO L134 CoverageAnalysis]: Checked inductivity of 1010 backedges. 156 proven. 854 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-06 21:07:29,462 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-11-06 21:07:29,463 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7] total 12 [2018-11-06 21:07:29,464 INFO L459 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-11-06 21:07:29,464 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-11-06 21:07:29,464 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=110, Unknown=0, NotChecked=0, Total=156 [2018-11-06 21:07:29,464 INFO L87 Difference]: Start difference. First operand 17700 states and 18743 transitions. Second operand 13 states. [2018-11-06 21:07:36,434 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 21:07:36,434 INFO L93 Difference]: Finished difference Result 48018 states and 50838 transitions. [2018-11-06 21:07:36,439 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-11-06 21:07:36,439 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 678 [2018-11-06 21:07:36,440 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 21:07:36,469 INFO L225 Difference]: With dead ends: 48018 [2018-11-06 21:07:36,469 INFO L226 Difference]: Without dead ends: 32731 [2018-11-06 21:07:36,480 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 689 GetRequests, 672 SyntacticMatches, 4 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 62 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=62, Invalid=148, Unknown=0, NotChecked=0, Total=210 [2018-11-06 21:07:36,496 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32731 states. [2018-11-06 21:07:36,764 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32731 to 20688. [2018-11-06 21:07:36,764 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 20688 states. [2018-11-06 21:07:36,781 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20688 states to 20688 states and 21922 transitions. [2018-11-06 21:07:36,781 INFO L78 Accepts]: Start accepts. Automaton has 20688 states and 21922 transitions. Word has length 678 [2018-11-06 21:07:36,782 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 21:07:36,782 INFO L480 AbstractCegarLoop]: Abstraction has 20688 states and 21922 transitions. [2018-11-06 21:07:36,782 INFO L481 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-11-06 21:07:36,782 INFO L276 IsEmpty]: Start isEmpty. Operand 20688 states and 21922 transitions. [2018-11-06 21:07:36,794 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 687 [2018-11-06 21:07:36,794 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 21:07:36,795 INFO L375 BasicCegarLoop]: trace histogram [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 21:07:36,795 INFO L423 AbstractCegarLoop]: === Iteration 23 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 21:07:36,795 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 21:07:36,796 INFO L82 PathProgramCache]: Analyzing trace with hash -817217683, now seen corresponding path program 1 times [2018-11-06 21:07:36,796 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 21:07:36,796 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 21:07:36,796 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:07:36,796 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:07:36,797 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 21:07:36,873 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:07:39,139 INFO L134 CoverageAnalysis]: Checked inductivity of 1009 backedges. 0 proven. 1009 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-06 21:07:39,140 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-06 21:07:39,140 INFO L225 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-11-06 21:07:39,148 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 21:07:39,310 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 21:07:39,320 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-06 21:08:09,123 WARN L179 SmtUtils]: Spent 29.05 s on a formula simplification. DAG size of input: 646 DAG size of output: 193 Received shutdown request... [2018-11-06 21:08:58,873 WARN L187 SmtUtils]: Removed 8 from assertion stack [2018-11-06 21:08:58,873 INFO L177 TraceCheckSpWp]: Timeout while computing interpolants [2018-11-06 21:08:59,074 WARN L521 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-06 21:08:59,075 WARN L549 AbstractCegarLoop]: Verification canceled [2018-11-06 21:08:59,080 WARN L205 ceAbstractionStarter]: Timeout [2018-11-06 21:08:59,081 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 06.11 09:08:59 BoogieIcfgContainer [2018-11-06 21:08:59,081 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-11-06 21:08:59,082 INFO L168 Benchmark]: Toolchain (without parser) took 234062.18 ms. Allocated memory was 1.5 GB in the beginning and 4.1 GB in the end (delta: 2.6 GB). Free memory was 1.4 GB in the beginning and 2.0 GB in the end (delta: -621.0 MB). Peak memory consumption was 1.9 GB. Max. memory is 7.1 GB. [2018-11-06 21:08:59,083 INFO L168 Benchmark]: CDTParser took 0.21 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-11-06 21:08:59,083 INFO L168 Benchmark]: CACSL2BoogieTranslator took 1022.13 ms. Allocated memory is still 1.5 GB. Free memory was 1.4 GB in the beginning and 1.4 GB in the end (delta: 52.8 MB). Peak memory consumption was 52.8 MB. Max. memory is 7.1 GB. [2018-11-06 21:08:59,084 INFO L168 Benchmark]: Boogie Procedure Inliner took 259.18 ms. Allocated memory was 1.5 GB in the beginning and 2.3 GB in the end (delta: 734.0 MB). Free memory was 1.4 GB in the beginning and 2.2 GB in the end (delta: -818.5 MB). Peak memory consumption was 23.0 MB. Max. memory is 7.1 GB. [2018-11-06 21:08:59,085 INFO L168 Benchmark]: Boogie Preprocessor took 122.24 ms. Allocated memory is still 2.3 GB. Free memory was 2.2 GB in the beginning and 2.2 GB in the end (delta: 13.5 MB). Peak memory consumption was 13.5 MB. Max. memory is 7.1 GB. [2018-11-06 21:08:59,086 INFO L168 Benchmark]: RCFGBuilder took 4590.12 ms. Allocated memory is still 2.3 GB. Free memory was 2.2 GB in the beginning and 2.0 GB in the end (delta: 184.8 MB). Peak memory consumption was 184.8 MB. Max. memory is 7.1 GB. [2018-11-06 21:08:59,086 INFO L168 Benchmark]: TraceAbstraction took 228062.28 ms. Allocated memory was 2.3 GB in the beginning and 4.1 GB in the end (delta: 1.8 GB). Free memory was 2.0 GB in the beginning and 2.0 GB in the end (delta: -53.7 MB). Peak memory consumption was 1.8 GB. Max. memory is 7.1 GB. [2018-11-06 21:08:59,093 INFO L336 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.21 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. * CACSL2BoogieTranslator took 1022.13 ms. Allocated memory is still 1.5 GB. Free memory was 1.4 GB in the beginning and 1.4 GB in the end (delta: 52.8 MB). Peak memory consumption was 52.8 MB. Max. memory is 7.1 GB. * Boogie Procedure Inliner took 259.18 ms. Allocated memory was 1.5 GB in the beginning and 2.3 GB in the end (delta: 734.0 MB). Free memory was 1.4 GB in the beginning and 2.2 GB in the end (delta: -818.5 MB). Peak memory consumption was 23.0 MB. Max. memory is 7.1 GB. * Boogie Preprocessor took 122.24 ms. Allocated memory is still 2.3 GB. Free memory was 2.2 GB in the beginning and 2.2 GB in the end (delta: 13.5 MB). Peak memory consumption was 13.5 MB. Max. memory is 7.1 GB. * RCFGBuilder took 4590.12 ms. Allocated memory is still 2.3 GB. Free memory was 2.2 GB in the beginning and 2.0 GB in the end (delta: 184.8 MB). Peak memory consumption was 184.8 MB. Max. memory is 7.1 GB. * TraceAbstraction took 228062.28 ms. Allocated memory was 2.3 GB in the beginning and 4.1 GB in the end (delta: 1.8 GB). Free memory was 2.0 GB in the beginning and 2.0 GB in the end (delta: -53.7 MB). Peak memory consumption was 1.8 GB. Max. memory is 7.1 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 102]: Timeout (TraceAbstraction) Unable to prove that call of __VERIFIER_error() unreachable (line 102). Cancelled while BasicCegarLoop was analyzing trace of length 687 with TraceHistMax 5,while TraceCheckSpWp was constructing forward predicates,while PredicateUnifier was unifying predicates,while SimplifyDDAWithTimeout was simplifying term of DAG size 202. - StatisticsResult: Ultimate Automizer benchmark data CFG has 1 procedures, 284 locations, 1 error locations. TIMEOUT Result, 227.9s OverallTime, 23 OverallIterations, 6 TraceHistogramMax, 108.7s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 3658 SDtfs, 24896 SDslu, 3623 SDs, 0 SdLazy, 61261 SolverSat, 7637 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 85.6s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 3855 GetRequests, 3664 SyntacticMatches, 26 SemanticMatches, 165 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 652 ImplicationChecksByTransitivity, 17.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=32746occurred in iteration=12, 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: 5.7s AutomataMinimizationTime, 22 MinimizatonAttempts, 85437 StatesRemovedByMinimization, 21 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.4s SsaConstructionTime, 1.8s SatisfiabilityAnalysisTime, 24.0s InterpolantComputationTime, 11891 NumberOfCodeBlocks, 11891 NumberOfCodeBlocksAsserted, 30 NumberOfCheckSat, 11861 ConstructedInterpolants, 418 QuantifiedInterpolants, 52895610 SizeOfPredicates, 14 NumberOfNonLiveVariables, 4766 ConjunctsInSsa, 72 ConjunctsInUnsatCore, 30 InterpolantComputations, 15 PerfectInterpolantSequences, 9866/14786 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Completed graceful shutdown