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/automizer/svcomp-Reach-64bit-Automizer_Default.epf -i ../../../trunk/examples/svcomp/eca-rers2012/Problem11_label45_true-unreach-call.c -------------------------------------------------------------------------------- This is Ultimate 0.1.23-1dbac8b [2018-10-26 21:11:52,922 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-10-26 21:11:52,924 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-10-26 21:11:52,943 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-10-26 21:11:52,943 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-10-26 21:11:52,945 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-10-26 21:11:52,947 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-10-26 21:11:52,950 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-10-26 21:11:52,952 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-10-26 21:11:52,954 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-10-26 21:11:52,955 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-10-26 21:11:52,958 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-10-26 21:11:52,959 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-10-26 21:11:52,960 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-10-26 21:11:52,963 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-10-26 21:11:52,964 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-10-26 21:11:52,965 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-10-26 21:11:52,974 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-10-26 21:11:52,975 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-10-26 21:11:52,981 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-10-26 21:11:52,982 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-10-26 21:11:52,983 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-10-26 21:11:52,986 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-10-26 21:11:52,986 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-10-26 21:11:52,986 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-10-26 21:11:52,989 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-10-26 21:11:52,990 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-10-26 21:11:52,991 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-10-26 21:11:52,994 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-10-26 21:11:52,997 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-10-26 21:11:52,997 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-10-26 21:11:52,998 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-10-26 21:11:52,999 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-10-26 21:11:52,999 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-10-26 21:11:53,000 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-10-26 21:11:53,001 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-10-26 21:11:53,001 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/../../../trunk/examples/settings/default/automizer/svcomp-Reach-64bit-Automizer_Default.epf [2018-10-26 21:11:53,026 INFO L110 SettingsManager]: Loading preferences was successful [2018-10-26 21:11:53,026 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-10-26 21:11:53,027 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-10-26 21:11:53,027 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-10-26 21:11:53,028 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-10-26 21:11:53,028 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-10-26 21:11:53,028 INFO L133 SettingsManager]: * Use SBE=true [2018-10-26 21:11:53,028 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-10-26 21:11:53,028 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-10-26 21:11:53,029 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-10-26 21:11:53,029 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-10-26 21:11:53,029 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-10-26 21:11:53,029 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-10-26 21:11:53,029 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-10-26 21:11:53,030 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-10-26 21:11:53,030 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-10-26 21:11:53,030 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-10-26 21:11:53,030 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-10-26 21:11:53,030 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-10-26 21:11:53,031 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-10-26 21:11:53,031 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-10-26 21:11:53,031 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-10-26 21:11:53,031 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-10-26 21:11:53,031 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-10-26 21:11:53,032 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-10-26 21:11:53,032 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-10-26 21:11:53,032 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-10-26 21:11:53,032 INFO L133 SettingsManager]: * To the following directory=dump/ [2018-10-26 21:11:53,081 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-10-26 21:11:53,094 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-10-26 21:11:53,098 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-10-26 21:11:53,100 INFO L271 PluginConnector]: Initializing CDTParser... [2018-10-26 21:11:53,100 INFO L276 PluginConnector]: CDTParser initialized [2018-10-26 21:11:53,101 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/../../../trunk/examples/svcomp/eca-rers2012/Problem11_label45_true-unreach-call.c [2018-10-26 21:11:53,160 INFO L218 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/data/87afbbaa7/8117ef11887b4b2883b3a4049222791f/FLAG95f59a51b [2018-10-26 21:11:53,804 INFO L298 CDTParser]: Found 1 translation units. [2018-10-26 21:11:53,807 INFO L158 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/eca-rers2012/Problem11_label45_true-unreach-call.c [2018-10-26 21:11:53,825 INFO L346 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/data/87afbbaa7/8117ef11887b4b2883b3a4049222791f/FLAG95f59a51b [2018-10-26 21:11:53,842 INFO L354 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/data/87afbbaa7/8117ef11887b4b2883b3a4049222791f [2018-10-26 21:11:53,854 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-10-26 21:11:53,856 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2018-10-26 21:11:53,857 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-10-26 21:11:53,857 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-10-26 21:11:53,862 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-10-26 21:11:53,863 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 26.10 09:11:53" (1/1) ... [2018-10-26 21:11:53,866 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@75024a1d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.10 09:11:53, skipping insertion in model container [2018-10-26 21:11:53,866 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 26.10 09:11:53" (1/1) ... [2018-10-26 21:11:53,878 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2018-10-26 21:11:53,975 INFO L174 MainTranslator]: Built tables and reachable declarations [2018-10-26 21:11:54,762 INFO L202 PostProcessor]: Analyzing one entry point: main [2018-10-26 21:11:54,767 INFO L189 MainTranslator]: Completed pre-run [2018-10-26 21:11:54,937 INFO L202 PostProcessor]: Analyzing one entry point: main [2018-10-26 21:11:54,956 INFO L193 MainTranslator]: Completed translation [2018-10-26 21:11:54,957 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.10 09:11:54 WrapperNode [2018-10-26 21:11:54,957 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-10-26 21:11:54,958 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2018-10-26 21:11:54,958 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2018-10-26 21:11:54,958 INFO L276 PluginConnector]: Boogie Procedure Inliner initialized [2018-10-26 21:11:54,969 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.10 09:11:54" (1/1) ... [2018-10-26 21:11:55,019 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.10 09:11:54" (1/1) ... [2018-10-26 21:11:55,278 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2018-10-26 21:11:55,279 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-10-26 21:11:55,279 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-10-26 21:11:55,279 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-10-26 21:11:55,291 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.10 09:11:54" (1/1) ... [2018-10-26 21:11:55,291 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.10 09:11:54" (1/1) ... [2018-10-26 21:11:55,308 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.10 09:11:54" (1/1) ... [2018-10-26 21:11:55,309 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.10 09:11:54" (1/1) ... [2018-10-26 21:11:55,369 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.10 09:11:54" (1/1) ... [2018-10-26 21:11:55,389 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.10 09:11:54" (1/1) ... [2018-10-26 21:11:55,403 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.10 09:11:54" (1/1) ... [2018-10-26 21:11:55,424 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-10-26 21:11:55,425 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-10-26 21:11:55,425 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-10-26 21:11:55,425 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-10-26 21:11:55,426 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.10 09:11:54" (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-26 21:11:55,495 INFO L130 BoogieDeclarations]: Found specification of procedure exit [2018-10-26 21:11:55,495 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-10-26 21:11:55,496 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-10-26 21:12:00,285 INFO L341 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-10-26 21:12:00,286 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.10 09:12:00 BoogieIcfgContainer [2018-10-26 21:12:00,286 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-10-26 21:12:00,287 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-10-26 21:12:00,288 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-10-26 21:12:00,292 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-10-26 21:12:00,293 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 26.10 09:11:53" (1/3) ... [2018-10-26 21:12:00,293 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3f71cd7f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 26.10 09:12:00, skipping insertion in model container [2018-10-26 21:12:00,294 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 26.10 09:11:54" (2/3) ... [2018-10-26 21:12:00,294 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3f71cd7f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 26.10 09:12:00, skipping insertion in model container [2018-10-26 21:12:00,294 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.10 09:12:00" (3/3) ... [2018-10-26 21:12:00,298 INFO L112 eAbstractionObserver]: Analyzing ICFG Problem11_label45_true-unreach-call.c [2018-10-26 21:12:00,310 INFO L136 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-10-26 21:12:00,325 INFO L148 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-10-26 21:12:00,344 INFO L257 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2018-10-26 21:12:00,396 INFO L135 ementStrategyFactory]: Using default assertion order modulation [2018-10-26 21:12:00,397 INFO L382 AbstractCegarLoop]: Interprodecural is true [2018-10-26 21:12:00,397 INFO L383 AbstractCegarLoop]: Hoare is true [2018-10-26 21:12:00,397 INFO L384 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-10-26 21:12:00,398 INFO L385 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-10-26 21:12:00,398 INFO L386 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-10-26 21:12:00,398 INFO L387 AbstractCegarLoop]: Difference is false [2018-10-26 21:12:00,398 INFO L388 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-10-26 21:12:00,398 INFO L393 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-10-26 21:12:00,435 INFO L276 IsEmpty]: Start isEmpty. Operand 284 states. [2018-10-26 21:12:00,451 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2018-10-26 21:12:00,451 INFO L367 BasicCegarLoop]: Found error trace [2018-10-26 21:12:00,454 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-26 21:12:00,457 INFO L424 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-26 21:12:00,464 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-26 21:12:00,464 INFO L82 PathProgramCache]: Analyzing trace with hash 575043410, now seen corresponding path program 1 times [2018-10-26 21:12:00,467 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-26 21:12:00,467 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-26 21:12:00,530 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:12:00,531 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:12:00,531 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:12:00,609 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:12:00,957 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-26 21:12:00,961 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-26 21:12:00,964 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-10-26 21:12:00,970 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-10-26 21:12:00,989 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-10-26 21:12:00,990 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-10-26 21:12:00,993 INFO L87 Difference]: Start difference. First operand 284 states. Second operand 4 states. [2018-10-26 21:12:04,660 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-26 21:12:04,660 INFO L93 Difference]: Finished difference Result 972 states and 1744 transitions. [2018-10-26 21:12:04,661 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-10-26 21:12:04,663 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 33 [2018-10-26 21:12:04,663 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-26 21:12:04,711 INFO L225 Difference]: With dead ends: 972 [2018-10-26 21:12:04,711 INFO L226 Difference]: Without dead ends: 681 [2018-10-26 21:12:04,719 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-10-26 21:12:04,743 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 681 states. [2018-10-26 21:12:04,811 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 681 to 469. [2018-10-26 21:12:04,816 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 469 states. [2018-10-26 21:12:04,818 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 469 states to 469 states and 728 transitions. [2018-10-26 21:12:04,820 INFO L78 Accepts]: Start accepts. Automaton has 469 states and 728 transitions. Word has length 33 [2018-10-26 21:12:04,821 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-26 21:12:04,822 INFO L481 AbstractCegarLoop]: Abstraction has 469 states and 728 transitions. [2018-10-26 21:12:04,822 INFO L482 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-10-26 21:12:04,822 INFO L276 IsEmpty]: Start isEmpty. Operand 469 states and 728 transitions. [2018-10-26 21:12:04,826 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 103 [2018-10-26 21:12:04,826 INFO L367 BasicCegarLoop]: Found error trace [2018-10-26 21:12:04,826 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-26 21:12:04,827 INFO L424 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-26 21:12:04,827 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-26 21:12:04,827 INFO L82 PathProgramCache]: Analyzing trace with hash -294278150, now seen corresponding path program 1 times [2018-10-26 21:12:04,827 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-26 21:12:04,828 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-26 21:12:04,829 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:12:04,829 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:12:04,829 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:12:04,892 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:12:05,086 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 30 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-26 21:12:05,086 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-26 21:12:05,086 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-10-26 21:12:05,088 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-10-26 21:12:05,089 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-10-26 21:12:05,089 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-10-26 21:12:05,089 INFO L87 Difference]: Start difference. First operand 469 states and 728 transitions. Second operand 4 states. [2018-10-26 21:12:08,952 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-26 21:12:08,953 INFO L93 Difference]: Finished difference Result 1695 states and 2717 transitions. [2018-10-26 21:12:08,953 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-10-26 21:12:08,954 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 102 [2018-10-26 21:12:08,954 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-26 21:12:08,962 INFO L225 Difference]: With dead ends: 1695 [2018-10-26 21:12:08,962 INFO L226 Difference]: Without dead ends: 1228 [2018-10-26 21:12:08,966 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-10-26 21:12:08,967 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1228 states. [2018-10-26 21:12:09,016 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1228 to 1214. [2018-10-26 21:12:09,017 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1214 states. [2018-10-26 21:12:09,022 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1214 states to 1214 states and 1784 transitions. [2018-10-26 21:12:09,022 INFO L78 Accepts]: Start accepts. Automaton has 1214 states and 1784 transitions. Word has length 102 [2018-10-26 21:12:09,023 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-26 21:12:09,023 INFO L481 AbstractCegarLoop]: Abstraction has 1214 states and 1784 transitions. [2018-10-26 21:12:09,023 INFO L482 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-10-26 21:12:09,023 INFO L276 IsEmpty]: Start isEmpty. Operand 1214 states and 1784 transitions. [2018-10-26 21:12:09,026 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 106 [2018-10-26 21:12:09,026 INFO L367 BasicCegarLoop]: Found error trace [2018-10-26 21:12:09,026 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-26 21:12:09,027 INFO L424 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-26 21:12:09,027 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-26 21:12:09,027 INFO L82 PathProgramCache]: Analyzing trace with hash -263297828, now seen corresponding path program 1 times [2018-10-26 21:12:09,027 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-26 21:12:09,027 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-26 21:12:09,028 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:12:09,029 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:12:09,029 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:12:09,063 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:12:09,384 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 30 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-26 21:12:09,384 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-26 21:12:09,385 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-10-26 21:12:09,385 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-10-26 21:12:09,385 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-10-26 21:12:09,386 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-10-26 21:12:09,386 INFO L87 Difference]: Start difference. First operand 1214 states and 1784 transitions. Second operand 4 states. [2018-10-26 21:12:13,207 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-26 21:12:13,208 INFO L93 Difference]: Finished difference Result 4657 states and 6912 transitions. [2018-10-26 21:12:13,209 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-10-26 21:12:13,209 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 105 [2018-10-26 21:12:13,210 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-26 21:12:13,226 INFO L225 Difference]: With dead ends: 4657 [2018-10-26 21:12:13,227 INFO L226 Difference]: Without dead ends: 3445 [2018-10-26 21:12:13,230 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-10-26 21:12:13,233 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3445 states. [2018-10-26 21:12:13,290 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3445 to 3445. [2018-10-26 21:12:13,290 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3445 states. [2018-10-26 21:12:13,298 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3445 states to 3445 states and 4375 transitions. [2018-10-26 21:12:13,298 INFO L78 Accepts]: Start accepts. Automaton has 3445 states and 4375 transitions. Word has length 105 [2018-10-26 21:12:13,299 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-26 21:12:13,299 INFO L481 AbstractCegarLoop]: Abstraction has 3445 states and 4375 transitions. [2018-10-26 21:12:13,299 INFO L482 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-10-26 21:12:13,299 INFO L276 IsEmpty]: Start isEmpty. Operand 3445 states and 4375 transitions. [2018-10-26 21:12:13,308 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 162 [2018-10-26 21:12:13,309 INFO L367 BasicCegarLoop]: Found error trace [2018-10-26 21:12:13,312 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-26 21:12:13,312 INFO L424 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-26 21:12:13,313 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-26 21:12:13,313 INFO L82 PathProgramCache]: Analyzing trace with hash 316350140, now seen corresponding path program 1 times [2018-10-26 21:12:13,313 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-26 21:12:13,313 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-26 21:12:13,314 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:12:13,314 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:12:13,314 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:12:13,373 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:12:13,709 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 30 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-26 21:12:13,710 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-26 21:12:13,710 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-10-26 21:12:13,711 INFO L460 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-10-26 21:12:13,711 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-10-26 21:12:13,711 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2018-10-26 21:12:13,711 INFO L87 Difference]: Start difference. First operand 3445 states and 4375 transitions. Second operand 5 states. [2018-10-26 21:12:17,996 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-26 21:12:17,996 INFO L93 Difference]: Finished difference Result 10825 states and 14157 transitions. [2018-10-26 21:12:17,997 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-10-26 21:12:17,997 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 161 [2018-10-26 21:12:17,998 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-26 21:12:18,032 INFO L225 Difference]: With dead ends: 10825 [2018-10-26 21:12:18,033 INFO L226 Difference]: Without dead ends: 7567 [2018-10-26 21:12:18,037 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2018-10-26 21:12:18,043 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 7567 states. [2018-10-26 21:12:18,156 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 7567 to 7566. [2018-10-26 21:12:18,156 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 7566 states. [2018-10-26 21:12:18,172 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7566 states to 7566 states and 9466 transitions. [2018-10-26 21:12:18,172 INFO L78 Accepts]: Start accepts. Automaton has 7566 states and 9466 transitions. Word has length 161 [2018-10-26 21:12:18,173 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-26 21:12:18,173 INFO L481 AbstractCegarLoop]: Abstraction has 7566 states and 9466 transitions. [2018-10-26 21:12:18,173 INFO L482 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-10-26 21:12:18,173 INFO L276 IsEmpty]: Start isEmpty. Operand 7566 states and 9466 transitions. [2018-10-26 21:12:18,180 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 229 [2018-10-26 21:12:18,180 INFO L367 BasicCegarLoop]: Found error trace [2018-10-26 21:12:18,180 INFO L375 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-26 21:12:18,182 INFO L424 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-26 21:12:18,182 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-26 21:12:18,182 INFO L82 PathProgramCache]: Analyzing trace with hash -2090882901, now seen corresponding path program 1 times [2018-10-26 21:12:18,182 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-26 21:12:18,182 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-26 21:12:18,183 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:12:18,183 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:12:18,184 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:12:18,243 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:12:18,604 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 61 proven. 0 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2018-10-26 21:12:18,604 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-26 21:12:18,604 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-10-26 21:12:18,605 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-10-26 21:12:18,605 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-10-26 21:12:18,605 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-10-26 21:12:18,606 INFO L87 Difference]: Start difference. First operand 7566 states and 9466 transitions. Second operand 4 states. [2018-10-26 21:12:20,871 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-26 21:12:20,871 INFO L93 Difference]: Finished difference Result 14971 states and 18789 transitions. [2018-10-26 21:12:20,872 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-10-26 21:12:20,873 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 228 [2018-10-26 21:12:20,873 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-26 21:12:20,899 INFO L225 Difference]: With dead ends: 14971 [2018-10-26 21:12:20,899 INFO L226 Difference]: Without dead ends: 7592 [2018-10-26 21:12:20,909 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-10-26 21:12:20,915 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 7592 states. [2018-10-26 21:12:21,034 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 7592 to 7565. [2018-10-26 21:12:21,034 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 7565 states. [2018-10-26 21:12:21,049 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7565 states to 7565 states and 8984 transitions. [2018-10-26 21:12:21,050 INFO L78 Accepts]: Start accepts. Automaton has 7565 states and 8984 transitions. Word has length 228 [2018-10-26 21:12:21,050 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-26 21:12:21,050 INFO L481 AbstractCegarLoop]: Abstraction has 7565 states and 8984 transitions. [2018-10-26 21:12:21,050 INFO L482 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-10-26 21:12:21,051 INFO L276 IsEmpty]: Start isEmpty. Operand 7565 states and 8984 transitions. [2018-10-26 21:12:21,055 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 230 [2018-10-26 21:12:21,056 INFO L367 BasicCegarLoop]: Found error trace [2018-10-26 21:12:21,056 INFO L375 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-26 21:12:21,056 INFO L424 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-26 21:12:21,057 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-26 21:12:21,057 INFO L82 PathProgramCache]: Analyzing trace with hash -506625732, now seen corresponding path program 1 times [2018-10-26 21:12:21,057 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-26 21:12:21,057 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-26 21:12:21,058 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:12:21,058 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:12:21,058 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:12:21,098 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:12:21,476 INFO L134 CoverageAnalysis]: Checked inductivity of 128 backedges. 128 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-26 21:12:21,477 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-26 21:12:21,477 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-10-26 21:12:21,478 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-10-26 21:12:21,478 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-10-26 21:12:21,478 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-10-26 21:12:21,478 INFO L87 Difference]: Start difference. First operand 7565 states and 8984 transitions. Second operand 4 states. [2018-10-26 21:12:23,380 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-26 21:12:23,380 INFO L93 Difference]: Finished difference Result 19035 states and 23078 transitions. [2018-10-26 21:12:23,383 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-10-26 21:12:23,383 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 229 [2018-10-26 21:12:23,385 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-26 21:12:23,441 INFO L225 Difference]: With dead ends: 19035 [2018-10-26 21:12:23,441 INFO L226 Difference]: Without dead ends: 11657 [2018-10-26 21:12:23,452 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-10-26 21:12:23,461 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 11657 states. [2018-10-26 21:12:23,634 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 11657 to 11080. [2018-10-26 21:12:23,634 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 11080 states. [2018-10-26 21:12:23,654 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11080 states to 11080 states and 13221 transitions. [2018-10-26 21:12:23,654 INFO L78 Accepts]: Start accepts. Automaton has 11080 states and 13221 transitions. Word has length 229 [2018-10-26 21:12:23,655 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-26 21:12:23,655 INFO L481 AbstractCegarLoop]: Abstraction has 11080 states and 13221 transitions. [2018-10-26 21:12:23,655 INFO L482 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-10-26 21:12:23,655 INFO L276 IsEmpty]: Start isEmpty. Operand 11080 states and 13221 transitions. [2018-10-26 21:12:23,666 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 286 [2018-10-26 21:12:23,666 INFO L367 BasicCegarLoop]: Found error trace [2018-10-26 21:12:23,667 INFO L375 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-26 21:12:23,667 INFO L424 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-26 21:12:23,667 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-26 21:12:23,667 INFO L82 PathProgramCache]: Analyzing trace with hash -1732908421, now seen corresponding path program 1 times [2018-10-26 21:12:23,668 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-26 21:12:23,668 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-26 21:12:23,669 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:12:23,669 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:12:23,669 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:12:23,729 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:12:24,046 INFO L134 CoverageAnalysis]: Checked inductivity of 297 backedges. 227 proven. 0 refuted. 0 times theorem prover too weak. 70 trivial. 0 not checked. [2018-10-26 21:12:24,046 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-26 21:12:24,047 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-10-26 21:12:24,047 INFO L460 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-10-26 21:12:24,048 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-10-26 21:12:24,048 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-10-26 21:12:24,048 INFO L87 Difference]: Start difference. First operand 11080 states and 13221 transitions. Second operand 3 states. [2018-10-26 21:12:25,799 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-26 21:12:25,800 INFO L93 Difference]: Finished difference Result 25300 states and 30301 transitions. [2018-10-26 21:12:25,800 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-10-26 21:12:25,800 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 285 [2018-10-26 21:12:25,801 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-26 21:12:25,826 INFO L225 Difference]: With dead ends: 25300 [2018-10-26 21:12:25,826 INFO L226 Difference]: Without dead ends: 13654 [2018-10-26 21:12:25,838 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-10-26 21:12:25,849 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 13654 states. [2018-10-26 21:12:25,984 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 13654 to 13282. [2018-10-26 21:12:25,984 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 13282 states. [2018-10-26 21:12:26,001 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13282 states to 13282 states and 15179 transitions. [2018-10-26 21:12:26,001 INFO L78 Accepts]: Start accepts. Automaton has 13282 states and 15179 transitions. Word has length 285 [2018-10-26 21:12:26,002 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-26 21:12:26,002 INFO L481 AbstractCegarLoop]: Abstraction has 13282 states and 15179 transitions. [2018-10-26 21:12:26,002 INFO L482 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-10-26 21:12:26,002 INFO L276 IsEmpty]: Start isEmpty. Operand 13282 states and 15179 transitions. [2018-10-26 21:12:26,016 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 329 [2018-10-26 21:12:26,016 INFO L367 BasicCegarLoop]: Found error trace [2018-10-26 21:12:26,017 INFO L375 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-26 21:12:26,017 INFO L424 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-26 21:12:26,017 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-26 21:12:26,017 INFO L82 PathProgramCache]: Analyzing trace with hash -1591903917, now seen corresponding path program 1 times [2018-10-26 21:12:26,018 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-26 21:12:26,018 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-26 21:12:26,019 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:12:26,019 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:12:26,019 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:12:26,084 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:12:26,406 INFO L134 CoverageAnalysis]: Checked inductivity of 333 backedges. 258 proven. 0 refuted. 0 times theorem prover too weak. 75 trivial. 0 not checked. [2018-10-26 21:12:26,406 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-26 21:12:26,406 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-10-26 21:12:26,407 INFO L460 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-10-26 21:12:26,407 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-10-26 21:12:26,407 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-10-26 21:12:26,407 INFO L87 Difference]: Start difference. First operand 13282 states and 15179 transitions. Second operand 3 states. [2018-10-26 21:12:27,643 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-26 21:12:27,644 INFO L93 Difference]: Finished difference Result 27314 states and 31303 transitions. [2018-10-26 21:12:27,645 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-10-26 21:12:27,646 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 328 [2018-10-26 21:12:27,647 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-26 21:12:27,671 INFO L225 Difference]: With dead ends: 27314 [2018-10-26 21:12:27,671 INFO L226 Difference]: Without dead ends: 12720 [2018-10-26 21:12:27,685 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-10-26 21:12:27,699 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 12720 states. [2018-10-26 21:12:27,835 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 12720 to 12345. [2018-10-26 21:12:27,835 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 12345 states. [2018-10-26 21:12:27,850 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 12345 states to 12345 states and 13968 transitions. [2018-10-26 21:12:27,851 INFO L78 Accepts]: Start accepts. Automaton has 12345 states and 13968 transitions. Word has length 328 [2018-10-26 21:12:27,851 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-26 21:12:27,851 INFO L481 AbstractCegarLoop]: Abstraction has 12345 states and 13968 transitions. [2018-10-26 21:12:27,851 INFO L482 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-10-26 21:12:27,852 INFO L276 IsEmpty]: Start isEmpty. Operand 12345 states and 13968 transitions. [2018-10-26 21:12:27,865 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 334 [2018-10-26 21:12:27,865 INFO L367 BasicCegarLoop]: Found error trace [2018-10-26 21:12:27,866 INFO L375 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-26 21:12:27,866 INFO L424 AbstractCegarLoop]: === Iteration 9 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-26 21:12:27,866 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-26 21:12:27,867 INFO L82 PathProgramCache]: Analyzing trace with hash 326232789, now seen corresponding path program 1 times [2018-10-26 21:12:27,867 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-26 21:12:27,867 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-26 21:12:27,868 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:12:27,868 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:12:27,868 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:12:27,922 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:12:28,660 INFO L134 CoverageAnalysis]: Checked inductivity of 186 backedges. 0 proven. 186 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-26 21:12:28,661 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-26 21:12:28,661 INFO L225 ckRefinementStrategy]: Switched to mode Z3_FP 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-26 21:12:28,671 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:12:28,805 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:12:28,835 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-26 21:12:29,480 INFO L134 CoverageAnalysis]: Checked inductivity of 186 backedges. 61 proven. 125 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-26 21:12:29,502 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-26 21:12:29,502 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2018-10-26 21:12:29,503 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-10-26 21:12:29,504 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-10-26 21:12:29,504 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2018-10-26 21:12:29,504 INFO L87 Difference]: Start difference. First operand 12345 states and 13968 transitions. Second operand 9 states. [2018-10-26 21:12:37,071 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-26 21:12:37,071 INFO L93 Difference]: Finished difference Result 38270 states and 43536 transitions. [2018-10-26 21:12:37,072 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-10-26 21:12:37,072 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 333 [2018-10-26 21:12:37,073 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-26 21:12:37,120 INFO L225 Difference]: With dead ends: 38270 [2018-10-26 21:12:37,120 INFO L226 Difference]: Without dead ends: 27043 [2018-10-26 21:12:37,137 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 338 GetRequests, 329 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2018-10-26 21:12:37,157 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27043 states. [2018-10-26 21:12:37,562 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27043 to 21838. [2018-10-26 21:12:37,563 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 21838 states. [2018-10-26 21:12:37,855 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21838 states to 21838 states and 24508 transitions. [2018-10-26 21:12:37,856 INFO L78 Accepts]: Start accepts. Automaton has 21838 states and 24508 transitions. Word has length 333 [2018-10-26 21:12:37,856 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-26 21:12:37,857 INFO L481 AbstractCegarLoop]: Abstraction has 21838 states and 24508 transitions. [2018-10-26 21:12:37,857 INFO L482 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-10-26 21:12:37,857 INFO L276 IsEmpty]: Start isEmpty. Operand 21838 states and 24508 transitions. [2018-10-26 21:12:37,874 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 342 [2018-10-26 21:12:37,874 INFO L367 BasicCegarLoop]: Found error trace [2018-10-26 21:12:37,874 INFO L375 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-26 21:12:37,875 INFO L424 AbstractCegarLoop]: === Iteration 10 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-26 21:12:37,875 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-26 21:12:37,875 INFO L82 PathProgramCache]: Analyzing trace with hash -249180895, now seen corresponding path program 1 times [2018-10-26 21:12:37,876 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-26 21:12:37,876 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-26 21:12:37,877 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:12:37,877 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:12:37,877 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:12:37,932 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:12:38,301 INFO L134 CoverageAnalysis]: Checked inductivity of 359 backedges. 328 proven. 0 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2018-10-26 21:12:38,302 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-26 21:12:38,302 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-10-26 21:12:38,303 INFO L460 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-10-26 21:12:38,303 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-10-26 21:12:38,303 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2018-10-26 21:12:38,303 INFO L87 Difference]: Start difference. First operand 21838 states and 24508 transitions. Second operand 5 states. [2018-10-26 21:12:42,903 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-26 21:12:42,904 INFO L93 Difference]: Finished difference Result 55730 states and 62701 transitions. [2018-10-26 21:12:42,905 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-10-26 21:12:42,905 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 341 [2018-10-26 21:12:42,906 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-26 21:12:42,944 INFO L225 Difference]: With dead ends: 55730 [2018-10-26 21:12:42,944 INFO L226 Difference]: Without dead ends: 34079 [2018-10-26 21:12:42,963 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2018-10-26 21:12:42,986 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34079 states. [2018-10-26 21:12:43,311 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34079 to 31658. [2018-10-26 21:12:43,311 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 31658 states. [2018-10-26 21:12:43,352 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31658 states to 31658 states and 34860 transitions. [2018-10-26 21:12:43,352 INFO L78 Accepts]: Start accepts. Automaton has 31658 states and 34860 transitions. Word has length 341 [2018-10-26 21:12:43,353 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-26 21:12:43,353 INFO L481 AbstractCegarLoop]: Abstraction has 31658 states and 34860 transitions. [2018-10-26 21:12:43,353 INFO L482 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-10-26 21:12:43,353 INFO L276 IsEmpty]: Start isEmpty. Operand 31658 states and 34860 transitions. [2018-10-26 21:12:43,370 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 345 [2018-10-26 21:12:43,371 INFO L367 BasicCegarLoop]: Found error trace [2018-10-26 21:12:43,371 INFO L375 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-26 21:12:43,371 INFO L424 AbstractCegarLoop]: === Iteration 11 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-26 21:12:43,372 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-26 21:12:43,372 INFO L82 PathProgramCache]: Analyzing trace with hash -1530952089, now seen corresponding path program 1 times [2018-10-26 21:12:43,372 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-26 21:12:43,372 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-26 21:12:43,375 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:12:43,375 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:12:43,376 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:12:43,427 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:12:44,161 WARN L179 SmtUtils]: Spent 318.00 ms on a formula simplification. DAG size of input: 16 DAG size of output: 11 [2018-10-26 21:12:44,608 WARN L179 SmtUtils]: Spent 359.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 12 [2018-10-26 21:12:44,787 INFO L134 CoverageAnalysis]: Checked inductivity of 379 backedges. 242 proven. 106 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2018-10-26 21:12:44,787 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-26 21:12:44,788 INFO L225 ckRefinementStrategy]: Switched to mode Z3_FP 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-26 21:12:44,796 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:12:44,885 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:12:44,901 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-26 21:12:45,676 INFO L134 CoverageAnalysis]: Checked inductivity of 379 backedges. 0 proven. 273 refuted. 0 times theorem prover too weak. 106 trivial. 0 not checked. [2018-10-26 21:12:45,700 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-26 21:12:45,700 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4] total 8 [2018-10-26 21:12:45,701 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-10-26 21:12:45,701 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-10-26 21:12:45,701 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-10-26 21:12:45,702 INFO L87 Difference]: Start difference. First operand 31658 states and 34860 transitions. Second operand 9 states. [2018-10-26 21:12:57,996 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-26 21:12:57,997 INFO L93 Difference]: Finished difference Result 72597 states and 79705 transitions. [2018-10-26 21:12:57,997 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-10-26 21:12:57,997 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 344 [2018-10-26 21:12:57,998 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-26 21:12:58,030 INFO L225 Difference]: With dead ends: 72597 [2018-10-26 21:12:58,031 INFO L226 Difference]: Without dead ends: 34406 [2018-10-26 21:12:58,056 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 361 GetRequests, 341 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 80 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=108, Invalid=354, Unknown=0, NotChecked=0, Total=462 [2018-10-26 21:12:58,081 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34406 states. [2018-10-26 21:12:58,687 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34406 to 32364. [2018-10-26 21:12:58,687 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 32364 states. [2018-10-26 21:12:58,729 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32364 states to 32364 states and 35297 transitions. [2018-10-26 21:12:58,730 INFO L78 Accepts]: Start accepts. Automaton has 32364 states and 35297 transitions. Word has length 344 [2018-10-26 21:12:58,730 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-26 21:12:58,730 INFO L481 AbstractCegarLoop]: Abstraction has 32364 states and 35297 transitions. [2018-10-26 21:12:58,730 INFO L482 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-10-26 21:12:58,731 INFO L276 IsEmpty]: Start isEmpty. Operand 32364 states and 35297 transitions. [2018-10-26 21:12:58,746 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 360 [2018-10-26 21:12:58,746 INFO L367 BasicCegarLoop]: Found error trace [2018-10-26 21:12:58,746 INFO L375 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-26 21:12:58,747 INFO L424 AbstractCegarLoop]: === Iteration 12 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-26 21:12:58,747 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-26 21:12:58,747 INFO L82 PathProgramCache]: Analyzing trace with hash 1571378605, now seen corresponding path program 1 times [2018-10-26 21:12:58,747 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-26 21:12:58,747 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-26 21:12:58,748 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:12:58,748 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:12:58,748 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:12:58,791 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:12:59,137 INFO L134 CoverageAnalysis]: Checked inductivity of 379 backedges. 348 proven. 0 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2018-10-26 21:12:59,138 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-26 21:12:59,138 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-10-26 21:12:59,138 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-10-26 21:12:59,138 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-10-26 21:12:59,139 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-10-26 21:12:59,139 INFO L87 Difference]: Start difference. First operand 32364 states and 35297 transitions. Second operand 4 states. [2018-10-26 21:13:01,138 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-26 21:13:01,138 INFO L93 Difference]: Finished difference Result 60855 states and 66434 transitions. [2018-10-26 21:13:01,139 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-10-26 21:13:01,139 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 359 [2018-10-26 21:13:01,139 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-26 21:13:01,175 INFO L225 Difference]: With dead ends: 60855 [2018-10-26 21:13:01,175 INFO L226 Difference]: Without dead ends: 36118 [2018-10-26 21:13:01,193 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-10-26 21:13:01,217 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36118 states. [2018-10-26 21:13:01,533 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36118 to 32931. [2018-10-26 21:13:01,534 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 32931 states. [2018-10-26 21:13:01,573 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32931 states to 32931 states and 35800 transitions. [2018-10-26 21:13:01,573 INFO L78 Accepts]: Start accepts. Automaton has 32931 states and 35800 transitions. Word has length 359 [2018-10-26 21:13:01,573 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-26 21:13:01,574 INFO L481 AbstractCegarLoop]: Abstraction has 32931 states and 35800 transitions. [2018-10-26 21:13:01,574 INFO L482 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-10-26 21:13:01,574 INFO L276 IsEmpty]: Start isEmpty. Operand 32931 states and 35800 transitions. [2018-10-26 21:13:01,589 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 410 [2018-10-26 21:13:01,590 INFO L367 BasicCegarLoop]: Found error trace [2018-10-26 21:13:01,590 INFO L375 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-26 21:13:01,590 INFO L424 AbstractCegarLoop]: === Iteration 13 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-26 21:13:01,591 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-26 21:13:01,591 INFO L82 PathProgramCache]: Analyzing trace with hash -711972748, now seen corresponding path program 1 times [2018-10-26 21:13:01,591 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-26 21:13:01,591 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-26 21:13:01,592 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:13:01,592 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:13:01,592 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:13:01,644 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:13:02,036 INFO L134 CoverageAnalysis]: Checked inductivity of 424 backedges. 290 proven. 103 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2018-10-26 21:13:02,037 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-26 21:13:02,037 INFO L225 ckRefinementStrategy]: Switched to mode Z3_FP 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-26 21:13:02,044 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:13:02,152 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:13:02,159 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-26 21:13:02,276 INFO L134 CoverageAnalysis]: Checked inductivity of 424 backedges. 290 proven. 103 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2018-10-26 21:13:02,298 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-26 21:13:02,298 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 3] total 4 [2018-10-26 21:13:02,299 INFO L460 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-10-26 21:13:02,299 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-10-26 21:13:02,299 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-10-26 21:13:02,300 INFO L87 Difference]: Start difference. First operand 32931 states and 35800 transitions. Second operand 5 states. [2018-10-26 21:13:05,383 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-26 21:13:05,383 INFO L93 Difference]: Finished difference Result 64186 states and 69600 transitions. [2018-10-26 21:13:05,384 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-10-26 21:13:05,384 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 409 [2018-10-26 21:13:05,384 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-26 21:13:05,416 INFO L225 Difference]: With dead ends: 64186 [2018-10-26 21:13:05,416 INFO L226 Difference]: Without dead ends: 34596 [2018-10-26 21:13:05,433 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 414 GetRequests, 407 SyntacticMatches, 2 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=18, Invalid=24, Unknown=0, NotChecked=0, Total=42 [2018-10-26 21:13:05,451 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34596 states. [2018-10-26 21:13:05,734 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34596 to 29940. [2018-10-26 21:13:05,734 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 29940 states. [2018-10-26 21:13:05,761 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29940 states to 29940 states and 32206 transitions. [2018-10-26 21:13:05,762 INFO L78 Accepts]: Start accepts. Automaton has 29940 states and 32206 transitions. Word has length 409 [2018-10-26 21:13:05,762 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-26 21:13:05,762 INFO L481 AbstractCegarLoop]: Abstraction has 29940 states and 32206 transitions. [2018-10-26 21:13:05,762 INFO L482 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-10-26 21:13:05,763 INFO L276 IsEmpty]: Start isEmpty. Operand 29940 states and 32206 transitions. [2018-10-26 21:13:05,776 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 420 [2018-10-26 21:13:05,776 INFO L367 BasicCegarLoop]: Found error trace [2018-10-26 21:13:05,777 INFO L375 BasicCegarLoop]: trace histogram [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-26 21:13:05,777 INFO L424 AbstractCegarLoop]: === Iteration 14 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-26 21:13:05,777 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-26 21:13:05,777 INFO L82 PathProgramCache]: Analyzing trace with hash -1562337051, now seen corresponding path program 1 times [2018-10-26 21:13:05,778 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-26 21:13:05,778 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-26 21:13:05,778 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:13:05,779 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:13:05,779 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:13:05,851 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:13:07,103 INFO L134 CoverageAnalysis]: Checked inductivity of 638 backedges. 0 proven. 556 refuted. 0 times theorem prover too weak. 82 trivial. 0 not checked. [2018-10-26 21:13:07,103 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-26 21:13:07,103 INFO L225 ckRefinementStrategy]: Switched to mode Z3_FP 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-26 21:13:07,113 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:13:07,226 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:13:07,232 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-26 21:13:07,641 WARN L179 SmtUtils]: Spent 238.00 ms on a formula simplification. DAG size of input: 161 DAG size of output: 43 [2018-10-26 21:13:10,728 INFO L134 CoverageAnalysis]: Checked inductivity of 638 backedges. 354 proven. 31 refuted. 0 times theorem prover too weak. 253 trivial. 0 not checked. [2018-10-26 21:13:10,749 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-26 21:13:10,749 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 4] total 8 [2018-10-26 21:13:10,750 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-10-26 21:13:10,750 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-10-26 21:13:10,750 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2018-10-26 21:13:10,751 INFO L87 Difference]: Start difference. First operand 29940 states and 32206 transitions. Second operand 8 states. [2018-10-26 21:13:23,442 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-26 21:13:23,443 INFO L93 Difference]: Finished difference Result 62126 states and 66894 transitions. [2018-10-26 21:13:23,443 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-10-26 21:13:23,443 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 419 [2018-10-26 21:13:23,444 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-26 21:13:23,481 INFO L225 Difference]: With dead ends: 62126 [2018-10-26 21:13:23,481 INFO L226 Difference]: Without dead ends: 35714 [2018-10-26 21:13:23,496 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 442 GetRequests, 425 SyntacticMatches, 3 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 35 ImplicationChecksByTransitivity, 3.6s TimeCoverageRelationStatistics Valid=60, Invalid=180, Unknown=0, NotChecked=0, Total=240 [2018-10-26 21:13:23,514 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35714 states. [2018-10-26 21:13:23,724 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35714 to 28446. [2018-10-26 21:13:23,725 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 28446 states. [2018-10-26 21:13:23,746 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28446 states to 28446 states and 30583 transitions. [2018-10-26 21:13:23,746 INFO L78 Accepts]: Start accepts. Automaton has 28446 states and 30583 transitions. Word has length 419 [2018-10-26 21:13:23,747 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-26 21:13:23,747 INFO L481 AbstractCegarLoop]: Abstraction has 28446 states and 30583 transitions. [2018-10-26 21:13:23,747 INFO L482 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-10-26 21:13:23,747 INFO L276 IsEmpty]: Start isEmpty. Operand 28446 states and 30583 transitions. [2018-10-26 21:13:23,761 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 453 [2018-10-26 21:13:23,762 INFO L367 BasicCegarLoop]: Found error trace [2018-10-26 21:13:23,762 INFO L375 BasicCegarLoop]: trace histogram [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-26 21:13:23,763 INFO L424 AbstractCegarLoop]: === Iteration 15 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-26 21:13:23,763 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-26 21:13:23,764 INFO L82 PathProgramCache]: Analyzing trace with hash 1889678859, now seen corresponding path program 1 times [2018-10-26 21:13:23,764 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-26 21:13:23,764 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-26 21:13:23,765 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:13:23,765 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:13:23,765 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:13:23,821 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:13:24,402 WARN L179 SmtUtils]: Spent 132.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2018-10-26 21:13:24,729 INFO L134 CoverageAnalysis]: Checked inductivity of 696 backedges. 134 proven. 465 refuted. 0 times theorem prover too weak. 97 trivial. 0 not checked. [2018-10-26 21:13:24,729 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-26 21:13:24,729 INFO L225 ckRefinementStrategy]: Switched to mode Z3_FP 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-26 21:13:24,737 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:13:24,856 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:13:24,863 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-26 21:13:26,882 INFO L134 CoverageAnalysis]: Checked inductivity of 696 backedges. 260 proven. 339 refuted. 0 times theorem prover too weak. 97 trivial. 0 not checked. [2018-10-26 21:13:26,916 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-26 21:13:26,917 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 5] total 11 [2018-10-26 21:13:26,918 INFO L460 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-10-26 21:13:26,918 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-10-26 21:13:26,918 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=94, Unknown=0, NotChecked=0, Total=132 [2018-10-26 21:13:26,919 INFO L87 Difference]: Start difference. First operand 28446 states and 30583 transitions. Second operand 12 states. [2018-10-26 21:13:35,958 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-26 21:13:35,958 INFO L93 Difference]: Finished difference Result 55575 states and 59795 transitions. [2018-10-26 21:13:35,958 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-10-26 21:13:35,958 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 452 [2018-10-26 21:13:35,959 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-26 21:13:35,986 INFO L225 Difference]: With dead ends: 55575 [2018-10-26 21:13:35,986 INFO L226 Difference]: Without dead ends: 29176 [2018-10-26 21:13:36,001 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 468 GetRequests, 447 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 74 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=160, Invalid=302, Unknown=0, NotChecked=0, Total=462 [2018-10-26 21:13:36,017 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29176 states. [2018-10-26 21:13:36,238 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29176 to 26451. [2018-10-26 21:13:36,238 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 26451 states. [2018-10-26 21:13:36,262 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26451 states to 26451 states and 28311 transitions. [2018-10-26 21:13:36,262 INFO L78 Accepts]: Start accepts. Automaton has 26451 states and 28311 transitions. Word has length 452 [2018-10-26 21:13:36,263 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-26 21:13:36,263 INFO L481 AbstractCegarLoop]: Abstraction has 26451 states and 28311 transitions. [2018-10-26 21:13:36,263 INFO L482 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-10-26 21:13:36,263 INFO L276 IsEmpty]: Start isEmpty. Operand 26451 states and 28311 transitions. [2018-10-26 21:13:36,274 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 509 [2018-10-26 21:13:36,274 INFO L367 BasicCegarLoop]: Found error trace [2018-10-26 21:13:36,275 INFO L375 BasicCegarLoop]: trace histogram [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-26 21:13:36,275 INFO L424 AbstractCegarLoop]: === Iteration 16 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-26 21:13:36,275 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-26 21:13:36,275 INFO L82 PathProgramCache]: Analyzing trace with hash -1264069308, now seen corresponding path program 1 times [2018-10-26 21:13:36,276 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-26 21:13:36,276 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-26 21:13:36,276 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:13:36,277 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:13:36,277 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:13:36,331 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:13:36,671 WARN L179 SmtUtils]: Spent 107.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-10-26 21:13:37,035 WARN L179 SmtUtils]: Spent 313.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 12 [2018-10-26 21:13:37,915 INFO L134 CoverageAnalysis]: Checked inductivity of 656 backedges. 463 proven. 162 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2018-10-26 21:13:37,916 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-26 21:13:37,916 INFO L225 ckRefinementStrategy]: Switched to mode Z3_FP 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-26 21:13:37,924 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:13:38,050 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:13:38,058 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-26 21:13:38,418 INFO L134 CoverageAnalysis]: Checked inductivity of 656 backedges. 467 proven. 158 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2018-10-26 21:13:38,439 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-26 21:13:38,439 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 5] total 9 [2018-10-26 21:13:38,441 INFO L460 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-10-26 21:13:38,441 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-10-26 21:13:38,441 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=61, Unknown=0, NotChecked=0, Total=90 [2018-10-26 21:13:38,441 INFO L87 Difference]: Start difference. First operand 26451 states and 28311 transitions. Second operand 10 states. [2018-10-26 21:13:44,844 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-26 21:13:44,844 INFO L93 Difference]: Finished difference Result 65114 states and 69663 transitions. [2018-10-26 21:13:44,845 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-10-26 21:13:44,845 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 508 [2018-10-26 21:13:44,845 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-26 21:13:44,884 INFO L225 Difference]: With dead ends: 65114 [2018-10-26 21:13:44,884 INFO L226 Difference]: Without dead ends: 40703 [2018-10-26 21:13:44,903 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 529 GetRequests, 505 SyntacticMatches, 3 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 110 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=185, Invalid=321, Unknown=0, NotChecked=0, Total=506 [2018-10-26 21:13:44,927 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40703 states. [2018-10-26 21:13:45,159 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40703 to 22551. [2018-10-26 21:13:45,159 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 22551 states. [2018-10-26 21:13:45,179 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22551 states to 22551 states and 24146 transitions. [2018-10-26 21:13:45,179 INFO L78 Accepts]: Start accepts. Automaton has 22551 states and 24146 transitions. Word has length 508 [2018-10-26 21:13:45,179 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-26 21:13:45,179 INFO L481 AbstractCegarLoop]: Abstraction has 22551 states and 24146 transitions. [2018-10-26 21:13:45,179 INFO L482 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-10-26 21:13:45,180 INFO L276 IsEmpty]: Start isEmpty. Operand 22551 states and 24146 transitions. [2018-10-26 21:13:45,188 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 526 [2018-10-26 21:13:45,188 INFO L367 BasicCegarLoop]: Found error trace [2018-10-26 21:13:45,189 INFO L375 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-26 21:13:45,189 INFO L424 AbstractCegarLoop]: === Iteration 17 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-26 21:13:45,189 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-26 21:13:45,189 INFO L82 PathProgramCache]: Analyzing trace with hash 1912565945, now seen corresponding path program 1 times [2018-10-26 21:13:45,189 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-26 21:13:45,189 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-26 21:13:45,190 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:13:45,190 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:13:45,190 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:13:45,244 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:13:45,790 WARN L179 SmtUtils]: Spent 129.00 ms on a formula simplification that was a NOOP. DAG size: 16 [2018-10-26 21:13:46,053 WARN L179 SmtUtils]: Spent 189.00 ms on a formula simplification. DAG size of input: 26 DAG size of output: 23 [2018-10-26 21:13:47,037 INFO L134 CoverageAnalysis]: Checked inductivity of 562 backedges. 92 proven. 319 refuted. 0 times theorem prover too weak. 151 trivial. 0 not checked. [2018-10-26 21:13:47,038 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-26 21:13:47,038 INFO L225 ckRefinementStrategy]: Switched to mode Z3_FP 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-26 21:13:47,047 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:13:47,178 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:13:47,187 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-26 21:13:48,149 WARN L179 SmtUtils]: Spent 461.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 43 [2018-10-26 21:13:49,428 INFO L134 CoverageAnalysis]: Checked inductivity of 562 backedges. 92 proven. 319 refuted. 0 times theorem prover too weak. 151 trivial. 0 not checked. [2018-10-26 21:13:49,448 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-26 21:13:49,448 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 5] total 11 [2018-10-26 21:13:49,449 INFO L460 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-10-26 21:13:49,450 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-10-26 21:13:49,450 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=99, Unknown=0, NotChecked=0, Total=132 [2018-10-26 21:13:49,450 INFO L87 Difference]: Start difference. First operand 22551 states and 24146 transitions. Second operand 12 states. [2018-10-26 21:13:50,375 WARN L179 SmtUtils]: Spent 115.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 42 [2018-10-26 21:13:52,956 WARN L179 SmtUtils]: Spent 267.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 46 [2018-10-26 21:13:57,131 WARN L179 SmtUtils]: Spent 118.00 ms on a formula simplification. DAG size of input: 55 DAG size of output: 30 [2018-10-26 21:13:58,208 WARN L179 SmtUtils]: Spent 107.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 41 [2018-10-26 21:14:00,565 WARN L179 SmtUtils]: Spent 173.00 ms on a formula simplification. DAG size of input: 33 DAG size of output: 30 [2018-10-26 21:14:00,975 WARN L179 SmtUtils]: Spent 128.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 32 [2018-10-26 21:14:02,755 WARN L179 SmtUtils]: Spent 255.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 45 [2018-10-26 21:14:03,177 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-26 21:14:03,178 INFO L93 Difference]: Finished difference Result 46563 states and 49827 transitions. [2018-10-26 21:14:03,178 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2018-10-26 21:14:03,179 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 525 [2018-10-26 21:14:03,179 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-26 21:14:03,202 INFO L225 Difference]: With dead ends: 46563 [2018-10-26 21:14:03,202 INFO L226 Difference]: Without dead ends: 25681 [2018-10-26 21:14:03,214 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 552 GetRequests, 512 SyntacticMatches, 11 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 257 ImplicationChecksByTransitivity, 4.1s TimeCoverageRelationStatistics Valid=269, Invalid=661, Unknown=0, NotChecked=0, Total=930 [2018-10-26 21:14:03,226 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25681 states. [2018-10-26 21:14:03,423 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25681 to 20493. [2018-10-26 21:14:03,423 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 20493 states. [2018-10-26 21:14:03,441 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20493 states to 20493 states and 21930 transitions. [2018-10-26 21:14:03,441 INFO L78 Accepts]: Start accepts. Automaton has 20493 states and 21930 transitions. Word has length 525 [2018-10-26 21:14:03,441 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-26 21:14:03,441 INFO L481 AbstractCegarLoop]: Abstraction has 20493 states and 21930 transitions. [2018-10-26 21:14:03,442 INFO L482 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-10-26 21:14:03,442 INFO L276 IsEmpty]: Start isEmpty. Operand 20493 states and 21930 transitions. [2018-10-26 21:14:03,451 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 544 [2018-10-26 21:14:03,451 INFO L367 BasicCegarLoop]: Found error trace [2018-10-26 21:14:03,451 INFO L375 BasicCegarLoop]: trace histogram [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-26 21:14:03,452 INFO L424 AbstractCegarLoop]: === Iteration 18 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-26 21:14:03,452 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-26 21:14:03,452 INFO L82 PathProgramCache]: Analyzing trace with hash -1849402497, now seen corresponding path program 1 times [2018-10-26 21:14:03,452 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-26 21:14:03,452 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-26 21:14:03,453 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:14:03,453 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:14:03,453 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:14:03,508 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:14:04,076 WARN L179 SmtUtils]: Spent 316.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 11 [2018-10-26 21:14:04,243 INFO L134 CoverageAnalysis]: Checked inductivity of 1072 backedges. 839 proven. 0 refuted. 0 times theorem prover too weak. 233 trivial. 0 not checked. [2018-10-26 21:14:04,243 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-26 21:14:04,243 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-10-26 21:14:04,244 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-10-26 21:14:04,244 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-10-26 21:14:04,244 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-10-26 21:14:04,245 INFO L87 Difference]: Start difference. First operand 20493 states and 21930 transitions. Second operand 4 states. [2018-10-26 21:14:06,019 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-26 21:14:06,020 INFO L93 Difference]: Finished difference Result 39878 states and 42722 transitions. [2018-10-26 21:14:06,020 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-10-26 21:14:06,020 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 543 [2018-10-26 21:14:06,021 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-26 21:14:06,040 INFO L225 Difference]: With dead ends: 39878 [2018-10-26 21:14:06,040 INFO L226 Difference]: Without dead ends: 21796 [2018-10-26 21:14:06,051 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-10-26 21:14:06,063 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21796 states. [2018-10-26 21:14:06,248 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21796 to 19935. [2018-10-26 21:14:06,248 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 19935 states. [2018-10-26 21:14:06,272 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19935 states to 19935 states and 21189 transitions. [2018-10-26 21:14:06,272 INFO L78 Accepts]: Start accepts. Automaton has 19935 states and 21189 transitions. Word has length 543 [2018-10-26 21:14:06,272 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-26 21:14:06,272 INFO L481 AbstractCegarLoop]: Abstraction has 19935 states and 21189 transitions. [2018-10-26 21:14:06,273 INFO L482 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-10-26 21:14:06,273 INFO L276 IsEmpty]: Start isEmpty. Operand 19935 states and 21189 transitions. [2018-10-26 21:14:06,285 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 555 [2018-10-26 21:14:06,285 INFO L367 BasicCegarLoop]: Found error trace [2018-10-26 21:14:06,286 INFO L375 BasicCegarLoop]: trace histogram [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-26 21:14:06,286 INFO L424 AbstractCegarLoop]: === Iteration 19 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-26 21:14:06,286 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-26 21:14:06,286 INFO L82 PathProgramCache]: Analyzing trace with hash 956786045, now seen corresponding path program 1 times [2018-10-26 21:14:06,287 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-26 21:14:06,287 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-26 21:14:06,287 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:14:06,288 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:14:06,288 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:14:06,352 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:14:06,742 WARN L179 SmtUtils]: Spent 103.00 ms on a formula simplification. DAG size of input: 13 DAG size of output: 9 [2018-10-26 21:14:06,916 INFO L134 CoverageAnalysis]: Checked inductivity of 761 backedges. 395 proven. 0 refuted. 0 times theorem prover too weak. 366 trivial. 0 not checked. [2018-10-26 21:14:06,916 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-26 21:14:06,916 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-10-26 21:14:06,917 INFO L460 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-10-26 21:14:06,917 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-10-26 21:14:06,917 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-10-26 21:14:06,918 INFO L87 Difference]: Start difference. First operand 19935 states and 21189 transitions. Second operand 5 states. [2018-10-26 21:14:09,535 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-26 21:14:09,535 INFO L93 Difference]: Finished difference Result 37090 states and 39456 transitions. [2018-10-26 21:14:09,535 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-10-26 21:14:09,535 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 554 [2018-10-26 21:14:09,536 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-26 21:14:09,552 INFO L225 Difference]: With dead ends: 37090 [2018-10-26 21:14:09,552 INFO L226 Difference]: Without dead ends: 19938 [2018-10-26 21:14:09,561 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-10-26 21:14:09,570 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19938 states. [2018-10-26 21:14:09,728 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19938 to 18825. [2018-10-26 21:14:09,728 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 18825 states. [2018-10-26 21:14:09,744 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18825 states to 18825 states and 19965 transitions. [2018-10-26 21:14:09,744 INFO L78 Accepts]: Start accepts. Automaton has 18825 states and 19965 transitions. Word has length 554 [2018-10-26 21:14:09,745 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-26 21:14:09,745 INFO L481 AbstractCegarLoop]: Abstraction has 18825 states and 19965 transitions. [2018-10-26 21:14:09,745 INFO L482 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-10-26 21:14:09,745 INFO L276 IsEmpty]: Start isEmpty. Operand 18825 states and 19965 transitions. [2018-10-26 21:14:09,760 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 641 [2018-10-26 21:14:09,760 INFO L367 BasicCegarLoop]: Found error trace [2018-10-26 21:14:09,760 INFO L375 BasicCegarLoop]: trace histogram [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-26 21:14:09,761 INFO L424 AbstractCegarLoop]: === Iteration 20 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-26 21:14:09,761 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-26 21:14:09,761 INFO L82 PathProgramCache]: Analyzing trace with hash -847476356, now seen corresponding path program 1 times [2018-10-26 21:14:09,761 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-26 21:14:09,761 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-26 21:14:09,762 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:14:09,762 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:14:09,762 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:14:09,988 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:14:11,066 INFO L134 CoverageAnalysis]: Checked inductivity of 949 backedges. 555 proven. 0 refuted. 0 times theorem prover too weak. 394 trivial. 0 not checked. [2018-10-26 21:14:11,067 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-26 21:14:11,067 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-10-26 21:14:11,067 INFO L460 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-10-26 21:14:11,068 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-10-26 21:14:11,068 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-10-26 21:14:11,068 INFO L87 Difference]: Start difference. First operand 18825 states and 19965 transitions. Second operand 6 states. [2018-10-26 21:14:14,360 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-26 21:14:14,361 INFO L93 Difference]: Finished difference Result 43034 states and 45613 transitions. [2018-10-26 21:14:14,361 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-10-26 21:14:14,361 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 640 [2018-10-26 21:14:14,362 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-26 21:14:14,387 INFO L225 Difference]: With dead ends: 43034 [2018-10-26 21:14:14,388 INFO L226 Difference]: Without dead ends: 26992 [2018-10-26 21:14:14,398 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-10-26 21:14:14,413 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26992 states. [2018-10-26 21:14:14,596 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26992 to 18264. [2018-10-26 21:14:14,596 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 18264 states. [2018-10-26 21:14:14,611 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18264 states to 18264 states and 19356 transitions. [2018-10-26 21:14:14,612 INFO L78 Accepts]: Start accepts. Automaton has 18264 states and 19356 transitions. Word has length 640 [2018-10-26 21:14:14,612 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-26 21:14:14,612 INFO L481 AbstractCegarLoop]: Abstraction has 18264 states and 19356 transitions. [2018-10-26 21:14:14,612 INFO L482 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-10-26 21:14:14,612 INFO L276 IsEmpty]: Start isEmpty. Operand 18264 states and 19356 transitions. [2018-10-26 21:14:14,626 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 648 [2018-10-26 21:14:14,626 INFO L367 BasicCegarLoop]: Found error trace [2018-10-26 21:14:14,627 INFO L375 BasicCegarLoop]: trace histogram [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-26 21:14:14,627 INFO L424 AbstractCegarLoop]: === Iteration 21 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-26 21:14:14,627 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-26 21:14:14,627 INFO L82 PathProgramCache]: Analyzing trace with hash -1534956161, now seen corresponding path program 1 times [2018-10-26 21:14:14,628 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-26 21:14:14,628 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-26 21:14:14,628 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:14:14,628 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:14:14,629 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:14:14,699 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:14:15,353 INFO L134 CoverageAnalysis]: Checked inductivity of 1189 backedges. 595 proven. 0 refuted. 0 times theorem prover too weak. 594 trivial. 0 not checked. [2018-10-26 21:14:15,353 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-26 21:14:15,354 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-10-26 21:14:15,354 INFO L460 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-10-26 21:14:15,354 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-10-26 21:14:15,354 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-10-26 21:14:15,355 INFO L87 Difference]: Start difference. First operand 18264 states and 19356 transitions. Second operand 6 states. [2018-10-26 21:14:19,487 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-26 21:14:19,487 INFO L93 Difference]: Finished difference Result 39864 states and 42236 transitions. [2018-10-26 21:14:19,487 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-10-26 21:14:19,487 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 647 [2018-10-26 21:14:19,488 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-26 21:14:19,505 INFO L225 Difference]: With dead ends: 39864 [2018-10-26 21:14:19,505 INFO L226 Difference]: Without dead ends: 24383 [2018-10-26 21:14:19,514 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-10-26 21:14:19,525 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24383 states. [2018-10-26 21:14:19,834 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24383 to 16774. [2018-10-26 21:14:19,835 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 16774 states. [2018-10-26 21:14:19,850 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16774 states to 16774 states and 17788 transitions. [2018-10-26 21:14:19,850 INFO L78 Accepts]: Start accepts. Automaton has 16774 states and 17788 transitions. Word has length 647 [2018-10-26 21:14:19,851 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-26 21:14:19,851 INFO L481 AbstractCegarLoop]: Abstraction has 16774 states and 17788 transitions. [2018-10-26 21:14:19,851 INFO L482 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-10-26 21:14:19,851 INFO L276 IsEmpty]: Start isEmpty. Operand 16774 states and 17788 transitions. [2018-10-26 21:14:19,861 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 679 [2018-10-26 21:14:19,861 INFO L367 BasicCegarLoop]: Found error trace [2018-10-26 21:14:19,862 INFO L375 BasicCegarLoop]: trace histogram [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-26 21:14:19,862 INFO L424 AbstractCegarLoop]: === Iteration 22 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-26 21:14:19,862 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-26 21:14:19,862 INFO L82 PathProgramCache]: Analyzing trace with hash 725576367, now seen corresponding path program 1 times [2018-10-26 21:14:19,862 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-26 21:14:19,862 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-26 21:14:19,863 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:14:19,863 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:14:19,863 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:14:19,930 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:14:20,957 WARN L179 SmtUtils]: Spent 112.00 ms on a formula simplification. DAG size of input: 14 DAG size of output: 5 [2018-10-26 21:14:21,519 INFO L134 CoverageAnalysis]: Checked inductivity of 1010 backedges. 31 proven. 979 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-26 21:14:21,520 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-26 21:14:21,520 INFO L225 ckRefinementStrategy]: Switched to mode Z3_FP 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-26 21:14:21,528 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:14:21,701 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:14:21,711 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-26 21:14:23,283 INFO L134 CoverageAnalysis]: Checked inductivity of 1010 backedges. 156 proven. 854 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-26 21:14:23,304 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-26 21:14:23,304 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7] total 12 [2018-10-26 21:14:23,306 INFO L460 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-10-26 21:14:23,306 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-10-26 21:14:23,306 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=110, Unknown=0, NotChecked=0, Total=156 [2018-10-26 21:14:23,306 INFO L87 Difference]: Start difference. First operand 16774 states and 17788 transitions. Second operand 13 states. [2018-10-26 21:14:32,126 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-26 21:14:32,126 INFO L93 Difference]: Finished difference Result 45241 states and 47969 transitions. [2018-10-26 21:14:32,131 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-10-26 21:14:32,131 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 678 [2018-10-26 21:14:32,132 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-26 21:14:32,158 INFO L225 Difference]: With dead ends: 45241 [2018-10-26 21:14:32,158 INFO L226 Difference]: Without dead ends: 30880 [2018-10-26 21:14:32,169 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 689 GetRequests, 672 SyntacticMatches, 4 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 62 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=62, Invalid=148, Unknown=0, NotChecked=0, Total=210 [2018-10-26 21:14:32,187 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30880 states. [2018-10-26 21:14:32,445 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30880 to 19762. [2018-10-26 21:14:32,445 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 19762 states. [2018-10-26 21:14:32,460 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19762 states to 19762 states and 20966 transitions. [2018-10-26 21:14:32,461 INFO L78 Accepts]: Start accepts. Automaton has 19762 states and 20966 transitions. Word has length 678 [2018-10-26 21:14:32,461 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-26 21:14:32,461 INFO L481 AbstractCegarLoop]: Abstraction has 19762 states and 20966 transitions. [2018-10-26 21:14:32,461 INFO L482 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-10-26 21:14:32,461 INFO L276 IsEmpty]: Start isEmpty. Operand 19762 states and 20966 transitions. [2018-10-26 21:14:32,472 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 687 [2018-10-26 21:14:32,472 INFO L367 BasicCegarLoop]: Found error trace [2018-10-26 21:14:32,472 INFO L375 BasicCegarLoop]: trace histogram [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-26 21:14:32,472 INFO L424 AbstractCegarLoop]: === Iteration 23 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-26 21:14:32,473 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-26 21:14:32,473 INFO L82 PathProgramCache]: Analyzing trace with hash -817217683, now seen corresponding path program 1 times [2018-10-26 21:14:32,473 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-26 21:14:32,473 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-26 21:14:32,474 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:14:32,474 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:14:32,474 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:14:32,551 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:14:34,236 INFO L134 CoverageAnalysis]: Checked inductivity of 1009 backedges. 0 proven. 1009 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-26 21:14:34,237 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-26 21:14:34,237 INFO L225 ckRefinementStrategy]: Switched to mode Z3_FP 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-26 21:14:34,244 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:14:34,415 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:14:34,424 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-26 21:14:52,225 WARN L179 SmtUtils]: Spent 17.22 s on a formula simplification. DAG size of input: 646 DAG size of output: 42 [2018-10-26 21:14:54,401 INFO L134 CoverageAnalysis]: Checked inductivity of 1009 backedges. 683 proven. 201 refuted. 0 times theorem prover too weak. 125 trivial. 0 not checked. [2018-10-26 21:14:54,421 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-26 21:14:54,422 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 12 [2018-10-26 21:14:54,423 INFO L460 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-10-26 21:14:54,423 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-10-26 21:14:54,423 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=91, Unknown=0, NotChecked=0, Total=132 [2018-10-26 21:14:54,423 INFO L87 Difference]: Start difference. First operand 19762 states and 20966 transitions. Second operand 12 states. [2018-10-26 21:15:08,485 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-26 21:15:08,485 INFO L93 Difference]: Finished difference Result 52702 states and 55847 transitions. [2018-10-26 21:15:08,485 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-10-26 21:15:08,485 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 686 [2018-10-26 21:15:08,486 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-26 21:15:08,517 INFO L225 Difference]: With dead ends: 52702 [2018-10-26 21:15:08,517 INFO L226 Difference]: Without dead ends: 35540 [2018-10-26 21:15:08,529 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 700 GetRequests, 684 SyntacticMatches, 3 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 18.6s TimeCoverageRelationStatistics Valid=66, Invalid=144, Unknown=0, NotChecked=0, Total=210 [2018-10-26 21:15:08,546 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35540 states. [2018-10-26 21:15:08,821 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35540 to 18656. [2018-10-26 21:15:08,821 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 18656 states. [2018-10-26 21:15:08,836 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18656 states to 18656 states and 19773 transitions. [2018-10-26 21:15:08,837 INFO L78 Accepts]: Start accepts. Automaton has 18656 states and 19773 transitions. Word has length 686 [2018-10-26 21:15:08,837 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-26 21:15:08,837 INFO L481 AbstractCegarLoop]: Abstraction has 18656 states and 19773 transitions. [2018-10-26 21:15:08,837 INFO L482 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-10-26 21:15:08,838 INFO L276 IsEmpty]: Start isEmpty. Operand 18656 states and 19773 transitions. [2018-10-26 21:15:08,849 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 711 [2018-10-26 21:15:08,849 INFO L367 BasicCegarLoop]: Found error trace [2018-10-26 21:15:08,849 INFO L375 BasicCegarLoop]: trace histogram [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-26 21:15:08,850 INFO L424 AbstractCegarLoop]: === Iteration 24 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-26 21:15:08,850 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-26 21:15:08,850 INFO L82 PathProgramCache]: Analyzing trace with hash 922977328, now seen corresponding path program 1 times [2018-10-26 21:15:08,850 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-26 21:15:08,850 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-26 21:15:08,851 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:15:08,851 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:15:08,851 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:15:08,918 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:15:10,091 WARN L179 SmtUtils]: Spent 100.00 ms on a formula simplification. DAG size of input: 8 DAG size of output: 3 [2018-10-26 21:15:10,695 INFO L134 CoverageAnalysis]: Checked inductivity of 1298 backedges. 122 proven. 1025 refuted. 0 times theorem prover too weak. 151 trivial. 0 not checked. [2018-10-26 21:15:10,696 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-26 21:15:10,696 INFO L225 ckRefinementStrategy]: Switched to mode Z3_FP 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-26 21:15:10,703 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:15:10,874 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:15:10,882 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-26 21:15:12,008 INFO L134 CoverageAnalysis]: Checked inductivity of 1298 backedges. 870 proven. 62 refuted. 0 times theorem prover too weak. 366 trivial. 0 not checked. [2018-10-26 21:15:12,029 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-26 21:15:12,029 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 5] total 11 [2018-10-26 21:15:12,030 INFO L460 AbstractCegarLoop]: Interpolant automaton has 11 states [2018-10-26 21:15:12,030 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2018-10-26 21:15:12,030 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=81, Unknown=0, NotChecked=0, Total=110 [2018-10-26 21:15:12,030 INFO L87 Difference]: Start difference. First operand 18656 states and 19773 transitions. Second operand 11 states. [2018-10-26 21:15:35,434 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-26 21:15:35,434 INFO L93 Difference]: Finished difference Result 48620 states and 51389 transitions. [2018-10-26 21:15:35,435 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2018-10-26 21:15:35,435 INFO L78 Accepts]: Start accepts. Automaton has 11 states. Word has length 710 [2018-10-26 21:15:35,436 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-26 21:15:35,464 INFO L225 Difference]: With dead ends: 48620 [2018-10-26 21:15:35,465 INFO L226 Difference]: Without dead ends: 32946 [2018-10-26 21:15:35,477 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 738 GetRequests, 717 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 83 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=109, Invalid=353, Unknown=0, NotChecked=0, Total=462 [2018-10-26 21:15:35,495 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32946 states. [2018-10-26 21:15:35,780 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32946 to 19952. [2018-10-26 21:15:35,781 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 19952 states. [2018-10-26 21:15:35,797 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19952 states to 19952 states and 21122 transitions. [2018-10-26 21:15:35,798 INFO L78 Accepts]: Start accepts. Automaton has 19952 states and 21122 transitions. Word has length 710 [2018-10-26 21:15:35,798 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-26 21:15:35,798 INFO L481 AbstractCegarLoop]: Abstraction has 19952 states and 21122 transitions. [2018-10-26 21:15:35,798 INFO L482 AbstractCegarLoop]: Interpolant automaton has 11 states. [2018-10-26 21:15:35,798 INFO L276 IsEmpty]: Start isEmpty. Operand 19952 states and 21122 transitions. [2018-10-26 21:15:35,815 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 969 [2018-10-26 21:15:35,815 INFO L367 BasicCegarLoop]: Found error trace [2018-10-26 21:15:35,815 INFO L375 BasicCegarLoop]: trace histogram [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-26 21:15:35,816 INFO L424 AbstractCegarLoop]: === Iteration 25 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-26 21:15:35,816 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-26 21:15:35,816 INFO L82 PathProgramCache]: Analyzing trace with hash 1485580583, now seen corresponding path program 1 times [2018-10-26 21:15:35,816 INFO L225 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-26 21:15:35,816 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-26 21:15:35,817 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:15:35,817 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:15:35,817 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-26 21:15:35,908 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:15:36,985 WARN L179 SmtUtils]: Spent 302.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 17 [2018-10-26 21:15:38,188 INFO L134 CoverageAnalysis]: Checked inductivity of 2314 backedges. 1445 proven. 687 refuted. 0 times theorem prover too weak. 182 trivial. 0 not checked. [2018-10-26 21:15:38,188 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-26 21:15:38,188 INFO L225 ckRefinementStrategy]: Switched to mode Z3_FP 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-26 21:15:38,196 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-26 21:15:38,427 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-26 21:15:38,439 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-26 21:15:39,565 WARN L179 SmtUtils]: Spent 836.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 16 Received shutdown request... [2018-10-26 21:15:48,538 WARN L187 SmtUtils]: Removed 20 from assertion stack [2018-10-26 21:15:48,538 INFO L177 TraceCheckSpWp]: Timeout while computing interpolants [2018-10-26 21:15:48,739 WARN L522 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-26 21:15:48,740 WARN L550 AbstractCegarLoop]: Verification canceled [2018-10-26 21:15:48,745 WARN L205 ceAbstractionStarter]: Timeout [2018-10-26 21:15:48,746 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 26.10 09:15:48 BoogieIcfgContainer [2018-10-26 21:15:48,746 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-10-26 21:15:48,747 INFO L168 Benchmark]: Toolchain (without parser) took 234891.89 ms. Allocated memory was 1.5 GB in the beginning and 4.1 GB in the end (delta: 2.6 GB). Free memory was 1.4 GB in the beginning and 1.9 GB in the end (delta: -493.3 MB). Peak memory consumption was 2.1 GB. Max. memory is 7.1 GB. [2018-10-26 21:15:48,748 INFO L168 Benchmark]: CDTParser took 0.21 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-26 21:15:48,748 INFO L168 Benchmark]: CACSL2BoogieTranslator took 1100.16 ms. Allocated memory is still 1.5 GB. Free memory was 1.4 GB in the beginning and 1.3 GB in the end (delta: 52.9 MB). Peak memory consumption was 52.9 MB. Max. memory is 7.1 GB. [2018-10-26 21:15:48,749 INFO L168 Benchmark]: Boogie Procedure Inliner took 320.79 ms. Allocated memory was 1.5 GB in the beginning and 2.3 GB in the end (delta: 730.9 MB). Free memory was 1.3 GB in the beginning and 2.2 GB in the end (delta: -821.8 MB). Peak memory consumption was 24.3 MB. Max. memory is 7.1 GB. [2018-10-26 21:15:48,750 INFO L168 Benchmark]: Boogie Preprocessor took 145.53 ms. Allocated memory is still 2.3 GB. Free memory was 2.2 GB in the beginning and 2.2 GB in the end (delta: 13.7 MB). Peak memory consumption was 13.7 MB. Max. memory is 7.1 GB. [2018-10-26 21:15:48,751 INFO L168 Benchmark]: RCFGBuilder took 4861.50 ms. Allocated memory is still 2.3 GB. Free memory was 2.2 GB in the beginning and 2.0 GB in the end (delta: 173.9 MB). Peak memory consumption was 173.9 MB. Max. memory is 7.1 GB. [2018-10-26 21:15:48,751 INFO L168 Benchmark]: TraceAbstraction took 228458.61 ms. Allocated memory was 2.3 GB in the beginning and 4.1 GB in the end (delta: 1.8 GB). Free memory was 2.0 GB in the beginning and 1.9 GB in the end (delta: 88.0 MB). Peak memory consumption was 1.9 GB. Max. memory is 7.1 GB. [2018-10-26 21:15:48,758 INFO L336 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.21 ms. Allocated memory is still 1.5 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. * CACSL2BoogieTranslator took 1100.16 ms. Allocated memory is still 1.5 GB. Free memory was 1.4 GB in the beginning and 1.3 GB in the end (delta: 52.9 MB). Peak memory consumption was 52.9 MB. Max. memory is 7.1 GB. * Boogie Procedure Inliner took 320.79 ms. Allocated memory was 1.5 GB in the beginning and 2.3 GB in the end (delta: 730.9 MB). Free memory was 1.3 GB in the beginning and 2.2 GB in the end (delta: -821.8 MB). Peak memory consumption was 24.3 MB. Max. memory is 7.1 GB. * Boogie Preprocessor took 145.53 ms. Allocated memory is still 2.3 GB. Free memory was 2.2 GB in the beginning and 2.2 GB in the end (delta: 13.7 MB). Peak memory consumption was 13.7 MB. Max. memory is 7.1 GB. * RCFGBuilder took 4861.50 ms. Allocated memory is still 2.3 GB. Free memory was 2.2 GB in the beginning and 2.0 GB in the end (delta: 173.9 MB). Peak memory consumption was 173.9 MB. Max. memory is 7.1 GB. * TraceAbstraction took 228458.61 ms. Allocated memory was 2.3 GB in the beginning and 4.1 GB in the end (delta: 1.8 GB). Free memory was 2.0 GB in the beginning and 1.9 GB in the end (delta: 88.0 MB). Peak memory consumption was 1.9 GB. Max. memory is 7.1 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 102]: Timeout (TraceAbstraction) Unable to prove that call of __VERIFIER_error() unreachable (line 102). Cancelled while BasicCegarLoop was analyzing trace of length 969 with TraceHistMax 7,while TraceCheckSpWp was constructing forward predicates,while PredicateUnifier was unifying predicates,while SimplifyDDAWithTimeout was simplifying term of DAG size 674. - StatisticsResult: Ultimate Automizer benchmark data CFG has 1 procedures, 284 locations, 1 error locations. TIMEOUT Result, 228.3s OverallTime, 25 OverallIterations, 7 TraceHistogramMax, 153.3s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 3800 SDtfs, 27486 SDslu, 4418 SDs, 0 SdLazy, 78401 SolverSat, 8439 SolverUnsat, 12 SolverUnknown, 0 SolverNotchecked, 126.7s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 5292 GetRequests, 5063 SyntacticMatches, 33 SemanticMatches, 196 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 743 ImplicationChecksByTransitivity, 37.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=32931occurred in iteration=12, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 6.3s AutomataMinimizationTime, 24 MinimizatonAttempts, 112729 StatesRemovedByMinimization, 23 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.5s SsaConstructionTime, 2.3s SatisfiabilityAnalysisTime, 46.4s InterpolantComputationTime, 14683 NumberOfCodeBlocks, 14683 NumberOfCodeBlocksAsserted, 34 NumberOfCheckSat, 14649 ConstructedInterpolants, 780 QuantifiedInterpolants, 55795002 SizeOfPredicates, 21 NumberOfNonLiveVariables, 6501 ConjunctsInSsa, 96 ConjunctsInUnsatCore, 34 InterpolantComputations, 14 PerfectInterpolantSequences, 12025/19400 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Completed graceful shutdown