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/loops/linear_sea.ch_true-unreach-call.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-df4b876 [2018-11-06 22:38:54,169 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-11-06 22:38:54,171 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-11-06 22:38:54,183 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-11-06 22:38:54,183 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-11-06 22:38:54,185 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-11-06 22:38:54,186 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-11-06 22:38:54,188 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-11-06 22:38:54,189 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-11-06 22:38:54,190 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-11-06 22:38:54,191 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-11-06 22:38:54,191 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-11-06 22:38:54,192 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-11-06 22:38:54,193 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-11-06 22:38:54,194 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-11-06 22:38:54,195 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-11-06 22:38:54,196 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-11-06 22:38:54,198 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-11-06 22:38:54,200 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-11-06 22:38:54,201 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-11-06 22:38:54,203 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-11-06 22:38:54,204 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-11-06 22:38:54,206 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-11-06 22:38:54,207 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-11-06 22:38:54,207 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-11-06 22:38:54,208 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-11-06 22:38:54,209 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-11-06 22:38:54,210 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-11-06 22:38:54,210 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-11-06 22:38:54,212 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-11-06 22:38:54,212 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-11-06 22:38:54,213 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-11-06 22:38:54,213 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-11-06 22:38:54,213 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-11-06 22:38:54,214 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-11-06 22:38:54,215 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-11-06 22:38:54,215 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 22:38:54,233 INFO L110 SettingsManager]: Loading preferences was successful [2018-11-06 22:38:54,233 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-11-06 22:38:54,234 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-11-06 22:38:54,234 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-11-06 22:38:54,235 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-11-06 22:38:54,235 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-11-06 22:38:54,235 INFO L133 SettingsManager]: * Use SBE=true [2018-11-06 22:38:54,236 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-11-06 22:38:54,236 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-11-06 22:38:54,236 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-11-06 22:38:54,236 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-11-06 22:38:54,237 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-11-06 22:38:54,237 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-11-06 22:38:54,237 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-11-06 22:38:54,237 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-11-06 22:38:54,237 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-11-06 22:38:54,238 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-11-06 22:38:54,238 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-11-06 22:38:54,238 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-11-06 22:38:54,238 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-11-06 22:38:54,238 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-11-06 22:38:54,239 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-11-06 22:38:54,239 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-11-06 22:38:54,239 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-11-06 22:38:54,239 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-11-06 22:38:54,239 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-11-06 22:38:54,240 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-11-06 22:38:54,240 INFO L133 SettingsManager]: * To the following directory=dump/ [2018-11-06 22:38:54,283 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-11-06 22:38:54,297 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-11-06 22:38:54,300 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-11-06 22:38:54,302 INFO L271 PluginConnector]: Initializing CDTParser... [2018-11-06 22:38:54,302 INFO L276 PluginConnector]: CDTParser initialized [2018-11-06 22:38:54,303 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/loops/linear_sea.ch_true-unreach-call.i [2018-11-06 22:38:54,363 INFO L218 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/9aab54cb1/f59609725bcb4620bd845a3d92babe8b/FLAGac0fb6996 [2018-11-06 22:38:54,796 INFO L298 CDTParser]: Found 1 translation units. [2018-11-06 22:38:54,797 INFO L158 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/loops/linear_sea.ch_true-unreach-call.i [2018-11-06 22:38:54,804 INFO L346 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/9aab54cb1/f59609725bcb4620bd845a3d92babe8b/FLAGac0fb6996 [2018-11-06 22:38:54,818 INFO L354 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/9aab54cb1/f59609725bcb4620bd845a3d92babe8b [2018-11-06 22:38:54,827 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-11-06 22:38:54,829 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2018-11-06 22:38:54,830 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-11-06 22:38:54,830 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-11-06 22:38:54,834 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-11-06 22:38:54,835 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.11 10:38:54" (1/1) ... [2018-11-06 22:38:54,838 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@56a4e2c2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:38:54, skipping insertion in model container [2018-11-06 22:38:54,838 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.11 10:38:54" (1/1) ... [2018-11-06 22:38:54,848 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2018-11-06 22:38:54,871 INFO L174 MainTranslator]: Built tables and reachable declarations [2018-11-06 22:38:55,083 INFO L202 PostProcessor]: Analyzing one entry point: main [2018-11-06 22:38:55,099 INFO L189 MainTranslator]: Completed pre-run [2018-11-06 22:38:55,127 INFO L202 PostProcessor]: Analyzing one entry point: main [2018-11-06 22:38:55,148 INFO L193 MainTranslator]: Completed translation [2018-11-06 22:38:55,149 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:38:55 WrapperNode [2018-11-06 22:38:55,149 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-11-06 22:38:55,151 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2018-11-06 22:38:55,152 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2018-11-06 22:38:55,152 INFO L276 PluginConnector]: Boogie Procedure Inliner initialized [2018-11-06 22:38:55,164 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:38:55" (1/1) ... [2018-11-06 22:38:55,176 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:38:55" (1/1) ... [2018-11-06 22:38:55,202 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2018-11-06 22:38:55,203 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-11-06 22:38:55,203 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-11-06 22:38:55,203 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-11-06 22:38:55,216 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:38:55" (1/1) ... [2018-11-06 22:38:55,216 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:38:55" (1/1) ... [2018-11-06 22:38:55,219 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:38:55" (1/1) ... [2018-11-06 22:38:55,219 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:38:55" (1/1) ... [2018-11-06 22:38:55,224 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:38:55" (1/1) ... [2018-11-06 22:38:55,229 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:38:55" (1/1) ... [2018-11-06 22:38:55,231 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:38:55" (1/1) ... [2018-11-06 22:38:55,233 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-11-06 22:38:55,234 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-11-06 22:38:55,234 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-11-06 22:38:55,234 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-11-06 22:38:55,235 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:38:55" (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 22:38:55,381 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2018-11-06 22:38:55,381 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-11-06 22:38:55,381 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-11-06 22:38:55,381 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-11-06 22:38:55,381 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2018-11-06 22:38:55,382 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-11-06 22:38:55,759 INFO L276 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-11-06 22:38:55,760 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.11 10:38:55 BoogieIcfgContainer [2018-11-06 22:38:55,760 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-11-06 22:38:55,761 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-11-06 22:38:55,762 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-11-06 22:38:55,765 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-11-06 22:38:55,765 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.11 10:38:54" (1/3) ... [2018-11-06 22:38:55,766 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2f95a035 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.11 10:38:55, skipping insertion in model container [2018-11-06 22:38:55,766 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:38:55" (2/3) ... [2018-11-06 22:38:55,767 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2f95a035 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.11 10:38:55, skipping insertion in model container [2018-11-06 22:38:55,767 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.11 10:38:55" (3/3) ... [2018-11-06 22:38:55,769 INFO L112 eAbstractionObserver]: Analyzing ICFG linear_sea.ch_true-unreach-call.i [2018-11-06 22:38:55,779 INFO L136 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-11-06 22:38:55,788 INFO L148 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-11-06 22:38:55,806 INFO L257 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2018-11-06 22:38:55,840 INFO L135 ementStrategyFactory]: Using default assertion order modulation [2018-11-06 22:38:55,840 INFO L382 AbstractCegarLoop]: Interprodecural is true [2018-11-06 22:38:55,841 INFO L383 AbstractCegarLoop]: Hoare is true [2018-11-06 22:38:55,841 INFO L384 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-11-06 22:38:55,841 INFO L385 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-11-06 22:38:55,841 INFO L386 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-11-06 22:38:55,841 INFO L387 AbstractCegarLoop]: Difference is false [2018-11-06 22:38:55,841 INFO L388 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-11-06 22:38:55,842 INFO L393 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-11-06 22:38:55,858 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states. [2018-11-06 22:38:55,865 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2018-11-06 22:38:55,865 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 22:38:55,867 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 22:38:55,869 INFO L423 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 22:38:55,875 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 22:38:55,876 INFO L82 PathProgramCache]: Analyzing trace with hash -760237379, now seen corresponding path program 1 times [2018-11-06 22:38:55,878 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 22:38:55,879 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 22:38:55,938 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 22:38:55,938 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 22:38:55,938 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 22:38:56,002 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 22:38:56,073 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 22:38:56,076 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-06 22:38:56,076 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-11-06 22:38:56,080 INFO L459 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-11-06 22:38:56,096 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-11-06 22:38:56,097 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-11-06 22:38:56,099 INFO L87 Difference]: Start difference. First operand 22 states. Second operand 2 states. [2018-11-06 22:38:56,117 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 22:38:56,118 INFO L93 Difference]: Finished difference Result 33 states and 38 transitions. [2018-11-06 22:38:56,118 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-11-06 22:38:56,119 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 10 [2018-11-06 22:38:56,120 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 22:38:56,131 INFO L225 Difference]: With dead ends: 33 [2018-11-06 22:38:56,132 INFO L226 Difference]: Without dead ends: 16 [2018-11-06 22:38:56,135 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-11-06 22:38:56,156 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 16 states. [2018-11-06 22:38:56,174 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 16 to 16. [2018-11-06 22:38:56,177 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 16 states. [2018-11-06 22:38:56,178 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 18 transitions. [2018-11-06 22:38:56,180 INFO L78 Accepts]: Start accepts. Automaton has 16 states and 18 transitions. Word has length 10 [2018-11-06 22:38:56,181 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 22:38:56,181 INFO L480 AbstractCegarLoop]: Abstraction has 16 states and 18 transitions. [2018-11-06 22:38:56,181 INFO L481 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-11-06 22:38:56,181 INFO L276 IsEmpty]: Start isEmpty. Operand 16 states and 18 transitions. [2018-11-06 22:38:56,183 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2018-11-06 22:38:56,184 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 22:38:56,184 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 22:38:56,184 INFO L423 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 22:38:56,187 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 22:38:56,187 INFO L82 PathProgramCache]: Analyzing trace with hash 1932954667, now seen corresponding path program 1 times [2018-11-06 22:38:56,187 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 22:38:56,188 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 22:38:56,189 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 22:38:56,189 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 22:38:56,189 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 22:38:56,299 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 22:38:56,605 WARN L179 SmtUtils]: Spent 194.00 ms on a formula simplification. DAG size of input: 11 DAG size of output: 6 [2018-11-06 22:38:56,830 WARN L179 SmtUtils]: Spent 125.00 ms on a formula simplification. DAG size of input: 21 DAG size of output: 8 [2018-11-06 22:38:56,885 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 22:38:56,885 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-06 22:38:56,885 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-11-06 22:38:56,887 INFO L459 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-11-06 22:38:56,887 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-11-06 22:38:56,888 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-11-06 22:38:56,888 INFO L87 Difference]: Start difference. First operand 16 states and 18 transitions. Second operand 4 states. [2018-11-06 22:38:57,007 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 22:38:57,009 INFO L93 Difference]: Finished difference Result 31 states and 34 transitions. [2018-11-06 22:38:57,009 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-11-06 22:38:57,009 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 13 [2018-11-06 22:38:57,009 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 22:38:57,010 INFO L225 Difference]: With dead ends: 31 [2018-11-06 22:38:57,010 INFO L226 Difference]: Without dead ends: 27 [2018-11-06 22:38:57,011 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 3 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-11-06 22:38:57,012 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2018-11-06 22:38:57,016 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 23. [2018-11-06 22:38:57,016 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 23 states. [2018-11-06 22:38:57,018 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 27 transitions. [2018-11-06 22:38:57,019 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 27 transitions. Word has length 13 [2018-11-06 22:38:57,019 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 22:38:57,019 INFO L480 AbstractCegarLoop]: Abstraction has 23 states and 27 transitions. [2018-11-06 22:38:57,019 INFO L481 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-11-06 22:38:57,020 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 27 transitions. [2018-11-06 22:38:57,020 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2018-11-06 22:38:57,020 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 22:38:57,021 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 22:38:57,021 INFO L423 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 22:38:57,021 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 22:38:57,021 INFO L82 PathProgramCache]: Analyzing trace with hash 1932895085, now seen corresponding path program 1 times [2018-11-06 22:38:57,022 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 22:38:57,022 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 22:38:57,023 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 22:38:57,023 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 22:38:57,024 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 22:38:57,062 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 22:38:57,157 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 22:38:57,158 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-06 22:38:57,158 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-11-06 22:38:57,159 INFO L459 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-11-06 22:38:57,159 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-11-06 22:38:57,160 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-11-06 22:38:57,160 INFO L87 Difference]: Start difference. First operand 23 states and 27 transitions. Second operand 4 states. [2018-11-06 22:38:57,255 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 22:38:57,255 INFO L93 Difference]: Finished difference Result 27 states and 30 transitions. [2018-11-06 22:38:57,257 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-11-06 22:38:57,257 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 13 [2018-11-06 22:38:57,257 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 22:38:57,258 INFO L225 Difference]: With dead ends: 27 [2018-11-06 22:38:57,258 INFO L226 Difference]: Without dead ends: 22 [2018-11-06 22:38:57,259 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-11-06 22:38:57,259 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2018-11-06 22:38:57,264 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 22. [2018-11-06 22:38:57,265 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 22 states. [2018-11-06 22:38:57,265 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 24 transitions. [2018-11-06 22:38:57,267 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 24 transitions. Word has length 13 [2018-11-06 22:38:57,267 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 22:38:57,267 INFO L480 AbstractCegarLoop]: Abstraction has 22 states and 24 transitions. [2018-11-06 22:38:57,267 INFO L481 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-11-06 22:38:57,267 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 24 transitions. [2018-11-06 22:38:57,268 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2018-11-06 22:38:57,269 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 22:38:57,269 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 22:38:57,269 INFO L423 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 22:38:57,269 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 22:38:57,269 INFO L82 PathProgramCache]: Analyzing trace with hash -1866436973, now seen corresponding path program 1 times [2018-11-06 22:38:57,270 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 22:38:57,270 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 22:38:57,272 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 22:38:57,272 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 22:38:57,272 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 22:38:57,303 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 22:38:57,384 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-06 22:38:57,384 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-06 22:38:57,384 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-11-06 22:38:57,385 INFO L459 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-11-06 22:38:57,385 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-11-06 22:38:57,385 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-11-06 22:38:57,386 INFO L87 Difference]: Start difference. First operand 22 states and 24 transitions. Second operand 3 states. [2018-11-06 22:38:57,406 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 22:38:57,407 INFO L93 Difference]: Finished difference Result 35 states and 39 transitions. [2018-11-06 22:38:57,407 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-11-06 22:38:57,407 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 17 [2018-11-06 22:38:57,407 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 22:38:57,408 INFO L225 Difference]: With dead ends: 35 [2018-11-06 22:38:57,408 INFO L226 Difference]: Without dead ends: 23 [2018-11-06 22:38:57,408 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 22:38:57,409 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2018-11-06 22:38:57,412 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-11-06 22:38:57,412 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 23 states. [2018-11-06 22:38:57,413 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-11-06 22:38:57,413 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 17 [2018-11-06 22:38:57,414 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 22:38:57,414 INFO L480 AbstractCegarLoop]: Abstraction has 23 states and 24 transitions. [2018-11-06 22:38:57,414 INFO L481 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-11-06 22:38:57,414 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 24 transitions. [2018-11-06 22:38:57,415 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2018-11-06 22:38:57,415 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 22:38:57,415 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 22:38:57,415 INFO L423 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 22:38:57,416 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 22:38:57,416 INFO L82 PathProgramCache]: Analyzing trace with hash 933989398, now seen corresponding path program 1 times [2018-11-06 22:38:57,416 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 22:38:57,416 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 22:38:57,417 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 22:38:57,417 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 22:38:57,418 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 22:38:57,455 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 22:38:58,048 WARN L179 SmtUtils]: Spent 368.00 ms on a formula simplification. DAG size of input: 136 DAG size of output: 27 [2018-11-06 22:38:58,253 WARN L179 SmtUtils]: Spent 174.00 ms on a formula simplification. DAG size of input: 97 DAG size of output: 26 [2018-11-06 22:38:58,748 WARN L179 SmtUtils]: Spent 104.00 ms on a formula simplification. DAG size of input: 103 DAG size of output: 20 [2018-11-06 22:38:59,224 WARN L179 SmtUtils]: Spent 362.00 ms on a formula simplification. DAG size of input: 90 DAG size of output: 21 [2018-11-06 22:38:59,459 WARN L179 SmtUtils]: Spent 161.00 ms on a formula simplification. DAG size of input: 107 DAG size of output: 24 [2018-11-06 22:38:59,464 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-06 22:38:59,464 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-06 22:38:59,465 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 22:38:59,482 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 22:38:59,525 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 22:38:59,536 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-06 22:38:59,595 WARN L307 Elim1Store]: Array PQE input equivalent to false [2018-11-06 22:38:59,595 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-11-06 22:38:59,635 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 18 [2018-11-06 22:38:59,638 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 17 [2018-11-06 22:38:59,639 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-11-06 22:38:59,643 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-06 22:38:59,652 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-06 22:38:59,652 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 2 variables, input treesize:91, output treesize:17 [2018-11-06 22:38:59,871 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 27 [2018-11-06 22:38:59,888 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 27 treesize of output 24 [2018-11-06 22:38:59,889 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-11-06 22:38:59,897 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-11-06 22:38:59,917 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-11-06 22:38:59,918 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:44, output treesize:52 [2018-11-06 22:39:00,416 WARN L179 SmtUtils]: Spent 105.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 18 [2018-11-06 22:39:00,429 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-06 22:39:00,458 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-11-06 22:39:00,458 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 10] total 17 [2018-11-06 22:39:00,459 INFO L459 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-11-06 22:39:00,459 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-11-06 22:39:00,460 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=230, Unknown=0, NotChecked=0, Total=272 [2018-11-06 22:39:00,461 INFO L87 Difference]: Start difference. First operand 23 states and 24 transitions. Second operand 17 states. [2018-11-06 22:39:00,904 WARN L179 SmtUtils]: Spent 119.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 40 [2018-11-06 22:39:01,372 WARN L179 SmtUtils]: Spent 199.00 ms on a formula simplification. DAG size of input: 69 DAG size of output: 43 [2018-11-06 22:39:01,517 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 22:39:01,518 INFO L93 Difference]: Finished difference Result 35 states and 37 transitions. [2018-11-06 22:39:01,521 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-11-06 22:39:01,521 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 19 [2018-11-06 22:39:01,522 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 22:39:01,522 INFO L225 Difference]: With dead ends: 35 [2018-11-06 22:39:01,522 INFO L226 Difference]: Without dead ends: 29 [2018-11-06 22:39:01,524 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 35 GetRequests, 12 SyntacticMatches, 1 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 72 ImplicationChecksByTransitivity, 3.2s TimeCoverageRelationStatistics Valid=116, Invalid=436, Unknown=0, NotChecked=0, Total=552 [2018-11-06 22:39:01,524 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2018-11-06 22:39:01,528 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 29. [2018-11-06 22:39:01,528 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 29 states. [2018-11-06 22:39:01,529 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 30 transitions. [2018-11-06 22:39:01,529 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 30 transitions. Word has length 19 [2018-11-06 22:39:01,530 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 22:39:01,530 INFO L480 AbstractCegarLoop]: Abstraction has 29 states and 30 transitions. [2018-11-06 22:39:01,530 INFO L481 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-11-06 22:39:01,530 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 30 transitions. [2018-11-06 22:39:01,531 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2018-11-06 22:39:01,531 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 22:39:01,531 INFO L375 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 22:39:01,532 INFO L423 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 22:39:01,532 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 22:39:01,532 INFO L82 PathProgramCache]: Analyzing trace with hash -1182945343, now seen corresponding path program 2 times [2018-11-06 22:39:01,532 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 22:39:01,532 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 22:39:01,534 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 22:39:01,534 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-06 22:39:01,534 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 22:39:01,577 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 22:39:08,134 WARN L179 SmtUtils]: Spent 6.17 s on a formula simplification. DAG size of input: 145 DAG size of output: 28 [2018-11-06 22:39:18,375 WARN L179 SmtUtils]: Spent 10.21 s on a formula simplification. DAG size of input: 142 DAG size of output: 40 [2018-11-06 22:39:22,842 WARN L179 SmtUtils]: Spent 4.35 s on a formula simplification. DAG size of input: 158 DAG size of output: 46 [2018-11-06 22:39:35,510 WARN L179 SmtUtils]: Spent 10.45 s on a formula simplification. DAG size of input: 179 DAG size of output: 48 [2018-11-06 22:39:38,050 WARN L179 SmtUtils]: Spent 2.48 s on a formula simplification. DAG size of input: 209 DAG size of output: 64 [2018-11-06 22:39:40,649 WARN L179 SmtUtils]: Spent 2.51 s on a formula simplification. DAG size of input: 207 DAG size of output: 59 [2018-11-06 22:39:43,193 WARN L179 SmtUtils]: Spent 2.41 s on a formula simplification. DAG size of input: 179 DAG size of output: 42 [2018-11-06 22:39:45,939 WARN L179 SmtUtils]: Spent 2.65 s on a formula simplification. DAG size of input: 178 DAG size of output: 41 [2018-11-06 22:39:48,138 WARN L179 SmtUtils]: Spent 2.13 s on a formula simplification. DAG size of input: 157 DAG size of output: 18 [2018-11-06 22:39:54,651 WARN L179 SmtUtils]: Spent 6.31 s on a formula simplification. DAG size of input: 141 DAG size of output: 27 [2018-11-06 22:39:58,899 WARN L179 SmtUtils]: Spent 4.13 s on a formula simplification. DAG size of input: 140 DAG size of output: 26 [2018-11-06 22:39:58,906 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-06 22:39:58,906 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-06 22:39:58,906 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 22:39:58,919 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-11-06 22:39:58,981 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-11-06 22:39:58,981 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-06 22:39:58,988 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-06 22:39:59,378 WARN L307 Elim1Store]: Array PQE input equivalent to false [2018-11-06 22:39:59,379 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-11-06 22:39:59,416 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 18 [2018-11-06 22:39:59,419 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 17 [2018-11-06 22:39:59,420 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-11-06 22:39:59,422 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-06 22:39:59,434 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-11-06 22:39:59,434 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 3 variables, input treesize:142, output treesize:30 [2018-11-06 22:40:04,233 WARN L179 SmtUtils]: Spent 110.00 ms on a formula simplification that was a NOOP. DAG size: 38 [2018-11-06 22:40:07,982 WARN L179 SmtUtils]: Spent 1.67 s on a formula simplification that was a NOOP. DAG size: 42 [2018-11-06 22:40:10,084 WARN L179 SmtUtils]: Spent 2.03 s on a formula simplification that was a NOOP. DAG size: 40 [2018-11-06 22:40:10,391 WARN L179 SmtUtils]: Spent 150.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 41 [2018-11-06 22:40:10,399 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 41 treesize of output 35 [2018-11-06 22:40:10,404 INFO L700 Elim1Store]: detected not equals via solver [2018-11-06 22:40:10,407 INFO L700 Elim1Store]: detected not equals via solver [2018-11-06 22:40:10,421 INFO L700 Elim1Store]: detected not equals via solver [2018-11-06 22:40:10,437 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 4 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 35 treesize of output 61 [2018-11-06 22:40:10,438 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-11-06 22:40:10,480 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-11-06 22:40:10,557 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 2 xjuncts. [2018-11-06 22:40:10,558 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:61, output treesize:98 [2018-11-06 22:40:13,455 WARN L179 SmtUtils]: Spent 2.78 s on a formula simplification that was a NOOP. DAG size: 44 [2018-11-06 22:40:16,121 WARN L179 SmtUtils]: Spent 456.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 41 [2018-11-06 22:40:19,703 WARN L179 SmtUtils]: Spent 1.50 s on a formula simplification that was a NOOP. DAG size: 33 [2018-11-06 22:40:19,977 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 2 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-06 22:40:19,997 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-11-06 22:40:19,997 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 15] total 27 [2018-11-06 22:40:19,998 INFO L459 AbstractCegarLoop]: Interpolant automaton has 27 states [2018-11-06 22:40:19,998 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2018-11-06 22:40:19,999 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=119, Invalid=581, Unknown=2, NotChecked=0, Total=702 [2018-11-06 22:40:19,999 INFO L87 Difference]: Start difference. First operand 29 states and 30 transitions. Second operand 27 states. [2018-11-06 22:40:22,559 WARN L179 SmtUtils]: Spent 2.24 s on a formula simplification. DAG size of input: 52 DAG size of output: 52 [2018-11-06 22:40:23,457 WARN L179 SmtUtils]: Spent 819.00 ms on a formula simplification that was a NOOP. DAG size: 47 [2018-11-06 22:40:23,917 WARN L179 SmtUtils]: Spent 228.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 63 [2018-11-06 22:40:26,384 WARN L179 SmtUtils]: Spent 2.40 s on a formula simplification. DAG size of input: 75 DAG size of output: 65 [2018-11-06 22:40:27,222 WARN L179 SmtUtils]: Spent 637.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 45 [2018-11-06 22:40:27,569 WARN L179 SmtUtils]: Spent 288.00 ms on a formula simplification. DAG size of input: 94 DAG size of output: 46 [2018-11-06 22:40:28,090 WARN L179 SmtUtils]: Spent 108.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 44 [2018-11-06 22:40:28,117 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 22:40:28,117 INFO L93 Difference]: Finished difference Result 50 states and 54 transitions. [2018-11-06 22:40:28,118 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-11-06 22:40:28,118 INFO L78 Accepts]: Start accepts. Automaton has 27 states. Word has length 25 [2018-11-06 22:40:28,118 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 22:40:28,119 INFO L225 Difference]: With dead ends: 50 [2018-11-06 22:40:28,119 INFO L226 Difference]: Without dead ends: 41 [2018-11-06 22:40:28,121 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 13 SyntacticMatches, 1 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 306 ImplicationChecksByTransitivity, 85.0s TimeCoverageRelationStatistics Valid=303, Invalid=1177, Unknown=2, NotChecked=0, Total=1482 [2018-11-06 22:40:28,122 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2018-11-06 22:40:28,126 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2018-11-06 22:40:28,127 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 41 states. [2018-11-06 22:40:28,128 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 42 transitions. [2018-11-06 22:40:28,128 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 42 transitions. Word has length 25 [2018-11-06 22:40:28,128 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 22:40:28,128 INFO L480 AbstractCegarLoop]: Abstraction has 41 states and 42 transitions. [2018-11-06 22:40:28,128 INFO L481 AbstractCegarLoop]: Interpolant automaton has 27 states. [2018-11-06 22:40:28,128 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 42 transitions. [2018-11-06 22:40:28,129 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2018-11-06 22:40:28,129 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 22:40:28,130 INFO L375 BasicCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 22:40:28,130 INFO L423 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 22:40:28,130 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 22:40:28,130 INFO L82 PathProgramCache]: Analyzing trace with hash 2012095063, now seen corresponding path program 3 times [2018-11-06 22:40:28,130 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 22:40:28,131 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 22:40:28,131 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 22:40:28,131 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-06 22:40:28,132 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 22:40:28,166 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 22:40:32,676 WARN L179 SmtUtils]: Spent 4.12 s on a formula simplification. DAG size of input: 102 DAG size of output: 24 [2018-11-06 22:40:34,803 WARN L179 SmtUtils]: Spent 2.11 s on a formula simplification. DAG size of input: 117 DAG size of output: 39 [2018-11-06 22:40:34,971 WARN L179 SmtUtils]: Spent 141.00 ms on a formula simplification. DAG size of input: 138 DAG size of output: 43 [2018-11-06 22:40:37,483 WARN L179 SmtUtils]: Spent 2.35 s on a formula simplification. DAG size of input: 162 DAG size of output: 48 [2018-11-06 22:40:39,924 WARN L179 SmtUtils]: Spent 2.28 s on a formula simplification. DAG size of input: 162 DAG size of output: 49 [2018-11-06 22:40:44,237 WARN L179 SmtUtils]: Spent 4.23 s on a formula simplification. DAG size of input: 180 DAG size of output: 50 [2018-11-06 22:40:48,531 WARN L179 SmtUtils]: Spent 4.23 s on a formula simplification. DAG size of input: 172 DAG size of output: 42 [2018-11-06 22:40:52,890 WARN L179 SmtUtils]: Spent 4.24 s on a formula simplification. DAG size of input: 171 DAG size of output: 41 [2018-11-06 22:40:57,235 WARN L179 SmtUtils]: Spent 4.22 s on a formula simplification. DAG size of input: 152 DAG size of output: 31 [2018-11-06 22:41:01,527 WARN L179 SmtUtils]: Spent 4.21 s on a formula simplification. DAG size of input: 166 DAG size of output: 30 [2018-11-06 22:41:03,946 WARN L179 SmtUtils]: Spent 2.17 s on a formula simplification. DAG size of input: 164 DAG size of output: 28 [2018-11-06 22:41:06,258 WARN L179 SmtUtils]: Spent 2.15 s on a formula simplification. DAG size of input: 151 DAG size of output: 23 [2018-11-06 22:41:08,574 WARN L179 SmtUtils]: Spent 2.13 s on a formula simplification. DAG size of input: 143 DAG size of output: 22 [2018-11-06 22:41:12,925 WARN L179 SmtUtils]: Spent 4.19 s on a formula simplification. DAG size of input: 118 DAG size of output: 37 [2018-11-06 22:41:15,196 WARN L179 SmtUtils]: Spent 2.17 s on a formula simplification. DAG size of input: 117 DAG size of output: 36 [2018-11-06 22:41:15,210 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 0 proven. 52 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-06 22:41:15,210 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-06 22:41:15,210 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 22:41:15,220 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-06 22:41:36,363 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2018-11-06 22:41:36,363 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-06 22:41:36,384 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-06 22:41:38,323 WARN L179 SmtUtils]: Spent 1.81 s on a formula simplification. DAG size of input: 35 DAG size of output: 13 [2018-11-06 22:41:38,398 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 45 treesize of output 42 [2018-11-06 22:41:38,401 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 17 [2018-11-06 22:41:38,401 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-06 22:41:38,415 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-06 22:41:38,420 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 44 treesize of output 41 [2018-11-06 22:41:38,424 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 17 [2018-11-06 22:41:38,424 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-11-06 22:41:38,442 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-06 22:41:38,489 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-11-06 22:41:38,489 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:142, output treesize:30 [2018-11-06 22:41:40,523 WARN L179 SmtUtils]: Spent 1.87 s on a formula simplification. DAG size of input: 39 DAG size of output: 32 [2018-11-06 22:41:41,161 WARN L179 SmtUtils]: Spent 144.00 ms on a formula simplification that was a NOOP. DAG size: 40 [2018-11-06 22:41:41,558 WARN L179 SmtUtils]: Spent 152.00 ms on a formula simplification that was a NOOP. DAG size: 44 [2018-11-06 22:41:46,518 WARN L179 SmtUtils]: Spent 4.35 s on a formula simplification. DAG size of input: 49 DAG size of output: 44 [2018-11-06 22:41:47,279 WARN L179 SmtUtils]: Spent 204.00 ms on a formula simplification that was a NOOP. DAG size: 48 [2018-11-06 22:41:48,603 WARN L179 SmtUtils]: Spent 952.00 ms on a formula simplification that was a NOOP. DAG size: 52 [2018-11-06 22:41:49,086 WARN L179 SmtUtils]: Spent 226.00 ms on a formula simplification that was a NOOP. DAG size: 50 [2018-11-06 22:41:54,469 WARN L179 SmtUtils]: Spent 4.30 s on a formula simplification. DAG size of input: 57 DAG size of output: 52 [2018-11-06 22:41:54,695 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 55 treesize of output 47 [2018-11-06 22:41:54,709 INFO L700 Elim1Store]: detected not equals via solver [2018-11-06 22:41:54,718 INFO L700 Elim1Store]: detected not equals via solver [2018-11-06 22:41:54,719 INFO L700 Elim1Store]: detected not equals via solver [2018-11-06 22:41:54,731 INFO L700 Elim1Store]: detected not equals via solver [2018-11-06 22:41:54,742 INFO L700 Elim1Store]: detected not equals via solver [2018-11-06 22:41:54,743 INFO L700 Elim1Store]: detected not equals via solver [2018-11-06 22:41:54,758 INFO L700 Elim1Store]: detected not equals via solver [2018-11-06 22:41:54,768 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 9 disjoint index pairs (out of 6 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 47 treesize of output 117 [2018-11-06 22:41:54,770 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-11-06 22:41:54,820 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-11-06 22:41:54,921 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 2 xjuncts. [2018-11-06 22:41:54,921 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:84, output treesize:152 [2018-11-06 22:41:56,583 WARN L179 SmtUtils]: Spent 155.00 ms on a formula simplification that was a NOOP. DAG size: 52 [2018-11-06 22:41:58,728 WARN L179 SmtUtils]: Spent 504.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 50 [2018-11-06 22:42:01,809 WARN L179 SmtUtils]: Spent 247.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 39 [2018-11-06 22:42:01,824 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 0 proven. 52 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-06 22:42:01,845 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-11-06 22:42:01,846 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 21] total 37 [2018-11-06 22:42:01,846 INFO L459 AbstractCegarLoop]: Interpolant automaton has 37 states [2018-11-06 22:42:01,847 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2018-11-06 22:42:01,848 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=141, Invalid=1190, Unknown=1, NotChecked=0, Total=1332 [2018-11-06 22:42:01,849 INFO L87 Difference]: Start difference. First operand 41 states and 42 transitions. Second operand 37 states. [2018-11-06 22:42:02,459 WARN L179 SmtUtils]: Spent 415.00 ms on a formula simplification that was a NOOP. DAG size: 39 [2018-11-06 22:42:02,639 WARN L179 SmtUtils]: Spent 112.00 ms on a formula simplification. DAG size of input: 68 DAG size of output: 50 [2018-11-06 22:42:04,821 WARN L179 SmtUtils]: Spent 2.04 s on a formula simplification that was a NOOP. DAG size: 39 [2018-11-06 22:42:05,195 WARN L179 SmtUtils]: Spent 298.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 48 [2018-11-06 22:42:05,460 WARN L179 SmtUtils]: Spent 175.00 ms on a formula simplification. DAG size of input: 76 DAG size of output: 44 [2018-11-06 22:42:05,815 WARN L179 SmtUtils]: Spent 203.00 ms on a formula simplification. DAG size of input: 81 DAG size of output: 49 [2018-11-06 22:42:08,433 WARN L179 SmtUtils]: Spent 2.51 s on a formula simplification. DAG size of input: 54 DAG size of output: 54 [2018-11-06 22:42:10,635 WARN L179 SmtUtils]: Spent 2.09 s on a formula simplification that was a NOOP. DAG size: 49 [2018-11-06 22:42:11,089 WARN L179 SmtUtils]: Spent 157.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 56 [2018-11-06 22:42:13,764 WARN L179 SmtUtils]: Spent 2.49 s on a formula simplification. DAG size of input: 62 DAG size of output: 62 [2018-11-06 22:42:14,075 WARN L179 SmtUtils]: Spent 116.00 ms on a formula simplification that was a NOOP. DAG size: 57 [2018-11-06 22:42:14,474 WARN L179 SmtUtils]: Spent 237.00 ms on a formula simplification that was a NOOP. DAG size: 59 [2018-11-06 22:42:16,988 WARN L179 SmtUtils]: Spent 2.31 s on a formula simplification. DAG size of input: 78 DAG size of output: 65 [2018-11-06 22:42:20,891 WARN L179 SmtUtils]: Spent 3.72 s on a formula simplification. DAG size of input: 81 DAG size of output: 75 [2018-11-06 22:42:22,033 WARN L179 SmtUtils]: Spent 1.02 s on a formula simplification. DAG size of input: 57 DAG size of output: 51 [2018-11-06 22:42:24,738 WARN L179 SmtUtils]: Spent 2.62 s on a formula simplification. DAG size of input: 59 DAG size of output: 52 [2018-11-06 22:42:27,260 WARN L179 SmtUtils]: Spent 123.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 47 [2018-11-06 22:42:27,327 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 22:42:27,328 INFO L93 Difference]: Finished difference Result 54 states and 56 transitions. [2018-11-06 22:42:27,328 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-11-06 22:42:27,328 INFO L78 Accepts]: Start accepts. Automaton has 37 states. Word has length 37 [2018-11-06 22:42:27,329 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 22:42:27,329 INFO L225 Difference]: With dead ends: 54 [2018-11-06 22:42:27,329 INFO L226 Difference]: Without dead ends: 47 [2018-11-06 22:42:27,335 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 75 GetRequests, 19 SyntacticMatches, 3 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 724 ImplicationChecksByTransitivity, 93.7s TimeCoverageRelationStatistics Valid=376, Invalid=2593, Unknown=1, NotChecked=0, Total=2970 [2018-11-06 22:42:27,335 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2018-11-06 22:42:27,342 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2018-11-06 22:42:27,343 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 47 states. [2018-11-06 22:42:27,343 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 48 transitions. [2018-11-06 22:42:27,344 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 48 transitions. Word has length 37 [2018-11-06 22:42:27,344 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 22:42:27,345 INFO L480 AbstractCegarLoop]: Abstraction has 47 states and 48 transitions. [2018-11-06 22:42:27,345 INFO L481 AbstractCegarLoop]: Interpolant automaton has 37 states. [2018-11-06 22:42:27,345 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 48 transitions. [2018-11-06 22:42:27,346 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2018-11-06 22:42:27,346 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 22:42:27,346 INFO L375 BasicCegarLoop]: trace histogram [6, 6, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 22:42:27,347 INFO L423 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 22:42:27,347 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 22:42:27,347 INFO L82 PathProgramCache]: Analyzing trace with hash -1788030654, now seen corresponding path program 4 times [2018-11-06 22:42:27,348 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 22:42:27,348 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 22:42:27,348 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 22:42:27,349 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-06 22:42:27,349 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 22:42:27,397 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 22:42:27,965 WARN L179 SmtUtils]: Spent 124.00 ms on a formula simplification. DAG size of input: 154 DAG size of output: 31 [2018-11-06 22:42:28,206 WARN L179 SmtUtils]: Spent 219.00 ms on a formula simplification. DAG size of input: 176 DAG size of output: 42 [2018-11-06 22:42:28,446 WARN L179 SmtUtils]: Spent 206.00 ms on a formula simplification. DAG size of input: 198 DAG size of output: 43 [2018-11-06 22:42:28,976 WARN L179 SmtUtils]: Spent 340.00 ms on a formula simplification. DAG size of input: 238 DAG size of output: 50 [2018-11-06 22:42:29,506 WARN L179 SmtUtils]: Spent 370.00 ms on a formula simplification. DAG size of input: 244 DAG size of output: 53 [2018-11-06 22:42:30,135 WARN L179 SmtUtils]: Spent 292.00 ms on a formula simplification. DAG size of input: 241 DAG size of output: 48 [2018-11-06 22:42:30,599 WARN L179 SmtUtils]: Spent 369.00 ms on a formula simplification. DAG size of input: 298 DAG size of output: 59 [2018-11-06 22:42:31,020 WARN L179 SmtUtils]: Spent 325.00 ms on a formula simplification. DAG size of input: 291 DAG size of output: 50 [2018-11-06 22:42:31,482 WARN L179 SmtUtils]: Spent 353.00 ms on a formula simplification. DAG size of input: 290 DAG size of output: 49 [2018-11-06 22:42:31,777 WARN L179 SmtUtils]: Spent 214.00 ms on a formula simplification. DAG size of input: 201 DAG size of output: 41 [2018-11-06 22:42:32,037 WARN L179 SmtUtils]: Spent 174.00 ms on a formula simplification. DAG size of input: 200 DAG size of output: 39 [2018-11-06 22:42:32,350 WARN L179 SmtUtils]: Spent 209.00 ms on a formula simplification. DAG size of input: 210 DAG size of output: 47 [2018-11-06 22:42:32,659 WARN L179 SmtUtils]: Spent 185.00 ms on a formula simplification. DAG size of input: 208 DAG size of output: 39 [2018-11-06 22:42:33,038 WARN L179 SmtUtils]: Spent 234.00 ms on a formula simplification. DAG size of input: 190 DAG size of output: 36 [2018-11-06 22:42:33,393 WARN L179 SmtUtils]: Spent 215.00 ms on a formula simplification. DAG size of input: 184 DAG size of output: 33 [2018-11-06 22:42:33,686 WARN L179 SmtUtils]: Spent 169.00 ms on a formula simplification. DAG size of input: 156 DAG size of output: 32 [2018-11-06 22:42:33,975 WARN L179 SmtUtils]: Spent 153.00 ms on a formula simplification. DAG size of input: 155 DAG size of output: 30 [2018-11-06 22:42:34,000 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 0 proven. 80 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-06 22:42:34,000 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-06 22:42:34,001 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 22:42:34,017 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-11-06 22:42:34,107 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-11-06 22:42:34,107 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-06 22:42:34,111 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-06 22:42:34,152 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 24 [2018-11-06 22:42:34,167 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 17 [2018-11-06 22:42:34,168 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-06 22:42:34,233 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-06 22:42:34,272 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 28 treesize of output 25 [2018-11-06 22:42:34,274 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 17 [2018-11-06 22:42:34,275 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-11-06 22:42:34,278 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-06 22:42:34,293 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-06 22:42:34,293 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 2 variables, input treesize:91, output treesize:17 [2018-11-06 22:42:34,765 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 54 treesize of output 50 [2018-11-06 22:42:34,770 INFO L700 Elim1Store]: detected not equals via solver [2018-11-06 22:42:34,771 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 20 [2018-11-06 22:42:34,772 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-06 22:42:34,785 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-06 22:42:34,789 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 52 treesize of output 48 [2018-11-06 22:42:34,804 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 27 treesize of output 24 [2018-11-06 22:42:34,804 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 2 xjuncts. [2018-11-06 22:42:34,827 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-11-06 22:42:34,878 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 3 xjuncts. [2018-11-06 22:42:34,879 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:107, output treesize:87 [2018-11-06 22:42:35,894 WARN L179 SmtUtils]: Spent 112.00 ms on a formula simplification. DAG size of input: 32 DAG size of output: 30 [2018-11-06 22:42:36,295 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 5 proven. 75 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-06 22:42:36,315 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-11-06 22:42:36,316 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 16] total 34 [2018-11-06 22:42:36,316 INFO L459 AbstractCegarLoop]: Interpolant automaton has 34 states [2018-11-06 22:42:36,316 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2018-11-06 22:42:36,317 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=91, Invalid=1031, Unknown=0, NotChecked=0, Total=1122 [2018-11-06 22:42:36,317 INFO L87 Difference]: Start difference. First operand 47 states and 48 transitions. Second operand 34 states. [2018-11-06 22:42:36,879 WARN L179 SmtUtils]: Spent 120.00 ms on a formula simplification. DAG size of input: 80 DAG size of output: 49 [2018-11-06 22:42:37,061 WARN L179 SmtUtils]: Spent 106.00 ms on a formula simplification. DAG size of input: 97 DAG size of output: 44 [2018-11-06 22:42:37,497 WARN L179 SmtUtils]: Spent 111.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 48 [2018-11-06 22:42:37,824 WARN L179 SmtUtils]: Spent 182.00 ms on a formula simplification. DAG size of input: 103 DAG size of output: 56 [2018-11-06 22:42:38,126 WARN L179 SmtUtils]: Spent 103.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 47 [2018-11-06 22:42:38,442 WARN L179 SmtUtils]: Spent 161.00 ms on a formula simplification. DAG size of input: 103 DAG size of output: 55 [2018-11-06 22:42:38,885 WARN L179 SmtUtils]: Spent 322.00 ms on a formula simplification. DAG size of input: 127 DAG size of output: 62 [2018-11-06 22:42:39,592 WARN L179 SmtUtils]: Spent 536.00 ms on a formula simplification. DAG size of input: 122 DAG size of output: 60 [2018-11-06 22:42:39,932 WARN L179 SmtUtils]: Spent 128.00 ms on a formula simplification. DAG size of input: 84 DAG size of output: 46 [2018-11-06 22:42:40,398 WARN L179 SmtUtils]: Spent 225.00 ms on a formula simplification. DAG size of input: 100 DAG size of output: 54 [2018-11-06 22:42:40,918 WARN L179 SmtUtils]: Spent 148.00 ms on a formula simplification. DAG size of input: 82 DAG size of output: 46 [2018-11-06 22:42:42,513 WARN L179 SmtUtils]: Spent 1.38 s on a formula simplification. DAG size of input: 99 DAG size of output: 54 [2018-11-06 22:42:42,871 WARN L179 SmtUtils]: Spent 183.00 ms on a formula simplification. DAG size of input: 91 DAG size of output: 43 [2018-11-06 22:42:43,248 WARN L179 SmtUtils]: Spent 150.00 ms on a formula simplification. DAG size of input: 82 DAG size of output: 45 [2018-11-06 22:42:43,650 WARN L179 SmtUtils]: Spent 120.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 43 [2018-11-06 22:42:44,148 WARN L179 SmtUtils]: Spent 191.00 ms on a formula simplification. DAG size of input: 67 DAG size of output: 47 [2018-11-06 22:42:44,448 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-06 22:42:44,448 INFO L93 Difference]: Finished difference Result 60 states and 62 transitions. [2018-11-06 22:42:44,453 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2018-11-06 22:42:44,453 INFO L78 Accepts]: Start accepts. Automaton has 34 states. Word has length 43 [2018-11-06 22:42:44,453 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-06 22:42:44,454 INFO L225 Difference]: With dead ends: 60 [2018-11-06 22:42:44,454 INFO L226 Difference]: Without dead ends: 53 [2018-11-06 22:42:44,455 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 83 GetRequests, 30 SyntacticMatches, 2 SemanticMatches, 51 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 471 ImplicationChecksByTransitivity, 14.5s TimeCoverageRelationStatistics Valid=302, Invalid=2454, Unknown=0, NotChecked=0, Total=2756 [2018-11-06 22:42:44,456 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2018-11-06 22:42:44,462 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 53. [2018-11-06 22:42:44,462 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 53 states. [2018-11-06 22:42:44,463 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 54 transitions. [2018-11-06 22:42:44,463 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 54 transitions. Word has length 43 [2018-11-06 22:42:44,463 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-06 22:42:44,463 INFO L480 AbstractCegarLoop]: Abstraction has 53 states and 54 transitions. [2018-11-06 22:42:44,463 INFO L481 AbstractCegarLoop]: Interpolant automaton has 34 states. [2018-11-06 22:42:44,464 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 54 transitions. [2018-11-06 22:42:44,465 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2018-11-06 22:42:44,465 INFO L367 BasicCegarLoop]: Found error trace [2018-11-06 22:42:44,465 INFO L375 BasicCegarLoop]: trace histogram [7, 7, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-06 22:42:44,465 INFO L423 AbstractCegarLoop]: === Iteration 9 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-06 22:42:44,465 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-06 22:42:44,466 INFO L82 PathProgramCache]: Analyzing trace with hash 671704045, now seen corresponding path program 5 times [2018-11-06 22:42:44,466 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-06 22:42:44,466 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-06 22:42:44,467 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 22:42:44,467 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-06 22:42:44,467 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-06 22:42:44,499 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-06 22:42:47,039 WARN L179 SmtUtils]: Spent 2.13 s on a formula simplification. DAG size of input: 114 DAG size of output: 24 [2018-11-06 22:43:05,305 WARN L179 SmtUtils]: Spent 18.25 s on a formula simplification. DAG size of input: 134 DAG size of output: 40 [2018-11-06 22:43:07,533 WARN L179 SmtUtils]: Spent 2.20 s on a formula simplification. DAG size of input: 154 DAG size of output: 46 [2018-11-06 22:43:07,903 WARN L179 SmtUtils]: Spent 291.00 ms on a formula simplification. DAG size of input: 175 DAG size of output: 50 [2018-11-06 22:43:12,252 WARN L179 SmtUtils]: Spent 4.31 s on a formula simplification. DAG size of input: 175 DAG size of output: 51 [2018-11-06 22:43:12,560 WARN L179 SmtUtils]: Spent 264.00 ms on a formula simplification. DAG size of input: 175 DAG size of output: 50 [2018-11-06 22:43:25,044 WARN L179 SmtUtils]: Spent 12.42 s on a formula simplification. DAG size of input: 188 DAG size of output: 70 Received shutdown request... [2018-11-06 22:43:35,469 WARN L187 SmtUtils]: Removed 7 from assertion stack [2018-11-06 22:43:35,470 WARN L549 AbstractCegarLoop]: Verification canceled [2018-11-06 22:43:35,473 WARN L205 ceAbstractionStarter]: Timeout [2018-11-06 22:43:35,473 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 06.11 10:43:35 BoogieIcfgContainer [2018-11-06 22:43:35,474 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-11-06 22:43:35,474 INFO L168 Benchmark]: Toolchain (without parser) took 280646.60 ms. Allocated memory was 1.5 GB in the beginning and 2.5 GB in the end (delta: 947.9 MB). Free memory was 1.4 GB in the beginning and 1.8 GB in the end (delta: -383.6 MB). Peak memory consumption was 564.3 MB. Max. memory is 7.1 GB. [2018-11-06 22:43:35,475 INFO L168 Benchmark]: CDTParser took 0.24 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 22:43:35,476 INFO L168 Benchmark]: CACSL2BoogieTranslator took 321.11 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: 10.6 MB). Peak memory consumption was 10.6 MB. Max. memory is 7.1 GB. [2018-11-06 22:43:35,476 INFO L168 Benchmark]: Boogie Procedure Inliner took 51.05 ms. Allocated memory is still 1.5 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-11-06 22:43:35,476 INFO L168 Benchmark]: Boogie Preprocessor took 30.38 ms. Allocated memory is still 1.5 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-11-06 22:43:35,477 INFO L168 Benchmark]: RCFGBuilder took 526.82 ms. Allocated memory was 1.5 GB in the beginning and 2.3 GB in the end (delta: 746.1 MB). Free memory was 1.4 GB in the beginning and 2.2 GB in the end (delta: -791.9 MB). Peak memory consumption was 15.1 MB. Max. memory is 7.1 GB. [2018-11-06 22:43:35,477 INFO L168 Benchmark]: TraceAbstraction took 279712.23 ms. Allocated memory was 2.3 GB in the beginning and 2.5 GB in the end (delta: 201.9 MB). Free memory was 2.2 GB in the beginning and 1.8 GB in the end (delta: 397.8 MB). Peak memory consumption was 599.6 MB. Max. memory is 7.1 GB. [2018-11-06 22:43:35,480 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.24 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 321.11 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: 10.6 MB). Peak memory consumption was 10.6 MB. Max. memory is 7.1 GB. * Boogie Procedure Inliner took 51.05 ms. Allocated memory is still 1.5 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. * Boogie Preprocessor took 30.38 ms. Allocated memory is still 1.5 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. * RCFGBuilder took 526.82 ms. Allocated memory was 1.5 GB in the beginning and 2.3 GB in the end (delta: 746.1 MB). Free memory was 1.4 GB in the beginning and 2.2 GB in the end (delta: -791.9 MB). Peak memory consumption was 15.1 MB. Max. memory is 7.1 GB. * TraceAbstraction took 279712.23 ms. Allocated memory was 2.3 GB in the beginning and 2.5 GB in the end (delta: 201.9 MB). Free memory was 2.2 GB in the beginning and 1.8 GB in the end (delta: 397.8 MB). Peak memory consumption was 599.6 MB. Max. memory is 7.1 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 5]: Timeout (TraceAbstraction) Unable to prove that call of __VERIFIER_error() unreachable (line 5). Cancelled while BasicCegarLoop was analyzing trace of length 50 with TraceHistMax 7,while InterpolatingTraceCheckCraig was constructing Craig interpolants,while PredicateUnifier was unifying predicates,while SimplifyDDAWithTimeout was simplifying term of DAG size 180. - StatisticsResult: Ultimate Automizer benchmark data CFG has 1 procedures, 22 locations, 1 error locations. TIMEOUT Result, 279.6s OverallTime, 9 OverallIterations, 7 TraceHistogramMax, 43.1s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 123 SDtfs, 662 SDslu, 630 SDs, 0 SdLazy, 1644 SolverSat, 169 SolverUnsat, 2 SolverUnknown, 0 SolverNotchecked, 5.7s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 261 GetRequests, 82 SyntacticMatches, 10 SemanticMatches, 169 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1573 ImplicationChecksByTransitivity, 197.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=53occurred in iteration=8, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 8 MinimizatonAttempts, 4 StatesRemovedByMinimization, 1 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 21.6s SatisfiabilityAnalysisTime, 163.3s InterpolantComputationTime, 301 NumberOfCodeBlocks, 301 NumberOfCodeBlocksAsserted, 18 NumberOfCheckSat, 289 ConstructedInterpolants, 49 QuantifiedInterpolants, 442139 SizeOfPredicates, 65 NumberOfNonLiveVariables, 328 ConjunctsInSsa, 166 ConjunctsInUnsatCore, 12 InterpolantComputations, 4 PerfectInterpolantSequences, 11/304 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Completed graceful shutdown