java -Xmx6000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data ./data --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/ai/eq-bench/svcomp-DerefFreeMemtrack-32bit-Automizer_Fixed_noBitfields+AI_EQ_SS.epf -i ../../../trunk/examples/svcomp/array-examples/standard_strcpy_false-valid-deref_ground.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8168ed2-m [2018-04-11 21:01:57,689 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-04-11 21:01:57,690 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-04-11 21:01:57,703 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-04-11 21:01:57,703 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-04-11 21:01:57,704 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-04-11 21:01:57,704 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-04-11 21:01:57,706 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-04-11 21:01:57,707 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-04-11 21:01:57,707 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-04-11 21:01:57,708 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-04-11 21:01:57,708 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-04-11 21:01:57,709 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-04-11 21:01:57,710 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-04-11 21:01:57,711 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-04-11 21:01:57,713 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-04-11 21:01:57,715 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-04-11 21:01:57,717 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-04-11 21:01:57,718 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-04-11 21:01:57,719 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-04-11 21:01:57,721 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-04-11 21:01:57,722 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-04-11 21:01:57,722 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-04-11 21:01:57,723 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-04-11 21:01:57,724 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-04-11 21:01:57,725 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-04-11 21:01:57,725 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-04-11 21:01:57,726 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-04-11 21:01:57,727 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-04-11 21:01:57,727 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-04-11 21:01:57,728 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-04-11 21:01:57,728 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/ai/eq-bench/svcomp-DerefFreeMemtrack-32bit-Automizer_Fixed_noBitfields+AI_EQ_SS.epf [2018-04-11 21:01:57,752 INFO L110 SettingsManager]: Loading preferences was successful [2018-04-11 21:01:57,752 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-04-11 21:01:57,753 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-04-11 21:01:57,753 INFO L133 SettingsManager]: * ultimate.logging.details=de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation=DEBUG; [2018-04-11 21:01:57,753 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-04-11 21:01:57,754 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-04-11 21:01:57,754 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-04-11 21:01:57,754 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-04-11 21:01:57,754 INFO L133 SettingsManager]: * Parallel states before merging=1 [2018-04-11 21:01:57,755 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-04-11 21:01:57,755 INFO L131 SettingsManager]: Preferences of LTL2Aut differ from their defaults: [2018-04-11 21:01:57,755 INFO L133 SettingsManager]: * Property to check=[] a a: x > 42 [2018-04-11 21:01:57,755 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-04-11 21:01:57,756 INFO L133 SettingsManager]: * sizeof long=4 [2018-04-11 21:01:57,756 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-04-11 21:01:57,756 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-04-11 21:01:57,756 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-04-11 21:01:57,756 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-04-11 21:01:57,757 INFO L133 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2018-04-11 21:01:57,757 INFO L133 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2018-04-11 21:01:57,757 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-04-11 21:01:57,757 INFO L133 SettingsManager]: * sizeof long double=12 [2018-04-11 21:01:57,757 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-04-11 21:01:57,758 INFO L133 SettingsManager]: * Size of a code block=SingleStatement [2018-04-11 21:01:57,758 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-04-11 21:01:57,758 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-04-11 21:01:57,758 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-04-11 21:01:57,758 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-04-11 21:01:57,759 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-04-11 21:01:57,759 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-04-11 21:01:57,759 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-04-11 21:01:57,759 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-04-11 21:01:57,759 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:01:57,759 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-04-11 21:01:57,760 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-04-11 21:01:57,760 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-04-11 21:01:57,761 INFO L131 SettingsManager]: Preferences of Boogie Printer differ from their defaults: [2018-04-11 21:01:57,761 INFO L133 SettingsManager]: * Dump path:=C:\Users\alex\AppData\Local\Temp\ [2018-04-11 21:01:57,794 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-04-11 21:01:57,807 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully (re)initialized [2018-04-11 21:01:57,812 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-04-11 21:01:57,813 INFO L271 PluginConnector]: Initializing CDTParser... [2018-04-11 21:01:57,814 INFO L276 PluginConnector]: CDTParser initialized [2018-04-11 21:01:57,815 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/array-examples/standard_strcpy_false-valid-deref_ground.i [2018-04-11 21:01:58,168 INFO L225 CDTParser]: Created temporary CDT project at /storage/ultimate/releaseScripts/default/UAutomizer-linux/data/FLAGedd379e45 [2018-04-11 21:01:58,277 INFO L287 CDTParser]: IsIndexed: true [2018-04-11 21:01:58,277 INFO L288 CDTParser]: Found 1 translation units. [2018-04-11 21:01:58,277 INFO L168 CDTParser]: Scanning standard_strcpy_false-valid-deref_ground.i [2018-04-11 21:01:58,278 INFO L210 ultiparseSymbolTable]: Include resolver: [2018-04-11 21:01:58,278 INFO L215 ultiparseSymbolTable]: [2018-04-11 21:01:58,278 INFO L218 ultiparseSymbolTable]: Function table: [2018-04-11 21:01:58,278 INFO L221 ultiparseSymbolTable]: Function definition of __U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert ('__VERIFIER_assert') in standard_strcpy_false-valid-deref_ground.i [2018-04-11 21:01:58,279 INFO L221 ultiparseSymbolTable]: Function definition of null ('main') in standard_strcpy_false-valid-deref_ground.i [2018-04-11 21:01:58,279 INFO L227 ultiparseSymbolTable]: Global variable table: [2018-04-11 21:01:58,279 INFO L233 ultiparseSymbolTable]: [2018-04-11 21:01:58,295 INFO L330 CDTParser]: Deleted temporary CDT project at /storage/ultimate/releaseScripts/default/UAutomizer-linux/data/FLAGedd379e45 [2018-04-11 21:01:58,299 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-04-11 21:01:58,301 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-04-11 21:01:58,301 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-04-11 21:01:58,301 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-04-11 21:01:58,306 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-04-11 21:01:58,307 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 11.04 09:01:58" (1/1) ... [2018-04-11 21:01:58,309 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@f490f67 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.04 09:01:58, skipping insertion in model container [2018-04-11 21:01:58,309 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 11.04 09:01:58" (1/1) ... [2018-04-11 21:01:58,323 INFO L167 Dispatcher]: Using SV-COMP mode [2018-04-11 21:01:58,338 INFO L167 Dispatcher]: Using SV-COMP mode [2018-04-11 21:01:58,464 INFO L175 PostProcessor]: Settings: Checked method=main [2018-04-11 21:01:58,478 INFO L175 PostProcessor]: Settings: Checked method=main [2018-04-11 21:01:58,482 INFO L100 SccComputation]: Graph consists of 0 InCaSumBalls and 5 non ball SCCs. Number of states in SCCs 5. [2018-04-11 21:01:58,489 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.04 09:01:58 WrapperNode [2018-04-11 21:01:58,489 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-04-11 21:01:58,489 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-04-11 21:01:58,489 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-04-11 21:01:58,490 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-04-11 21:01:58,499 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.04 09:01:58" (1/1) ... [2018-04-11 21:01:58,499 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.04 09:01:58" (1/1) ... [2018-04-11 21:01:58,504 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.04 09:01:58" (1/1) ... [2018-04-11 21:01:58,504 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.04 09:01:58" (1/1) ... [2018-04-11 21:01:58,506 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.04 09:01:58" (1/1) ... [2018-04-11 21:01:58,511 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.04 09:01:58" (1/1) ... [2018-04-11 21:01:58,512 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.04 09:01:58" (1/1) ... [2018-04-11 21:01:58,514 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-04-11 21:01:58,514 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-04-11 21:01:58,514 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-04-11 21:01:58,515 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-04-11 21:01:58,516 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.04 09:01:58" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-04-11 21:01:58,580 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-04-11 21:01:58,581 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-04-11 21:01:58,581 INFO L136 BoogieDeclarations]: Found implementation of procedure __U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert [2018-04-11 21:01:58,581 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-04-11 21:01:58,581 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_error [2018-04-11 21:01:58,581 INFO L128 BoogieDeclarations]: Found specification of procedure __U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert [2018-04-11 21:01:58,581 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-04-11 21:01:58,581 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-04-11 21:01:58,582 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-04-11 21:01:58,781 INFO L259 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-04-11 21:01:58,782 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.04 09:01:58 BoogieIcfgContainer [2018-04-11 21:01:58,782 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-04-11 21:01:58,783 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-04-11 21:01:58,783 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-04-11 21:01:58,785 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-04-11 21:01:58,785 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 11.04 09:01:58" (1/3) ... [2018-04-11 21:01:58,786 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@580a6f79 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 11.04 09:01:58, skipping insertion in model container [2018-04-11 21:01:58,786 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.04 09:01:58" (2/3) ... [2018-04-11 21:01:58,786 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@580a6f79 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 11.04 09:01:58, skipping insertion in model container [2018-04-11 21:01:58,786 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.04 09:01:58" (3/3) ... [2018-04-11 21:01:58,788 INFO L107 eAbstractionObserver]: Analyzing ICFG standard_strcpy_false-valid-deref_ground.i [2018-04-11 21:01:58,796 INFO L131 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-04-11 21:01:58,804 INFO L143 ceAbstractionStarter]: Appying trace abstraction to program that has 5 error locations. [2018-04-11 21:01:58,839 INFO L128 ementStrategyFactory]: Using default assertion order modulation [2018-04-11 21:01:58,840 INFO L369 AbstractCegarLoop]: Interprodecural is true [2018-04-11 21:01:58,840 INFO L370 AbstractCegarLoop]: Hoare is true [2018-04-11 21:01:58,840 INFO L371 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-04-11 21:01:58,840 INFO L372 AbstractCegarLoop]: Backedges is TWOTRACK [2018-04-11 21:01:58,840 INFO L373 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-04-11 21:01:58,840 INFO L374 AbstractCegarLoop]: Difference is false [2018-04-11 21:01:58,840 INFO L375 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-04-11 21:01:58,841 INFO L380 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-04-11 21:01:58,841 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-04-11 21:01:58,859 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states. [2018-04-11 21:01:58,866 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2018-04-11 21:01:58,866 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:01:58,867 INFO L355 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:01:58,867 INFO L408 AbstractCegarLoop]: === Iteration 1 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:01:58,871 INFO L82 PathProgramCache]: Analyzing trace with hash 442952750, now seen corresponding path program 1 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:01:58,883 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:01:58,899 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:01:58,904 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:01:58,942 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-11 21:01:58,942 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:01:58,972 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-11 21:01:58,994 INFO L320 seRefinementStrategy]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2018-04-11 21:01:58,994 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2, 2] imperfect sequences [] total 3 [2018-04-11 21:01:58,996 INFO L442 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-04-11 21:01:59,005 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-04-11 21:01:59,006 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-04-11 21:01:59,007 INFO L87 Difference]: Start difference. First operand 39 states. Second operand 4 states. [2018-04-11 21:01:59,109 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:01:59,109 INFO L93 Difference]: Finished difference Result 108 states and 130 transitions. [2018-04-11 21:01:59,110 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-04-11 21:01:59,111 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 9 [2018-04-11 21:01:59,112 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:01:59,120 INFO L225 Difference]: With dead ends: 108 [2018-04-11 21:01:59,120 INFO L226 Difference]: Without dead ends: 71 [2018-04-11 21:01:59,124 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 15 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-04-11 21:01:59,139 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2018-04-11 21:01:59,163 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 45. [2018-04-11 21:01:59,164 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 45 states. [2018-04-11 21:01:59,166 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 48 transitions. [2018-04-11 21:01:59,167 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 48 transitions. Word has length 9 [2018-04-11 21:01:59,168 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:01:59,168 INFO L459 AbstractCegarLoop]: Abstraction has 45 states and 48 transitions. [2018-04-11 21:01:59,168 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-04-11 21:01:59,168 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 48 transitions. [2018-04-11 21:01:59,169 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-04-11 21:01:59,169 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:01:59,169 INFO L355 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:01:59,170 INFO L408 AbstractCegarLoop]: === Iteration 2 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:01:59,170 INFO L82 PathProgramCache]: Analyzing trace with hash 1498590240, now seen corresponding path program 1 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:01:59,183 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:01:59,190 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:01:59,192 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:01:59,210 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-11 21:01:59,210 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:01:59,255 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-11 21:01:59,288 INFO L320 seRefinementStrategy]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2018-04-11 21:01:59,288 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2, 2] imperfect sequences [] total 3 [2018-04-11 21:01:59,290 INFO L442 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-04-11 21:01:59,290 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-04-11 21:01:59,290 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-04-11 21:01:59,291 INFO L87 Difference]: Start difference. First operand 45 states and 48 transitions. Second operand 4 states. [2018-04-11 21:01:59,306 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:01:59,306 INFO L93 Difference]: Finished difference Result 54 states and 58 transitions. [2018-04-11 21:01:59,307 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-04-11 21:01:59,307 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 15 [2018-04-11 21:01:59,307 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:01:59,308 INFO L225 Difference]: With dead ends: 54 [2018-04-11 21:01:59,308 INFO L226 Difference]: Without dead ends: 52 [2018-04-11 21:01:59,309 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 27 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-04-11 21:01:59,309 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2018-04-11 21:01:59,315 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 49. [2018-04-11 21:01:59,315 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 49 states. [2018-04-11 21:01:59,317 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 52 transitions. [2018-04-11 21:01:59,317 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 52 transitions. Word has length 15 [2018-04-11 21:01:59,317 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:01:59,317 INFO L459 AbstractCegarLoop]: Abstraction has 49 states and 52 transitions. [2018-04-11 21:01:59,317 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-04-11 21:01:59,317 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 52 transitions. [2018-04-11 21:01:59,318 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2018-04-11 21:01:59,318 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:01:59,318 INFO L355 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:01:59,319 INFO L408 AbstractCegarLoop]: === Iteration 3 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:01:59,319 INFO L82 PathProgramCache]: Analyzing trace with hash -554303570, now seen corresponding path program 1 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:01:59,325 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:01:59,331 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:01:59,333 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:01:59,362 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 0 proven. 11 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-11 21:01:59,362 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:01:59,447 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 0 proven. 11 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-11 21:01:59,467 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:01:59,467 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 7 [2018-04-11 21:01:59,468 INFO L442 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-04-11 21:01:59,468 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-04-11 21:01:59,468 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=34, Unknown=0, NotChecked=0, Total=56 [2018-04-11 21:01:59,469 INFO L87 Difference]: Start difference. First operand 49 states and 52 transitions. Second operand 8 states. [2018-04-11 21:01:59,667 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:01:59,668 INFO L93 Difference]: Finished difference Result 178 states and 200 transitions. [2018-04-11 21:01:59,668 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-04-11 21:01:59,668 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 23 [2018-04-11 21:01:59,669 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:01:59,671 INFO L225 Difference]: With dead ends: 178 [2018-04-11 21:01:59,671 INFO L226 Difference]: Without dead ends: 175 [2018-04-11 21:01:59,672 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 39 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=38, Invalid=52, Unknown=0, NotChecked=0, Total=90 [2018-04-11 21:01:59,672 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 175 states. [2018-04-11 21:01:59,684 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 175 to 77. [2018-04-11 21:01:59,684 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 77 states. [2018-04-11 21:01:59,686 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 84 transitions. [2018-04-11 21:01:59,687 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 84 transitions. Word has length 23 [2018-04-11 21:01:59,687 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:01:59,687 INFO L459 AbstractCegarLoop]: Abstraction has 77 states and 84 transitions. [2018-04-11 21:01:59,687 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-04-11 21:01:59,688 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 84 transitions. [2018-04-11 21:01:59,688 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2018-04-11 21:01:59,689 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:01:59,689 INFO L355 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:01:59,689 INFO L408 AbstractCegarLoop]: === Iteration 4 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:01:59,689 INFO L82 PathProgramCache]: Analyzing trace with hash 1357875333, now seen corresponding path program 1 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:01:59,699 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:01:59,708 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:01:59,711 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:01:59,743 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-04-11 21:01:59,743 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:01:59,799 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-04-11 21:01:59,832 INFO L320 seRefinementStrategy]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2018-04-11 21:01:59,832 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4, 4] imperfect sequences [] total 5 [2018-04-11 21:01:59,832 INFO L442 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-04-11 21:01:59,832 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-04-11 21:01:59,833 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-04-11 21:01:59,833 INFO L87 Difference]: Start difference. First operand 77 states and 84 transitions. Second operand 5 states. [2018-04-11 21:01:59,912 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:01:59,912 INFO L93 Difference]: Finished difference Result 97 states and 104 transitions. [2018-04-11 21:01:59,913 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-04-11 21:01:59,913 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 27 [2018-04-11 21:01:59,913 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:01:59,915 INFO L225 Difference]: With dead ends: 97 [2018-04-11 21:01:59,915 INFO L226 Difference]: Without dead ends: 77 [2018-04-11 21:01:59,918 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 53 GetRequests, 49 SyntacticMatches, 1 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-04-11 21:01:59,918 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2018-04-11 21:01:59,926 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 77. [2018-04-11 21:01:59,926 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 77 states. [2018-04-11 21:01:59,928 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 83 transitions. [2018-04-11 21:01:59,928 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 83 transitions. Word has length 27 [2018-04-11 21:01:59,929 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:01:59,929 INFO L459 AbstractCegarLoop]: Abstraction has 77 states and 83 transitions. [2018-04-11 21:01:59,929 INFO L460 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-04-11 21:01:59,929 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 83 transitions. [2018-04-11 21:01:59,930 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2018-04-11 21:01:59,930 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:01:59,931 INFO L355 BasicCegarLoop]: trace histogram [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-04-11 21:01:59,931 INFO L408 AbstractCegarLoop]: === Iteration 5 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:01:59,931 INFO L82 PathProgramCache]: Analyzing trace with hash -1112537975, now seen corresponding path program 1 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:01:59,940 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:01:59,956 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:01:59,959 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:02:00,043 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 3 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-11 21:02:00,043 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:02:00,112 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 3 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-11 21:02:00,143 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:02:00,143 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2018-04-11 21:02:00,144 INFO L442 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-04-11 21:02:00,144 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-04-11 21:02:00,144 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=63, Unknown=0, NotChecked=0, Total=90 [2018-04-11 21:02:00,145 INFO L87 Difference]: Start difference. First operand 77 states and 83 transitions. Second operand 10 states. [2018-04-11 21:02:00,244 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:02:00,244 INFO L93 Difference]: Finished difference Result 103 states and 110 transitions. [2018-04-11 21:02:00,246 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-04-11 21:02:00,246 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 34 [2018-04-11 21:02:00,246 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:02:00,247 INFO L225 Difference]: With dead ends: 103 [2018-04-11 21:02:00,247 INFO L226 Difference]: Without dead ends: 77 [2018-04-11 21:02:00,248 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 57 SyntacticMatches, 2 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=44, Invalid=88, Unknown=0, NotChecked=0, Total=132 [2018-04-11 21:02:00,248 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2018-04-11 21:02:00,253 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 77. [2018-04-11 21:02:00,253 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 77 states. [2018-04-11 21:02:00,254 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 82 transitions. [2018-04-11 21:02:00,254 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 82 transitions. Word has length 34 [2018-04-11 21:02:00,255 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:02:00,255 INFO L459 AbstractCegarLoop]: Abstraction has 77 states and 82 transitions. [2018-04-11 21:02:00,255 INFO L460 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-04-11 21:02:00,255 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 82 transitions. [2018-04-11 21:02:00,256 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2018-04-11 21:02:00,256 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:02:00,256 INFO L355 BasicCegarLoop]: trace histogram [3, 3, 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] [2018-04-11 21:02:00,256 INFO L408 AbstractCegarLoop]: === Iteration 6 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:02:00,256 INFO L82 PathProgramCache]: Analyzing trace with hash 707836933, now seen corresponding path program 2 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:02:00,262 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:02:00,269 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:02:00,272 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:02:00,283 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2018-04-11 21:02:00,283 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:02:00,318 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2018-04-11 21:02:00,338 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:02:00,338 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 7 [2018-04-11 21:02:00,339 INFO L442 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-04-11 21:02:00,339 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-04-11 21:02:00,339 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-04-11 21:02:00,340 INFO L87 Difference]: Start difference. First operand 77 states and 82 transitions. Second operand 8 states. [2018-04-11 21:02:00,468 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:02:00,468 INFO L93 Difference]: Finished difference Result 98 states and 108 transitions. [2018-04-11 21:02:00,468 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-04-11 21:02:00,468 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 41 [2018-04-11 21:02:00,469 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:02:00,469 INFO L225 Difference]: With dead ends: 98 [2018-04-11 21:02:00,469 INFO L226 Difference]: Without dead ends: 96 [2018-04-11 21:02:00,470 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 85 GetRequests, 75 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2018-04-11 21:02:00,470 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2018-04-11 21:02:00,475 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 93. [2018-04-11 21:02:00,475 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 93 states. [2018-04-11 21:02:00,476 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 100 transitions. [2018-04-11 21:02:00,476 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 100 transitions. Word has length 41 [2018-04-11 21:02:00,477 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:02:00,477 INFO L459 AbstractCegarLoop]: Abstraction has 93 states and 100 transitions. [2018-04-11 21:02:00,477 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-04-11 21:02:00,477 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 100 transitions. [2018-04-11 21:02:00,479 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2018-04-11 21:02:00,479 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:02:00,479 INFO L355 BasicCegarLoop]: trace histogram [7, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:02:00,479 INFO L408 AbstractCegarLoop]: === Iteration 7 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:02:00,480 INFO L82 PathProgramCache]: Analyzing trace with hash 835962542, now seen corresponding path program 2 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:02:00,487 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:02:00,495 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:02:00,498 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:02:00,558 INFO L134 CoverageAnalysis]: Checked inductivity of 117 backedges. 0 proven. 117 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-11 21:02:00,558 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:02:00,653 INFO L134 CoverageAnalysis]: Checked inductivity of 117 backedges. 0 proven. 117 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-11 21:02:00,672 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:02:00,673 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 15 [2018-04-11 21:02:00,673 INFO L442 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-04-11 21:02:00,673 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-04-11 21:02:00,674 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=162, Unknown=0, NotChecked=0, Total=240 [2018-04-11 21:02:00,674 INFO L87 Difference]: Start difference. First operand 93 states and 100 transitions. Second operand 16 states. [2018-04-11 21:02:01,065 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:02:01,066 INFO L93 Difference]: Finished difference Result 538 states and 610 transitions. [2018-04-11 21:02:01,066 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-04-11 21:02:01,066 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 51 [2018-04-11 21:02:01,067 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:02:01,069 INFO L225 Difference]: With dead ends: 538 [2018-04-11 21:02:01,069 INFO L226 Difference]: Without dead ends: 535 [2018-04-11 21:02:01,070 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 107 GetRequests, 87 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=174, Invalid=288, Unknown=0, NotChecked=0, Total=462 [2018-04-11 21:02:01,071 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 535 states. [2018-04-11 21:02:01,094 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 535 to 149. [2018-04-11 21:02:01,094 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 149 states. [2018-04-11 21:02:01,096 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 149 states to 149 states and 164 transitions. [2018-04-11 21:02:01,096 INFO L78 Accepts]: Start accepts. Automaton has 149 states and 164 transitions. Word has length 51 [2018-04-11 21:02:01,097 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:02:01,097 INFO L459 AbstractCegarLoop]: Abstraction has 149 states and 164 transitions. [2018-04-11 21:02:01,097 INFO L460 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-04-11 21:02:01,097 INFO L276 IsEmpty]: Start isEmpty. Operand 149 states and 164 transitions. [2018-04-11 21:02:01,099 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2018-04-11 21:02:01,099 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:02:01,099 INFO L355 BasicCegarLoop]: trace histogram [4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:02:01,099 INFO L408 AbstractCegarLoop]: === Iteration 8 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:02:01,099 INFO L82 PathProgramCache]: Analyzing trace with hash 476702287, now seen corresponding path program 3 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:02:01,106 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:02:01,116 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:02:01,118 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:02:01,184 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 40 proven. 13 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2018-04-11 21:02:01,184 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:02:01,230 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 32 proven. 13 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2018-04-11 21:02:01,251 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:02:01,251 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 15 [2018-04-11 21:02:01,251 INFO L442 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-04-11 21:02:01,251 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-04-11 21:02:01,251 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=158, Unknown=0, NotChecked=0, Total=210 [2018-04-11 21:02:01,252 INFO L87 Difference]: Start difference. First operand 149 states and 164 transitions. Second operand 15 states. [2018-04-11 21:02:01,335 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:02:01,336 INFO L93 Difference]: Finished difference Result 185 states and 202 transitions. [2018-04-11 21:02:01,336 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-04-11 21:02:01,336 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 65 [2018-04-11 21:02:01,337 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:02:01,338 INFO L225 Difference]: With dead ends: 185 [2018-04-11 21:02:01,338 INFO L226 Difference]: Without dead ends: 149 [2018-04-11 21:02:01,339 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 133 GetRequests, 113 SyntacticMatches, 3 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 66 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=98, Invalid=244, Unknown=0, NotChecked=0, Total=342 [2018-04-11 21:02:01,339 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 149 states. [2018-04-11 21:02:01,350 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 149 to 149. [2018-04-11 21:02:01,351 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 149 states. [2018-04-11 21:02:01,352 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 149 states to 149 states and 163 transitions. [2018-04-11 21:02:01,352 INFO L78 Accepts]: Start accepts. Automaton has 149 states and 163 transitions. Word has length 65 [2018-04-11 21:02:01,353 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:02:01,353 INFO L459 AbstractCegarLoop]: Abstraction has 149 states and 163 transitions. [2018-04-11 21:02:01,353 INFO L460 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-04-11 21:02:01,353 INFO L276 IsEmpty]: Start isEmpty. Operand 149 states and 163 transitions. [2018-04-11 21:02:01,354 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2018-04-11 21:02:01,355 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:02:01,355 INFO L355 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:02:01,355 INFO L408 AbstractCegarLoop]: === Iteration 9 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:02:01,355 INFO L82 PathProgramCache]: Analyzing trace with hash -1796128941, now seen corresponding path program 4 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:02:01,362 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:02:01,376 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:02:01,379 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:02:01,460 INFO L134 CoverageAnalysis]: Checked inductivity of 75 backedges. 33 proven. 30 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2018-04-11 21:02:01,460 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:02:01,534 INFO L134 CoverageAnalysis]: Checked inductivity of 75 backedges. 33 proven. 30 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2018-04-11 21:02:01,554 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:02:01,554 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 20 [2018-04-11 21:02:01,554 INFO L442 AbstractCegarLoop]: Interpolant automaton has 20 states [2018-04-11 21:02:01,554 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2018-04-11 21:02:01,555 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=84, Invalid=296, Unknown=0, NotChecked=0, Total=380 [2018-04-11 21:02:01,555 INFO L87 Difference]: Start difference. First operand 149 states and 163 transitions. Second operand 20 states. [2018-04-11 21:02:01,708 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:02:01,708 INFO L93 Difference]: Finished difference Result 191 states and 208 transitions. [2018-04-11 21:02:01,709 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-04-11 21:02:01,709 INFO L78 Accepts]: Start accepts. Automaton has 20 states. Word has length 72 [2018-04-11 21:02:01,710 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:02:01,711 INFO L225 Difference]: With dead ends: 191 [2018-04-11 21:02:01,711 INFO L226 Difference]: Without dead ends: 149 [2018-04-11 21:02:01,712 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 121 SyntacticMatches, 4 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 137 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=171, Invalid=479, Unknown=0, NotChecked=0, Total=650 [2018-04-11 21:02:01,713 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 149 states. [2018-04-11 21:02:01,724 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 149 to 149. [2018-04-11 21:02:01,724 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 149 states. [2018-04-11 21:02:01,726 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 149 states to 149 states and 162 transitions. [2018-04-11 21:02:01,726 INFO L78 Accepts]: Start accepts. Automaton has 149 states and 162 transitions. Word has length 72 [2018-04-11 21:02:01,726 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:02:01,727 INFO L459 AbstractCegarLoop]: Abstraction has 149 states and 162 transitions. [2018-04-11 21:02:01,727 INFO L460 AbstractCegarLoop]: Interpolant automaton has 20 states. [2018-04-11 21:02:01,727 INFO L276 IsEmpty]: Start isEmpty. Operand 149 states and 162 transitions. [2018-04-11 21:02:01,728 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2018-04-11 21:02:01,728 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:02:01,728 INFO L355 BasicCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:02:01,729 INFO L408 AbstractCegarLoop]: === Iteration 10 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:02:01,729 INFO L82 PathProgramCache]: Analyzing trace with hash -1364690481, now seen corresponding path program 5 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:02:01,737 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:02:01,758 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:02:01,762 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:02:01,845 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2018-04-11 21:02:01,846 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:02:01,939 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2018-04-11 21:02:01,958 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:02:01,958 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 15 [2018-04-11 21:02:01,959 INFO L442 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-04-11 21:02:01,959 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-04-11 21:02:01,959 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=186, Unknown=0, NotChecked=0, Total=240 [2018-04-11 21:02:01,959 INFO L87 Difference]: Start difference. First operand 149 states and 162 transitions. Second operand 16 states. [2018-04-11 21:02:02,196 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:02:02,196 INFO L93 Difference]: Finished difference Result 186 states and 210 transitions. [2018-04-11 21:02:02,196 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-04-11 21:02:02,196 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 79 [2018-04-11 21:02:02,197 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:02:02,198 INFO L225 Difference]: With dead ends: 186 [2018-04-11 21:02:02,198 INFO L226 Difference]: Without dead ends: 184 [2018-04-11 21:02:02,198 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 171 GetRequests, 143 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 116 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=244, Invalid=626, Unknown=0, NotChecked=0, Total=870 [2018-04-11 21:02:02,199 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 184 states. [2018-04-11 21:02:02,210 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 184 to 181. [2018-04-11 21:02:02,210 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 181 states. [2018-04-11 21:02:02,212 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 181 states to 181 states and 198 transitions. [2018-04-11 21:02:02,212 INFO L78 Accepts]: Start accepts. Automaton has 181 states and 198 transitions. Word has length 79 [2018-04-11 21:02:02,212 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:02:02,212 INFO L459 AbstractCegarLoop]: Abstraction has 181 states and 198 transitions. [2018-04-11 21:02:02,213 INFO L460 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-04-11 21:02:02,213 INFO L276 IsEmpty]: Start isEmpty. Operand 181 states and 198 transitions. [2018-04-11 21:02:02,214 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2018-04-11 21:02:02,214 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:02:02,215 INFO L355 BasicCegarLoop]: trace histogram [15, 14, 14, 14, 14, 14, 14, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:02:02,215 INFO L408 AbstractCegarLoop]: === Iteration 11 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:02:02,215 INFO L82 PathProgramCache]: Analyzing trace with hash 212718766, now seen corresponding path program 3 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:02:02,223 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:02:02,238 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:02:02,241 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:02:02,346 INFO L134 CoverageAnalysis]: Checked inductivity of 665 backedges. 0 proven. 665 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-11 21:02:02,346 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:02:02,720 INFO L134 CoverageAnalysis]: Checked inductivity of 665 backedges. 0 proven. 665 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-11 21:02:02,739 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:02:02,739 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 31 [2018-04-11 21:02:02,740 INFO L442 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-04-11 21:02:02,740 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-04-11 21:02:02,740 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=286, Invalid=706, Unknown=0, NotChecked=0, Total=992 [2018-04-11 21:02:02,740 INFO L87 Difference]: Start difference. First operand 181 states and 198 transitions. Second operand 32 states. [2018-04-11 21:02:04,080 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:02:04,080 INFO L93 Difference]: Finished difference Result 1962 states and 2222 transitions. [2018-04-11 21:02:04,080 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2018-04-11 21:02:04,081 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 107 [2018-04-11 21:02:04,081 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:02:04,090 INFO L225 Difference]: With dead ends: 1962 [2018-04-11 21:02:04,090 INFO L226 Difference]: Without dead ends: 1959 [2018-04-11 21:02:04,093 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 227 GetRequests, 183 SyntacticMatches, 0 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 91 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=734, Invalid=1336, Unknown=0, NotChecked=0, Total=2070 [2018-04-11 21:02:04,093 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1959 states. [2018-04-11 21:02:04,132 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1959 to 293. [2018-04-11 21:02:04,133 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 293 states. [2018-04-11 21:02:04,134 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 293 states to 293 states and 326 transitions. [2018-04-11 21:02:04,134 INFO L78 Accepts]: Start accepts. Automaton has 293 states and 326 transitions. Word has length 107 [2018-04-11 21:02:04,134 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:02:04,134 INFO L459 AbstractCegarLoop]: Abstraction has 293 states and 326 transitions. [2018-04-11 21:02:04,134 INFO L460 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-04-11 21:02:04,134 INFO L276 IsEmpty]: Start isEmpty. Operand 293 states and 326 transitions. [2018-04-11 21:02:04,136 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 128 [2018-04-11 21:02:04,136 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:02:04,136 INFO L355 BasicCegarLoop]: trace histogram [8, 8, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 5, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:02:04,136 INFO L408 AbstractCegarLoop]: === Iteration 12 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:02:04,136 INFO L82 PathProgramCache]: Analyzing trace with hash -1443326877, now seen corresponding path program 6 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:02:04,142 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:02:04,161 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:02:04,164 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:02:04,274 INFO L134 CoverageAnalysis]: Checked inductivity of 327 backedges. 210 proven. 54 refuted. 0 times theorem prover too weak. 63 trivial. 0 not checked. [2018-04-11 21:02:04,274 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:02:04,381 INFO L134 CoverageAnalysis]: Checked inductivity of 327 backedges. 162 proven. 54 refuted. 0 times theorem prover too weak. 111 trivial. 0 not checked. [2018-04-11 21:02:04,401 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:02:04,401 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 25 [2018-04-11 21:02:04,402 INFO L442 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-04-11 21:02:04,402 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-04-11 21:02:04,402 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=123, Invalid=477, Unknown=0, NotChecked=0, Total=600 [2018-04-11 21:02:04,402 INFO L87 Difference]: Start difference. First operand 293 states and 326 transitions. Second operand 25 states. [2018-04-11 21:02:04,620 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:02:04,620 INFO L93 Difference]: Finished difference Result 361 states and 400 transitions. [2018-04-11 21:02:04,620 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2018-04-11 21:02:04,620 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 127 [2018-04-11 21:02:04,621 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:02:04,622 INFO L225 Difference]: With dead ends: 361 [2018-04-11 21:02:04,622 INFO L226 Difference]: Without dead ends: 293 [2018-04-11 21:02:04,624 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 261 GetRequests, 225 SyntacticMatches, 5 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 235 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=263, Invalid=793, Unknown=0, NotChecked=0, Total=1056 [2018-04-11 21:02:04,624 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 293 states. [2018-04-11 21:02:04,646 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 293 to 293. [2018-04-11 21:02:04,646 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 293 states. [2018-04-11 21:02:04,648 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 293 states to 293 states and 325 transitions. [2018-04-11 21:02:04,648 INFO L78 Accepts]: Start accepts. Automaton has 293 states and 325 transitions. Word has length 127 [2018-04-11 21:02:04,649 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:02:04,649 INFO L459 AbstractCegarLoop]: Abstraction has 293 states and 325 transitions. [2018-04-11 21:02:04,649 INFO L460 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-04-11 21:02:04,649 INFO L276 IsEmpty]: Start isEmpty. Operand 293 states and 325 transitions. [2018-04-11 21:02:04,651 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 135 [2018-04-11 21:02:04,651 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:02:04,651 INFO L355 BasicCegarLoop]: trace histogram [8, 8, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:02:04,651 INFO L408 AbstractCegarLoop]: === Iteration 13 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:02:04,651 INFO L82 PathProgramCache]: Analyzing trace with hash -1820836249, now seen corresponding path program 7 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:02:04,660 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:02:04,684 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:02:04,689 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:02:04,826 INFO L134 CoverageAnalysis]: Checked inductivity of 358 backedges. 219 proven. 85 refuted. 0 times theorem prover too weak. 54 trivial. 0 not checked. [2018-04-11 21:02:04,826 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:02:04,959 INFO L134 CoverageAnalysis]: Checked inductivity of 358 backedges. 179 proven. 85 refuted. 0 times theorem prover too weak. 94 trivial. 0 not checked. [2018-04-11 21:02:04,979 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:02:04,979 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19] total 30 [2018-04-11 21:02:04,979 INFO L442 AbstractCegarLoop]: Interpolant automaton has 30 states [2018-04-11 21:02:04,980 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2018-04-11 21:02:04,980 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=169, Invalid=701, Unknown=0, NotChecked=0, Total=870 [2018-04-11 21:02:04,980 INFO L87 Difference]: Start difference. First operand 293 states and 325 transitions. Second operand 30 states. [2018-04-11 21:02:05,296 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:02:05,296 INFO L93 Difference]: Finished difference Result 361 states and 399 transitions. [2018-04-11 21:02:05,297 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-04-11 21:02:05,297 INFO L78 Accepts]: Start accepts. Automaton has 30 states. Word has length 134 [2018-04-11 21:02:05,298 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:02:05,299 INFO L225 Difference]: With dead ends: 361 [2018-04-11 21:02:05,299 INFO L226 Difference]: Without dead ends: 293 [2018-04-11 21:02:05,300 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 277 GetRequests, 233 SyntacticMatches, 6 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 360 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=374, Invalid=1186, Unknown=0, NotChecked=0, Total=1560 [2018-04-11 21:02:05,301 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 293 states. [2018-04-11 21:02:05,321 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 293 to 293. [2018-04-11 21:02:05,321 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 293 states. [2018-04-11 21:02:05,323 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 293 states to 293 states and 324 transitions. [2018-04-11 21:02:05,323 INFO L78 Accepts]: Start accepts. Automaton has 293 states and 324 transitions. Word has length 134 [2018-04-11 21:02:05,323 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:02:05,323 INFO L459 AbstractCegarLoop]: Abstraction has 293 states and 324 transitions. [2018-04-11 21:02:05,323 INFO L460 AbstractCegarLoop]: Interpolant automaton has 30 states. [2018-04-11 21:02:05,323 INFO L276 IsEmpty]: Start isEmpty. Operand 293 states and 324 transitions. [2018-04-11 21:02:05,325 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 142 [2018-04-11 21:02:05,325 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:02:05,325 INFO L355 BasicCegarLoop]: trace histogram [8, 8, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:02:05,325 INFO L408 AbstractCegarLoop]: === Iteration 14 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:02:05,326 INFO L82 PathProgramCache]: Analyzing trace with hash -194377757, now seen corresponding path program 8 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 15 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:02:05,334 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:02:05,359 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:02:05,363 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:02:05,670 INFO L134 CoverageAnalysis]: Checked inductivity of 396 backedges. 212 proven. 123 refuted. 0 times theorem prover too weak. 61 trivial. 0 not checked. [2018-04-11 21:02:05,670 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:02:05,889 INFO L134 CoverageAnalysis]: Checked inductivity of 396 backedges. 188 proven. 123 refuted. 0 times theorem prover too weak. 85 trivial. 0 not checked. [2018-04-11 21:02:05,920 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:02:05,921 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 35 [2018-04-11 21:02:05,921 INFO L442 AbstractCegarLoop]: Interpolant automaton has 35 states [2018-04-11 21:02:05,921 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2018-04-11 21:02:05,922 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=222, Invalid=968, Unknown=0, NotChecked=0, Total=1190 [2018-04-11 21:02:05,922 INFO L87 Difference]: Start difference. First operand 293 states and 324 transitions. Second operand 35 states. [2018-04-11 21:02:06,429 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:02:06,429 INFO L93 Difference]: Finished difference Result 361 states and 398 transitions. [2018-04-11 21:02:06,429 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2018-04-11 21:02:06,429 INFO L78 Accepts]: Start accepts. Automaton has 35 states. Word has length 141 [2018-04-11 21:02:06,430 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:02:06,431 INFO L225 Difference]: With dead ends: 361 [2018-04-11 21:02:06,432 INFO L226 Difference]: Without dead ends: 293 [2018-04-11 21:02:06,433 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 293 GetRequests, 241 SyntacticMatches, 7 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 512 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=504, Invalid=1658, Unknown=0, NotChecked=0, Total=2162 [2018-04-11 21:02:06,433 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 293 states. [2018-04-11 21:02:06,452 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 293 to 293. [2018-04-11 21:02:06,453 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 293 states. [2018-04-11 21:02:06,454 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 293 states to 293 states and 323 transitions. [2018-04-11 21:02:06,454 INFO L78 Accepts]: Start accepts. Automaton has 293 states and 323 transitions. Word has length 141 [2018-04-11 21:02:06,455 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:02:06,455 INFO L459 AbstractCegarLoop]: Abstraction has 293 states and 323 transitions. [2018-04-11 21:02:06,455 INFO L460 AbstractCegarLoop]: Interpolant automaton has 35 states. [2018-04-11 21:02:06,455 INFO L276 IsEmpty]: Start isEmpty. Operand 293 states and 323 transitions. [2018-04-11 21:02:06,457 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 149 [2018-04-11 21:02:06,457 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:02:06,457 INFO L355 BasicCegarLoop]: trace histogram [8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:02:06,457 INFO L408 AbstractCegarLoop]: === Iteration 15 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:02:06,457 INFO L82 PathProgramCache]: Analyzing trace with hash -274343193, now seen corresponding path program 9 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 16 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 16 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:02:06,466 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:02:06,493 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:02:06,497 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:02:06,739 INFO L134 CoverageAnalysis]: Checked inductivity of 441 backedges. 189 proven. 168 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2018-04-11 21:02:06,740 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:02:07,001 INFO L134 CoverageAnalysis]: Checked inductivity of 441 backedges. 189 proven. 168 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2018-04-11 21:02:07,020 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:02:07,021 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 25] total 40 [2018-04-11 21:02:07,021 INFO L442 AbstractCegarLoop]: Interpolant automaton has 40 states [2018-04-11 21:02:07,021 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 40 interpolants. [2018-04-11 21:02:07,022 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=282, Invalid=1278, Unknown=0, NotChecked=0, Total=1560 [2018-04-11 21:02:07,022 INFO L87 Difference]: Start difference. First operand 293 states and 323 transitions. Second operand 40 states. [2018-04-11 21:02:07,312 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:02:07,312 INFO L93 Difference]: Finished difference Result 367 states and 404 transitions. [2018-04-11 21:02:07,312 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2018-04-11 21:02:07,312 INFO L78 Accepts]: Start accepts. Automaton has 40 states. Word has length 148 [2018-04-11 21:02:07,313 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:02:07,314 INFO L225 Difference]: With dead ends: 367 [2018-04-11 21:02:07,314 INFO L226 Difference]: Without dead ends: 293 [2018-04-11 21:02:07,315 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 309 GetRequests, 249 SyntacticMatches, 8 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 691 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=653, Invalid=2209, Unknown=0, NotChecked=0, Total=2862 [2018-04-11 21:02:07,315 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 293 states. [2018-04-11 21:02:07,328 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 293 to 293. [2018-04-11 21:02:07,328 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 293 states. [2018-04-11 21:02:07,329 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 293 states to 293 states and 322 transitions. [2018-04-11 21:02:07,329 INFO L78 Accepts]: Start accepts. Automaton has 293 states and 322 transitions. Word has length 148 [2018-04-11 21:02:07,329 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:02:07,329 INFO L459 AbstractCegarLoop]: Abstraction has 293 states and 322 transitions. [2018-04-11 21:02:07,329 INFO L460 AbstractCegarLoop]: Interpolant automaton has 40 states. [2018-04-11 21:02:07,329 INFO L276 IsEmpty]: Start isEmpty. Operand 293 states and 322 transitions. [2018-04-11 21:02:07,331 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 156 [2018-04-11 21:02:07,331 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:02:07,331 INFO L355 BasicCegarLoop]: trace histogram [9, 9, 8, 8, 8, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:02:07,331 INFO L408 AbstractCegarLoop]: === Iteration 16 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:02:07,331 INFO L82 PathProgramCache]: Analyzing trace with hash 596335459, now seen corresponding path program 10 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 17 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 17 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:02:07,343 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:02:07,370 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:02:07,373 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:02:07,482 INFO L134 CoverageAnalysis]: Checked inductivity of 493 backedges. 0 proven. 189 refuted. 0 times theorem prover too weak. 304 trivial. 0 not checked. [2018-04-11 21:02:07,482 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:02:07,825 INFO L134 CoverageAnalysis]: Checked inductivity of 493 backedges. 0 proven. 189 refuted. 0 times theorem prover too weak. 304 trivial. 0 not checked. [2018-04-11 21:02:07,855 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:02:07,856 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 31 [2018-04-11 21:02:07,856 INFO L442 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-04-11 21:02:07,856 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-04-11 21:02:07,856 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=174, Invalid=818, Unknown=0, NotChecked=0, Total=992 [2018-04-11 21:02:07,857 INFO L87 Difference]: Start difference. First operand 293 states and 322 transitions. Second operand 32 states. [2018-04-11 21:02:09,035 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:02:09,035 INFO L93 Difference]: Finished difference Result 362 states and 414 transitions. [2018-04-11 21:02:09,035 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2018-04-11 21:02:09,035 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 155 [2018-04-11 21:02:09,036 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:02:09,037 INFO L225 Difference]: With dead ends: 362 [2018-04-11 21:02:09,037 INFO L226 Difference]: Without dead ends: 360 [2018-04-11 21:02:09,038 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 343 GetRequests, 279 SyntacticMatches, 0 SemanticMatches, 64 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 716 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=1096, Invalid=3194, Unknown=0, NotChecked=0, Total=4290 [2018-04-11 21:02:09,038 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 360 states. [2018-04-11 21:02:09,051 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 360 to 357. [2018-04-11 21:02:09,051 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 357 states. [2018-04-11 21:02:09,052 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 357 states to 357 states and 394 transitions. [2018-04-11 21:02:09,052 INFO L78 Accepts]: Start accepts. Automaton has 357 states and 394 transitions. Word has length 155 [2018-04-11 21:02:09,053 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:02:09,053 INFO L459 AbstractCegarLoop]: Abstraction has 357 states and 394 transitions. [2018-04-11 21:02:09,053 INFO L460 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-04-11 21:02:09,053 INFO L276 IsEmpty]: Start isEmpty. Operand 357 states and 394 transitions. [2018-04-11 21:02:09,054 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 220 [2018-04-11 21:02:09,054 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:02:09,054 INFO L355 BasicCegarLoop]: trace histogram [31, 30, 30, 30, 30, 30, 30, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:02:09,055 INFO L408 AbstractCegarLoop]: === Iteration 17 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:02:09,055 INFO L82 PathProgramCache]: Analyzing trace with hash 2010902702, now seen corresponding path program 4 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 18 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 18 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:02:09,066 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:02:09,090 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:02:09,093 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:02:09,526 INFO L134 CoverageAnalysis]: Checked inductivity of 3105 backedges. 0 proven. 3105 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-11 21:02:09,526 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:02:10,561 INFO L134 CoverageAnalysis]: Checked inductivity of 3105 backedges. 0 proven. 3105 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-11 21:02:10,580 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:02:10,581 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [32, 32] total 63 [2018-04-11 21:02:10,581 INFO L442 AbstractCegarLoop]: Interpolant automaton has 64 states [2018-04-11 21:02:10,581 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 64 interpolants. [2018-04-11 21:02:10,582 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1086, Invalid=2946, Unknown=0, NotChecked=0, Total=4032 [2018-04-11 21:02:10,582 INFO L87 Difference]: Start difference. First operand 357 states and 394 transitions. Second operand 64 states. [2018-04-11 21:02:16,259 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:02:16,259 INFO L93 Difference]: Finished difference Result 7498 states and 8470 transitions. [2018-04-11 21:02:16,275 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 64 states. [2018-04-11 21:02:16,275 INFO L78 Accepts]: Start accepts. Automaton has 64 states. Word has length 219 [2018-04-11 21:02:16,276 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:02:16,309 INFO L225 Difference]: With dead ends: 7498 [2018-04-11 21:02:16,309 INFO L226 Difference]: Without dead ends: 7495 [2018-04-11 21:02:16,314 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 467 GetRequests, 375 SyntacticMatches, 0 SemanticMatches, 92 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 435 ImplicationChecksByTransitivity, 4.0s TimeCoverageRelationStatistics Valid=3006, Invalid=5736, Unknown=0, NotChecked=0, Total=8742 [2018-04-11 21:02:16,319 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 7495 states. [2018-04-11 21:02:16,509 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 7495 to 581. [2018-04-11 21:02:16,509 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-04-11 21:02:16,511 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 650 transitions. [2018-04-11 21:02:16,511 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 650 transitions. Word has length 219 [2018-04-11 21:02:16,512 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:02:16,512 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 650 transitions. [2018-04-11 21:02:16,512 INFO L460 AbstractCegarLoop]: Interpolant automaton has 64 states. [2018-04-11 21:02:16,512 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 650 transitions. [2018-04-11 21:02:16,523 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 252 [2018-04-11 21:02:16,523 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:02:16,524 INFO L355 BasicCegarLoop]: trace histogram [16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 9, 9, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:02:16,524 INFO L408 AbstractCegarLoop]: === Iteration 18 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:02:16,524 INFO L82 PathProgramCache]: Analyzing trace with hash 1912252555, now seen corresponding path program 11 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 19 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 19 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:02:16,533 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:02:16,576 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:02:16,582 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:02:17,088 INFO L134 CoverageAnalysis]: Checked inductivity of 1525 backedges. 934 proven. 220 refuted. 0 times theorem prover too weak. 371 trivial. 0 not checked. [2018-04-11 21:02:17,088 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:02:17,390 INFO L134 CoverageAnalysis]: Checked inductivity of 1525 backedges. 710 proven. 220 refuted. 0 times theorem prover too weak. 595 trivial. 0 not checked. [2018-04-11 21:02:17,410 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:02:17,410 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [28, 28] total 45 [2018-04-11 21:02:17,411 INFO L442 AbstractCegarLoop]: Interpolant automaton has 45 states [2018-04-11 21:02:17,411 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2018-04-11 21:02:17,412 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=349, Invalid=1631, Unknown=0, NotChecked=0, Total=1980 [2018-04-11 21:02:17,412 INFO L87 Difference]: Start difference. First operand 581 states and 650 transitions. Second operand 45 states. [2018-04-11 21:02:17,836 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:02:17,837 INFO L93 Difference]: Finished difference Result 713 states and 796 transitions. [2018-04-11 21:02:17,837 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2018-04-11 21:02:17,837 INFO L78 Accepts]: Start accepts. Automaton has 45 states. Word has length 251 [2018-04-11 21:02:17,837 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:02:17,839 INFO L225 Difference]: With dead ends: 713 [2018-04-11 21:02:17,839 INFO L226 Difference]: Without dead ends: 581 [2018-04-11 21:02:17,840 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 517 GetRequests, 449 SyntacticMatches, 9 SemanticMatches, 59 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 897 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=821, Invalid=2839, Unknown=0, NotChecked=0, Total=3660 [2018-04-11 21:02:17,840 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-04-11 21:02:17,880 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-04-11 21:02:17,880 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-04-11 21:02:17,882 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 649 transitions. [2018-04-11 21:02:17,882 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 649 transitions. Word has length 251 [2018-04-11 21:02:17,882 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:02:17,882 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 649 transitions. [2018-04-11 21:02:17,882 INFO L460 AbstractCegarLoop]: Interpolant automaton has 45 states. [2018-04-11 21:02:17,882 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 649 transitions. [2018-04-11 21:02:17,883 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 259 [2018-04-11 21:02:17,884 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:02:17,884 INFO L355 BasicCegarLoop]: trace histogram [16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 10, 10, 9, 9, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:02:17,884 INFO L408 AbstractCegarLoop]: === Iteration 19 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:02:17,884 INFO L82 PathProgramCache]: Analyzing trace with hash -922504049, now seen corresponding path program 12 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 20 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 20 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:02:17,890 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:02:17,925 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:02:17,929 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:02:18,349 INFO L134 CoverageAnalysis]: Checked inductivity of 1584 backedges. 975 proven. 279 refuted. 0 times theorem prover too weak. 330 trivial. 0 not checked. [2018-04-11 21:02:18,349 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:02:18,707 INFO L134 CoverageAnalysis]: Checked inductivity of 1584 backedges. 759 proven. 279 refuted. 0 times theorem prover too weak. 546 trivial. 0 not checked. [2018-04-11 21:02:18,727 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:02:18,727 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [31, 31] total 50 [2018-04-11 21:02:18,728 INFO L442 AbstractCegarLoop]: Interpolant automaton has 50 states [2018-04-11 21:02:18,728 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 50 interpolants. [2018-04-11 21:02:18,729 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=423, Invalid=2027, Unknown=0, NotChecked=0, Total=2450 [2018-04-11 21:02:18,729 INFO L87 Difference]: Start difference. First operand 581 states and 649 transitions. Second operand 50 states. [2018-04-11 21:02:19,210 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:02:19,210 INFO L93 Difference]: Finished difference Result 713 states and 795 transitions. [2018-04-11 21:02:19,210 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2018-04-11 21:02:19,210 INFO L78 Accepts]: Start accepts. Automaton has 50 states. Word has length 258 [2018-04-11 21:02:19,211 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:02:19,212 INFO L225 Difference]: With dead ends: 713 [2018-04-11 21:02:19,212 INFO L226 Difference]: Without dead ends: 581 [2018-04-11 21:02:19,214 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 533 GetRequests, 457 SyntacticMatches, 10 SemanticMatches, 66 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1130 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=1008, Invalid=3548, Unknown=0, NotChecked=0, Total=4556 [2018-04-11 21:02:19,214 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-04-11 21:02:19,253 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-04-11 21:02:19,253 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-04-11 21:02:19,254 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 648 transitions. [2018-04-11 21:02:19,254 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 648 transitions. Word has length 258 [2018-04-11 21:02:19,254 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:02:19,255 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 648 transitions. [2018-04-11 21:02:19,255 INFO L460 AbstractCegarLoop]: Interpolant automaton has 50 states. [2018-04-11 21:02:19,255 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 648 transitions. [2018-04-11 21:02:19,256 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 266 [2018-04-11 21:02:19,256 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:02:19,256 INFO L355 BasicCegarLoop]: trace histogram [16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 11, 11, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:02:19,256 INFO L408 AbstractCegarLoop]: === Iteration 20 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:02:19,257 INFO L82 PathProgramCache]: Analyzing trace with hash 1400495115, now seen corresponding path program 13 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 21 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 21 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:02:19,263 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:02:19,298 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:02:19,302 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:02:19,723 INFO L134 CoverageAnalysis]: Checked inductivity of 1650 backedges. 1000 proven. 345 refuted. 0 times theorem prover too weak. 305 trivial. 0 not checked. [2018-04-11 21:02:19,724 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:02:20,126 INFO L134 CoverageAnalysis]: Checked inductivity of 1650 backedges. 800 proven. 345 refuted. 0 times theorem prover too weak. 505 trivial. 0 not checked. [2018-04-11 21:02:20,146 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:02:20,147 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [34, 34] total 55 [2018-04-11 21:02:20,147 INFO L442 AbstractCegarLoop]: Interpolant automaton has 55 states [2018-04-11 21:02:20,147 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 55 interpolants. [2018-04-11 21:02:20,148 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=504, Invalid=2466, Unknown=0, NotChecked=0, Total=2970 [2018-04-11 21:02:20,148 INFO L87 Difference]: Start difference. First operand 581 states and 648 transitions. Second operand 55 states. [2018-04-11 21:02:20,784 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:02:20,784 INFO L93 Difference]: Finished difference Result 713 states and 794 transitions. [2018-04-11 21:02:20,785 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2018-04-11 21:02:20,785 INFO L78 Accepts]: Start accepts. Automaton has 55 states. Word has length 265 [2018-04-11 21:02:20,785 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:02:20,787 INFO L225 Difference]: With dead ends: 713 [2018-04-11 21:02:20,787 INFO L226 Difference]: Without dead ends: 581 [2018-04-11 21:02:20,788 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 549 GetRequests, 465 SyntacticMatches, 11 SemanticMatches, 73 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1390 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=1214, Invalid=4336, Unknown=0, NotChecked=0, Total=5550 [2018-04-11 21:02:20,788 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-04-11 21:02:20,827 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-04-11 21:02:20,827 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-04-11 21:02:20,828 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 647 transitions. [2018-04-11 21:02:20,828 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 647 transitions. Word has length 265 [2018-04-11 21:02:20,828 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:02:20,828 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 647 transitions. [2018-04-11 21:02:20,829 INFO L460 AbstractCegarLoop]: Interpolant automaton has 55 states. [2018-04-11 21:02:20,829 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 647 transitions. [2018-04-11 21:02:20,830 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 273 [2018-04-11 21:02:20,830 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:02:20,830 INFO L355 BasicCegarLoop]: trace histogram [16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 12, 12, 11, 11, 11, 11, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:02:20,830 INFO L408 AbstractCegarLoop]: === Iteration 21 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:02:20,831 INFO L82 PathProgramCache]: Analyzing trace with hash -685010673, now seen corresponding path program 14 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 22 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 22 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:02:20,837 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:02:20,866 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:02:20,870 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:02:21,230 INFO L134 CoverageAnalysis]: Checked inductivity of 1723 backedges. 1009 proven. 418 refuted. 0 times theorem prover too weak. 296 trivial. 0 not checked. [2018-04-11 21:02:21,230 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:02:21,707 INFO L134 CoverageAnalysis]: Checked inductivity of 1723 backedges. 833 proven. 418 refuted. 0 times theorem prover too weak. 472 trivial. 0 not checked. [2018-04-11 21:02:21,726 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:02:21,727 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [37, 37] total 60 [2018-04-11 21:02:21,727 INFO L442 AbstractCegarLoop]: Interpolant automaton has 60 states [2018-04-11 21:02:21,727 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 60 interpolants. [2018-04-11 21:02:21,728 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=592, Invalid=2948, Unknown=0, NotChecked=0, Total=3540 [2018-04-11 21:02:21,729 INFO L87 Difference]: Start difference. First operand 581 states and 647 transitions. Second operand 60 states. [2018-04-11 21:02:22,435 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:02:22,436 INFO L93 Difference]: Finished difference Result 713 states and 793 transitions. [2018-04-11 21:02:22,436 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 48 states. [2018-04-11 21:02:22,436 INFO L78 Accepts]: Start accepts. Automaton has 60 states. Word has length 272 [2018-04-11 21:02:22,436 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:02:22,438 INFO L225 Difference]: With dead ends: 713 [2018-04-11 21:02:22,438 INFO L226 Difference]: Without dead ends: 581 [2018-04-11 21:02:22,439 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 565 GetRequests, 473 SyntacticMatches, 12 SemanticMatches, 80 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1677 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=1439, Invalid=5203, Unknown=0, NotChecked=0, Total=6642 [2018-04-11 21:02:22,439 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-04-11 21:02:22,504 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-04-11 21:02:22,504 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-04-11 21:02:22,506 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 646 transitions. [2018-04-11 21:02:22,506 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 646 transitions. Word has length 272 [2018-04-11 21:02:22,506 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:02:22,507 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 646 transitions. [2018-04-11 21:02:22,507 INFO L460 AbstractCegarLoop]: Interpolant automaton has 60 states. [2018-04-11 21:02:22,507 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 646 transitions. [2018-04-11 21:02:22,509 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 280 [2018-04-11 21:02:22,509 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:02:22,509 INFO L355 BasicCegarLoop]: trace histogram [16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 13, 13, 12, 12, 12, 12, 12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:02:22,509 INFO L408 AbstractCegarLoop]: === Iteration 22 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:02:22,510 INFO L82 PathProgramCache]: Analyzing trace with hash -828838005, now seen corresponding path program 15 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 23 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 23 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:02:22,523 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:02:22,571 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:02:22,578 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:02:23,060 INFO L134 CoverageAnalysis]: Checked inductivity of 1803 backedges. 1002 proven. 498 refuted. 0 times theorem prover too weak. 303 trivial. 0 not checked. [2018-04-11 21:02:23,061 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:02:23,729 INFO L134 CoverageAnalysis]: Checked inductivity of 1803 backedges. 858 proven. 498 refuted. 0 times theorem prover too weak. 447 trivial. 0 not checked. [2018-04-11 21:02:23,751 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:02:23,751 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [40, 40] total 65 [2018-04-11 21:02:23,751 INFO L442 AbstractCegarLoop]: Interpolant automaton has 65 states [2018-04-11 21:02:23,752 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 65 interpolants. [2018-04-11 21:02:23,752 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=687, Invalid=3473, Unknown=0, NotChecked=0, Total=4160 [2018-04-11 21:02:23,752 INFO L87 Difference]: Start difference. First operand 581 states and 646 transitions. Second operand 65 states. [2018-04-11 21:02:24,782 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:02:24,782 INFO L93 Difference]: Finished difference Result 713 states and 792 transitions. [2018-04-11 21:02:24,783 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 52 states. [2018-04-11 21:02:24,783 INFO L78 Accepts]: Start accepts. Automaton has 65 states. Word has length 279 [2018-04-11 21:02:24,784 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:02:24,786 INFO L225 Difference]: With dead ends: 713 [2018-04-11 21:02:24,786 INFO L226 Difference]: Without dead ends: 581 [2018-04-11 21:02:24,787 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 581 GetRequests, 481 SyntacticMatches, 13 SemanticMatches, 87 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1991 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=1683, Invalid=6149, Unknown=0, NotChecked=0, Total=7832 [2018-04-11 21:02:24,787 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-04-11 21:02:24,827 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-04-11 21:02:24,827 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-04-11 21:02:24,829 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 645 transitions. [2018-04-11 21:02:24,829 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 645 transitions. Word has length 279 [2018-04-11 21:02:24,829 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:02:24,829 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 645 transitions. [2018-04-11 21:02:24,829 INFO L460 AbstractCegarLoop]: Interpolant automaton has 65 states. [2018-04-11 21:02:24,830 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 645 transitions. [2018-04-11 21:02:24,831 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 287 [2018-04-11 21:02:24,831 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:02:24,831 INFO L355 BasicCegarLoop]: trace histogram [16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 14, 14, 13, 13, 13, 13, 13, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:02:24,831 INFO L408 AbstractCegarLoop]: === Iteration 23 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:02:24,831 INFO L82 PathProgramCache]: Analyzing trace with hash 303533455, now seen corresponding path program 16 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 24 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 24 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:02:24,837 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:02:24,874 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:02:24,880 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:02:25,449 INFO L134 CoverageAnalysis]: Checked inductivity of 1890 backedges. 979 proven. 585 refuted. 0 times theorem prover too weak. 326 trivial. 0 not checked. [2018-04-11 21:02:25,450 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:02:26,100 INFO L134 CoverageAnalysis]: Checked inductivity of 1890 backedges. 875 proven. 585 refuted. 0 times theorem prover too weak. 430 trivial. 0 not checked. [2018-04-11 21:02:26,120 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:02:26,120 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [43, 43] total 70 [2018-04-11 21:02:26,120 INFO L442 AbstractCegarLoop]: Interpolant automaton has 70 states [2018-04-11 21:02:26,121 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 70 interpolants. [2018-04-11 21:02:26,121 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=789, Invalid=4041, Unknown=0, NotChecked=0, Total=4830 [2018-04-11 21:02:26,121 INFO L87 Difference]: Start difference. First operand 581 states and 645 transitions. Second operand 70 states. [2018-04-11 21:02:26,933 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:02:26,933 INFO L93 Difference]: Finished difference Result 713 states and 791 transitions. [2018-04-11 21:02:26,933 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 56 states. [2018-04-11 21:02:26,934 INFO L78 Accepts]: Start accepts. Automaton has 70 states. Word has length 286 [2018-04-11 21:02:26,934 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:02:26,936 INFO L225 Difference]: With dead ends: 713 [2018-04-11 21:02:26,936 INFO L226 Difference]: Without dead ends: 581 [2018-04-11 21:02:26,937 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 597 GetRequests, 489 SyntacticMatches, 14 SemanticMatches, 94 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2332 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=1946, Invalid=7174, Unknown=0, NotChecked=0, Total=9120 [2018-04-11 21:02:26,937 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-04-11 21:02:26,989 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-04-11 21:02:26,990 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-04-11 21:02:26,991 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 644 transitions. [2018-04-11 21:02:26,991 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 644 transitions. Word has length 286 [2018-04-11 21:02:26,991 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:02:26,991 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 644 transitions. [2018-04-11 21:02:26,991 INFO L460 AbstractCegarLoop]: Interpolant automaton has 70 states. [2018-04-11 21:02:26,991 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 644 transitions. [2018-04-11 21:02:26,993 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 294 [2018-04-11 21:02:26,993 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:02:26,993 INFO L355 BasicCegarLoop]: trace histogram [16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 14, 14, 14, 14, 14, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:02:26,993 INFO L408 AbstractCegarLoop]: === Iteration 24 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:02:26,993 INFO L82 PathProgramCache]: Analyzing trace with hash 504357643, now seen corresponding path program 17 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 25 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 25 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:02:27,001 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:02:27,038 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:02:27,043 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:02:27,719 INFO L134 CoverageAnalysis]: Checked inductivity of 1984 backedges. 940 proven. 679 refuted. 0 times theorem prover too weak. 365 trivial. 0 not checked. [2018-04-11 21:02:27,720 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:02:28,428 INFO L134 CoverageAnalysis]: Checked inductivity of 1984 backedges. 884 proven. 679 refuted. 0 times theorem prover too weak. 421 trivial. 0 not checked. [2018-04-11 21:02:28,447 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:02:28,448 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [46, 46] total 75 [2018-04-11 21:02:28,448 INFO L442 AbstractCegarLoop]: Interpolant automaton has 75 states [2018-04-11 21:02:28,448 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 75 interpolants. [2018-04-11 21:02:28,449 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=898, Invalid=4652, Unknown=0, NotChecked=0, Total=5550 [2018-04-11 21:02:28,449 INFO L87 Difference]: Start difference. First operand 581 states and 644 transitions. Second operand 75 states. [2018-04-11 21:02:29,345 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:02:29,345 INFO L93 Difference]: Finished difference Result 713 states and 790 transitions. [2018-04-11 21:02:29,345 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 60 states. [2018-04-11 21:02:29,345 INFO L78 Accepts]: Start accepts. Automaton has 75 states. Word has length 293 [2018-04-11 21:02:29,346 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:02:29,347 INFO L225 Difference]: With dead ends: 713 [2018-04-11 21:02:29,347 INFO L226 Difference]: Without dead ends: 581 [2018-04-11 21:02:29,348 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 613 GetRequests, 497 SyntacticMatches, 15 SemanticMatches, 101 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2700 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=2228, Invalid=8278, Unknown=0, NotChecked=0, Total=10506 [2018-04-11 21:02:29,349 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-04-11 21:02:29,383 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-04-11 21:02:29,383 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-04-11 21:02:29,385 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 643 transitions. [2018-04-11 21:02:29,385 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 643 transitions. Word has length 293 [2018-04-11 21:02:29,385 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:02:29,385 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 643 transitions. [2018-04-11 21:02:29,385 INFO L460 AbstractCegarLoop]: Interpolant automaton has 75 states. [2018-04-11 21:02:29,385 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 643 transitions. [2018-04-11 21:02:29,387 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 301 [2018-04-11 21:02:29,387 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:02:29,387 INFO L355 BasicCegarLoop]: trace histogram [16, 16, 16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:02:29,387 INFO L408 AbstractCegarLoop]: === Iteration 25 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:02:29,387 INFO L82 PathProgramCache]: Analyzing trace with hash 1074768399, now seen corresponding path program 18 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 26 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 26 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:02:29,401 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:02:29,450 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:02:29,455 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:02:30,171 INFO L134 CoverageAnalysis]: Checked inductivity of 2085 backedges. 885 proven. 780 refuted. 0 times theorem prover too weak. 420 trivial. 0 not checked. [2018-04-11 21:02:30,171 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:02:30,965 INFO L134 CoverageAnalysis]: Checked inductivity of 2085 backedges. 885 proven. 780 refuted. 0 times theorem prover too weak. 420 trivial. 0 not checked. [2018-04-11 21:02:30,985 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:02:30,985 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [49, 49] total 80 [2018-04-11 21:02:30,985 INFO L442 AbstractCegarLoop]: Interpolant automaton has 80 states [2018-04-11 21:02:30,986 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 80 interpolants. [2018-04-11 21:02:30,986 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1014, Invalid=5306, Unknown=0, NotChecked=0, Total=6320 [2018-04-11 21:02:30,987 INFO L87 Difference]: Start difference. First operand 581 states and 643 transitions. Second operand 80 states. [2018-04-11 21:02:31,987 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:02:31,988 INFO L93 Difference]: Finished difference Result 719 states and 796 transitions. [2018-04-11 21:02:31,988 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 64 states. [2018-04-11 21:02:31,988 INFO L78 Accepts]: Start accepts. Automaton has 80 states. Word has length 300 [2018-04-11 21:02:31,988 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:02:31,990 INFO L225 Difference]: With dead ends: 719 [2018-04-11 21:02:31,990 INFO L226 Difference]: Without dead ends: 581 [2018-04-11 21:02:31,991 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 629 GetRequests, 505 SyntacticMatches, 16 SemanticMatches, 108 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3095 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=2529, Invalid=9461, Unknown=0, NotChecked=0, Total=11990 [2018-04-11 21:02:31,991 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-04-11 21:02:32,026 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-04-11 21:02:32,026 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-04-11 21:02:32,027 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 642 transitions. [2018-04-11 21:02:32,027 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 642 transitions. Word has length 300 [2018-04-11 21:02:32,028 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:02:32,028 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 642 transitions. [2018-04-11 21:02:32,028 INFO L460 AbstractCegarLoop]: Interpolant automaton has 80 states. [2018-04-11 21:02:32,028 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 642 transitions. [2018-04-11 21:02:32,030 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 308 [2018-04-11 21:02:32,031 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:02:32,031 INFO L355 BasicCegarLoop]: trace histogram [17, 17, 16, 16, 16, 16, 16, 16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:02:32,031 INFO L408 AbstractCegarLoop]: === Iteration 26 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:02:32,031 INFO L82 PathProgramCache]: Analyzing trace with hash 1519826571, now seen corresponding path program 19 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 27 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 27 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:02:32,041 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:02:32,090 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:02:32,096 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:02:32,437 INFO L134 CoverageAnalysis]: Checked inductivity of 2193 backedges. 0 proven. 885 refuted. 0 times theorem prover too weak. 1308 trivial. 0 not checked. [2018-04-11 21:02:32,437 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:02:33,400 INFO L134 CoverageAnalysis]: Checked inductivity of 2193 backedges. 0 proven. 885 refuted. 0 times theorem prover too weak. 1308 trivial. 0 not checked. [2018-04-11 21:02:33,420 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:02:33,420 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [32, 32] total 63 [2018-04-11 21:02:33,421 INFO L442 AbstractCegarLoop]: Interpolant automaton has 64 states [2018-04-11 21:02:33,421 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 64 interpolants. [2018-04-11 21:02:33,421 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=606, Invalid=3426, Unknown=0, NotChecked=0, Total=4032 [2018-04-11 21:02:33,421 INFO L87 Difference]: Start difference. First operand 581 states and 642 transitions. Second operand 64 states. [2018-04-11 21:02:37,937 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:02:37,937 INFO L93 Difference]: Finished difference Result 714 states and 822 transitions. [2018-04-11 21:02:37,937 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 93 states. [2018-04-11 21:02:37,937 INFO L78 Accepts]: Start accepts. Automaton has 64 states. Word has length 307 [2018-04-11 21:02:37,938 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:02:37,940 INFO L225 Difference]: With dead ends: 714 [2018-04-11 21:02:37,940 INFO L226 Difference]: Without dead ends: 712 [2018-04-11 21:02:37,941 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 687 GetRequests, 551 SyntacticMatches, 0 SemanticMatches, 136 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3452 ImplicationChecksByTransitivity, 4.8s TimeCoverageRelationStatistics Valid=4624, Invalid=14282, Unknown=0, NotChecked=0, Total=18906 [2018-04-11 21:02:37,941 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 712 states. [2018-04-11 21:02:37,978 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 712 to 709. [2018-04-11 21:02:37,978 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 709 states. [2018-04-11 21:02:37,980 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 709 states to 709 states and 786 transitions. [2018-04-11 21:02:37,980 INFO L78 Accepts]: Start accepts. Automaton has 709 states and 786 transitions. Word has length 307 [2018-04-11 21:02:37,980 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:02:37,980 INFO L459 AbstractCegarLoop]: Abstraction has 709 states and 786 transitions. [2018-04-11 21:02:37,980 INFO L460 AbstractCegarLoop]: Interpolant automaton has 64 states. [2018-04-11 21:02:37,980 INFO L276 IsEmpty]: Start isEmpty. Operand 709 states and 786 transitions. [2018-04-11 21:02:37,984 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 444 [2018-04-11 21:02:37,984 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:02:37,984 INFO L355 BasicCegarLoop]: trace histogram [63, 62, 62, 62, 62, 62, 62, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:02:37,985 INFO L408 AbstractCegarLoop]: === Iteration 27 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:02:37,985 INFO L82 PathProgramCache]: Analyzing trace with hash 740305070, now seen corresponding path program 5 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 28 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 28 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:02:37,996 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:02:38,034 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:02:38,040 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:02:39,298 INFO L134 CoverageAnalysis]: Checked inductivity of 13361 backedges. 0 proven. 13361 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-11 21:02:39,298 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:02:43,060 INFO L134 CoverageAnalysis]: Checked inductivity of 13361 backedges. 0 proven. 13361 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-11 21:02:43,080 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:02:43,081 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [64, 64] total 127 [2018-04-11 21:02:43,081 INFO L442 AbstractCegarLoop]: Interpolant automaton has 128 states [2018-04-11 21:02:43,082 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 128 interpolants. [2018-04-11 21:02:43,082 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=4222, Invalid=12034, Unknown=0, NotChecked=0, Total=16256 [2018-04-11 21:02:43,082 INFO L87 Difference]: Start difference. First operand 709 states and 786 transitions. Second operand 128 states. [2018-04-11 21:02:48,655 WARN L151 SmtUtils]: Spent 247ms on a formula simplification. DAG size of input: 316 DAG size of output 6 [2018-04-11 21:02:49,123 WARN L151 SmtUtils]: Spent 238ms on a formula simplification. DAG size of input: 311 DAG size of output 6 [2018-04-11 21:02:49,594 WARN L151 SmtUtils]: Spent 236ms on a formula simplification. DAG size of input: 306 DAG size of output 6 [2018-04-11 21:02:50,069 WARN L151 SmtUtils]: Spent 235ms on a formula simplification. DAG size of input: 301 DAG size of output 6 [2018-04-11 21:02:50,529 WARN L151 SmtUtils]: Spent 222ms on a formula simplification. DAG size of input: 296 DAG size of output 6 [2018-04-11 21:02:50,975 WARN L151 SmtUtils]: Spent 213ms on a formula simplification. DAG size of input: 291 DAG size of output 6 [2018-04-11 21:02:51,437 WARN L151 SmtUtils]: Spent 216ms on a formula simplification. DAG size of input: 286 DAG size of output 6 [2018-04-11 21:02:51,896 WARN L151 SmtUtils]: Spent 201ms on a formula simplification. DAG size of input: 281 DAG size of output 6 [2018-04-11 21:02:52,328 WARN L151 SmtUtils]: Spent 194ms on a formula simplification. DAG size of input: 276 DAG size of output 6 [2018-04-11 21:02:52,764 WARN L151 SmtUtils]: Spent 186ms on a formula simplification. DAG size of input: 271 DAG size of output 6 [2018-04-11 21:02:53,182 WARN L151 SmtUtils]: Spent 178ms on a formula simplification. DAG size of input: 266 DAG size of output 6 [2018-04-11 21:02:53,610 WARN L151 SmtUtils]: Spent 169ms on a formula simplification. DAG size of input: 261 DAG size of output 6 [2018-04-11 21:02:54,030 WARN L151 SmtUtils]: Spent 179ms on a formula simplification. DAG size of input: 256 DAG size of output 6 [2018-04-11 21:02:54,434 WARN L151 SmtUtils]: Spent 166ms on a formula simplification. DAG size of input: 251 DAG size of output 6 [2018-04-11 21:02:54,829 WARN L151 SmtUtils]: Spent 157ms on a formula simplification. DAG size of input: 246 DAG size of output 6 [2018-04-11 21:02:55,225 WARN L151 SmtUtils]: Spent 158ms on a formula simplification. DAG size of input: 241 DAG size of output 6 [2018-04-11 21:02:55,614 WARN L151 SmtUtils]: Spent 151ms on a formula simplification. DAG size of input: 236 DAG size of output 6 [2018-04-11 21:02:55,995 WARN L151 SmtUtils]: Spent 146ms on a formula simplification. DAG size of input: 231 DAG size of output 6 [2018-04-11 21:02:56,370 WARN L151 SmtUtils]: Spent 139ms on a formula simplification. DAG size of input: 226 DAG size of output 6 [2018-04-11 21:02:56,753 WARN L151 SmtUtils]: Spent 144ms on a formula simplification. DAG size of input: 221 DAG size of output 6 [2018-04-11 21:02:57,108 WARN L151 SmtUtils]: Spent 120ms on a formula simplification. DAG size of input: 216 DAG size of output 6 [2018-04-11 21:02:57,463 WARN L151 SmtUtils]: Spent 122ms on a formula simplification. DAG size of input: 211 DAG size of output 6 [2018-04-11 21:02:57,810 WARN L151 SmtUtils]: Spent 114ms on a formula simplification. DAG size of input: 206 DAG size of output 6 [2018-04-11 21:02:58,148 WARN L151 SmtUtils]: Spent 109ms on a formula simplification. DAG size of input: 201 DAG size of output 6 [2018-04-11 21:02:58,494 WARN L151 SmtUtils]: Spent 105ms on a formula simplification. DAG size of input: 196 DAG size of output 6 [2018-04-11 21:02:58,823 WARN L151 SmtUtils]: Spent 104ms on a formula simplification. DAG size of input: 191 DAG size of output 6 [2018-04-11 21:03:12,106 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:03:12,106 INFO L93 Difference]: Finished difference Result 29322 states and 33062 transitions. [2018-04-11 21:03:12,107 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 128 states. [2018-04-11 21:03:12,107 INFO L78 Accepts]: Start accepts. Automaton has 128 states. Word has length 443 [2018-04-11 21:03:12,107 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:03:12,182 INFO L225 Difference]: With dead ends: 29322 [2018-04-11 21:03:12,182 INFO L226 Difference]: Without dead ends: 29319 [2018-04-11 21:03:12,190 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 947 GetRequests, 759 SyntacticMatches, 0 SemanticMatches, 188 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1891 ImplicationChecksByTransitivity, 21.7s TimeCoverageRelationStatistics Valid=12158, Invalid=23752, Unknown=0, NotChecked=0, Total=35910 [2018-04-11 21:03:12,202 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29319 states. [2018-04-11 21:03:12,632 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29319 to 1157. [2018-04-11 21:03:12,633 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-11 21:03:12,634 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1298 transitions. [2018-04-11 21:03:12,634 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1298 transitions. Word has length 443 [2018-04-11 21:03:12,635 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:03:12,635 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1298 transitions. [2018-04-11 21:03:12,635 INFO L460 AbstractCegarLoop]: Interpolant automaton has 128 states. [2018-04-11 21:03:12,635 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1298 transitions. [2018-04-11 21:03:12,638 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 500 [2018-04-11 21:03:12,638 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:03:12,638 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 17, 17, 16, 16, 16, 16, 16, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:03:12,638 INFO L408 AbstractCegarLoop]: === Iteration 28 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:03:12,639 INFO L82 PathProgramCache]: Analyzing trace with hash 1232187611, now seen corresponding path program 20 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 29 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 29 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:03:12,649 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:03:12,712 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:03:12,718 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:03:13,559 INFO L134 CoverageAnalysis]: Checked inductivity of 6561 backedges. 3918 proven. 888 refuted. 0 times theorem prover too weak. 1755 trivial. 0 not checked. [2018-04-11 21:03:13,560 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:03:14,514 INFO L134 CoverageAnalysis]: Checked inductivity of 6561 backedges. 2958 proven. 888 refuted. 0 times theorem prover too weak. 2715 trivial. 0 not checked. [2018-04-11 21:03:14,535 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:03:14,535 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [52, 52] total 85 [2018-04-11 21:03:14,535 INFO L442 AbstractCegarLoop]: Interpolant automaton has 85 states [2018-04-11 21:03:14,536 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 85 interpolants. [2018-04-11 21:03:14,536 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1137, Invalid=6003, Unknown=0, NotChecked=0, Total=7140 [2018-04-11 21:03:14,536 INFO L87 Difference]: Start difference. First operand 1157 states and 1298 transitions. Second operand 85 states. [2018-04-11 21:03:15,785 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:03:15,785 INFO L93 Difference]: Finished difference Result 1417 states and 1588 transitions. [2018-04-11 21:03:15,786 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 68 states. [2018-04-11 21:03:15,786 INFO L78 Accepts]: Start accepts. Automaton has 85 states. Word has length 499 [2018-04-11 21:03:15,786 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:03:15,788 INFO L225 Difference]: With dead ends: 1417 [2018-04-11 21:03:15,788 INFO L226 Difference]: Without dead ends: 1157 [2018-04-11 21:03:15,791 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1029 GetRequests, 897 SyntacticMatches, 17 SemanticMatches, 115 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3517 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=2849, Invalid=10723, Unknown=0, NotChecked=0, Total=13572 [2018-04-11 21:03:15,792 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-11 21:03:15,949 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-11 21:03:15,950 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-11 21:03:15,951 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1297 transitions. [2018-04-11 21:03:15,951 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1297 transitions. Word has length 499 [2018-04-11 21:03:15,951 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:03:15,951 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1297 transitions. [2018-04-11 21:03:15,951 INFO L460 AbstractCegarLoop]: Interpolant automaton has 85 states. [2018-04-11 21:03:15,952 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1297 transitions. [2018-04-11 21:03:15,954 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 507 [2018-04-11 21:03:15,954 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:03:15,954 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 18, 18, 17, 17, 17, 17, 17, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:03:15,954 INFO L408 AbstractCegarLoop]: === Iteration 29 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:03:15,955 INFO L82 PathProgramCache]: Analyzing trace with hash 1001423071, now seen corresponding path program 21 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 30 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 30 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:03:15,960 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:03:16,026 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:03:16,032 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:03:17,402 INFO L134 CoverageAnalysis]: Checked inductivity of 6676 backedges. 4023 proven. 1003 refuted. 0 times theorem prover too weak. 1650 trivial. 0 not checked. [2018-04-11 21:03:17,402 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:03:18,590 INFO L134 CoverageAnalysis]: Checked inductivity of 6676 backedges. 3071 proven. 1003 refuted. 0 times theorem prover too weak. 2602 trivial. 0 not checked. [2018-04-11 21:03:18,610 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:03:18,611 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [55, 55] total 90 [2018-04-11 21:03:18,612 INFO L442 AbstractCegarLoop]: Interpolant automaton has 90 states [2018-04-11 21:03:18,612 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 90 interpolants. [2018-04-11 21:03:18,613 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1267, Invalid=6743, Unknown=0, NotChecked=0, Total=8010 [2018-04-11 21:03:18,613 INFO L87 Difference]: Start difference. First operand 1157 states and 1297 transitions. Second operand 90 states. [2018-04-11 21:03:20,091 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:03:20,091 INFO L93 Difference]: Finished difference Result 1417 states and 1587 transitions. [2018-04-11 21:03:20,091 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 72 states. [2018-04-11 21:03:20,091 INFO L78 Accepts]: Start accepts. Automaton has 90 states. Word has length 506 [2018-04-11 21:03:20,092 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:03:20,093 INFO L225 Difference]: With dead ends: 1417 [2018-04-11 21:03:20,093 INFO L226 Difference]: Without dead ends: 1157 [2018-04-11 21:03:20,095 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1045 GetRequests, 905 SyntacticMatches, 18 SemanticMatches, 122 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3966 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=3188, Invalid=12064, Unknown=0, NotChecked=0, Total=15252 [2018-04-11 21:03:20,096 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-11 21:03:20,303 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-11 21:03:20,303 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-11 21:03:20,304 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1296 transitions. [2018-04-11 21:03:20,305 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1296 transitions. Word has length 506 [2018-04-11 21:03:20,305 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:03:20,305 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1296 transitions. [2018-04-11 21:03:20,305 INFO L460 AbstractCegarLoop]: Interpolant automaton has 90 states. [2018-04-11 21:03:20,305 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1296 transitions. [2018-04-11 21:03:20,307 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 514 [2018-04-11 21:03:20,307 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:03:20,308 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 19, 19, 18, 18, 18, 18, 18, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:03:20,308 INFO L408 AbstractCegarLoop]: === Iteration 30 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:03:20,308 INFO L82 PathProgramCache]: Analyzing trace with hash 2074895451, now seen corresponding path program 22 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 31 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 31 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:03:20,316 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:03:20,380 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:03:20,388 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:03:21,424 INFO L134 CoverageAnalysis]: Checked inductivity of 6798 backedges. 4112 proven. 1125 refuted. 0 times theorem prover too weak. 1561 trivial. 0 not checked. [2018-04-11 21:03:21,425 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:03:22,766 INFO L134 CoverageAnalysis]: Checked inductivity of 6798 backedges. 3176 proven. 1125 refuted. 0 times theorem prover too weak. 2497 trivial. 0 not checked. [2018-04-11 21:03:22,798 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:03:22,799 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [58, 58] total 95 [2018-04-11 21:03:22,799 INFO L442 AbstractCegarLoop]: Interpolant automaton has 95 states [2018-04-11 21:03:22,800 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 95 interpolants. [2018-04-11 21:03:22,800 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1404, Invalid=7526, Unknown=0, NotChecked=0, Total=8930 [2018-04-11 21:03:22,800 INFO L87 Difference]: Start difference. First operand 1157 states and 1296 transitions. Second operand 95 states. [2018-04-11 21:03:24,314 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:03:24,314 INFO L93 Difference]: Finished difference Result 1417 states and 1586 transitions. [2018-04-11 21:03:24,315 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 76 states. [2018-04-11 21:03:24,315 INFO L78 Accepts]: Start accepts. Automaton has 95 states. Word has length 513 [2018-04-11 21:03:24,315 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:03:24,318 INFO L225 Difference]: With dead ends: 1417 [2018-04-11 21:03:24,318 INFO L226 Difference]: Without dead ends: 1157 [2018-04-11 21:03:24,321 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1061 GetRequests, 913 SyntacticMatches, 19 SemanticMatches, 129 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4442 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=3546, Invalid=13484, Unknown=0, NotChecked=0, Total=17030 [2018-04-11 21:03:24,322 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-11 21:03:24,568 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-11 21:03:24,569 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-11 21:03:24,571 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1295 transitions. [2018-04-11 21:03:24,571 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1295 transitions. Word has length 513 [2018-04-11 21:03:24,572 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:03:24,572 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1295 transitions. [2018-04-11 21:03:24,572 INFO L460 AbstractCegarLoop]: Interpolant automaton has 95 states. [2018-04-11 21:03:24,572 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1295 transitions. [2018-04-11 21:03:24,576 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 521 [2018-04-11 21:03:24,576 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:03:24,576 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 20, 20, 19, 19, 19, 19, 19, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:03:24,576 INFO L408 AbstractCegarLoop]: === Iteration 31 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:03:24,577 INFO L82 PathProgramCache]: Analyzing trace with hash 1462558047, now seen corresponding path program 23 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 32 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 32 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:03:24,585 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:03:24,671 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:03:24,680 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:03:26,238 INFO L134 CoverageAnalysis]: Checked inductivity of 6927 backedges. 4185 proven. 1254 refuted. 0 times theorem prover too weak. 1488 trivial. 0 not checked. [2018-04-11 21:03:26,238 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:03:27,549 INFO L134 CoverageAnalysis]: Checked inductivity of 6927 backedges. 3273 proven. 1254 refuted. 0 times theorem prover too weak. 2400 trivial. 0 not checked. [2018-04-11 21:03:27,570 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:03:27,570 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [61, 61] total 100 [2018-04-11 21:03:27,571 INFO L442 AbstractCegarLoop]: Interpolant automaton has 100 states [2018-04-11 21:03:27,571 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 100 interpolants. [2018-04-11 21:03:27,571 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1548, Invalid=8352, Unknown=0, NotChecked=0, Total=9900 [2018-04-11 21:03:27,572 INFO L87 Difference]: Start difference. First operand 1157 states and 1295 transitions. Second operand 100 states. [2018-04-11 21:03:29,271 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:03:29,271 INFO L93 Difference]: Finished difference Result 1417 states and 1585 transitions. [2018-04-11 21:03:29,271 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 80 states. [2018-04-11 21:03:29,272 INFO L78 Accepts]: Start accepts. Automaton has 100 states. Word has length 520 [2018-04-11 21:03:29,272 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:03:29,274 INFO L225 Difference]: With dead ends: 1417 [2018-04-11 21:03:29,274 INFO L226 Difference]: Without dead ends: 1157 [2018-04-11 21:03:29,275 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1077 GetRequests, 921 SyntacticMatches, 20 SemanticMatches, 136 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4945 ImplicationChecksByTransitivity, 3.2s TimeCoverageRelationStatistics Valid=3923, Invalid=14983, Unknown=0, NotChecked=0, Total=18906 [2018-04-11 21:03:29,276 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-11 21:03:29,422 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-11 21:03:29,423 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-11 21:03:29,424 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1294 transitions. [2018-04-11 21:03:29,424 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1294 transitions. Word has length 520 [2018-04-11 21:03:29,424 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:03:29,424 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1294 transitions. [2018-04-11 21:03:29,424 INFO L460 AbstractCegarLoop]: Interpolant automaton has 100 states. [2018-04-11 21:03:29,425 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1294 transitions. [2018-04-11 21:03:29,427 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 528 [2018-04-11 21:03:29,427 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:03:29,428 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 21, 21, 20, 20, 20, 20, 20, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:03:29,428 INFO L408 AbstractCegarLoop]: === Iteration 32 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:03:29,428 INFO L82 PathProgramCache]: Analyzing trace with hash -1721305125, now seen corresponding path program 24 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 33 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 33 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:03:29,435 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:03:29,500 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:03:29,506 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:03:30,647 INFO L134 CoverageAnalysis]: Checked inductivity of 7063 backedges. 4242 proven. 1390 refuted. 0 times theorem prover too weak. 1431 trivial. 0 not checked. [2018-04-11 21:03:30,648 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:03:32,085 INFO L134 CoverageAnalysis]: Checked inductivity of 7063 backedges. 3362 proven. 1390 refuted. 0 times theorem prover too weak. 2311 trivial. 0 not checked. [2018-04-11 21:03:32,105 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:03:32,166 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [64, 64] total 105 [2018-04-11 21:03:32,167 INFO L442 AbstractCegarLoop]: Interpolant automaton has 105 states [2018-04-11 21:03:32,167 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 105 interpolants. [2018-04-11 21:03:32,168 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1699, Invalid=9221, Unknown=0, NotChecked=0, Total=10920 [2018-04-11 21:03:32,168 INFO L87 Difference]: Start difference. First operand 1157 states and 1294 transitions. Second operand 105 states. [2018-04-11 21:03:33,810 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:03:33,811 INFO L93 Difference]: Finished difference Result 1417 states and 1584 transitions. [2018-04-11 21:03:33,811 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 84 states. [2018-04-11 21:03:33,811 INFO L78 Accepts]: Start accepts. Automaton has 105 states. Word has length 527 [2018-04-11 21:03:33,811 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:03:33,813 INFO L225 Difference]: With dead ends: 1417 [2018-04-11 21:03:33,813 INFO L226 Difference]: Without dead ends: 1157 [2018-04-11 21:03:33,816 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1093 GetRequests, 929 SyntacticMatches, 21 SemanticMatches, 143 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5475 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=4319, Invalid=16561, Unknown=0, NotChecked=0, Total=20880 [2018-04-11 21:03:33,816 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-11 21:03:33,960 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-11 21:03:33,960 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-11 21:03:33,961 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1293 transitions. [2018-04-11 21:03:33,961 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1293 transitions. Word has length 527 [2018-04-11 21:03:33,962 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:03:33,962 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1293 transitions. [2018-04-11 21:03:33,962 INFO L460 AbstractCegarLoop]: Interpolant automaton has 105 states. [2018-04-11 21:03:33,962 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1293 transitions. [2018-04-11 21:03:33,964 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 535 [2018-04-11 21:03:33,964 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:03:33,964 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 22, 22, 21, 21, 21, 21, 21, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:03:33,964 INFO L408 AbstractCegarLoop]: === Iteration 33 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:03:33,965 INFO L82 PathProgramCache]: Analyzing trace with hash 1905088991, now seen corresponding path program 25 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 34 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 34 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:03:33,970 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:03:34,023 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:03:34,028 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:03:35,152 INFO L134 CoverageAnalysis]: Checked inductivity of 7206 backedges. 4283 proven. 1533 refuted. 0 times theorem prover too weak. 1390 trivial. 0 not checked. [2018-04-11 21:03:35,153 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:03:36,756 INFO L134 CoverageAnalysis]: Checked inductivity of 7206 backedges. 3443 proven. 1533 refuted. 0 times theorem prover too weak. 2230 trivial. 0 not checked. [2018-04-11 21:03:36,776 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:03:36,776 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [67, 67] total 110 [2018-04-11 21:03:36,777 INFO L442 AbstractCegarLoop]: Interpolant automaton has 110 states [2018-04-11 21:03:36,777 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 110 interpolants. [2018-04-11 21:03:36,777 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1857, Invalid=10133, Unknown=0, NotChecked=0, Total=11990 [2018-04-11 21:03:36,777 INFO L87 Difference]: Start difference. First operand 1157 states and 1293 transitions. Second operand 110 states. [2018-04-11 21:03:38,508 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:03:38,508 INFO L93 Difference]: Finished difference Result 1417 states and 1583 transitions. [2018-04-11 21:03:38,508 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 88 states. [2018-04-11 21:03:38,508 INFO L78 Accepts]: Start accepts. Automaton has 110 states. Word has length 534 [2018-04-11 21:03:38,509 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:03:38,510 INFO L225 Difference]: With dead ends: 1417 [2018-04-11 21:03:38,510 INFO L226 Difference]: Without dead ends: 1157 [2018-04-11 21:03:38,512 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1109 GetRequests, 937 SyntacticMatches, 22 SemanticMatches, 150 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6032 ImplicationChecksByTransitivity, 3.2s TimeCoverageRelationStatistics Valid=4734, Invalid=18218, Unknown=0, NotChecked=0, Total=22952 [2018-04-11 21:03:38,512 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-11 21:03:38,648 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-11 21:03:38,648 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-11 21:03:38,650 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1292 transitions. [2018-04-11 21:03:38,650 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1292 transitions. Word has length 534 [2018-04-11 21:03:38,650 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:03:38,650 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1292 transitions. [2018-04-11 21:03:38,650 INFO L460 AbstractCegarLoop]: Interpolant automaton has 110 states. [2018-04-11 21:03:38,651 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1292 transitions. [2018-04-11 21:03:38,654 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 542 [2018-04-11 21:03:38,654 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:03:38,655 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 23, 23, 22, 22, 22, 22, 22, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:03:38,655 INFO L408 AbstractCegarLoop]: === Iteration 34 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:03:38,655 INFO L82 PathProgramCache]: Analyzing trace with hash 358181723, now seen corresponding path program 26 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 35 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 35 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:03:38,680 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:03:38,733 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:03:38,738 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:03:39,930 INFO L134 CoverageAnalysis]: Checked inductivity of 7356 backedges. 4308 proven. 1683 refuted. 0 times theorem prover too weak. 1365 trivial. 0 not checked. [2018-04-11 21:03:39,930 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:03:41,596 INFO L134 CoverageAnalysis]: Checked inductivity of 7356 backedges. 3516 proven. 1683 refuted. 0 times theorem prover too weak. 2157 trivial. 0 not checked. [2018-04-11 21:03:41,616 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:03:41,616 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [70, 70] total 115 [2018-04-11 21:03:41,617 INFO L442 AbstractCegarLoop]: Interpolant automaton has 115 states [2018-04-11 21:03:41,617 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 115 interpolants. [2018-04-11 21:03:41,618 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2022, Invalid=11088, Unknown=0, NotChecked=0, Total=13110 [2018-04-11 21:03:41,618 INFO L87 Difference]: Start difference. First operand 1157 states and 1292 transitions. Second operand 115 states. [2018-04-11 21:03:43,560 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:03:43,560 INFO L93 Difference]: Finished difference Result 1417 states and 1582 transitions. [2018-04-11 21:03:43,560 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 92 states. [2018-04-11 21:03:43,560 INFO L78 Accepts]: Start accepts. Automaton has 115 states. Word has length 541 [2018-04-11 21:03:43,561 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:03:43,561 INFO L225 Difference]: With dead ends: 1417 [2018-04-11 21:03:43,561 INFO L226 Difference]: Without dead ends: 1157 [2018-04-11 21:03:43,563 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1125 GetRequests, 945 SyntacticMatches, 23 SemanticMatches, 157 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6616 ImplicationChecksByTransitivity, 3.4s TimeCoverageRelationStatistics Valid=5168, Invalid=19954, Unknown=0, NotChecked=0, Total=25122 [2018-04-11 21:03:43,563 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-11 21:03:43,698 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-11 21:03:43,698 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-11 21:03:43,699 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1291 transitions. [2018-04-11 21:03:43,699 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1291 transitions. Word has length 541 [2018-04-11 21:03:43,700 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:03:43,700 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1291 transitions. [2018-04-11 21:03:43,700 INFO L460 AbstractCegarLoop]: Interpolant automaton has 115 states. [2018-04-11 21:03:43,700 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1291 transitions. [2018-04-11 21:03:43,703 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 549 [2018-04-11 21:03:43,703 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:03:43,703 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 24, 24, 23, 23, 23, 23, 23, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:03:43,703 INFO L408 AbstractCegarLoop]: === Iteration 35 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:03:43,703 INFO L82 PathProgramCache]: Analyzing trace with hash 421131871, now seen corresponding path program 27 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 36 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 36 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:03:43,709 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:03:43,762 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:03:43,768 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:03:45,071 INFO L134 CoverageAnalysis]: Checked inductivity of 7513 backedges. 4317 proven. 1840 refuted. 0 times theorem prover too weak. 1356 trivial. 0 not checked. [2018-04-11 21:03:45,071 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:03:46,868 INFO L134 CoverageAnalysis]: Checked inductivity of 7513 backedges. 3581 proven. 1840 refuted. 0 times theorem prover too weak. 2092 trivial. 0 not checked. [2018-04-11 21:03:46,888 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:03:46,889 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [73, 73] total 120 [2018-04-11 21:03:46,889 INFO L442 AbstractCegarLoop]: Interpolant automaton has 120 states [2018-04-11 21:03:46,890 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 120 interpolants. [2018-04-11 21:03:46,890 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2194, Invalid=12086, Unknown=0, NotChecked=0, Total=14280 [2018-04-11 21:03:46,890 INFO L87 Difference]: Start difference. First operand 1157 states and 1291 transitions. Second operand 120 states. [2018-04-11 21:03:49,233 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:03:49,234 INFO L93 Difference]: Finished difference Result 1417 states and 1581 transitions. [2018-04-11 21:03:49,234 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 96 states. [2018-04-11 21:03:49,234 INFO L78 Accepts]: Start accepts. Automaton has 120 states. Word has length 548 [2018-04-11 21:03:49,234 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:03:49,235 INFO L225 Difference]: With dead ends: 1417 [2018-04-11 21:03:49,235 INFO L226 Difference]: Without dead ends: 1157 [2018-04-11 21:03:49,237 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1141 GetRequests, 953 SyntacticMatches, 24 SemanticMatches, 164 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7227 ImplicationChecksByTransitivity, 3.7s TimeCoverageRelationStatistics Valid=5621, Invalid=21769, Unknown=0, NotChecked=0, Total=27390 [2018-04-11 21:03:49,238 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-11 21:03:49,372 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-11 21:03:49,372 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-11 21:03:49,373 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1290 transitions. [2018-04-11 21:03:49,373 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1290 transitions. Word has length 548 [2018-04-11 21:03:49,374 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:03:49,374 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1290 transitions. [2018-04-11 21:03:49,374 INFO L460 AbstractCegarLoop]: Interpolant automaton has 120 states. [2018-04-11 21:03:49,374 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1290 transitions. [2018-04-11 21:03:49,376 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 556 [2018-04-11 21:03:49,376 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:03:49,377 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 25, 25, 24, 24, 24, 24, 24, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:03:49,377 INFO L408 AbstractCegarLoop]: === Iteration 36 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:03:49,377 INFO L82 PathProgramCache]: Analyzing trace with hash 1077657307, now seen corresponding path program 28 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 37 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 37 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:03:49,393 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:03:49,446 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:03:49,452 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:03:50,805 INFO L134 CoverageAnalysis]: Checked inductivity of 7677 backedges. 4310 proven. 2004 refuted. 0 times theorem prover too weak. 1363 trivial. 0 not checked. [2018-04-11 21:03:50,805 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:03:52,709 INFO L134 CoverageAnalysis]: Checked inductivity of 7677 backedges. 3638 proven. 2004 refuted. 0 times theorem prover too weak. 2035 trivial. 0 not checked. [2018-04-11 21:03:52,729 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:03:52,729 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [76, 76] total 125 [2018-04-11 21:03:52,730 INFO L442 AbstractCegarLoop]: Interpolant automaton has 125 states [2018-04-11 21:03:52,730 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 125 interpolants. [2018-04-11 21:03:52,731 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2373, Invalid=13127, Unknown=0, NotChecked=0, Total=15500 [2018-04-11 21:03:52,731 INFO L87 Difference]: Start difference. First operand 1157 states and 1290 transitions. Second operand 125 states. [2018-04-11 21:03:54,908 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:03:54,908 INFO L93 Difference]: Finished difference Result 1417 states and 1580 transitions. [2018-04-11 21:03:54,908 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 100 states. [2018-04-11 21:03:54,909 INFO L78 Accepts]: Start accepts. Automaton has 125 states. Word has length 555 [2018-04-11 21:03:54,909 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:03:54,910 INFO L225 Difference]: With dead ends: 1417 [2018-04-11 21:03:54,911 INFO L226 Difference]: Without dead ends: 1157 [2018-04-11 21:03:54,914 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1157 GetRequests, 961 SyntacticMatches, 25 SemanticMatches, 171 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7865 ImplicationChecksByTransitivity, 4.0s TimeCoverageRelationStatistics Valid=6093, Invalid=23663, Unknown=0, NotChecked=0, Total=29756 [2018-04-11 21:03:54,914 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-11 21:03:55,094 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-11 21:03:55,095 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-11 21:03:55,096 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1289 transitions. [2018-04-11 21:03:55,096 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1289 transitions. Word has length 555 [2018-04-11 21:03:55,096 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:03:55,096 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1289 transitions. [2018-04-11 21:03:55,096 INFO L460 AbstractCegarLoop]: Interpolant automaton has 125 states. [2018-04-11 21:03:55,096 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1289 transitions. [2018-04-11 21:03:55,099 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 563 [2018-04-11 21:03:55,099 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:03:55,099 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 26, 26, 25, 25, 25, 25, 25, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:03:55,099 INFO L408 AbstractCegarLoop]: === Iteration 37 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:03:55,099 INFO L82 PathProgramCache]: Analyzing trace with hash 1041937119, now seen corresponding path program 29 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 38 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 38 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:03:55,107 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:03:55,173 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:03:55,178 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:03:56,733 INFO L134 CoverageAnalysis]: Checked inductivity of 7848 backedges. 4287 proven. 2175 refuted. 0 times theorem prover too weak. 1386 trivial. 0 not checked. [2018-04-11 21:03:56,733 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:03:58,961 INFO L134 CoverageAnalysis]: Checked inductivity of 7848 backedges. 3687 proven. 2175 refuted. 0 times theorem prover too weak. 1986 trivial. 0 not checked. [2018-04-11 21:03:58,983 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:03:58,983 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [79, 79] total 130 [2018-04-11 21:03:58,984 INFO L442 AbstractCegarLoop]: Interpolant automaton has 130 states [2018-04-11 21:03:58,985 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 130 interpolants. [2018-04-11 21:03:58,986 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2559, Invalid=14211, Unknown=0, NotChecked=0, Total=16770 [2018-04-11 21:03:58,986 INFO L87 Difference]: Start difference. First operand 1157 states and 1289 transitions. Second operand 130 states. [2018-04-11 21:04:01,460 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:04:01,460 INFO L93 Difference]: Finished difference Result 1417 states and 1579 transitions. [2018-04-11 21:04:01,460 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 104 states. [2018-04-11 21:04:01,460 INFO L78 Accepts]: Start accepts. Automaton has 130 states. Word has length 562 [2018-04-11 21:04:01,460 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:04:01,461 INFO L225 Difference]: With dead ends: 1417 [2018-04-11 21:04:01,461 INFO L226 Difference]: Without dead ends: 1157 [2018-04-11 21:04:01,463 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1173 GetRequests, 969 SyntacticMatches, 26 SemanticMatches, 178 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8530 ImplicationChecksByTransitivity, 4.6s TimeCoverageRelationStatistics Valid=6584, Invalid=25636, Unknown=0, NotChecked=0, Total=32220 [2018-04-11 21:04:01,463 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-11 21:04:01,605 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-11 21:04:01,606 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-11 21:04:01,606 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1288 transitions. [2018-04-11 21:04:01,607 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1288 transitions. Word has length 562 [2018-04-11 21:04:01,607 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:04:01,607 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1288 transitions. [2018-04-11 21:04:01,607 INFO L460 AbstractCegarLoop]: Interpolant automaton has 130 states. [2018-04-11 21:04:01,607 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1288 transitions. [2018-04-11 21:04:01,609 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 570 [2018-04-11 21:04:01,610 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:04:01,610 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 27, 27, 26, 26, 26, 26, 26, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:04:01,610 INFO L408 AbstractCegarLoop]: === Iteration 38 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:04:01,610 INFO L82 PathProgramCache]: Analyzing trace with hash -926551461, now seen corresponding path program 30 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 39 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 39 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:04:01,616 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:04:01,673 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:04:01,678 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:04:03,279 INFO L134 CoverageAnalysis]: Checked inductivity of 8026 backedges. 4248 proven. 2353 refuted. 0 times theorem prover too weak. 1425 trivial. 0 not checked. [2018-04-11 21:04:03,279 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:04:05,518 INFO L134 CoverageAnalysis]: Checked inductivity of 8026 backedges. 3728 proven. 2353 refuted. 0 times theorem prover too weak. 1945 trivial. 0 not checked. [2018-04-11 21:04:05,538 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:04:05,567 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [82, 82] total 135 [2018-04-11 21:04:05,568 INFO L442 AbstractCegarLoop]: Interpolant automaton has 135 states [2018-04-11 21:04:05,568 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 135 interpolants. [2018-04-11 21:04:05,569 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2752, Invalid=15338, Unknown=0, NotChecked=0, Total=18090 [2018-04-11 21:04:05,569 INFO L87 Difference]: Start difference. First operand 1157 states and 1288 transitions. Second operand 135 states. [2018-04-11 21:04:08,324 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:04:08,324 INFO L93 Difference]: Finished difference Result 1417 states and 1578 transitions. [2018-04-11 21:04:08,324 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 108 states. [2018-04-11 21:04:08,324 INFO L78 Accepts]: Start accepts. Automaton has 135 states. Word has length 569 [2018-04-11 21:04:08,325 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:04:08,325 INFO L225 Difference]: With dead ends: 1417 [2018-04-11 21:04:08,326 INFO L226 Difference]: Without dead ends: 1157 [2018-04-11 21:04:08,327 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1189 GetRequests, 977 SyntacticMatches, 27 SemanticMatches, 185 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9222 ImplicationChecksByTransitivity, 4.7s TimeCoverageRelationStatistics Valid=7094, Invalid=27688, Unknown=0, NotChecked=0, Total=34782 [2018-04-11 21:04:08,328 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-11 21:04:08,462 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-11 21:04:08,462 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-11 21:04:08,463 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1287 transitions. [2018-04-11 21:04:08,463 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1287 transitions. Word has length 569 [2018-04-11 21:04:08,464 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:04:08,464 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1287 transitions. [2018-04-11 21:04:08,464 INFO L460 AbstractCegarLoop]: Interpolant automaton has 135 states. [2018-04-11 21:04:08,464 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1287 transitions. [2018-04-11 21:04:08,466 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 577 [2018-04-11 21:04:08,466 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:04:08,466 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 28, 28, 27, 27, 27, 27, 27, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:04:08,467 INFO L408 AbstractCegarLoop]: === Iteration 39 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:04:08,467 INFO L82 PathProgramCache]: Analyzing trace with hash -1294495905, now seen corresponding path program 31 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 40 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 40 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:04:08,473 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:04:08,530 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:04:08,536 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:04:10,225 INFO L134 CoverageAnalysis]: Checked inductivity of 8211 backedges. 4193 proven. 2538 refuted. 0 times theorem prover too weak. 1480 trivial. 0 not checked. [2018-04-11 21:04:10,225 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:04:12,641 INFO L134 CoverageAnalysis]: Checked inductivity of 8211 backedges. 3761 proven. 2538 refuted. 0 times theorem prover too weak. 1912 trivial. 0 not checked. [2018-04-11 21:04:12,660 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:04:12,661 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [85, 85] total 140 [2018-04-11 21:04:12,661 INFO L442 AbstractCegarLoop]: Interpolant automaton has 140 states [2018-04-11 21:04:12,662 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 140 interpolants. [2018-04-11 21:04:12,662 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2952, Invalid=16508, Unknown=0, NotChecked=0, Total=19460 [2018-04-11 21:04:12,662 INFO L87 Difference]: Start difference. First operand 1157 states and 1287 transitions. Second operand 140 states. [2018-04-11 21:04:15,246 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:04:15,247 INFO L93 Difference]: Finished difference Result 1417 states and 1577 transitions. [2018-04-11 21:04:15,247 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 112 states. [2018-04-11 21:04:15,247 INFO L78 Accepts]: Start accepts. Automaton has 140 states. Word has length 576 [2018-04-11 21:04:15,247 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:04:15,248 INFO L225 Difference]: With dead ends: 1417 [2018-04-11 21:04:15,248 INFO L226 Difference]: Without dead ends: 1157 [2018-04-11 21:04:15,252 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1205 GetRequests, 985 SyntacticMatches, 28 SemanticMatches, 192 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9941 ImplicationChecksByTransitivity, 5.1s TimeCoverageRelationStatistics Valid=7623, Invalid=29819, Unknown=0, NotChecked=0, Total=37442 [2018-04-11 21:04:15,253 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-11 21:04:15,419 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-11 21:04:15,419 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-11 21:04:15,420 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1286 transitions. [2018-04-11 21:04:15,420 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1286 transitions. Word has length 576 [2018-04-11 21:04:15,420 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:04:15,420 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1286 transitions. [2018-04-11 21:04:15,420 INFO L460 AbstractCegarLoop]: Interpolant automaton has 140 states. [2018-04-11 21:04:15,421 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1286 transitions. [2018-04-11 21:04:15,423 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 584 [2018-04-11 21:04:15,423 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:04:15,423 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 29, 29, 28, 28, 28, 28, 28, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:04:15,424 INFO L408 AbstractCegarLoop]: === Iteration 40 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:04:15,424 INFO L82 PathProgramCache]: Analyzing trace with hash 1001391579, now seen corresponding path program 32 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 41 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 41 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:04:15,429 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:04:15,496 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:04:15,504 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:04:17,345 INFO L134 CoverageAnalysis]: Checked inductivity of 8403 backedges. 4122 proven. 2730 refuted. 0 times theorem prover too weak. 1551 trivial. 0 not checked. [2018-04-11 21:04:17,346 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:04:19,886 INFO L134 CoverageAnalysis]: Checked inductivity of 8403 backedges. 3786 proven. 2730 refuted. 0 times theorem prover too weak. 1887 trivial. 0 not checked. [2018-04-11 21:04:19,906 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:04:19,906 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [88, 88] total 145 [2018-04-11 21:04:19,906 INFO L442 AbstractCegarLoop]: Interpolant automaton has 145 states [2018-04-11 21:04:19,907 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 145 interpolants. [2018-04-11 21:04:19,908 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3159, Invalid=17721, Unknown=0, NotChecked=0, Total=20880 [2018-04-11 21:04:19,908 INFO L87 Difference]: Start difference. First operand 1157 states and 1286 transitions. Second operand 145 states. [2018-04-11 21:04:23,055 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:04:23,056 INFO L93 Difference]: Finished difference Result 1417 states and 1576 transitions. [2018-04-11 21:04:23,056 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 116 states. [2018-04-11 21:04:23,056 INFO L78 Accepts]: Start accepts. Automaton has 145 states. Word has length 583 [2018-04-11 21:04:23,056 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:04:23,057 INFO L225 Difference]: With dead ends: 1417 [2018-04-11 21:04:23,057 INFO L226 Difference]: Without dead ends: 1157 [2018-04-11 21:04:23,059 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1221 GetRequests, 993 SyntacticMatches, 29 SemanticMatches, 199 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10687 ImplicationChecksByTransitivity, 5.5s TimeCoverageRelationStatistics Valid=8171, Invalid=32029, Unknown=0, NotChecked=0, Total=40200 [2018-04-11 21:04:23,060 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-11 21:04:23,195 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-11 21:04:23,195 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-11 21:04:23,196 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1285 transitions. [2018-04-11 21:04:23,196 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1285 transitions. Word has length 583 [2018-04-11 21:04:23,197 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:04:23,197 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1285 transitions. [2018-04-11 21:04:23,197 INFO L460 AbstractCegarLoop]: Interpolant automaton has 145 states. [2018-04-11 21:04:23,197 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1285 transitions. [2018-04-11 21:04:23,199 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 591 [2018-04-11 21:04:23,199 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:04:23,200 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 30, 30, 29, 29, 29, 29, 29, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:04:23,200 INFO L408 AbstractCegarLoop]: === Iteration 41 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:04:23,200 INFO L82 PathProgramCache]: Analyzing trace with hash -1416066081, now seen corresponding path program 33 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 42 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 42 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:04:23,206 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:04:23,263 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:04:23,269 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:04:25,201 INFO L134 CoverageAnalysis]: Checked inductivity of 8602 backedges. 4035 proven. 2929 refuted. 0 times theorem prover too weak. 1638 trivial. 0 not checked. [2018-04-11 21:04:25,202 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:04:27,926 INFO L134 CoverageAnalysis]: Checked inductivity of 8602 backedges. 3803 proven. 2929 refuted. 0 times theorem prover too weak. 1870 trivial. 0 not checked. [2018-04-11 21:04:27,946 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:04:27,946 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [91, 91] total 150 [2018-04-11 21:04:27,947 INFO L442 AbstractCegarLoop]: Interpolant automaton has 150 states [2018-04-11 21:04:27,948 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 150 interpolants. [2018-04-11 21:04:27,948 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3373, Invalid=18977, Unknown=0, NotChecked=0, Total=22350 [2018-04-11 21:04:27,948 INFO L87 Difference]: Start difference. First operand 1157 states and 1285 transitions. Second operand 150 states. [2018-04-11 21:04:30,753 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:04:30,753 INFO L93 Difference]: Finished difference Result 1417 states and 1575 transitions. [2018-04-11 21:04:30,790 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 120 states. [2018-04-11 21:04:30,790 INFO L78 Accepts]: Start accepts. Automaton has 150 states. Word has length 590 [2018-04-11 21:04:30,790 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:04:30,791 INFO L225 Difference]: With dead ends: 1417 [2018-04-11 21:04:30,791 INFO L226 Difference]: Without dead ends: 1157 [2018-04-11 21:04:30,793 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1237 GetRequests, 1001 SyntacticMatches, 30 SemanticMatches, 206 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11460 ImplicationChecksByTransitivity, 5.8s TimeCoverageRelationStatistics Valid=8738, Invalid=34318, Unknown=0, NotChecked=0, Total=43056 [2018-04-11 21:04:30,794 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-11 21:04:30,933 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-11 21:04:30,933 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-11 21:04:30,934 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1284 transitions. [2018-04-11 21:04:30,934 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1284 transitions. Word has length 590 [2018-04-11 21:04:30,934 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:04:30,934 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1284 transitions. [2018-04-11 21:04:30,934 INFO L460 AbstractCegarLoop]: Interpolant automaton has 150 states. [2018-04-11 21:04:30,934 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1284 transitions. [2018-04-11 21:04:30,937 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 598 [2018-04-11 21:04:30,937 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:04:30,937 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 30, 30, 30, 30, 30, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:04:30,937 INFO L408 AbstractCegarLoop]: === Iteration 42 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:04:30,937 INFO L82 PathProgramCache]: Analyzing trace with hash -2085488293, now seen corresponding path program 34 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 43 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 43 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:04:30,954 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:04:31,012 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:04:31,018 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:04:33,052 INFO L134 CoverageAnalysis]: Checked inductivity of 8808 backedges. 3932 proven. 3135 refuted. 0 times theorem prover too weak. 1741 trivial. 0 not checked. [2018-04-11 21:04:33,052 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:04:35,935 INFO L134 CoverageAnalysis]: Checked inductivity of 8808 backedges. 3812 proven. 3135 refuted. 0 times theorem prover too weak. 1861 trivial. 0 not checked. [2018-04-11 21:04:35,955 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:04:35,968 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [94, 94] total 155 [2018-04-11 21:04:35,969 INFO L442 AbstractCegarLoop]: Interpolant automaton has 155 states [2018-04-11 21:04:35,969 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 155 interpolants. [2018-04-11 21:04:35,970 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3594, Invalid=20276, Unknown=0, NotChecked=0, Total=23870 [2018-04-11 21:04:35,970 INFO L87 Difference]: Start difference. First operand 1157 states and 1284 transitions. Second operand 155 states. [2018-04-11 21:04:39,297 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:04:39,297 INFO L93 Difference]: Finished difference Result 1417 states and 1574 transitions. [2018-04-11 21:04:39,297 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 124 states. [2018-04-11 21:04:39,297 INFO L78 Accepts]: Start accepts. Automaton has 155 states. Word has length 597 [2018-04-11 21:04:39,298 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:04:39,298 INFO L225 Difference]: With dead ends: 1417 [2018-04-11 21:04:39,298 INFO L226 Difference]: Without dead ends: 1157 [2018-04-11 21:04:39,300 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1253 GetRequests, 1009 SyntacticMatches, 31 SemanticMatches, 213 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12260 ImplicationChecksByTransitivity, 6.2s TimeCoverageRelationStatistics Valid=9324, Invalid=36686, Unknown=0, NotChecked=0, Total=46010 [2018-04-11 21:04:39,301 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-11 21:04:39,435 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-11 21:04:39,435 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-11 21:04:39,436 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1283 transitions. [2018-04-11 21:04:39,437 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1283 transitions. Word has length 597 [2018-04-11 21:04:39,437 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:04:39,437 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1283 transitions. [2018-04-11 21:04:39,437 INFO L460 AbstractCegarLoop]: Interpolant automaton has 155 states. [2018-04-11 21:04:39,437 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1283 transitions. [2018-04-11 21:04:39,441 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 605 [2018-04-11 21:04:39,441 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:04:39,441 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 32, 32, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:04:39,442 INFO L408 AbstractCegarLoop]: === Iteration 43 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:04:39,442 INFO L82 PathProgramCache]: Analyzing trace with hash 1051043935, now seen corresponding path program 35 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 44 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 44 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:04:39,447 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:04:39,507 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:04:39,513 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:04:41,686 INFO L134 CoverageAnalysis]: Checked inductivity of 9021 backedges. 3813 proven. 3348 refuted. 0 times theorem prover too weak. 1860 trivial. 0 not checked. [2018-04-11 21:04:41,686 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:04:44,733 INFO L134 CoverageAnalysis]: Checked inductivity of 9021 backedges. 3813 proven. 3348 refuted. 0 times theorem prover too weak. 1860 trivial. 0 not checked. [2018-04-11 21:04:44,753 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:04:44,753 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [97, 97] total 160 [2018-04-11 21:04:44,754 INFO L442 AbstractCegarLoop]: Interpolant automaton has 160 states [2018-04-11 21:04:44,755 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 160 interpolants. [2018-04-11 21:04:44,756 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3822, Invalid=21618, Unknown=0, NotChecked=0, Total=25440 [2018-04-11 21:04:44,756 INFO L87 Difference]: Start difference. First operand 1157 states and 1283 transitions. Second operand 160 states. [2018-04-11 21:04:48,178 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:04:48,178 INFO L93 Difference]: Finished difference Result 1423 states and 1580 transitions. [2018-04-11 21:04:48,178 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 128 states. [2018-04-11 21:04:48,178 INFO L78 Accepts]: Start accepts. Automaton has 160 states. Word has length 604 [2018-04-11 21:04:48,179 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:04:48,180 INFO L225 Difference]: With dead ends: 1423 [2018-04-11 21:04:48,180 INFO L226 Difference]: Without dead ends: 1157 [2018-04-11 21:04:48,182 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1269 GetRequests, 1017 SyntacticMatches, 32 SemanticMatches, 220 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13087 ImplicationChecksByTransitivity, 6.6s TimeCoverageRelationStatistics Valid=9929, Invalid=39133, Unknown=0, NotChecked=0, Total=49062 [2018-04-11 21:04:48,183 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-11 21:04:48,317 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-11 21:04:48,317 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-11 21:04:48,318 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1282 transitions. [2018-04-11 21:04:48,318 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1282 transitions. Word has length 604 [2018-04-11 21:04:48,319 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:04:48,319 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1282 transitions. [2018-04-11 21:04:48,319 INFO L460 AbstractCegarLoop]: Interpolant automaton has 160 states. [2018-04-11 21:04:48,319 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1282 transitions. [2018-04-11 21:04:48,321 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 612 [2018-04-11 21:04:48,322 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:04:48,322 INFO L355 BasicCegarLoop]: trace histogram [33, 33, 32, 32, 32, 32, 32, 32, 32, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:04:48,322 INFO L408 AbstractCegarLoop]: === Iteration 44 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:04:48,322 INFO L82 PathProgramCache]: Analyzing trace with hash 1770245339, now seen corresponding path program 36 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 45 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 45 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:04:48,327 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:04:48,388 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:04:48,394 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:04:49,708 INFO L134 CoverageAnalysis]: Checked inductivity of 9241 backedges. 0 proven. 3813 refuted. 0 times theorem prover too weak. 5428 trivial. 0 not checked. [2018-04-11 21:04:49,708 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:04:53,375 INFO L134 CoverageAnalysis]: Checked inductivity of 9241 backedges. 0 proven. 3813 refuted. 0 times theorem prover too weak. 5428 trivial. 0 not checked. [2018-04-11 21:04:53,395 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:04:53,421 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [64, 64] total 127 [2018-04-11 21:04:53,422 INFO L442 AbstractCegarLoop]: Interpolant automaton has 128 states [2018-04-11 21:04:53,422 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 128 interpolants. [2018-04-11 21:04:53,423 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2238, Invalid=14018, Unknown=0, NotChecked=0, Total=16256 [2018-04-11 21:04:53,423 INFO L87 Difference]: Start difference. First operand 1157 states and 1282 transitions. Second operand 128 states. [2018-04-11 21:04:57,889 WARN L151 SmtUtils]: Spent 253ms on a formula simplification. DAG size of input: 252 DAG size of output 12 [2018-04-11 21:04:58,573 WARN L151 SmtUtils]: Spent 247ms on a formula simplification. DAG size of input: 247 DAG size of output 11 [2018-04-11 21:04:59,029 WARN L151 SmtUtils]: Spent 230ms on a formula simplification. DAG size of input: 244 DAG size of output 12 [2018-04-11 21:04:59,702 WARN L151 SmtUtils]: Spent 226ms on a formula simplification. DAG size of input: 239 DAG size of output 11 [2018-04-11 21:05:00,142 WARN L151 SmtUtils]: Spent 213ms on a formula simplification. DAG size of input: 236 DAG size of output 12 [2018-04-11 21:05:00,782 WARN L151 SmtUtils]: Spent 213ms on a formula simplification. DAG size of input: 231 DAG size of output 11 [2018-04-11 21:05:01,212 WARN L151 SmtUtils]: Spent 203ms on a formula simplification. DAG size of input: 228 DAG size of output 12 [2018-04-11 21:05:01,858 WARN L151 SmtUtils]: Spent 200ms on a formula simplification. DAG size of input: 223 DAG size of output 11 [2018-04-11 21:05:02,297 WARN L151 SmtUtils]: Spent 208ms on a formula simplification. DAG size of input: 220 DAG size of output 12 [2018-04-11 21:05:02,915 WARN L151 SmtUtils]: Spent 189ms on a formula simplification. DAG size of input: 215 DAG size of output 11 [2018-04-11 21:05:03,330 WARN L151 SmtUtils]: Spent 181ms on a formula simplification. DAG size of input: 212 DAG size of output 12 [2018-04-11 21:05:03,933 WARN L151 SmtUtils]: Spent 177ms on a formula simplification. DAG size of input: 207 DAG size of output 11 [2018-04-11 21:05:04,342 WARN L151 SmtUtils]: Spent 174ms on a formula simplification. DAG size of input: 204 DAG size of output 12 [2018-04-11 21:05:04,926 WARN L151 SmtUtils]: Spent 157ms on a formula simplification. DAG size of input: 199 DAG size of output 11 [2018-04-11 21:05:05,325 WARN L151 SmtUtils]: Spent 167ms on a formula simplification. DAG size of input: 196 DAG size of output 12 [2018-04-11 21:05:05,912 WARN L151 SmtUtils]: Spent 171ms on a formula simplification. DAG size of input: 191 DAG size of output 11 [2018-04-11 21:05:06,307 WARN L151 SmtUtils]: Spent 159ms on a formula simplification. DAG size of input: 188 DAG size of output 12 [2018-04-11 21:05:06,895 WARN L151 SmtUtils]: Spent 167ms on a formula simplification. DAG size of input: 183 DAG size of output 11 [2018-04-11 21:05:07,312 WARN L151 SmtUtils]: Spent 145ms on a formula simplification. DAG size of input: 180 DAG size of output 12 [2018-04-11 21:05:07,837 WARN L151 SmtUtils]: Spent 129ms on a formula simplification. DAG size of input: 175 DAG size of output 11 [2018-04-11 21:05:08,178 WARN L151 SmtUtils]: Spent 123ms on a formula simplification. DAG size of input: 172 DAG size of output 12 [2018-04-11 21:05:08,699 WARN L151 SmtUtils]: Spent 118ms on a formula simplification. DAG size of input: 167 DAG size of output 11 [2018-04-11 21:05:09,030 WARN L151 SmtUtils]: Spent 114ms on a formula simplification. DAG size of input: 164 DAG size of output 12 [2018-04-11 21:05:09,520 WARN L151 SmtUtils]: Spent 112ms on a formula simplification. DAG size of input: 159 DAG size of output 11 [2018-04-11 21:05:09,838 WARN L151 SmtUtils]: Spent 105ms on a formula simplification. DAG size of input: 156 DAG size of output 12 [2018-04-11 21:05:10,612 WARN L151 SmtUtils]: Spent 104ms on a formula simplification. DAG size of input: 148 DAG size of output 12 [2018-04-11 21:05:19,271 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-11 21:05:19,272 INFO L93 Difference]: Finished difference Result 1418 states and 1638 transitions. [2018-04-11 21:05:19,272 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 189 states. [2018-04-11 21:05:19,272 INFO L78 Accepts]: Start accepts. Automaton has 128 states. Word has length 611 [2018-04-11 21:05:19,273 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-11 21:05:19,274 INFO L225 Difference]: With dead ends: 1418 [2018-04-11 21:05:19,274 INFO L226 Difference]: Without dead ends: 1416 [2018-04-11 21:05:19,279 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1375 GetRequests, 1095 SyntacticMatches, 0 SemanticMatches, 280 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15068 ImplicationChecksByTransitivity, 27.1s TimeCoverageRelationStatistics Valid=18976, Invalid=60266, Unknown=0, NotChecked=0, Total=79242 [2018-04-11 21:05:19,280 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1416 states. [2018-04-11 21:05:19,417 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1416 to 1413. [2018-04-11 21:05:19,417 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1413 states. [2018-04-11 21:05:19,418 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1413 states to 1413 states and 1570 transitions. [2018-04-11 21:05:19,418 INFO L78 Accepts]: Start accepts. Automaton has 1413 states and 1570 transitions. Word has length 611 [2018-04-11 21:05:19,419 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-11 21:05:19,419 INFO L459 AbstractCegarLoop]: Abstraction has 1413 states and 1570 transitions. [2018-04-11 21:05:19,419 INFO L460 AbstractCegarLoop]: Interpolant automaton has 128 states. [2018-04-11 21:05:19,419 INFO L276 IsEmpty]: Start isEmpty. Operand 1413 states and 1570 transitions. [2018-04-11 21:05:19,424 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 892 [2018-04-11 21:05:19,425 INFO L347 BasicCegarLoop]: Found error trace [2018-04-11 21:05:19,425 INFO L355 BasicCegarLoop]: trace histogram [127, 126, 126, 126, 126, 126, 126, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-11 21:05:19,425 INFO L408 AbstractCegarLoop]: === Iteration 45 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-11 21:05:19,425 INFO L82 PathProgramCache]: Analyzing trace with hash 1279826094, now seen corresponding path program 6 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 46 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 46 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-11 21:05:19,431 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-11 21:05:19,501 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-11 21:05:19,510 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-11 21:05:24,235 INFO L134 CoverageAnalysis]: Checked inductivity of 55377 backedges. 0 proven. 55377 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-11 21:05:24,235 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-11 21:05:38,871 INFO L134 CoverageAnalysis]: Checked inductivity of 55377 backedges. 0 proven. 55377 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-11 21:05:38,891 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-11 21:05:38,925 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [128, 128] total 255 [2018-04-11 21:05:38,926 INFO L442 AbstractCegarLoop]: Interpolant automaton has 256 states [2018-04-11 21:05:38,928 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 256 interpolants. [2018-04-11 21:05:38,930 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=16638, Invalid=48642, Unknown=0, NotChecked=0, Total=65280 [2018-04-11 21:05:38,930 INFO L87 Difference]: Start difference. First operand 1413 states and 1570 transitions. Second operand 256 states. Received shutdown request... [2018-04-11 21:05:44,456 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 47 states. [2018-04-11 21:05:44,456 WARN L519 AbstractCegarLoop]: Verification canceled [2018-04-11 21:05:44,461 WARN L197 ceAbstractionStarter]: Timeout [2018-04-11 21:05:44,461 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 11.04 09:05:44 BoogieIcfgContainer [2018-04-11 21:05:44,461 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-04-11 21:05:44,462 INFO L168 Benchmark]: Toolchain (without parser) took 226162.70 ms. Allocated memory was 308.3 MB in the beginning and 1.1 GB in the end (delta: 777.0 MB). Free memory was 250.8 MB in the beginning and 553.5 MB in the end (delta: -302.7 MB). Peak memory consumption was 474.3 MB. Max. memory is 5.3 GB. [2018-04-11 21:05:44,464 INFO L168 Benchmark]: CDTParser took 0.26 ms. Allocated memory is still 308.3 MB. Free memory is still 270.6 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-04-11 21:05:44,464 INFO L168 Benchmark]: CACSL2BoogieTranslator took 187.74 ms. Allocated memory is still 308.3 MB. Free memory was 250.8 MB in the beginning and 241.6 MB in the end (delta: 9.2 MB). Peak memory consumption was 9.2 MB. Max. memory is 5.3 GB. [2018-04-11 21:05:44,464 INFO L168 Benchmark]: Boogie Preprocessor took 24.40 ms. Allocated memory is still 308.3 MB. Free memory was 241.6 MB in the beginning and 239.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. [2018-04-11 21:05:44,465 INFO L168 Benchmark]: RCFGBuilder took 267.76 ms. Allocated memory was 308.3 MB in the beginning and 472.9 MB in the end (delta: 164.6 MB). Free memory was 239.6 MB in the beginning and 442.0 MB in the end (delta: -202.3 MB). Peak memory consumption was 21.7 MB. Max. memory is 5.3 GB. [2018-04-11 21:05:44,465 INFO L168 Benchmark]: TraceAbstraction took 225678.90 ms. Allocated memory was 472.9 MB in the beginning and 1.1 GB in the end (delta: 612.4 MB). Free memory was 442.0 MB in the beginning and 553.5 MB in the end (delta: -111.5 MB). Peak memory consumption was 500.9 MB. Max. memory is 5.3 GB. [2018-04-11 21:05:44,468 INFO L344 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.26 ms. Allocated memory is still 308.3 MB. Free memory is still 270.6 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 187.74 ms. Allocated memory is still 308.3 MB. Free memory was 250.8 MB in the beginning and 241.6 MB in the end (delta: 9.2 MB). Peak memory consumption was 9.2 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 24.40 ms. Allocated memory is still 308.3 MB. Free memory was 241.6 MB in the beginning and 239.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. * RCFGBuilder took 267.76 ms. Allocated memory was 308.3 MB in the beginning and 472.9 MB in the end (delta: 164.6 MB). Free memory was 239.6 MB in the beginning and 442.0 MB in the end (delta: -202.3 MB). Peak memory consumption was 21.7 MB. Max. memory is 5.3 GB. * TraceAbstraction took 225678.90 ms. Allocated memory was 472.9 MB in the beginning and 1.1 GB in the end (delta: 612.4 MB). Free memory was 442.0 MB in the beginning and 553.5 MB in the end (delta: -111.5 MB). Peak memory consumption was 500.9 MB. Max. memory is 5.3 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 13]: Timeout (TraceAbstraction) Unable to prove that array index is always in bounds (line 13). Cancelled while BasicCegarLoop was constructing difference of abstraction (1413states) and interpolant automaton (currently 47 states, 256 states before enhancement), while ReachableStatesComputation was computing reachable states (414 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 13]: Timeout (TraceAbstraction) Unable to prove that array index is always in bounds (line 13). Cancelled while BasicCegarLoop was constructing difference of abstraction (1413states) and interpolant automaton (currently 47 states, 256 states before enhancement), while ReachableStatesComputation was computing reachable states (414 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 8]: Timeout (TraceAbstraction) Unable to prove that array index is always in bounds (line 8). Cancelled while BasicCegarLoop was constructing difference of abstraction (1413states) and interpolant automaton (currently 47 states, 256 states before enhancement), while ReachableStatesComputation was computing reachable states (414 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 8]: Timeout (TraceAbstraction) Unable to prove that array index is always in bounds (line 8). Cancelled while BasicCegarLoop was constructing difference of abstraction (1413states) and interpolant automaton (currently 47 states, 256 states before enhancement), while ReachableStatesComputation was computing reachable states (414 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 7]: Timeout (TraceAbstraction) Unable to prove that array index is always in bounds (line 7). Cancelled while BasicCegarLoop was constructing difference of abstraction (1413states) and interpolant automaton (currently 47 states, 256 states before enhancement), while ReachableStatesComputation was computing reachable states (414 states constructedinput type IntersectNwa). - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 39 locations, 5 error locations. TIMEOUT Result, 225.6s OverallTime, 45 OverallIterations, 127 TraceHistogramMax, 118.5s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 6339 SDtfs, 47801 SDslu, 160436 SDs, 0 SdLazy, 102029 SolverSat, 8239 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 27.7s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 30795 GetRequests, 25571 SyntacticMatches, 528 SemanticMatches, 4696 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 164302 ImplicationChecksByTransitivity, 158.2s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=1413occurred in iteration=44, 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: 3.9s AutomataMinimizationTime, 44 MinimizatonAttempts, 37270 StatesRemovedByMinimization, 12 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.3s SsaConstructionTime, 1.4s SatisfiabilityAnalysisTime, 99.4s InterpolantComputationTime, 14727 NumberOfCodeBlocks, 14727 NumberOfCodeBlocksAsserted, 45 NumberOfCheckSat, 29364 ConstructedInterpolants, 0 QuantifiedInterpolants, 52740228 SizeOfPredicates, 1170 NumberOfNonLiveVariables, 20170 ConjunctsInSsa, 2331 ConjunctsInUnsatCore, 90 InterpolantComputations, 6 PerfectInterpolantSequences, 219030/446564 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/standard_strcpy_false-valid-deref_ground.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Fixed_noBitfields+AI_EQ_SS.epf_AutomizerC.xml/Csv-Benchmark-0-2018-04-11_21-05-44-477.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/standard_strcpy_false-valid-deref_ground.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Fixed_noBitfields+AI_EQ_SS.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-0-2018-04-11_21-05-44-477.csv Completed graceful shutdown