java -Xmx8000000000 -jar /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/data -tc ../../../trunk/examples/toolchains/AutomizerCInline.xml -s ../../../trunk/examples/settings/default/taipan/svcomp-Reach-64bit-Taipan_Default.epf -i ../../../trunk/examples/svcomp/loops/linear_search_false-unreach-call.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-b6335f6 [2018-10-23 09:51:05,276 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-10-23 09:51:05,278 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-10-23 09:51:05,290 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-10-23 09:51:05,291 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-10-23 09:51:05,292 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-10-23 09:51:05,293 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-10-23 09:51:05,296 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-10-23 09:51:05,302 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-10-23 09:51:05,303 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-10-23 09:51:05,304 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-10-23 09:51:05,304 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-10-23 09:51:05,307 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-10-23 09:51:05,308 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-10-23 09:51:05,309 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-10-23 09:51:05,319 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-10-23 09:51:05,320 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-10-23 09:51:05,322 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-10-23 09:51:05,324 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-10-23 09:51:05,328 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-10-23 09:51:05,329 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-10-23 09:51:05,332 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-10-23 09:51:05,337 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-10-23 09:51:05,337 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-10-23 09:51:05,337 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-10-23 09:51:05,341 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-10-23 09:51:05,342 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-10-23 09:51:05,344 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-10-23 09:51:05,347 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-10-23 09:51:05,348 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-10-23 09:51:05,348 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-10-23 09:51:05,350 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-10-23 09:51:05,350 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-10-23 09:51:05,350 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-10-23 09:51:05,351 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-10-23 09:51:05,354 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-10-23 09:51:05,354 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/../../../trunk/examples/settings/default/taipan/svcomp-Reach-64bit-Taipan_Default.epf [2018-10-23 09:51:05,385 INFO L110 SettingsManager]: Loading preferences was successful [2018-10-23 09:51:05,385 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-10-23 09:51:05,389 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-10-23 09:51:05,389 INFO L133 SettingsManager]: * User list type=DISABLED [2018-10-23 09:51:05,390 INFO L133 SettingsManager]: * calls to implemented procedures=false [2018-10-23 09:51:05,390 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-10-23 09:51:05,390 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2018-10-23 09:51:05,390 INFO L133 SettingsManager]: * Abstract domain=CompoundDomain [2018-10-23 09:51:05,390 INFO L133 SettingsManager]: * Log string format=TERM [2018-10-23 09:51:05,391 INFO L133 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2018-10-23 09:51:05,391 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-10-23 09:51:05,391 INFO L133 SettingsManager]: * Interval Domain=false [2018-10-23 09:51:05,395 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-10-23 09:51:05,395 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-10-23 09:51:05,395 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-10-23 09:51:05,396 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-10-23 09:51:05,396 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-10-23 09:51:05,396 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-10-23 09:51:05,396 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-10-23 09:51:05,396 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-10-23 09:51:05,397 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-10-23 09:51:05,398 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-10-23 09:51:05,399 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-10-23 09:51:05,399 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-10-23 09:51:05,399 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-10-23 09:51:05,399 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-10-23 09:51:05,400 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-10-23 09:51:05,400 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-10-23 09:51:05,400 INFO L133 SettingsManager]: * Trace refinement strategy=TAIPAN [2018-10-23 09:51:05,400 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-10-23 09:51:05,400 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-10-23 09:51:05,401 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-10-23 09:51:05,401 INFO L133 SettingsManager]: * To the following directory=dump/ [2018-10-23 09:51:05,401 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-10-23 09:51:05,470 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-10-23 09:51:05,484 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-10-23 09:51:05,487 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-10-23 09:51:05,488 INFO L271 PluginConnector]: Initializing CDTParser... [2018-10-23 09:51:05,489 INFO L276 PluginConnector]: CDTParser initialized [2018-10-23 09:51:05,489 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/../../../trunk/examples/svcomp/loops/linear_search_false-unreach-call.i [2018-10-23 09:51:05,550 INFO L218 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/data/91b57c090/4f797a4496114ad1b5f9f41f74ee1faa/FLAG6a9fc1d58 [2018-10-23 09:51:06,004 INFO L298 CDTParser]: Found 1 translation units. [2018-10-23 09:51:06,005 INFO L158 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/loops/linear_search_false-unreach-call.i [2018-10-23 09:51:06,011 INFO L346 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/data/91b57c090/4f797a4496114ad1b5f9f41f74ee1faa/FLAG6a9fc1d58 [2018-10-23 09:51:06,028 INFO L354 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/data/91b57c090/4f797a4496114ad1b5f9f41f74ee1faa [2018-10-23 09:51:06,041 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-10-23 09:51:06,043 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2018-10-23 09:51:06,044 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-10-23 09:51:06,044 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-10-23 09:51:06,048 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-10-23 09:51:06,049 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.10 09:51:06" (1/1) ... [2018-10-23 09:51:06,052 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2c0d6973 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.10 09:51:06, skipping insertion in model container [2018-10-23 09:51:06,053 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.10 09:51:06" (1/1) ... [2018-10-23 09:51:06,063 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2018-10-23 09:51:06,082 INFO L174 MainTranslator]: Built tables and reachable declarations [2018-10-23 09:51:06,271 INFO L202 PostProcessor]: Analyzing one entry point: main [2018-10-23 09:51:06,283 INFO L189 MainTranslator]: Completed pre-run [2018-10-23 09:51:06,305 INFO L202 PostProcessor]: Analyzing one entry point: main [2018-10-23 09:51:06,324 INFO L193 MainTranslator]: Completed translation [2018-10-23 09:51:06,325 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.10 09:51:06 WrapperNode [2018-10-23 09:51:06,325 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-10-23 09:51:06,326 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2018-10-23 09:51:06,326 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2018-10-23 09:51:06,326 INFO L276 PluginConnector]: Boogie Procedure Inliner initialized [2018-10-23 09:51:06,336 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.10 09:51:06" (1/1) ... [2018-10-23 09:51:06,346 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.10 09:51:06" (1/1) ... [2018-10-23 09:51:06,370 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2018-10-23 09:51:06,371 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-10-23 09:51:06,371 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-10-23 09:51:06,371 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-10-23 09:51:06,382 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.10 09:51:06" (1/1) ... [2018-10-23 09:51:06,383 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.10 09:51:06" (1/1) ... [2018-10-23 09:51:06,384 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.10 09:51:06" (1/1) ... [2018-10-23 09:51:06,385 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.10 09:51:06" (1/1) ... [2018-10-23 09:51:06,391 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.10 09:51:06" (1/1) ... [2018-10-23 09:51:06,396 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.10 09:51:06" (1/1) ... [2018-10-23 09:51:06,401 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.10 09:51:06" (1/1) ... [2018-10-23 09:51:06,403 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-10-23 09:51:06,404 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-10-23 09:51:06,404 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-10-23 09:51:06,404 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-10-23 09:51:06,405 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.10 09:51:06" (1/1) ... No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-10-23 09:51:06,573 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-10-23 09:51:06,573 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-10-23 09:51:06,573 INFO L130 BoogieDeclarations]: Found specification of procedure linear_search [2018-10-23 09:51:06,573 INFO L138 BoogieDeclarations]: Found implementation of procedure linear_search [2018-10-23 09:51:06,573 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-10-23 09:51:06,574 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-10-23 09:51:06,574 INFO L130 BoogieDeclarations]: Found specification of procedure main [2018-10-23 09:51:06,574 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2018-10-23 09:51:06,574 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2018-10-23 09:51:06,574 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2018-10-23 09:51:07,046 INFO L341 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-10-23 09:51:07,047 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.10 09:51:07 BoogieIcfgContainer [2018-10-23 09:51:07,047 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-10-23 09:51:07,051 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-10-23 09:51:07,051 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-10-23 09:51:07,057 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-10-23 09:51:07,057 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 23.10 09:51:06" (1/3) ... [2018-10-23 09:51:07,058 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6bdfa0ba and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.10 09:51:07, skipping insertion in model container [2018-10-23 09:51:07,058 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.10 09:51:06" (2/3) ... [2018-10-23 09:51:07,059 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6bdfa0ba and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.10 09:51:07, skipping insertion in model container [2018-10-23 09:51:07,059 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.10 09:51:07" (3/3) ... [2018-10-23 09:51:07,061 INFO L112 eAbstractionObserver]: Analyzing ICFG linear_search_false-unreach-call.i [2018-10-23 09:51:07,071 INFO L136 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-10-23 09:51:07,082 INFO L148 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-10-23 09:51:07,099 INFO L257 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2018-10-23 09:51:07,133 INFO L382 AbstractCegarLoop]: Interprodecural is true [2018-10-23 09:51:07,134 INFO L383 AbstractCegarLoop]: Hoare is true [2018-10-23 09:51:07,134 INFO L384 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-10-23 09:51:07,134 INFO L385 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-10-23 09:51:07,134 INFO L386 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-10-23 09:51:07,134 INFO L387 AbstractCegarLoop]: Difference is false [2018-10-23 09:51:07,135 INFO L388 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-10-23 09:51:07,135 INFO L393 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-10-23 09:51:07,155 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states. [2018-10-23 09:51:07,162 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2018-10-23 09:51:07,162 INFO L367 BasicCegarLoop]: Found error trace [2018-10-23 09:51:07,163 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-23 09:51:07,166 INFO L424 AbstractCegarLoop]: === Iteration 1 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-23 09:51:07,174 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-23 09:51:07,175 INFO L82 PathProgramCache]: Analyzing trace with hash 1855752643, now seen corresponding path program 1 times [2018-10-23 09:51:07,178 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-23 09:51:07,227 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:51:07,227 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-23 09:51:07,228 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:51:07,228 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-23 09:51:07,326 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:51:07,398 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:51:07,401 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-23 09:51:07,401 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-10-23 09:51:07,401 INFO L258 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-10-23 09:51:07,405 INFO L460 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-10-23 09:51:07,417 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-10-23 09:51:07,418 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-10-23 09:51:07,420 INFO L87 Difference]: Start difference. First operand 29 states. Second operand 2 states. [2018-10-23 09:51:07,445 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-23 09:51:07,446 INFO L93 Difference]: Finished difference Result 45 states and 52 transitions. [2018-10-23 09:51:07,446 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-10-23 09:51:07,447 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 17 [2018-10-23 09:51:07,448 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-23 09:51:07,459 INFO L225 Difference]: With dead ends: 45 [2018-10-23 09:51:07,459 INFO L226 Difference]: Without dead ends: 22 [2018-10-23 09:51:07,465 INFO L605 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-10-23 09:51:07,483 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2018-10-23 09:51:07,499 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 22. [2018-10-23 09:51:07,500 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 22 states. [2018-10-23 09:51:07,502 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 25 transitions. [2018-10-23 09:51:07,504 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 25 transitions. Word has length 17 [2018-10-23 09:51:07,504 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-23 09:51:07,505 INFO L481 AbstractCegarLoop]: Abstraction has 22 states and 25 transitions. [2018-10-23 09:51:07,505 INFO L482 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-10-23 09:51:07,505 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 25 transitions. [2018-10-23 09:51:07,506 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-10-23 09:51:07,506 INFO L367 BasicCegarLoop]: Found error trace [2018-10-23 09:51:07,506 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-23 09:51:07,507 INFO L424 AbstractCegarLoop]: === Iteration 2 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-23 09:51:07,507 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-23 09:51:07,507 INFO L82 PathProgramCache]: Analyzing trace with hash -1049182020, now seen corresponding path program 1 times [2018-10-23 09:51:07,508 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-23 09:51:07,509 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:51:07,509 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-23 09:51:07,509 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:51:07,509 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-23 09:51:07,608 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:51:07,899 WARN L179 SmtUtils]: Spent 106.00 ms on a formula simplification. DAG size of input: 24 DAG size of output: 17 [2018-10-23 09:51:08,053 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:51:08,054 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-23 09:51:08,054 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-10-23 09:51:08,054 INFO L258 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-10-23 09:51:08,056 INFO L460 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-10-23 09:51:08,056 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-10-23 09:51:08,057 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2018-10-23 09:51:08,057 INFO L87 Difference]: Start difference. First operand 22 states and 25 transitions. Second operand 6 states. [2018-10-23 09:51:08,255 WARN L179 SmtUtils]: Spent 153.00 ms on a formula simplification that was a NOOP. DAG size: 19 [2018-10-23 09:51:08,619 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-23 09:51:08,620 INFO L93 Difference]: Finished difference Result 41 states and 48 transitions. [2018-10-23 09:51:08,620 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-10-23 09:51:08,620 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 20 [2018-10-23 09:51:08,621 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-23 09:51:08,624 INFO L225 Difference]: With dead ends: 41 [2018-10-23 09:51:08,624 INFO L226 Difference]: Without dead ends: 33 [2018-10-23 09:51:08,625 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=28, Invalid=44, Unknown=0, NotChecked=0, Total=72 [2018-10-23 09:51:08,626 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2018-10-23 09:51:08,632 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 27. [2018-10-23 09:51:08,633 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 27 states. [2018-10-23 09:51:08,634 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 32 transitions. [2018-10-23 09:51:08,634 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 32 transitions. Word has length 20 [2018-10-23 09:51:08,634 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-23 09:51:08,635 INFO L481 AbstractCegarLoop]: Abstraction has 27 states and 32 transitions. [2018-10-23 09:51:08,635 INFO L482 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-10-23 09:51:08,635 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 32 transitions. [2018-10-23 09:51:08,636 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-10-23 09:51:08,636 INFO L367 BasicCegarLoop]: Found error trace [2018-10-23 09:51:08,636 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-23 09:51:08,636 INFO L424 AbstractCegarLoop]: === Iteration 3 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-23 09:51:08,637 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-23 09:51:08,637 INFO L82 PathProgramCache]: Analyzing trace with hash 1502974941, now seen corresponding path program 1 times [2018-10-23 09:51:08,637 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-23 09:51:08,638 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:51:08,639 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-23 09:51:08,639 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:51:08,639 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-23 09:51:08,657 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:51:08,819 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:51:08,821 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-23 09:51:08,821 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-10-23 09:51:08,821 INFO L258 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-10-23 09:51:08,824 INFO L460 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-10-23 09:51:08,824 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-10-23 09:51:08,825 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-10-23 09:51:08,825 INFO L87 Difference]: Start difference. First operand 27 states and 32 transitions. Second operand 6 states. [2018-10-23 09:51:08,901 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-23 09:51:08,901 INFO L93 Difference]: Finished difference Result 35 states and 39 transitions. [2018-10-23 09:51:08,902 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-10-23 09:51:08,902 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 20 [2018-10-23 09:51:08,902 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-23 09:51:08,903 INFO L225 Difference]: With dead ends: 35 [2018-10-23 09:51:08,903 INFO L226 Difference]: Without dead ends: 26 [2018-10-23 09:51:08,905 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2018-10-23 09:51:08,905 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2018-10-23 09:51:08,909 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2018-10-23 09:51:08,909 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 26 states. [2018-10-23 09:51:08,910 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 29 transitions. [2018-10-23 09:51:08,910 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 29 transitions. Word has length 20 [2018-10-23 09:51:08,911 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-23 09:51:08,911 INFO L481 AbstractCegarLoop]: Abstraction has 26 states and 29 transitions. [2018-10-23 09:51:08,911 INFO L482 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-10-23 09:51:08,911 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 29 transitions. [2018-10-23 09:51:08,912 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-10-23 09:51:08,912 INFO L367 BasicCegarLoop]: Found error trace [2018-10-23 09:51:08,912 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-23 09:51:08,912 INFO L424 AbstractCegarLoop]: === Iteration 4 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-23 09:51:08,913 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-23 09:51:08,913 INFO L82 PathProgramCache]: Analyzing trace with hash -1442209030, now seen corresponding path program 1 times [2018-10-23 09:51:08,913 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-23 09:51:08,914 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:51:08,914 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-23 09:51:08,914 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:51:08,914 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-23 09:51:08,974 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:51:09,377 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:51:09,377 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-23 09:51:09,378 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-10-23 09:51:09,378 INFO L258 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-10-23 09:51:09,379 INFO L460 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-10-23 09:51:09,379 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-10-23 09:51:09,379 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-10-23 09:51:09,380 INFO L87 Difference]: Start difference. First operand 26 states and 29 transitions. Second operand 5 states. [2018-10-23 09:51:09,491 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-23 09:51:09,491 INFO L93 Difference]: Finished difference Result 36 states and 39 transitions. [2018-10-23 09:51:09,492 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-10-23 09:51:09,493 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 20 [2018-10-23 09:51:09,493 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-23 09:51:09,494 INFO L225 Difference]: With dead ends: 36 [2018-10-23 09:51:09,494 INFO L226 Difference]: Without dead ends: 27 [2018-10-23 09:51:09,495 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2018-10-23 09:51:09,495 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2018-10-23 09:51:09,499 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 26. [2018-10-23 09:51:09,500 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 26 states. [2018-10-23 09:51:09,501 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 29 transitions. [2018-10-23 09:51:09,501 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 29 transitions. Word has length 20 [2018-10-23 09:51:09,501 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-23 09:51:09,501 INFO L481 AbstractCegarLoop]: Abstraction has 26 states and 29 transitions. [2018-10-23 09:51:09,501 INFO L482 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-10-23 09:51:09,502 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 29 transitions. [2018-10-23 09:51:09,502 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2018-10-23 09:51:09,502 INFO L367 BasicCegarLoop]: Found error trace [2018-10-23 09:51:09,503 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-23 09:51:09,503 INFO L424 AbstractCegarLoop]: === Iteration 5 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-23 09:51:09,503 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-23 09:51:09,503 INFO L82 PathProgramCache]: Analyzing trace with hash -469535236, now seen corresponding path program 1 times [2018-10-23 09:51:09,504 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-23 09:51:09,504 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:51:09,505 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-23 09:51:09,505 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:51:09,505 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-23 09:51:09,526 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:51:09,668 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:51:09,669 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-23 09:51:09,669 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-10-23 09:51:09,669 INFO L258 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-10-23 09:51:09,669 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-10-23 09:51:09,670 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-10-23 09:51:09,670 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-10-23 09:51:09,670 INFO L87 Difference]: Start difference. First operand 26 states and 29 transitions. Second operand 4 states. [2018-10-23 09:51:09,901 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-23 09:51:09,902 INFO L93 Difference]: Finished difference Result 49 states and 57 transitions. [2018-10-23 09:51:09,902 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-10-23 09:51:09,903 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 25 [2018-10-23 09:51:09,903 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-23 09:51:09,904 INFO L225 Difference]: With dead ends: 49 [2018-10-23 09:51:09,904 INFO L226 Difference]: Without dead ends: 34 [2018-10-23 09:51:09,905 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 3 SyntacticMatches, 2 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-10-23 09:51:09,905 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2018-10-23 09:51:09,910 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 30. [2018-10-23 09:51:09,910 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 30 states. [2018-10-23 09:51:09,911 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 32 transitions. [2018-10-23 09:51:09,911 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 32 transitions. Word has length 25 [2018-10-23 09:51:09,912 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-23 09:51:09,912 INFO L481 AbstractCegarLoop]: Abstraction has 30 states and 32 transitions. [2018-10-23 09:51:09,912 INFO L482 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-10-23 09:51:09,912 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 32 transitions. [2018-10-23 09:51:09,913 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2018-10-23 09:51:09,913 INFO L367 BasicCegarLoop]: Found error trace [2018-10-23 09:51:09,913 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-23 09:51:09,914 INFO L424 AbstractCegarLoop]: === Iteration 6 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-23 09:51:09,914 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-23 09:51:09,914 INFO L82 PathProgramCache]: Analyzing trace with hash -862562246, now seen corresponding path program 1 times [2018-10-23 09:51:09,914 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-23 09:51:09,915 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:51:09,915 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-23 09:51:09,916 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:51:09,916 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-23 09:51:09,957 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:51:10,074 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:51:10,075 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-23 09:51:10,075 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-10-23 09:51:10,075 INFO L258 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-10-23 09:51:10,076 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-10-23 09:51:10,076 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-10-23 09:51:10,076 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-10-23 09:51:10,076 INFO L87 Difference]: Start difference. First operand 30 states and 32 transitions. Second operand 4 states. [2018-10-23 09:51:10,184 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-23 09:51:10,185 INFO L93 Difference]: Finished difference Result 52 states and 56 transitions. [2018-10-23 09:51:10,191 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-10-23 09:51:10,191 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 25 [2018-10-23 09:51:10,192 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-23 09:51:10,192 INFO L225 Difference]: With dead ends: 52 [2018-10-23 09:51:10,193 INFO L226 Difference]: Without dead ends: 39 [2018-10-23 09:51:10,193 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-10-23 09:51:10,194 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2018-10-23 09:51:10,201 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 31. [2018-10-23 09:51:10,201 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 31 states. [2018-10-23 09:51:10,202 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 33 transitions. [2018-10-23 09:51:10,202 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 33 transitions. Word has length 25 [2018-10-23 09:51:10,203 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-23 09:51:10,203 INFO L481 AbstractCegarLoop]: Abstraction has 31 states and 33 transitions. [2018-10-23 09:51:10,203 INFO L482 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-10-23 09:51:10,203 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 33 transitions. [2018-10-23 09:51:10,204 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2018-10-23 09:51:10,204 INFO L367 BasicCegarLoop]: Found error trace [2018-10-23 09:51:10,204 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-23 09:51:10,204 INFO L424 AbstractCegarLoop]: === Iteration 7 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-23 09:51:10,205 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-23 09:51:10,205 INFO L82 PathProgramCache]: Analyzing trace with hash -1056341250, now seen corresponding path program 1 times [2018-10-23 09:51:10,205 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-23 09:51:10,206 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:51:10,206 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-23 09:51:10,206 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:51:10,207 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-23 09:51:10,229 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:51:10,736 WARN L179 SmtUtils]: Spent 217.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 16 [2018-10-23 09:51:11,006 WARN L179 SmtUtils]: Spent 191.00 ms on a formula simplification that was a NOOP. DAG size: 23 [2018-10-23 09:51:11,201 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:51:11,201 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:51:11,203 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-23 09:51:11,204 INFO L200 CegarAbsIntRunner]: Running AI on error trace of length 26 with the following transitions: [2018-10-23 09:51:11,208 INFO L202 CegarAbsIntRunner]: [0], [1], [2], [6], [8], [11], [17], [19], [24], [32], [33], [37], [39], [43], [46], [48], [54], [55], [56], [58], [59], [60] [2018-10-23 09:51:11,265 INFO L148 AbstractInterpreter]: Using domain PoormanAbstractDomain with backing domain CompoundDomain [CongruenceDomain, OctagonDomain] [2018-10-23 09:51:11,265 INFO L101 FixpointEngine]: Starting fixpoint engine with domain PoormanAbstractDomain (maxUnwinding=3, maxParallelStates=2) [2018-10-23 09:51:11,406 WARN L79 EvaluatorLogger]: Possible loss of precision. Operator ARITHMOD has no precise implementation. [2018-10-23 09:51:16,741 INFO L263 AbstractInterpreter]: Some error location(s) were reachable [2018-10-23 09:51:16,743 INFO L272 AbstractInterpreter]: Visited 22 different actions 337 times. Merged at 8 different actions 280 times. Widened at 1 different actions 31 times. Found 36 fixpoints after 2 different actions. Largest state had 29 variables. [2018-10-23 09:51:16,783 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-23 09:51:16,784 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-10-23 09:51:16,784 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:51:16,784 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-23 09:51:16,793 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-23 09:51:16,794 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-10-23 09:51:16,834 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:51:16,843 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-23 09:51:17,213 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-10-23 09:51:17,213 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-23 09:51:17,813 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-10-23 09:51:17,844 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-23 09:51:17,845 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 6, 6] total 16 [2018-10-23 09:51:17,845 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-23 09:51:17,845 INFO L460 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-10-23 09:51:17,846 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-10-23 09:51:17,846 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=192, Unknown=0, NotChecked=0, Total=240 [2018-10-23 09:51:17,846 INFO L87 Difference]: Start difference. First operand 31 states and 33 transitions. Second operand 12 states. [2018-10-23 09:51:18,645 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-23 09:51:18,645 INFO L93 Difference]: Finished difference Result 51 states and 54 transitions. [2018-10-23 09:51:18,645 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-10-23 09:51:18,646 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 25 [2018-10-23 09:51:18,646 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-23 09:51:18,647 INFO L225 Difference]: With dead ends: 51 [2018-10-23 09:51:18,647 INFO L226 Difference]: Without dead ends: 39 [2018-10-23 09:51:18,648 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 42 SyntacticMatches, 3 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 67 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=142, Invalid=458, Unknown=0, NotChecked=0, Total=600 [2018-10-23 09:51:18,648 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2018-10-23 09:51:18,652 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 31. [2018-10-23 09:51:18,652 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 31 states. [2018-10-23 09:51:18,653 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 32 transitions. [2018-10-23 09:51:18,654 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 32 transitions. Word has length 25 [2018-10-23 09:51:18,654 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-23 09:51:18,654 INFO L481 AbstractCegarLoop]: Abstraction has 31 states and 32 transitions. [2018-10-23 09:51:18,654 INFO L482 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-10-23 09:51:18,654 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 32 transitions. [2018-10-23 09:51:18,655 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2018-10-23 09:51:18,655 INFO L367 BasicCegarLoop]: Found error trace [2018-10-23 09:51:18,655 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-23 09:51:18,656 INFO L424 AbstractCegarLoop]: === Iteration 8 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-23 09:51:18,656 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-23 09:51:18,656 INFO L82 PathProgramCache]: Analyzing trace with hash -1449368260, now seen corresponding path program 1 times [2018-10-23 09:51:18,656 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-23 09:51:18,657 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:51:18,657 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-23 09:51:18,657 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:51:18,657 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-23 09:51:18,684 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:51:19,097 WARN L179 SmtUtils]: Spent 323.00 ms on a formula simplification. DAG size of input: 117 DAG size of output: 27 [2018-10-23 09:51:19,392 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:51:19,392 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:51:19,393 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-23 09:51:19,393 INFO L200 CegarAbsIntRunner]: Running AI on error trace of length 26 with the following transitions: [2018-10-23 09:51:19,393 INFO L202 CegarAbsIntRunner]: [0], [1], [2], [6], [8], [11], [13], [17], [19], [24], [32], [33], [37], [39], [43], [46], [48], [54], [55], [56], [58], [59], [60] [2018-10-23 09:51:19,395 INFO L148 AbstractInterpreter]: Using domain PoormanAbstractDomain with backing domain CompoundDomain [CongruenceDomain, OctagonDomain] [2018-10-23 09:51:19,396 INFO L101 FixpointEngine]: Starting fixpoint engine with domain PoormanAbstractDomain (maxUnwinding=3, maxParallelStates=2) [2018-10-23 09:51:19,409 WARN L79 EvaluatorLogger]: Possible loss of precision. Operator ARITHMOD has no precise implementation. [2018-10-23 09:51:23,884 INFO L263 AbstractInterpreter]: Some error location(s) were reachable [2018-10-23 09:51:23,885 INFO L272 AbstractInterpreter]: Visited 23 different actions 404 times. Merged at 9 different actions 305 times. Widened at 1 different actions 32 times. Found 78 fixpoints after 5 different actions. Largest state had 29 variables. [2018-10-23 09:51:23,928 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-23 09:51:23,928 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-10-23 09:51:23,928 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:51:23,929 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-23 09:51:23,944 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-23 09:51:23,944 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-10-23 09:51:23,985 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:51:23,993 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-23 09:51:24,035 WARN L307 Elim1Store]: Array PQE input equivalent to false [2018-10-23 09:51:24,036 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-10-23 09:51:26,168 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-10-23 09:51:26,170 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-10-23 09:51:26,171 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-10-23 09:51:26,174 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-23 09:51:26,179 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-10-23 09:51:26,180 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 2 variables, input treesize:100, output treesize:21 [2018-10-23 09:51:26,621 WARN L179 SmtUtils]: Spent 160.00 ms on a formula simplification that was a NOOP. DAG size: 37 [2018-10-23 09:51:27,285 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:51:27,285 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-23 09:51:27,452 WARN L179 SmtUtils]: Spent 165.00 ms on a formula simplification. DAG size of input: 61 DAG size of output: 49 [2018-10-23 09:51:28,233 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:51:28,264 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-23 09:51:28,265 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 10, 10] total 24 [2018-10-23 09:51:28,265 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-23 09:51:28,265 INFO L460 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-10-23 09:51:28,265 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-10-23 09:51:28,266 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=95, Invalid=457, Unknown=0, NotChecked=0, Total=552 [2018-10-23 09:51:28,266 INFO L87 Difference]: Start difference. First operand 31 states and 32 transitions. Second operand 16 states. [2018-10-23 09:51:28,533 WARN L179 SmtUtils]: Spent 106.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 48 [2018-10-23 09:51:28,927 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-23 09:51:28,927 INFO L93 Difference]: Finished difference Result 45 states and 46 transitions. [2018-10-23 09:51:28,928 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-10-23 09:51:28,928 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 25 [2018-10-23 09:51:28,929 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-23 09:51:28,929 INFO L225 Difference]: With dead ends: 45 [2018-10-23 09:51:28,930 INFO L226 Difference]: Without dead ends: 35 [2018-10-23 09:51:28,931 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 34 SyntacticMatches, 2 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 144 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=122, Invalid=528, Unknown=0, NotChecked=0, Total=650 [2018-10-23 09:51:28,932 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2018-10-23 09:51:28,937 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 34. [2018-10-23 09:51:28,937 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 34 states. [2018-10-23 09:51:28,938 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 35 transitions. [2018-10-23 09:51:28,938 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 35 transitions. Word has length 25 [2018-10-23 09:51:28,938 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-23 09:51:28,938 INFO L481 AbstractCegarLoop]: Abstraction has 34 states and 35 transitions. [2018-10-23 09:51:28,938 INFO L482 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-10-23 09:51:28,939 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 35 transitions. [2018-10-23 09:51:28,939 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2018-10-23 09:51:28,940 INFO L367 BasicCegarLoop]: Found error trace [2018-10-23 09:51:28,940 INFO L375 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-23 09:51:28,940 INFO L424 AbstractCegarLoop]: === Iteration 9 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-23 09:51:28,941 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-23 09:51:28,941 INFO L82 PathProgramCache]: Analyzing trace with hash 890023736, now seen corresponding path program 1 times [2018-10-23 09:51:28,941 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-23 09:51:28,942 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:51:28,942 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-23 09:51:28,942 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:51:28,943 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-23 09:51:28,959 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:51:29,268 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 8 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:51:29,269 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:51:29,269 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-23 09:51:29,269 INFO L200 CegarAbsIntRunner]: Running AI on error trace of length 31 with the following transitions: [2018-10-23 09:51:29,269 INFO L202 CegarAbsIntRunner]: [0], [1], [2], [6], [8], [11], [13], [17], [19], [22], [24], [32], [33], [37], [39], [43], [46], [48], [54], [55], [56], [58], [59], [60] [2018-10-23 09:51:29,276 INFO L148 AbstractInterpreter]: Using domain PoormanAbstractDomain with backing domain CompoundDomain [CongruenceDomain, OctagonDomain] [2018-10-23 09:51:29,276 INFO L101 FixpointEngine]: Starting fixpoint engine with domain PoormanAbstractDomain (maxUnwinding=3, maxParallelStates=2) [2018-10-23 09:51:29,291 WARN L79 EvaluatorLogger]: Possible loss of precision. Operator ARITHMOD has no precise implementation. [2018-10-23 09:51:33,448 INFO L263 AbstractInterpreter]: Some error location(s) were reachable [2018-10-23 09:51:33,448 INFO L272 AbstractInterpreter]: Visited 24 different actions 461 times. Merged at 10 different actions 318 times. Widened at 2 different actions 33 times. Found 106 fixpoints after 6 different actions. Largest state had 29 variables. [2018-10-23 09:51:33,473 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-23 09:51:33,474 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-10-23 09:51:33,474 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:51:33,474 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-23 09:51:33,488 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-23 09:51:33,488 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-10-23 09:51:33,525 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:51:33,527 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-23 09:51:33,770 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 8 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:51:33,770 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-23 09:51:34,352 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 8 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:51:34,381 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-23 09:51:34,382 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 10 [2018-10-23 09:51:34,382 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-23 09:51:34,382 INFO L460 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-10-23 09:51:34,383 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-10-23 09:51:34,383 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=56, Unknown=0, NotChecked=0, Total=90 [2018-10-23 09:51:34,383 INFO L87 Difference]: Start difference. First operand 34 states and 35 transitions. Second operand 7 states. [2018-10-23 09:51:34,910 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-23 09:51:34,910 INFO L93 Difference]: Finished difference Result 57 states and 59 transitions. [2018-10-23 09:51:34,911 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-10-23 09:51:34,911 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 30 [2018-10-23 09:51:34,911 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-23 09:51:34,912 INFO L225 Difference]: With dead ends: 57 [2018-10-23 09:51:34,912 INFO L226 Difference]: Without dead ends: 44 [2018-10-23 09:51:34,912 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 56 SyntacticMatches, 1 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=34, Invalid=56, Unknown=0, NotChecked=0, Total=90 [2018-10-23 09:51:34,913 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2018-10-23 09:51:34,922 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 36. [2018-10-23 09:51:34,922 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 36 states. [2018-10-23 09:51:34,923 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 37 transitions. [2018-10-23 09:51:34,924 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 37 transitions. Word has length 30 [2018-10-23 09:51:34,924 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-23 09:51:34,924 INFO L481 AbstractCegarLoop]: Abstraction has 36 states and 37 transitions. [2018-10-23 09:51:34,924 INFO L482 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-10-23 09:51:34,924 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 37 transitions. [2018-10-23 09:51:34,925 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2018-10-23 09:51:34,925 INFO L367 BasicCegarLoop]: Found error trace [2018-10-23 09:51:34,925 INFO L375 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-23 09:51:34,926 INFO L424 AbstractCegarLoop]: === Iteration 10 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-23 09:51:34,927 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-23 09:51:34,927 INFO L82 PathProgramCache]: Analyzing trace with hash 303217722, now seen corresponding path program 2 times [2018-10-23 09:51:34,927 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-23 09:51:34,928 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:51:34,928 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-23 09:51:34,928 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:51:34,928 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-23 09:51:34,976 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:51:37,723 WARN L179 SmtUtils]: Spent 2.62 s on a formula simplification. DAG size of input: 102 DAG size of output: 30 [2018-10-23 09:51:38,391 WARN L179 SmtUtils]: Spent 617.00 ms on a formula simplification. DAG size of input: 24 DAG size of output: 21 [2018-10-23 09:51:39,252 WARN L179 SmtUtils]: Spent 782.00 ms on a formula simplification. DAG size of input: 52 DAG size of output: 29 [2018-10-23 09:51:39,989 WARN L179 SmtUtils]: Spent 117.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 52 [2018-10-23 09:51:44,383 WARN L179 SmtUtils]: Spent 2.17 s on a formula simplification. DAG size of input: 59 DAG size of output: 51 [2018-10-23 09:51:44,936 WARN L179 SmtUtils]: Spent 285.00 ms on a formula simplification. DAG size of input: 102 DAG size of output: 46 [2018-10-23 09:51:44,945 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:51:44,945 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:51:44,945 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-23 09:51:44,945 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-23 09:51:44,945 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-23 09:51:44,946 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:51:44,946 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-23 09:51:44,961 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-10-23 09:51:44,961 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-10-23 09:51:45,024 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-10-23 09:51:45,024 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-23 09:51:45,028 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-23 09:51:45,047 WARN L307 Elim1Store]: Array PQE input equivalent to false [2018-10-23 09:51:45,047 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-10-23 09:51:45,143 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-10-23 09:51:45,147 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-10-23 09:51:45,148 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-10-23 09:51:45,163 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-23 09:51:45,168 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-10-23 09:51:45,168 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 2 variables, input treesize:100, output treesize:21 [2018-10-23 09:51:45,715 WARN L179 SmtUtils]: Spent 132.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 49 [2018-10-23 09:51:49,098 WARN L179 SmtUtils]: Spent 120.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 48 [2018-10-23 09:51:49,625 WARN L179 SmtUtils]: Spent 107.00 ms on a formula simplification that was a NOOP. DAG size: 43 [2018-10-23 09:51:49,848 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:51:49,848 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-23 09:51:50,094 WARN L179 SmtUtils]: Spent 244.00 ms on a formula simplification. DAG size of input: 96 DAG size of output: 71 [2018-10-23 09:51:50,285 WARN L179 SmtUtils]: Spent 126.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 60 [2018-10-23 09:51:50,925 WARN L179 SmtUtils]: Spent 172.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 44 [2018-10-23 09:51:51,626 WARN L179 SmtUtils]: Spent 254.00 ms on a formula simplification. DAG size of input: 58 DAG size of output: 58 [2018-10-23 09:51:51,953 WARN L179 SmtUtils]: Spent 221.00 ms on a formula simplification. DAG size of input: 58 DAG size of output: 58 [2018-10-23 09:51:52,172 WARN L179 SmtUtils]: Spent 125.00 ms on a formula simplification that was a NOOP. DAG size: 61 [2018-10-23 09:51:52,533 WARN L179 SmtUtils]: Spent 238.00 ms on a formula simplification that was a NOOP. DAG size: 65 [2018-10-23 09:51:52,830 WARN L179 SmtUtils]: Spent 161.00 ms on a formula simplification that was a NOOP. DAG size: 65 [2018-10-23 09:51:52,854 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:51:52,877 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-23 09:51:52,878 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 14, 14] total 37 [2018-10-23 09:51:52,878 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-23 09:51:52,878 INFO L460 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-10-23 09:51:52,879 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-10-23 09:51:52,879 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=176, Invalid=1154, Unknown=2, NotChecked=0, Total=1332 [2018-10-23 09:51:52,880 INFO L87 Difference]: Start difference. First operand 36 states and 37 transitions. Second operand 25 states. [2018-10-23 09:51:53,667 WARN L179 SmtUtils]: Spent 146.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 60 [2018-10-23 09:51:53,986 WARN L179 SmtUtils]: Spent 128.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 51 [2018-10-23 09:51:54,408 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-23 09:51:54,408 INFO L93 Difference]: Finished difference Result 50 states and 51 transitions. [2018-10-23 09:51:54,409 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-10-23 09:51:54,409 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 30 [2018-10-23 09:51:54,409 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-23 09:51:54,410 INFO L225 Difference]: With dead ends: 50 [2018-10-23 09:51:54,411 INFO L226 Difference]: Without dead ends: 40 [2018-10-23 09:51:54,413 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 35 SyntacticMatches, 4 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 405 ImplicationChecksByTransitivity, 17.5s TimeCoverageRelationStatistics Valid=270, Invalid=1450, Unknown=2, NotChecked=0, Total=1722 [2018-10-23 09:51:54,413 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2018-10-23 09:51:54,418 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 39. [2018-10-23 09:51:54,418 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 39 states. [2018-10-23 09:51:54,419 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 40 transitions. [2018-10-23 09:51:54,419 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 40 transitions. Word has length 30 [2018-10-23 09:51:54,420 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-23 09:51:54,420 INFO L481 AbstractCegarLoop]: Abstraction has 39 states and 40 transitions. [2018-10-23 09:51:54,420 INFO L482 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-10-23 09:51:54,420 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 40 transitions. [2018-10-23 09:51:54,421 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2018-10-23 09:51:54,421 INFO L367 BasicCegarLoop]: Found error trace [2018-10-23 09:51:54,421 INFO L375 BasicCegarLoop]: trace histogram [4, 4, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-23 09:51:54,421 INFO L424 AbstractCegarLoop]: === Iteration 11 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-23 09:51:54,422 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-23 09:51:54,422 INFO L82 PathProgramCache]: Analyzing trace with hash 411764474, now seen corresponding path program 2 times [2018-10-23 09:51:54,422 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-23 09:51:54,423 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:51:54,423 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-23 09:51:54,423 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:51:54,423 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-23 09:51:54,437 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:51:55,047 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 12 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:51:55,047 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:51:55,048 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-23 09:51:55,048 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-23 09:51:55,048 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-23 09:51:55,048 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:51:55,048 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-23 09:51:55,067 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-10-23 09:51:55,067 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-10-23 09:51:55,121 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-10-23 09:51:55,121 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-23 09:51:55,124 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-23 09:51:55,304 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 12 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:51:55,305 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-23 09:51:55,371 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 12 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:51:55,392 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-23 09:51:55,393 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 13 [2018-10-23 09:51:55,393 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-23 09:51:55,393 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-10-23 09:51:55,394 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-10-23 09:51:55,394 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=102, Unknown=0, NotChecked=0, Total=156 [2018-10-23 09:51:55,394 INFO L87 Difference]: Start difference. First operand 39 states and 40 transitions. Second operand 9 states. [2018-10-23 09:51:55,561 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-23 09:51:55,562 INFO L93 Difference]: Finished difference Result 62 states and 64 transitions. [2018-10-23 09:51:55,562 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-10-23 09:51:55,563 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 35 [2018-10-23 09:51:55,563 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-23 09:51:55,564 INFO L225 Difference]: With dead ends: 62 [2018-10-23 09:51:55,564 INFO L226 Difference]: Without dead ends: 49 [2018-10-23 09:51:55,565 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 64 SyntacticMatches, 1 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=54, Invalid=102, Unknown=0, NotChecked=0, Total=156 [2018-10-23 09:51:55,566 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2018-10-23 09:51:55,572 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 41. [2018-10-23 09:51:55,572 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 41 states. [2018-10-23 09:51:55,572 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 42 transitions. [2018-10-23 09:51:55,573 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 42 transitions. Word has length 35 [2018-10-23 09:51:55,573 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-23 09:51:55,573 INFO L481 AbstractCegarLoop]: Abstraction has 41 states and 42 transitions. [2018-10-23 09:51:55,573 INFO L482 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-10-23 09:51:55,573 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 42 transitions. [2018-10-23 09:51:55,574 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2018-10-23 09:51:55,574 INFO L367 BasicCegarLoop]: Found error trace [2018-10-23 09:51:55,574 INFO L375 BasicCegarLoop]: trace histogram [4, 4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-23 09:51:55,574 INFO L424 AbstractCegarLoop]: === Iteration 12 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-23 09:51:55,575 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-23 09:51:55,575 INFO L82 PathProgramCache]: Analyzing trace with hash -175041540, now seen corresponding path program 3 times [2018-10-23 09:51:55,575 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-23 09:51:55,576 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:51:55,576 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-23 09:51:55,576 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:51:55,576 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-23 09:51:55,600 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:51:55,962 WARN L179 SmtUtils]: Spent 192.00 ms on a formula simplification. DAG size of input: 140 DAG size of output: 29 [2018-10-23 09:51:56,241 WARN L179 SmtUtils]: Spent 100.00 ms on a formula simplification. DAG size of input: 94 DAG size of output: 23 [2018-10-23 09:51:56,790 WARN L179 SmtUtils]: Spent 364.00 ms on a formula simplification. DAG size of input: 116 DAG size of output: 56 [2018-10-23 09:51:57,039 WARN L179 SmtUtils]: Spent 220.00 ms on a formula simplification. DAG size of input: 101 DAG size of output: 53 [2018-10-23 09:51:57,329 WARN L179 SmtUtils]: Spent 165.00 ms on a formula simplification. DAG size of input: 104 DAG size of output: 58 [2018-10-23 09:51:57,786 WARN L179 SmtUtils]: Spent 212.00 ms on a formula simplification. DAG size of input: 102 DAG size of output: 51 [2018-10-23 09:51:57,955 WARN L179 SmtUtils]: Spent 131.00 ms on a formula simplification. DAG size of input: 80 DAG size of output: 45 [2018-10-23 09:51:58,162 WARN L179 SmtUtils]: Spent 171.00 ms on a formula simplification. DAG size of input: 63 DAG size of output: 41 [2018-10-23 09:51:58,316 WARN L179 SmtUtils]: Spent 111.00 ms on a formula simplification. DAG size of input: 79 DAG size of output: 45 [2018-10-23 09:51:58,630 WARN L179 SmtUtils]: Spent 270.00 ms on a formula simplification. DAG size of input: 71 DAG size of output: 36 [2018-10-23 09:51:58,924 WARN L179 SmtUtils]: Spent 106.00 ms on a formula simplification. DAG size of input: 113 DAG size of output: 31 [2018-10-23 09:51:58,933 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 0 proven. 27 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:51:58,933 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:51:58,934 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-23 09:51:58,934 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-23 09:51:58,934 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-23 09:51:58,934 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:51:58,934 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-23 09:51:58,946 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-23 09:51:58,947 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-10-23 09:51:59,042 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-23 09:51:59,043 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-23 09:51:59,047 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-23 09:51:59,057 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 30 treesize of output 27 [2018-10-23 09:51:59,059 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-10-23 09:51:59,060 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-10-23 09:51:59,073 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-23 09:51:59,077 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 31 treesize of output 28 [2018-10-23 09:51:59,079 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-10-23 09:51:59,080 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-10-23 09:51:59,089 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-23 09:52:01,121 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-10-23 09:52:01,121 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 2 variables, input treesize:100, output treesize:21 [2018-10-23 09:52:01,598 WARN L179 SmtUtils]: Spent 129.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 41 [2018-10-23 09:52:02,082 WARN L179 SmtUtils]: Spent 115.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 44 [2018-10-23 09:52:02,585 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 0 proven. 27 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:52:02,586 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-23 09:52:02,781 WARN L179 SmtUtils]: Spent 193.00 ms on a formula simplification. DAG size of input: 98 DAG size of output: 71 [2018-10-23 09:52:03,483 WARN L179 SmtUtils]: Spent 134.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 39 [2018-10-23 09:52:04,754 WARN L179 SmtUtils]: Spent 171.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 45 [2018-10-23 09:52:05,017 WARN L179 SmtUtils]: Spent 102.00 ms on a formula simplification that was a NOOP. DAG size: 49 [2018-10-23 09:52:05,358 WARN L179 SmtUtils]: Spent 155.00 ms on a formula simplification that was a NOOP. DAG size: 57 [2018-10-23 09:52:05,849 WARN L179 SmtUtils]: Spent 249.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 57 [2018-10-23 09:52:06,136 WARN L179 SmtUtils]: Spent 133.00 ms on a formula simplification that was a NOOP. DAG size: 58 [2018-10-23 09:52:06,416 WARN L179 SmtUtils]: Spent 132.00 ms on a formula simplification that was a NOOP. DAG size: 60 [2018-10-23 09:52:07,012 WARN L179 SmtUtils]: Spent 292.00 ms on a formula simplification. DAG size of input: 59 DAG size of output: 58 [2018-10-23 09:52:07,135 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 0 proven. 27 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:52:07,168 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-23 09:52:07,168 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17, 17] total 47 [2018-10-23 09:52:07,169 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-23 09:52:07,169 INFO L460 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-10-23 09:52:07,169 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-10-23 09:52:07,171 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=239, Invalid=1923, Unknown=0, NotChecked=0, Total=2162 [2018-10-23 09:52:07,171 INFO L87 Difference]: Start difference. First operand 41 states and 42 transitions. Second operand 32 states. [2018-10-23 09:52:09,626 WARN L179 SmtUtils]: Spent 121.00 ms on a formula simplification. DAG size of input: 70 DAG size of output: 45 [2018-10-23 09:52:10,644 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-23 09:52:10,644 INFO L93 Difference]: Finished difference Result 55 states and 56 transitions. [2018-10-23 09:52:10,644 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-10-23 09:52:10,645 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 35 [2018-10-23 09:52:10,645 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-23 09:52:10,645 INFO L225 Difference]: With dead ends: 55 [2018-10-23 09:52:10,645 INFO L226 Difference]: Without dead ends: 45 [2018-10-23 09:52:10,646 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 94 GetRequests, 39 SyntacticMatches, 3 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 680 ImplicationChecksByTransitivity, 9.3s TimeCoverageRelationStatistics Valid=364, Invalid=2498, Unknown=0, NotChecked=0, Total=2862 [2018-10-23 09:52:10,647 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2018-10-23 09:52:10,655 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 44. [2018-10-23 09:52:10,655 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 44 states. [2018-10-23 09:52:10,656 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 45 transitions. [2018-10-23 09:52:10,656 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 45 transitions. Word has length 35 [2018-10-23 09:52:10,656 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-23 09:52:10,656 INFO L481 AbstractCegarLoop]: Abstraction has 44 states and 45 transitions. [2018-10-23 09:52:10,656 INFO L482 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-10-23 09:52:10,657 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 45 transitions. [2018-10-23 09:52:10,657 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2018-10-23 09:52:10,657 INFO L367 BasicCegarLoop]: Found error trace [2018-10-23 09:52:10,658 INFO L375 BasicCegarLoop]: trace histogram [5, 5, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-23 09:52:10,658 INFO L424 AbstractCegarLoop]: === Iteration 13 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-23 09:52:10,658 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-23 09:52:10,658 INFO L82 PathProgramCache]: Analyzing trace with hash 1953970296, now seen corresponding path program 3 times [2018-10-23 09:52:10,658 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-23 09:52:10,659 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:52:10,659 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-23 09:52:10,659 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:52:10,659 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-23 09:52:10,673 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:52:11,847 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 16 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:52:11,847 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:52:11,847 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-23 09:52:11,847 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-23 09:52:11,847 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-23 09:52:11,847 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:52:11,848 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-23 09:52:11,855 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-23 09:52:11,855 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-10-23 09:52:11,887 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-23 09:52:11,887 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-23 09:52:11,891 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-23 09:52:11,932 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 16 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:52:11,933 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-23 09:52:12,031 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 16 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:52:12,051 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-23 09:52:12,052 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 16 [2018-10-23 09:52:12,052 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-23 09:52:12,052 INFO L460 AbstractCegarLoop]: Interpolant automaton has 11 states [2018-10-23 09:52:12,052 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2018-10-23 09:52:12,052 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=162, Unknown=0, NotChecked=0, Total=240 [2018-10-23 09:52:12,053 INFO L87 Difference]: Start difference. First operand 44 states and 45 transitions. Second operand 11 states. [2018-10-23 09:52:12,252 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-23 09:52:12,252 INFO L93 Difference]: Finished difference Result 67 states and 69 transitions. [2018-10-23 09:52:12,253 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-10-23 09:52:12,253 INFO L78 Accepts]: Start accepts. Automaton has 11 states. Word has length 40 [2018-10-23 09:52:12,253 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-23 09:52:12,254 INFO L225 Difference]: With dead ends: 67 [2018-10-23 09:52:12,254 INFO L226 Difference]: Without dead ends: 54 [2018-10-23 09:52:12,255 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 87 GetRequests, 72 SyntacticMatches, 1 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 46 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=78, Invalid=162, Unknown=0, NotChecked=0, Total=240 [2018-10-23 09:52:12,256 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2018-10-23 09:52:12,262 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 46. [2018-10-23 09:52:12,262 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 46 states. [2018-10-23 09:52:12,263 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 47 transitions. [2018-10-23 09:52:12,263 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 47 transitions. Word has length 40 [2018-10-23 09:52:12,263 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-23 09:52:12,263 INFO L481 AbstractCegarLoop]: Abstraction has 46 states and 47 transitions. [2018-10-23 09:52:12,263 INFO L482 AbstractCegarLoop]: Interpolant automaton has 11 states. [2018-10-23 09:52:12,263 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 47 transitions. [2018-10-23 09:52:12,264 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2018-10-23 09:52:12,264 INFO L367 BasicCegarLoop]: Found error trace [2018-10-23 09:52:12,264 INFO L375 BasicCegarLoop]: trace histogram [5, 5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-23 09:52:12,265 INFO L424 AbstractCegarLoop]: === Iteration 14 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-23 09:52:12,265 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-23 09:52:12,265 INFO L82 PathProgramCache]: Analyzing trace with hash 1367164282, now seen corresponding path program 4 times [2018-10-23 09:52:12,265 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-23 09:52:12,266 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:52:12,266 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-23 09:52:12,266 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:52:12,266 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-23 09:52:12,296 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:52:14,683 WARN L179 SmtUtils]: Spent 2.19 s on a formula simplification. DAG size of input: 111 DAG size of output: 24 [2018-10-23 09:52:15,048 WARN L179 SmtUtils]: Spent 153.00 ms on a formula simplification. DAG size of input: 74 DAG size of output: 31 [2018-10-23 09:52:15,230 WARN L179 SmtUtils]: Spent 135.00 ms on a formula simplification. DAG size of input: 81 DAG size of output: 47 [2018-10-23 09:52:15,357 WARN L179 SmtUtils]: Spent 100.00 ms on a formula simplification. DAG size of input: 80 DAG size of output: 43 [2018-10-23 09:52:15,569 WARN L179 SmtUtils]: Spent 176.00 ms on a formula simplification. DAG size of input: 90 DAG size of output: 55 [2018-10-23 09:52:15,789 WARN L179 SmtUtils]: Spent 185.00 ms on a formula simplification. DAG size of input: 95 DAG size of output: 63 [2018-10-23 09:52:15,953 WARN L179 SmtUtils]: Spent 127.00 ms on a formula simplification. DAG size of input: 83 DAG size of output: 54 [2018-10-23 09:52:16,220 WARN L179 SmtUtils]: Spent 106.00 ms on a formula simplification. DAG size of input: 71 DAG size of output: 46 [2018-10-23 09:52:18,553 WARN L854 $PredicateComparison]: unable to prove that (or (let ((.cse13 (div c_~SIZE~0 4294967296))) (let ((.cse9 (* 4294967296 .cse13))) (and (let ((.cse11 (* 2 (div c_~SIZE~0 2)))) (let ((.cse4 (= .cse11 c_~SIZE~0)) (.cse6 (<= .cse9 c_~SIZE~0)) (.cse10 (div (+ c_~SIZE~0 (* (- 4294967296) .cse13)) 2))) (let ((.cse0 (div .cse10 4294967296)) (.cse1 (or .cse4 .cse6)) (.cse12 (not (= c_~SIZE~0 (+ |c_linear_search_#in~n| .cse9)))) (.cse5 (div (+ .cse10 1) 4294967296)) (.cse2 (not .cse4)) (.cse3 (< c_~SIZE~0 .cse9))) (or (and (<= (+ .cse0 1) 0) .cse1) (let ((.cse8 (* 8589934592 .cse13))) (and (or (and (or (and .cse2 .cse3) (< 0 .cse0)) (or .cse4 (< 0 .cse5) .cse6)) (and (let ((.cse7 (<= (+ c_~SIZE~0 1) .cse9))) (or .cse7 (and (or (not (= (select (select |c_#memory_int| |c_linear_search_#in~a.base|) (- (+ .cse8 (* (- 2) c_~SIZE~0)))) |c_linear_search_#in~q|)) (< (+ .cse9 (* 2 .cse10)) c_~SIZE~0)) (or (<= c_~SIZE~0 .cse11) (<= (+ .cse9 4294967300) c_~SIZE~0) (<= (+ .cse11 2) c_~SIZE~0) .cse7 .cse12)))) (not (= c_~SIZE~0 (+ |c_linear_search_#in~n| .cse9 4294967296))))) (or (<= (* 2 c_~SIZE~0) (+ .cse8 8)) (and (<= .cse0 0) .cse1) (and .cse2 (<= .cse5 0) .cse3)))) .cse12 (and (<= (+ .cse5 1) 0) .cse2 .cse3))))) (<= c_~SIZE~0 (+ .cse9 4))))) (not (= 0 |c_linear_search_#in~a.offset|))) is different from true [2018-10-23 09:52:18,570 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 0 proven. 46 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:52:18,571 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:52:18,571 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-23 09:52:18,571 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-23 09:52:18,571 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-23 09:52:18,571 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:52:18,571 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-23 09:52:18,604 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-23 09:52:18,604 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-10-23 09:52:18,672 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:52:18,678 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-23 09:52:18,689 WARN L307 Elim1Store]: Array PQE input equivalent to false [2018-10-23 09:52:18,689 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-10-23 09:52:18,718 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-10-23 09:52:18,726 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-10-23 09:52:18,727 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-10-23 09:52:18,731 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-23 09:52:18,738 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-10-23 09:52:18,738 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 2 variables, input treesize:100, output treesize:21 [2018-10-23 09:52:19,583 WARN L179 SmtUtils]: Spent 174.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 60 [2018-10-23 09:52:20,328 WARN L179 SmtUtils]: Spent 184.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 64 [2018-10-23 09:52:21,677 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 0 proven. 46 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:52:21,677 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-23 09:52:22,230 WARN L179 SmtUtils]: Spent 550.00 ms on a formula simplification. DAG size of input: 134 DAG size of output: 97 [2018-10-23 09:52:23,978 WARN L179 SmtUtils]: Spent 109.00 ms on a formula simplification that was a NOOP. DAG size: 55 [2018-10-23 09:52:24,592 WARN L179 SmtUtils]: Spent 217.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 54 [2018-10-23 09:52:26,954 WARN L179 SmtUtils]: Spent 128.00 ms on a formula simplification that was a NOOP. DAG size: 58 [2018-10-23 09:52:27,527 WARN L179 SmtUtils]: Spent 167.00 ms on a formula simplification that was a NOOP. DAG size: 60 [2018-10-23 09:52:27,900 WARN L179 SmtUtils]: Spent 149.00 ms on a formula simplification that was a NOOP. DAG size: 62 [2018-10-23 09:52:28,432 WARN L179 SmtUtils]: Spent 233.00 ms on a formula simplification that was a NOOP. DAG size: 65 [2018-10-23 09:52:29,368 WARN L179 SmtUtils]: Spent 391.00 ms on a formula simplification that was a NOOP. DAG size: 69 [2018-10-23 09:52:30,573 WARN L179 SmtUtils]: Spent 681.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 86 [2018-10-23 09:52:30,646 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 0 proven. 46 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:52:30,679 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-23 09:52:30,679 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 18, 20] total 50 [2018-10-23 09:52:30,679 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-23 09:52:30,680 INFO L460 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-10-23 09:52:30,680 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-10-23 09:52:30,681 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=217, Invalid=2136, Unknown=3, NotChecked=94, Total=2450 [2018-10-23 09:52:30,681 INFO L87 Difference]: Start difference. First operand 46 states and 47 transitions. Second operand 32 states. [2018-10-23 09:52:33,123 WARN L179 SmtUtils]: Spent 110.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 49 [2018-10-23 09:52:33,366 WARN L179 SmtUtils]: Spent 132.00 ms on a formula simplification. DAG size of input: 58 DAG size of output: 54 [2018-10-23 09:52:34,181 WARN L179 SmtUtils]: Spent 180.00 ms on a formula simplification. DAG size of input: 75 DAG size of output: 63 [2018-10-23 09:52:35,003 WARN L179 SmtUtils]: Spent 212.00 ms on a formula simplification. DAG size of input: 79 DAG size of output: 67 [2018-10-23 09:52:35,578 WARN L179 SmtUtils]: Spent 194.00 ms on a formula simplification. DAG size of input: 117 DAG size of output: 73 [2018-10-23 09:52:36,133 WARN L179 SmtUtils]: Spent 114.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 63 [2018-10-23 09:52:37,146 WARN L179 SmtUtils]: Spent 383.00 ms on a formula simplification. DAG size of input: 127 DAG size of output: 71 [2018-10-23 09:52:39,942 WARN L179 SmtUtils]: Spent 113.00 ms on a formula simplification. DAG size of input: 107 DAG size of output: 68 [2018-10-23 09:52:40,227 WARN L179 SmtUtils]: Spent 145.00 ms on a formula simplification. DAG size of input: 137 DAG size of output: 75 [2018-10-23 09:52:40,508 WARN L179 SmtUtils]: Spent 112.00 ms on a formula simplification. DAG size of input: 106 DAG size of output: 67 [2018-10-23 09:52:42,788 WARN L179 SmtUtils]: Spent 2.16 s on a formula simplification. DAG size of input: 174 DAG size of output: 69 [2018-10-23 09:52:42,938 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-23 09:52:42,938 INFO L93 Difference]: Finished difference Result 60 states and 61 transitions. [2018-10-23 09:52:42,939 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2018-10-23 09:52:42,939 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 40 [2018-10-23 09:52:42,939 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-23 09:52:42,940 INFO L225 Difference]: With dead ends: 60 [2018-10-23 09:52:42,940 INFO L226 Difference]: Without dead ends: 50 [2018-10-23 09:52:42,942 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 113 GetRequests, 44 SyntacticMatches, 5 SemanticMatches, 64 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 814 ImplicationChecksByTransitivity, 26.0s TimeCoverageRelationStatistics Valid=428, Invalid=3732, Unknown=4, NotChecked=126, Total=4290 [2018-10-23 09:52:42,942 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2018-10-23 09:52:42,949 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 49. [2018-10-23 09:52:42,950 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 49 states. [2018-10-23 09:52:42,952 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 50 transitions. [2018-10-23 09:52:42,953 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 50 transitions. Word has length 40 [2018-10-23 09:52:42,953 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-23 09:52:42,953 INFO L481 AbstractCegarLoop]: Abstraction has 49 states and 50 transitions. [2018-10-23 09:52:42,953 INFO L482 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-10-23 09:52:42,953 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 50 transitions. [2018-10-23 09:52:42,954 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2018-10-23 09:52:42,954 INFO L367 BasicCegarLoop]: Found error trace [2018-10-23 09:52:42,954 INFO L375 BasicCegarLoop]: trace histogram [6, 6, 5, 5, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-23 09:52:42,954 INFO L424 AbstractCegarLoop]: === Iteration 15 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-23 09:52:42,954 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-23 09:52:42,955 INFO L82 PathProgramCache]: Analyzing trace with hash 545539514, now seen corresponding path program 4 times [2018-10-23 09:52:42,955 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-23 09:52:42,955 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:52:42,956 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-23 09:52:42,956 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:52:42,956 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-23 09:52:42,970 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:52:44,906 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 20 proven. 50 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:52:44,906 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:52:44,906 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-23 09:52:44,906 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-23 09:52:44,906 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-23 09:52:44,907 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:52:44,907 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-23 09:52:44,914 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-23 09:52:44,915 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-10-23 09:52:44,942 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:52:44,944 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-23 09:52:45,076 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 20 proven. 50 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:52:45,076 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-23 09:52:45,217 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 20 proven. 50 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:52:45,238 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-23 09:52:45,239 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 19 [2018-10-23 09:52:45,239 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-23 09:52:45,239 INFO L460 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-10-23 09:52:45,239 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-10-23 09:52:45,240 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=106, Invalid=236, Unknown=0, NotChecked=0, Total=342 [2018-10-23 09:52:45,240 INFO L87 Difference]: Start difference. First operand 49 states and 50 transitions. Second operand 13 states. [2018-10-23 09:52:45,374 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-23 09:52:45,374 INFO L93 Difference]: Finished difference Result 72 states and 74 transitions. [2018-10-23 09:52:45,375 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-10-23 09:52:45,375 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 45 [2018-10-23 09:52:45,375 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-23 09:52:45,375 INFO L225 Difference]: With dead ends: 72 [2018-10-23 09:52:45,376 INFO L226 Difference]: Without dead ends: 59 [2018-10-23 09:52:45,376 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 98 GetRequests, 80 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 70 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=106, Invalid=236, Unknown=0, NotChecked=0, Total=342 [2018-10-23 09:52:45,376 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2018-10-23 09:52:45,384 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 51. [2018-10-23 09:52:45,384 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 51 states. [2018-10-23 09:52:45,385 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 52 transitions. [2018-10-23 09:52:45,385 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 52 transitions. Word has length 45 [2018-10-23 09:52:45,385 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-23 09:52:45,385 INFO L481 AbstractCegarLoop]: Abstraction has 51 states and 52 transitions. [2018-10-23 09:52:45,385 INFO L482 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-10-23 09:52:45,386 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 52 transitions. [2018-10-23 09:52:45,386 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2018-10-23 09:52:45,386 INFO L367 BasicCegarLoop]: Found error trace [2018-10-23 09:52:45,387 INFO L375 BasicCegarLoop]: trace histogram [6, 6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-23 09:52:45,387 INFO L424 AbstractCegarLoop]: === Iteration 16 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-23 09:52:45,387 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-23 09:52:45,387 INFO L82 PathProgramCache]: Analyzing trace with hash -41266500, now seen corresponding path program 5 times [2018-10-23 09:52:45,387 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-23 09:52:45,388 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:52:45,388 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-23 09:52:45,388 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:52:45,388 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-23 09:52:45,409 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:52:46,063 WARN L179 SmtUtils]: Spent 520.00 ms on a formula simplification. DAG size of input: 114 DAG size of output: 28 [2018-10-23 09:52:46,320 WARN L179 SmtUtils]: Spent 100.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 26 [2018-10-23 09:52:46,456 WARN L179 SmtUtils]: Spent 107.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 44 [2018-10-23 09:52:47,436 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 0 proven. 70 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:52:47,436 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:52:47,436 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-23 09:52:47,436 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-23 09:52:47,437 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-23 09:52:47,437 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:52:47,437 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-23 09:52:47,445 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-10-23 09:52:47,445 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-10-23 09:52:47,537 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-10-23 09:52:47,537 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-23 09:52:47,541 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-23 09:52:47,560 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 31 treesize of output 28 [2018-10-23 09:52:47,562 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-10-23 09:52:47,563 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-10-23 09:52:47,571 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-23 09:52:47,575 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 30 treesize of output 27 [2018-10-23 09:52:47,578 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-10-23 09:52:47,579 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-10-23 09:52:47,586 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-23 09:52:53,631 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-10-23 09:52:53,631 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 2 variables, input treesize:100, output treesize:21 [2018-10-23 09:52:54,729 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 0 proven. 70 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:52:54,730 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-23 09:52:54,938 WARN L179 SmtUtils]: Spent 207.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 65 [2018-10-23 09:52:55,187 WARN L179 SmtUtils]: Spent 141.00 ms on a formula simplification that was a NOOP. DAG size: 49 [2018-10-23 09:52:55,814 WARN L179 SmtUtils]: Spent 138.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 40 [2018-10-23 09:52:56,717 WARN L179 SmtUtils]: Spent 216.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 46 [2018-10-23 09:52:56,960 WARN L179 SmtUtils]: Spent 107.00 ms on a formula simplification that was a NOOP. DAG size: 48 [2018-10-23 09:52:57,264 WARN L179 SmtUtils]: Spent 113.00 ms on a formula simplification that was a NOOP. DAG size: 50 [2018-10-23 09:52:57,610 WARN L179 SmtUtils]: Spent 131.00 ms on a formula simplification that was a NOOP. DAG size: 58 [2018-10-23 09:52:57,911 WARN L179 SmtUtils]: Spent 134.00 ms on a formula simplification that was a NOOP. DAG size: 58 [2018-10-23 09:52:58,258 WARN L179 SmtUtils]: Spent 195.00 ms on a formula simplification that was a NOOP. DAG size: 59 [2018-10-23 09:52:58,965 WARN L179 SmtUtils]: Spent 147.00 ms on a formula simplification that was a NOOP. DAG size: 59 [2018-10-23 09:52:59,112 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 0 proven. 70 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:52:59,149 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-23 09:52:59,149 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 17, 17] total 46 [2018-10-23 09:52:59,149 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-23 09:52:59,150 INFO L460 AbstractCegarLoop]: Interpolant automaton has 31 states [2018-10-23 09:52:59,150 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2018-10-23 09:52:59,151 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=207, Invalid=1863, Unknown=0, NotChecked=0, Total=2070 [2018-10-23 09:52:59,151 INFO L87 Difference]: Start difference. First operand 51 states and 52 transitions. Second operand 31 states. [2018-10-23 09:53:00,037 WARN L179 SmtUtils]: Spent 125.00 ms on a formula simplification. DAG size of input: 78 DAG size of output: 44 [2018-10-23 09:53:01,150 WARN L179 SmtUtils]: Spent 257.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 67 [2018-10-23 09:53:01,564 WARN L179 SmtUtils]: Spent 107.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 41 [2018-10-23 09:53:02,073 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-23 09:53:02,073 INFO L93 Difference]: Finished difference Result 65 states and 66 transitions. [2018-10-23 09:53:02,073 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-10-23 09:53:02,074 INFO L78 Accepts]: Start accepts. Automaton has 31 states. Word has length 45 [2018-10-23 09:53:02,074 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-23 09:53:02,075 INFO L225 Difference]: With dead ends: 65 [2018-10-23 09:53:02,075 INFO L226 Difference]: Without dead ends: 55 [2018-10-23 09:53:02,077 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 117 GetRequests, 59 SyntacticMatches, 5 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 617 ImplicationChecksByTransitivity, 8.2s TimeCoverageRelationStatistics Valid=348, Invalid=2622, Unknown=0, NotChecked=0, Total=2970 [2018-10-23 09:53:02,077 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2018-10-23 09:53:02,084 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 54. [2018-10-23 09:53:02,085 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 54 states. [2018-10-23 09:53:02,085 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 55 transitions. [2018-10-23 09:53:02,085 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 55 transitions. Word has length 45 [2018-10-23 09:53:02,086 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-23 09:53:02,086 INFO L481 AbstractCegarLoop]: Abstraction has 54 states and 55 transitions. [2018-10-23 09:53:02,086 INFO L482 AbstractCegarLoop]: Interpolant automaton has 31 states. [2018-10-23 09:53:02,086 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 55 transitions. [2018-10-23 09:53:02,087 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2018-10-23 09:53:02,087 INFO L367 BasicCegarLoop]: Found error trace [2018-10-23 09:53:02,087 INFO L375 BasicCegarLoop]: trace histogram [7, 7, 6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-23 09:53:02,087 INFO L424 AbstractCegarLoop]: === Iteration 17 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-23 09:53:02,088 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-23 09:53:02,088 INFO L82 PathProgramCache]: Analyzing trace with hash -1808322120, now seen corresponding path program 5 times [2018-10-23 09:53:02,088 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-23 09:53:02,088 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:53:02,089 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-23 09:53:02,089 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:53:02,089 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-23 09:53:02,104 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:53:06,143 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 24 proven. 75 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:53:06,144 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:53:06,144 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-23 09:53:06,144 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-23 09:53:06,144 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-23 09:53:06,144 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:53:06,144 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-23 09:53:06,152 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-10-23 09:53:06,152 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-10-23 09:53:06,200 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-10-23 09:53:06,200 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-23 09:53:06,203 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-23 09:53:06,281 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 24 proven. 75 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:53:06,281 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-23 09:53:06,667 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 24 proven. 75 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:53:06,688 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-23 09:53:06,688 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 22 [2018-10-23 09:53:06,688 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-23 09:53:06,689 INFO L460 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-10-23 09:53:06,689 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-10-23 09:53:06,689 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=138, Invalid=323, Unknown=1, NotChecked=0, Total=462 [2018-10-23 09:53:06,689 INFO L87 Difference]: Start difference. First operand 54 states and 55 transitions. Second operand 15 states. [2018-10-23 09:53:06,965 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-23 09:53:06,966 INFO L93 Difference]: Finished difference Result 77 states and 79 transitions. [2018-10-23 09:53:06,966 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-10-23 09:53:06,966 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 50 [2018-10-23 09:53:06,967 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-23 09:53:06,968 INFO L225 Difference]: With dead ends: 77 [2018-10-23 09:53:06,968 INFO L226 Difference]: Without dead ends: 64 [2018-10-23 09:53:06,969 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 88 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 99 ImplicationChecksByTransitivity, 4.4s TimeCoverageRelationStatistics Valid=138, Invalid=323, Unknown=1, NotChecked=0, Total=462 [2018-10-23 09:53:06,969 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2018-10-23 09:53:06,977 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 56. [2018-10-23 09:53:06,977 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 56 states. [2018-10-23 09:53:06,977 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 57 transitions. [2018-10-23 09:53:06,978 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 57 transitions. Word has length 50 [2018-10-23 09:53:06,978 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-23 09:53:06,978 INFO L481 AbstractCegarLoop]: Abstraction has 56 states and 57 transitions. [2018-10-23 09:53:06,978 INFO L482 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-10-23 09:53:06,978 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 57 transitions. [2018-10-23 09:53:06,979 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2018-10-23 09:53:06,979 INFO L367 BasicCegarLoop]: Found error trace [2018-10-23 09:53:06,979 INFO L375 BasicCegarLoop]: trace histogram [7, 7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-23 09:53:06,980 INFO L424 AbstractCegarLoop]: === Iteration 18 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-23 09:53:06,980 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-23 09:53:06,980 INFO L82 PathProgramCache]: Analyzing trace with hash 1899839162, now seen corresponding path program 6 times [2018-10-23 09:53:06,980 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-23 09:53:06,981 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:53:06,981 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-23 09:53:06,981 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:53:06,981 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-23 09:53:07,006 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:53:09,359 WARN L179 SmtUtils]: Spent 2.20 s on a formula simplification. DAG size of input: 120 DAG size of output: 26 [2018-10-23 09:53:10,320 WARN L179 SmtUtils]: Spent 141.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 44 [2018-10-23 09:53:10,521 WARN L179 SmtUtils]: Spent 160.00 ms on a formula simplification. DAG size of input: 91 DAG size of output: 52 [2018-10-23 09:53:10,689 WARN L179 SmtUtils]: Spent 128.00 ms on a formula simplification. DAG size of input: 79 DAG size of output: 43 [2018-10-23 09:53:10,838 WARN L179 SmtUtils]: Spent 104.00 ms on a formula simplification. DAG size of input: 59 DAG size of output: 36 [2018-10-23 09:53:11,001 WARN L179 SmtUtils]: Spent 121.00 ms on a formula simplification. DAG size of input: 69 DAG size of output: 38 [2018-10-23 09:53:11,407 WARN L179 SmtUtils]: Spent 117.00 ms on a formula simplification. DAG size of input: 108 DAG size of output: 35 [2018-10-23 09:53:11,425 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 0 proven. 99 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:53:11,426 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:53:11,426 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-23 09:53:11,426 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-23 09:53:11,426 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-23 09:53:11,426 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:53:11,426 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-23 09:53:11,437 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-23 09:53:11,437 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-10-23 09:53:11,569 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-23 09:53:11,570 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-23 09:53:11,574 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-23 09:53:11,584 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 30 treesize of output 27 [2018-10-23 09:53:11,589 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-10-23 09:53:11,590 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-10-23 09:53:11,603 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-23 09:53:11,606 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 31 treesize of output 28 [2018-10-23 09:53:11,607 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-10-23 09:53:11,608 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-10-23 09:53:11,618 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-23 09:53:11,643 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-10-23 09:53:11,644 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 2 variables, input treesize:100, output treesize:21 [2018-10-23 09:53:13,478 WARN L179 SmtUtils]: Spent 243.00 ms on a formula simplification that was a NOOP. DAG size: 55 [2018-10-23 09:53:14,051 WARN L179 SmtUtils]: Spent 226.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 62 [2018-10-23 09:53:15,347 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 0 proven. 99 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:53:15,347 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-23 09:53:16,266 WARN L179 SmtUtils]: Spent 916.00 ms on a formula simplification. DAG size of input: 150 DAG size of output: 115 [2018-10-23 09:53:18,270 WARN L179 SmtUtils]: Spent 104.00 ms on a formula simplification that was a NOOP. DAG size: 57 [2018-10-23 09:53:18,746 WARN L179 SmtUtils]: Spent 303.00 ms on a formula simplification that was a NOOP. DAG size: 56 [2018-10-23 09:53:19,109 WARN L179 SmtUtils]: Spent 133.00 ms on a formula simplification that was a NOOP. DAG size: 61 [2018-10-23 09:53:19,497 WARN L179 SmtUtils]: Spent 152.00 ms on a formula simplification that was a NOOP. DAG size: 65 [2018-10-23 09:53:20,106 WARN L179 SmtUtils]: Spent 300.00 ms on a formula simplification. DAG size of input: 94 DAG size of output: 87 [2018-10-23 09:53:21,180 WARN L179 SmtUtils]: Spent 228.00 ms on a formula simplification that was a NOOP. DAG size: 92 [2018-10-23 09:53:22,210 WARN L179 SmtUtils]: Spent 419.00 ms on a formula simplification that was a NOOP. DAG size: 95 [2018-10-23 09:53:22,899 WARN L179 SmtUtils]: Spent 256.00 ms on a formula simplification that was a NOOP. DAG size: 96 [2018-10-23 09:53:24,605 WARN L179 SmtUtils]: Spent 442.00 ms on a formula simplification that was a NOOP. DAG size: 98 [2018-10-23 09:53:26,115 WARN L179 SmtUtils]: Spent 526.00 ms on a formula simplification that was a NOOP. DAG size: 101 [2018-10-23 09:53:26,205 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 0 proven. 99 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:53:26,225 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-23 09:53:26,225 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 20, 21] total 56 [2018-10-23 09:53:26,226 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-23 09:53:26,226 INFO L460 AbstractCegarLoop]: Interpolant automaton has 37 states [2018-10-23 09:53:26,226 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2018-10-23 09:53:26,227 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=232, Invalid=2848, Unknown=0, NotChecked=0, Total=3080 [2018-10-23 09:53:26,228 INFO L87 Difference]: Start difference. First operand 56 states and 57 transitions. Second operand 37 states. [2018-10-23 09:53:26,728 WARN L179 SmtUtils]: Spent 111.00 ms on a formula simplification. DAG size of input: 50 DAG size of output: 46 [2018-10-23 09:53:27,407 WARN L179 SmtUtils]: Spent 191.00 ms on a formula simplification. DAG size of input: 68 DAG size of output: 56 [2018-10-23 09:53:28,456 WARN L179 SmtUtils]: Spent 185.00 ms on a formula simplification. DAG size of input: 73 DAG size of output: 60 [2018-10-23 09:53:29,165 WARN L179 SmtUtils]: Spent 216.00 ms on a formula simplification. DAG size of input: 77 DAG size of output: 64 [2018-10-23 09:53:30,816 WARN L179 SmtUtils]: Spent 249.00 ms on a formula simplification. DAG size of input: 82 DAG size of output: 69 [2018-10-23 09:53:31,527 WARN L179 SmtUtils]: Spent 223.00 ms on a formula simplification. DAG size of input: 120 DAG size of output: 81 [2018-10-23 09:53:32,243 WARN L179 SmtUtils]: Spent 138.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 83 [2018-10-23 09:53:33,017 WARN L179 SmtUtils]: Spent 142.00 ms on a formula simplification. DAG size of input: 92 DAG size of output: 78 [2018-10-23 09:53:33,355 WARN L179 SmtUtils]: Spent 200.00 ms on a formula simplification. DAG size of input: 103 DAG size of output: 81 [2018-10-23 09:53:33,844 WARN L179 SmtUtils]: Spent 121.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 60 [2018-10-23 09:53:34,722 WARN L179 SmtUtils]: Spent 567.00 ms on a formula simplification. DAG size of input: 114 DAG size of output: 67 [2018-10-23 09:53:35,030 WARN L179 SmtUtils]: Spent 109.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 59 [2018-10-23 09:53:35,260 WARN L179 SmtUtils]: Spent 122.00 ms on a formula simplification. DAG size of input: 102 DAG size of output: 60 [2018-10-23 09:53:35,361 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-23 09:53:35,361 INFO L93 Difference]: Finished difference Result 70 states and 71 transitions. [2018-10-23 09:53:35,361 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-10-23 09:53:35,362 INFO L78 Accepts]: Start accepts. Automaton has 37 states. Word has length 50 [2018-10-23 09:53:35,362 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-23 09:53:35,362 INFO L225 Difference]: With dead ends: 70 [2018-10-23 09:53:35,362 INFO L226 Difference]: Without dead ends: 60 [2018-10-23 09:53:35,364 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 138 GetRequests, 61 SyntacticMatches, 4 SemanticMatches, 73 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1072 ImplicationChecksByTransitivity, 25.0s TimeCoverageRelationStatistics Valid=465, Invalid=5085, Unknown=0, NotChecked=0, Total=5550 [2018-10-23 09:53:35,364 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2018-10-23 09:53:35,374 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 59. [2018-10-23 09:53:35,375 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 59 states. [2018-10-23 09:53:35,375 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 60 transitions. [2018-10-23 09:53:35,376 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 60 transitions. Word has length 50 [2018-10-23 09:53:35,376 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-23 09:53:35,376 INFO L481 AbstractCegarLoop]: Abstraction has 59 states and 60 transitions. [2018-10-23 09:53:35,376 INFO L482 AbstractCegarLoop]: Interpolant automaton has 37 states. [2018-10-23 09:53:35,376 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 60 transitions. [2018-10-23 09:53:35,377 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2018-10-23 09:53:35,377 INFO L367 BasicCegarLoop]: Found error trace [2018-10-23 09:53:35,377 INFO L375 BasicCegarLoop]: trace histogram [8, 8, 7, 7, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-23 09:53:35,377 INFO L424 AbstractCegarLoop]: === Iteration 19 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-23 09:53:35,378 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-23 09:53:35,378 INFO L82 PathProgramCache]: Analyzing trace with hash 1410208890, now seen corresponding path program 6 times [2018-10-23 09:53:35,378 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-23 09:53:35,379 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:53:35,379 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-23 09:53:35,379 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:53:35,379 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-23 09:53:35,395 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:53:40,250 INFO L134 CoverageAnalysis]: Checked inductivity of 133 backedges. 28 proven. 105 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:53:40,250 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:53:40,250 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-23 09:53:40,250 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-23 09:53:40,251 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-23 09:53:40,251 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:53:40,251 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-23 09:53:40,259 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-23 09:53:40,260 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-10-23 09:53:40,303 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-23 09:53:40,303 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-23 09:53:40,305 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-23 09:53:40,385 INFO L134 CoverageAnalysis]: Checked inductivity of 133 backedges. 28 proven. 105 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:53:40,386 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-23 09:53:40,663 INFO L134 CoverageAnalysis]: Checked inductivity of 133 backedges. 28 proven. 105 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:53:40,685 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-23 09:53:40,686 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 10] total 25 [2018-10-23 09:53:40,686 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-23 09:53:40,686 INFO L460 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-10-23 09:53:40,686 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-10-23 09:53:40,687 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=174, Invalid=425, Unknown=1, NotChecked=0, Total=600 [2018-10-23 09:53:40,687 INFO L87 Difference]: Start difference. First operand 59 states and 60 transitions. Second operand 17 states. [2018-10-23 09:53:40,966 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-23 09:53:40,966 INFO L93 Difference]: Finished difference Result 82 states and 84 transitions. [2018-10-23 09:53:40,967 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-10-23 09:53:40,967 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 55 [2018-10-23 09:53:40,967 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-23 09:53:40,967 INFO L225 Difference]: With dead ends: 82 [2018-10-23 09:53:40,968 INFO L226 Difference]: Without dead ends: 69 [2018-10-23 09:53:40,968 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 120 GetRequests, 96 SyntacticMatches, 1 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 133 ImplicationChecksByTransitivity, 5.1s TimeCoverageRelationStatistics Valid=174, Invalid=425, Unknown=1, NotChecked=0, Total=600 [2018-10-23 09:53:40,968 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 69 states. [2018-10-23 09:53:40,975 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 69 to 61. [2018-10-23 09:53:40,976 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 61 states. [2018-10-23 09:53:40,976 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 62 transitions. [2018-10-23 09:53:40,976 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 62 transitions. Word has length 55 [2018-10-23 09:53:40,976 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-23 09:53:40,977 INFO L481 AbstractCegarLoop]: Abstraction has 61 states and 62 transitions. [2018-10-23 09:53:40,977 INFO L482 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-10-23 09:53:40,977 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 62 transitions. [2018-10-23 09:53:40,977 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2018-10-23 09:53:40,977 INFO L367 BasicCegarLoop]: Found error trace [2018-10-23 09:53:40,978 INFO L375 BasicCegarLoop]: trace histogram [8, 8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-23 09:53:40,978 INFO L424 AbstractCegarLoop]: === Iteration 20 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-23 09:53:40,978 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-23 09:53:40,978 INFO L82 PathProgramCache]: Analyzing trace with hash 823402876, now seen corresponding path program 7 times [2018-10-23 09:53:40,978 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-23 09:53:40,979 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:53:40,979 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-23 09:53:40,979 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:53:40,979 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-23 09:53:41,005 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:53:41,643 WARN L179 SmtUtils]: Spent 520.00 ms on a formula simplification. DAG size of input: 114 DAG size of output: 28 [2018-10-23 09:53:42,521 WARN L179 SmtUtils]: Spent 111.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 51 [2018-10-23 09:53:43,127 INFO L134 CoverageAnalysis]: Checked inductivity of 133 backedges. 0 proven. 133 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:53:43,127 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:53:43,127 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-23 09:53:43,127 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-23 09:53:43,127 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-23 09:53:43,127 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:53:43,127 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-23 09:53:43,134 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-23 09:53:43,135 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-10-23 09:53:43,286 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:53:43,295 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-23 09:53:43,337 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-10-23 09:53:43,347 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-10-23 09:53:43,347 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-10-23 09:53:43,452 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-23 09:53:43,456 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 46 treesize of output 43 [2018-10-23 09:53:43,461 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-10-23 09:53:43,461 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-10-23 09:53:43,477 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-23 09:53:43,478 WARN L307 Elim1Store]: Array PQE input equivalent to false [2018-10-23 09:53:43,479 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 1 xjuncts. [2018-10-23 09:53:43,484 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-10-23 09:53:43,488 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-10-23 09:53:43,489 INFO L267 ElimStorePlain]: Start of recursive call 8: End of recursive call: and 1 xjuncts. [2018-10-23 09:53:43,505 INFO L267 ElimStorePlain]: Start of recursive call 7: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-23 09:53:43,507 WARN L307 Elim1Store]: Array PQE input equivalent to false [2018-10-23 09:53:43,508 INFO L267 ElimStorePlain]: Start of recursive call 9: End of recursive call: and 1 xjuncts. [2018-10-23 09:53:43,548 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-10-23 09:53:43,553 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-10-23 09:53:43,553 INFO L267 ElimStorePlain]: Start of recursive call 11: End of recursive call: and 1 xjuncts. [2018-10-23 09:53:43,573 INFO L267 ElimStorePlain]: Start of recursive call 10: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-23 09:53:45,672 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 2 dim-2 vars, End of recursive call: 2 dim-0 vars, and 2 xjuncts. [2018-10-23 09:53:45,672 INFO L202 ElimStorePlain]: Needed 11 recursive calls to eliminate 5 variables, input treesize:445, output treesize:66 [2018-10-23 09:53:46,678 WARN L179 SmtUtils]: Spent 630.00 ms on a formula simplification that was a NOOP. DAG size: 45 [2018-10-23 09:53:47,361 WARN L179 SmtUtils]: Spent 630.00 ms on a formula simplification that was a NOOP. DAG size: 40 [2018-10-23 09:53:47,953 WARN L179 SmtUtils]: Spent 541.00 ms on a formula simplification that was a NOOP. DAG size: 39 [2018-10-23 09:53:49,844 WARN L179 SmtUtils]: Spent 1.82 s on a formula simplification. DAG size of input: 46 DAG size of output: 46 [2018-10-23 09:53:50,749 WARN L179 SmtUtils]: Spent 582.00 ms on a formula simplification that was a NOOP. DAG size: 44 [2018-10-23 09:53:51,517 WARN L179 SmtUtils]: Spent 702.00 ms on a formula simplification that was a NOOP. DAG size: 42 [2018-10-23 09:53:51,860 WARN L179 SmtUtils]: Spent 165.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 47 [2018-10-23 09:53:52,805 WARN L179 SmtUtils]: Spent 676.00 ms on a formula simplification that was a NOOP. DAG size: 41 [2018-10-23 09:53:54,388 WARN L179 SmtUtils]: Spent 1.35 s on a formula simplification. DAG size of input: 46 DAG size of output: 46 [2018-10-23 09:53:54,637 INFO L134 CoverageAnalysis]: Checked inductivity of 133 backedges. 0 proven. 133 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:53:54,638 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-23 09:53:54,898 WARN L179 SmtUtils]: Spent 258.00 ms on a formula simplification. DAG size of input: 111 DAG size of output: 82 [2018-10-23 09:53:55,727 WARN L179 SmtUtils]: Spent 144.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 40 [2018-10-23 09:53:56,861 WARN L179 SmtUtils]: Spent 180.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 46 [2018-10-23 09:53:57,515 WARN L179 SmtUtils]: Spent 116.00 ms on a formula simplification that was a NOOP. DAG size: 51 [2018-10-23 09:53:57,966 WARN L179 SmtUtils]: Spent 180.00 ms on a formula simplification that was a NOOP. DAG size: 57 [2018-10-23 09:53:58,391 WARN L179 SmtUtils]: Spent 132.00 ms on a formula simplification that was a NOOP. DAG size: 59 [2018-10-23 09:53:58,998 WARN L179 SmtUtils]: Spent 185.00 ms on a formula simplification that was a NOOP. DAG size: 60 [2018-10-23 09:54:00,510 WARN L179 SmtUtils]: Spent 194.00 ms on a formula simplification that was a NOOP. DAG size: 62 [2018-10-23 09:54:01,405 WARN L179 SmtUtils]: Spent 622.00 ms on a formula simplification. DAG size of input: 61 DAG size of output: 61 [2018-10-23 09:54:03,123 WARN L179 SmtUtils]: Spent 1.10 s on a formula simplification that was a NOOP. DAG size: 64 [2018-10-23 09:54:03,753 WARN L179 SmtUtils]: Spent 183.00 ms on a formula simplification that was a NOOP. DAG size: 67 [2018-10-23 09:54:04,723 WARN L179 SmtUtils]: Spent 542.00 ms on a formula simplification. DAG size of input: 66 DAG size of output: 62 [2018-10-23 09:54:05,519 WARN L179 SmtUtils]: Spent 268.00 ms on a formula simplification that was a NOOP. DAG size: 62 [2018-10-23 09:54:05,568 INFO L134 CoverageAnalysis]: Checked inductivity of 133 backedges. 0 proven. 133 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:54:05,591 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-23 09:54:05,591 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 22, 23] total 59 [2018-10-23 09:54:05,591 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-23 09:54:05,591 INFO L460 AbstractCegarLoop]: Interpolant automaton has 38 states [2018-10-23 09:54:05,592 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 38 interpolants. [2018-10-23 09:54:05,593 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=286, Invalid=3136, Unknown=0, NotChecked=0, Total=3422 [2018-10-23 09:54:05,593 INFO L87 Difference]: Start difference. First operand 61 states and 62 transitions. Second operand 38 states. [2018-10-23 09:54:07,265 WARN L179 SmtUtils]: Spent 927.00 ms on a formula simplification. DAG size of input: 67 DAG size of output: 51 [2018-10-23 09:54:08,948 WARN L179 SmtUtils]: Spent 1.39 s on a formula simplification. DAG size of input: 61 DAG size of output: 54 [2018-10-23 09:54:11,322 WARN L179 SmtUtils]: Spent 2.14 s on a formula simplification. DAG size of input: 59 DAG size of output: 52 [2018-10-23 09:54:12,562 WARN L179 SmtUtils]: Spent 838.00 ms on a formula simplification. DAG size of input: 67 DAG size of output: 60 [2018-10-23 09:54:13,425 WARN L179 SmtUtils]: Spent 625.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 53 [2018-10-23 09:54:13,720 WARN L179 SmtUtils]: Spent 149.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 54 [2018-10-23 09:54:14,055 WARN L179 SmtUtils]: Spent 139.00 ms on a formula simplification. DAG size of input: 78 DAG size of output: 70 [2018-10-23 09:54:16,577 WARN L179 SmtUtils]: Spent 2.36 s on a formula simplification. DAG size of input: 92 DAG size of output: 76 [2018-10-23 09:54:19,131 WARN L179 SmtUtils]: Spent 2.42 s on a formula simplification. DAG size of input: 63 DAG size of output: 52 [2018-10-23 09:54:20,147 WARN L179 SmtUtils]: Spent 846.00 ms on a formula simplification. DAG size of input: 73 DAG size of output: 60 [2018-10-23 09:54:20,388 WARN L179 SmtUtils]: Spent 137.00 ms on a formula simplification. DAG size of input: 73 DAG size of output: 57 [2018-10-23 09:54:20,982 WARN L179 SmtUtils]: Spent 474.00 ms on a formula simplification. DAG size of input: 67 DAG size of output: 55 [2018-10-23 09:54:21,301 WARN L179 SmtUtils]: Spent 201.00 ms on a formula simplification. DAG size of input: 92 DAG size of output: 55 [2018-10-23 09:54:21,407 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-23 09:54:21,408 INFO L93 Difference]: Finished difference Result 75 states and 76 transitions. [2018-10-23 09:54:21,408 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2018-10-23 09:54:21,408 INFO L78 Accepts]: Start accepts. Automaton has 38 states. Word has length 55 [2018-10-23 09:54:21,409 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-23 09:54:21,409 INFO L225 Difference]: With dead ends: 75 [2018-10-23 09:54:21,410 INFO L226 Difference]: Without dead ends: 65 [2018-10-23 09:54:21,413 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 143 GetRequests, 67 SyntacticMatches, 6 SemanticMatches, 70 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1119 ImplicationChecksByTransitivity, 35.7s TimeCoverageRelationStatistics Valid=490, Invalid=4622, Unknown=0, NotChecked=0, Total=5112 [2018-10-23 09:54:21,413 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2018-10-23 09:54:21,422 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 64. [2018-10-23 09:54:21,422 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 64 states. [2018-10-23 09:54:21,423 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 65 transitions. [2018-10-23 09:54:21,423 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 65 transitions. Word has length 55 [2018-10-23 09:54:21,423 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-23 09:54:21,424 INFO L481 AbstractCegarLoop]: Abstraction has 64 states and 65 transitions. [2018-10-23 09:54:21,424 INFO L482 AbstractCegarLoop]: Interpolant automaton has 38 states. [2018-10-23 09:54:21,424 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 65 transitions. [2018-10-23 09:54:21,424 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2018-10-23 09:54:21,425 INFO L367 BasicCegarLoop]: Found error trace [2018-10-23 09:54:21,425 INFO L375 BasicCegarLoop]: trace histogram [9, 9, 8, 8, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-23 09:54:21,425 INFO L424 AbstractCegarLoop]: === Iteration 21 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-23 09:54:21,425 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-23 09:54:21,425 INFO L82 PathProgramCache]: Analyzing trace with hash -62874888, now seen corresponding path program 7 times [2018-10-23 09:54:21,425 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-23 09:54:21,426 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:54:21,426 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-23 09:54:21,426 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:54:21,427 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-23 09:54:21,444 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:54:36,001 INFO L134 CoverageAnalysis]: Checked inductivity of 172 backedges. 32 proven. 140 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:54:36,002 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:54:36,002 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-23 09:54:36,002 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-23 09:54:36,002 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-23 09:54:36,002 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:54:36,002 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-23 09:54:36,010 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-23 09:54:36,011 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-10-23 09:54:36,051 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:54:36,054 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-23 09:54:36,162 INFO L134 CoverageAnalysis]: Checked inductivity of 172 backedges. 32 proven. 140 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:54:36,162 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-23 09:54:36,532 INFO L134 CoverageAnalysis]: Checked inductivity of 172 backedges. 32 proven. 140 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:54:36,553 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-10-23 09:54:36,553 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 11] total 28 [2018-10-23 09:54:36,553 INFO L251 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-23 09:54:36,555 INFO L460 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-10-23 09:54:36,556 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-10-23 09:54:36,556 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=214, Invalid=536, Unknown=6, NotChecked=0, Total=756 [2018-10-23 09:54:36,556 INFO L87 Difference]: Start difference. First operand 64 states and 65 transitions. Second operand 19 states. [2018-10-23 09:54:37,077 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-23 09:54:37,077 INFO L93 Difference]: Finished difference Result 87 states and 89 transitions. [2018-10-23 09:54:37,077 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-10-23 09:54:37,077 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 60 [2018-10-23 09:54:37,077 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-23 09:54:37,078 INFO L225 Difference]: With dead ends: 87 [2018-10-23 09:54:37,078 INFO L226 Difference]: Without dead ends: 74 [2018-10-23 09:54:37,079 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 131 GetRequests, 104 SyntacticMatches, 1 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 172 ImplicationChecksByTransitivity, 14.9s TimeCoverageRelationStatistics Valid=214, Invalid=536, Unknown=6, NotChecked=0, Total=756 [2018-10-23 09:54:37,079 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2018-10-23 09:54:37,088 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 66. [2018-10-23 09:54:37,088 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 66 states. [2018-10-23 09:54:37,089 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 66 states to 66 states and 67 transitions. [2018-10-23 09:54:37,089 INFO L78 Accepts]: Start accepts. Automaton has 66 states and 67 transitions. Word has length 60 [2018-10-23 09:54:37,089 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-23 09:54:37,089 INFO L481 AbstractCegarLoop]: Abstraction has 66 states and 67 transitions. [2018-10-23 09:54:37,089 INFO L482 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-10-23 09:54:37,089 INFO L276 IsEmpty]: Start isEmpty. Operand 66 states and 67 transitions. [2018-10-23 09:54:37,090 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2018-10-23 09:54:37,090 INFO L367 BasicCegarLoop]: Found error trace [2018-10-23 09:54:37,090 INFO L375 BasicCegarLoop]: trace histogram [9, 9, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-23 09:54:37,090 INFO L424 AbstractCegarLoop]: === Iteration 22 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-23 09:54:37,090 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-23 09:54:37,091 INFO L82 PathProgramCache]: Analyzing trace with hash -649680902, now seen corresponding path program 8 times [2018-10-23 09:54:37,091 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-23 09:54:37,091 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:54:37,091 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-23 09:54:37,091 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-23 09:54:37,092 INFO L288 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-23 09:54:37,120 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-23 09:54:39,490 WARN L179 SmtUtils]: Spent 2.21 s on a formula simplification. DAG size of input: 126 DAG size of output: 24 [2018-10-23 09:54:40,297 WARN L179 SmtUtils]: Spent 233.00 ms on a formula simplification. DAG size of input: 83 DAG size of output: 41 [2018-10-23 09:54:40,889 WARN L179 SmtUtils]: Spent 141.00 ms on a formula simplification. DAG size of input: 90 DAG size of output: 45 [2018-10-23 09:54:41,117 WARN L179 SmtUtils]: Spent 178.00 ms on a formula simplification. DAG size of input: 96 DAG size of output: 53 [2018-10-23 09:54:41,302 WARN L179 SmtUtils]: Spent 134.00 ms on a formula simplification. DAG size of input: 83 DAG size of output: 44 [2018-10-23 09:54:41,610 WARN L179 SmtUtils]: Spent 115.00 ms on a formula simplification. DAG size of input: 72 DAG size of output: 44 [2018-10-23 09:54:52,080 WARN L179 SmtUtils]: Spent 10.15 s on a formula simplification. DAG size of input: 87 DAG size of output: 36 [2018-10-23 09:54:52,105 INFO L134 CoverageAnalysis]: Checked inductivity of 172 backedges. 0 proven. 172 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-23 09:54:52,105 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:54:52,105 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-23 09:54:52,105 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-23 09:54:52,106 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-23 09:54:52,106 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-23 09:54:52,106 INFO L194 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-23 09:54:52,114 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-10-23 09:54:52,114 INFO L288 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-10-23 09:54:52,429 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-10-23 09:54:52,429 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-23 09:54:52,434 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-23 09:54:52,442 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 46 treesize of output 43 [2018-10-23 09:54:52,448 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-10-23 09:54:52,449 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-10-23 09:54:52,471 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-23 09:54:52,483 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-10-23 09:54:52,486 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-10-23 09:54:52,486 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-10-23 09:54:54,508 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-23 09:54:54,510 WARN L307 Elim1Store]: Array PQE input equivalent to false [2018-10-23 09:54:54,510 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 1 xjuncts. [2018-10-23 09:54:54,511 WARN L307 Elim1Store]: Array PQE input equivalent to false [2018-10-23 09:54:54,512 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-10-23 09:54:54,516 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-10-23 09:54:54,520 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-10-23 09:54:54,521 INFO L267 ElimStorePlain]: Start of recursive call 9: End of recursive call: and 1 xjuncts. [2018-10-23 09:54:54,548 INFO L267 ElimStorePlain]: Start of recursive call 8: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-23 09:54:54,554 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-10-23 09:54:54,557 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-10-23 09:54:54,557 INFO L267 ElimStorePlain]: Start of recursive call 11: End of recursive call: and 1 xjuncts. [2018-10-23 09:54:54,575 INFO L267 ElimStorePlain]: Start of recursive call 10: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-23 09:54:54,674 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 2 dim-2 vars, End of recursive call: 2 dim-0 vars, and 2 xjuncts. [2018-10-23 09:54:54,674 INFO L202 ElimStorePlain]: Needed 11 recursive calls to eliminate 5 variables, input treesize:445, output treesize:66 [2018-10-23 09:54:57,129 WARN L179 SmtUtils]: Spent 2.13 s on a formula simplification that was a NOOP. DAG size: 49 [2018-10-23 09:54:59,444 WARN L179 SmtUtils]: Spent 2.13 s on a formula simplification that was a NOOP. DAG size: 54 [2018-10-23 09:54:59,746 WARN L179 SmtUtils]: Spent 125.00 ms on a formula simplification that was a NOOP. DAG size: 58 [2018-10-23 09:55:02,528 WARN L179 SmtUtils]: Spent 2.27 s on a formula simplification. DAG size of input: 63 DAG size of output: 63 [2018-10-23 09:55:03,536 WARN L179 SmtUtils]: Spent 782.00 ms on a formula simplification that was a NOOP. DAG size: 66 [2018-10-23 09:55:07,162 WARN L179 SmtUtils]: Spent 3.03 s on a formula simplification. DAG size of input: 71 DAG size of output: 71 [2018-10-23 09:55:11,079 WARN L179 SmtUtils]: Spent 3.52 s on a formula simplification that was a NOOP. DAG size: 74 Received shutdown request... [2018-10-23 09:55:12,704 WARN L187 SmtUtils]: Removed 3 from assertion stack [2018-10-23 09:55:12,704 INFO L177 TraceCheckSpWp]: Timeout while computing interpolants [2018-10-23 09:55:12,905 WARN L522 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-23 09:55:12,905 WARN L550 AbstractCegarLoop]: Verification canceled [2018-10-23 09:55:12,910 WARN L205 ceAbstractionStarter]: Timeout [2018-10-23 09:55:12,910 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 23.10 09:55:12 BoogieIcfgContainer [2018-10-23 09:55:12,910 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-10-23 09:55:12,911 INFO L168 Benchmark]: Toolchain (without parser) took 246869.67 ms. Allocated memory was 1.5 GB in the beginning and 3.8 GB in the end (delta: 2.2 GB). Free memory was 1.4 GB in the beginning and 3.1 GB in the end (delta: -1.6 GB). Peak memory consumption was 608.3 MB. Max. memory is 7.1 GB. [2018-10-23 09:55:12,912 INFO L168 Benchmark]: CDTParser took 0.17 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-10-23 09:55:12,912 INFO L168 Benchmark]: CACSL2BoogieTranslator took 281.33 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-10-23 09:55:12,912 INFO L168 Benchmark]: Boogie Procedure Inliner took 44.40 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-10-23 09:55:12,913 INFO L168 Benchmark]: Boogie Preprocessor took 33.08 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-10-23 09:55:12,913 INFO L168 Benchmark]: RCFGBuilder took 643.09 ms. Allocated memory was 1.5 GB in the beginning and 2.3 GB in the end (delta: 762.8 MB). Free memory was 1.4 GB in the beginning and 2.2 GB in the end (delta: -797.7 MB). Peak memory consumption was 26.7 MB. Max. memory is 7.1 GB. [2018-10-23 09:55:12,913 INFO L168 Benchmark]: TraceAbstraction took 245859.53 ms. Allocated memory was 2.3 GB in the beginning and 3.8 GB in the end (delta: 1.5 GB). Free memory was 2.2 GB in the beginning and 3.1 GB in the end (delta: -846.4 MB). Peak memory consumption was 632.6 MB. Max. memory is 7.1 GB. [2018-10-23 09:55:12,915 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.17 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 281.33 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 44.40 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 33.08 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 643.09 ms. Allocated memory was 1.5 GB in the beginning and 2.3 GB in the end (delta: 762.8 MB). Free memory was 1.4 GB in the beginning and 2.2 GB in the end (delta: -797.7 MB). Peak memory consumption was 26.7 MB. Max. memory is 7.1 GB. * TraceAbstraction took 245859.53 ms. Allocated memory was 2.3 GB in the beginning and 3.8 GB in the end (delta: 1.5 GB). Free memory was 2.2 GB in the beginning and 3.1 GB in the end (delta: -846.4 MB). Peak memory consumption was 632.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 61 with TraceHistMax 9,while TraceCheckSpWp was constructing forward predicates,while PredicateUnifier was unifying predicates,while SimplifyDDAWithTimeout was simplifying term of DAG size 79. - StatisticsResult: Ultimate Automizer benchmark data CFG has 5 procedures, 29 locations, 1 error locations. TIMEOUT Result, 245.7s OverallTime, 22 OverallIterations, 9 TraceHistogramMax, 49.9s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 464 SDtfs, 539 SDslu, 3677 SDs, 0 SdLazy, 5801 SolverSat, 174 SolverUnsat, 2 SolverUnknown, 0 SolverNotchecked, 13.4s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1536 GetRequests, 954 SyntacticMatches, 43 SemanticMatches, 539 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 5479 ImplicationChecksByTransitivity, 157.6s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=66occurred in iteration=21, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 14.3s AbstIntTime, 3 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 21 MinimizatonAttempts, 90 StatesRemovedByMinimization, 19 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 1.4s SatisfiabilityAnalysisTime, 142.9s InterpolantComputationTime, 1367 NumberOfCodeBlocks, 1367 NumberOfCodeBlocksAsserted, 44 NumberOfCheckSat, 1936 ConstructedInterpolants, 225 QuantifiedInterpolants, 2941170 SizeOfPredicates, 190 NumberOfNonLiveVariables, 2759 ConjunctsInSsa, 580 ConjunctsInUnsatCore, 51 InterpolantComputations, 6 PerfectInterpolantSequences, 432/2876 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Completed graceful shutdown