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-453dfda-m [2018-04-09 20:44:00,778 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-04-09 20:44:00,780 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-04-09 20:44:00,794 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-04-09 20:44:00,794 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-04-09 20:44:00,795 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-04-09 20:44:00,795 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-04-09 20:44:00,797 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-04-09 20:44:00,799 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-04-09 20:44:00,800 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-04-09 20:44:00,801 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-04-09 20:44:00,801 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-04-09 20:44:00,802 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-04-09 20:44:00,804 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-04-09 20:44:00,805 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-04-09 20:44:00,807 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-04-09 20:44:00,809 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-04-09 20:44:00,811 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-04-09 20:44:00,812 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-04-09 20:44:00,813 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-04-09 20:44:00,815 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-04-09 20:44:00,816 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-04-09 20:44:00,816 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-04-09 20:44:00,817 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-04-09 20:44:00,818 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-04-09 20:44:00,819 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-04-09 20:44:00,820 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-04-09 20:44:00,820 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-04-09 20:44:00,821 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-04-09 20:44:00,821 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-04-09 20:44:00,822 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-04-09 20:44:00,822 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-09 20:44:00,844 INFO L110 SettingsManager]: Loading preferences was successful [2018-04-09 20:44:00,845 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-04-09 20:44:00,845 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-04-09 20:44:00,845 INFO L133 SettingsManager]: * ultimate.logging.details=de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation=DEBUG; [2018-04-09 20:44:00,846 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-04-09 20:44:00,846 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-04-09 20:44:00,846 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-04-09 20:44:00,846 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-04-09 20:44:00,846 INFO L133 SettingsManager]: * Parallel states before merging=1 [2018-04-09 20:44:00,847 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-04-09 20:44:00,847 INFO L131 SettingsManager]: Preferences of LTL2Aut differ from their defaults: [2018-04-09 20:44:00,847 INFO L133 SettingsManager]: * Property to check=[] a a: x > 42 [2018-04-09 20:44:00,847 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-04-09 20:44:00,847 INFO L133 SettingsManager]: * sizeof long=4 [2018-04-09 20:44:00,847 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-04-09 20:44:00,848 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-04-09 20:44:00,848 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-04-09 20:44:00,848 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-04-09 20:44:00,848 INFO L133 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2018-04-09 20:44:00,848 INFO L133 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2018-04-09 20:44:00,848 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-04-09 20:44:00,849 INFO L133 SettingsManager]: * sizeof long double=12 [2018-04-09 20:44:00,849 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-04-09 20:44:00,849 INFO L133 SettingsManager]: * Size of a code block=SingleStatement [2018-04-09 20:44:00,849 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-04-09 20:44:00,849 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-04-09 20:44:00,850 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-04-09 20:44:00,850 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-04-09 20:44:00,850 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-04-09 20:44:00,850 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-04-09 20:44:00,850 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-04-09 20:44:00,850 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-04-09 20:44:00,850 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-09 20:44:00,851 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-04-09 20:44:00,851 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-04-09 20:44:00,852 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-04-09 20:44:00,852 INFO L131 SettingsManager]: Preferences of Boogie Printer differ from their defaults: [2018-04-09 20:44:00,852 INFO L133 SettingsManager]: * Dump path:=C:\Users\alex\AppData\Local\Temp\ [2018-04-09 20:44:00,884 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-04-09 20:44:00,894 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully (re)initialized [2018-04-09 20:44:00,897 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-04-09 20:44:00,898 INFO L271 PluginConnector]: Initializing CDTParser... [2018-04-09 20:44:00,899 INFO L276 PluginConnector]: CDTParser initialized [2018-04-09 20:44:00,900 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-09 20:44:01,200 INFO L225 CDTParser]: Created temporary CDT project at /storage/ultimate/releaseScripts/default/UAutomizer-linux/data/FLAG3bc81af9c [2018-04-09 20:44:01,329 INFO L287 CDTParser]: IsIndexed: true [2018-04-09 20:44:01,329 INFO L288 CDTParser]: Found 1 translation units. [2018-04-09 20:44:01,329 INFO L168 CDTParser]: Scanning standard_strcpy_false-valid-deref_ground.i [2018-04-09 20:44:01,330 INFO L210 ultiparseSymbolTable]: Include resolver: [2018-04-09 20:44:01,330 INFO L215 ultiparseSymbolTable]: [2018-04-09 20:44:01,330 INFO L218 ultiparseSymbolTable]: Function table: [2018-04-09 20:44:01,330 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-09 20:44:01,331 INFO L221 ultiparseSymbolTable]: Function definition of null ('main') in standard_strcpy_false-valid-deref_ground.i [2018-04-09 20:44:01,331 INFO L227 ultiparseSymbolTable]: Global variable table: [2018-04-09 20:44:01,331 INFO L233 ultiparseSymbolTable]: [2018-04-09 20:44:01,345 INFO L330 CDTParser]: Deleted temporary CDT project at /storage/ultimate/releaseScripts/default/UAutomizer-linux/data/FLAG3bc81af9c [2018-04-09 20:44:01,349 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-04-09 20:44:01,352 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-04-09 20:44:01,353 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-04-09 20:44:01,353 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-04-09 20:44:01,359 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-04-09 20:44:01,360 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.04 08:44:01" (1/1) ... [2018-04-09 20:44:01,362 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@74006336 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.04 08:44:01, skipping insertion in model container [2018-04-09 20:44:01,362 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.04 08:44:01" (1/1) ... [2018-04-09 20:44:01,376 INFO L167 Dispatcher]: Using SV-COMP mode [2018-04-09 20:44:01,386 INFO L167 Dispatcher]: Using SV-COMP mode [2018-04-09 20:44:01,518 INFO L175 PostProcessor]: Settings: Checked method=main [2018-04-09 20:44:01,534 INFO L175 PostProcessor]: Settings: Checked method=main [2018-04-09 20:44:01,539 INFO L100 SccComputation]: Graph consists of 0 InCaSumBalls and 5 non ball SCCs. Number of states in SCCs 5. [2018-04-09 20:44:01,546 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.04 08:44:01 WrapperNode [2018-04-09 20:44:01,546 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-04-09 20:44:01,547 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-04-09 20:44:01,547 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-04-09 20:44:01,547 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-04-09 20:44:01,556 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.04 08:44:01" (1/1) ... [2018-04-09 20:44:01,556 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.04 08:44:01" (1/1) ... [2018-04-09 20:44:01,562 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.04 08:44:01" (1/1) ... [2018-04-09 20:44:01,562 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.04 08:44:01" (1/1) ... [2018-04-09 20:44:01,564 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.04 08:44:01" (1/1) ... [2018-04-09 20:44:01,568 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.04 08:44:01" (1/1) ... [2018-04-09 20:44:01,569 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.04 08:44:01" (1/1) ... [2018-04-09 20:44:01,569 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-04-09 20:44:01,570 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-04-09 20:44:01,570 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-04-09 20:44:01,570 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-04-09 20:44:01,571 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.04 08:44:01" (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-09 20:44:01,626 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-04-09 20:44:01,626 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-04-09 20:44:01,627 INFO L136 BoogieDeclarations]: Found implementation of procedure __U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert [2018-04-09 20:44:01,627 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-04-09 20:44:01,627 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_error [2018-04-09 20:44:01,627 INFO L128 BoogieDeclarations]: Found specification of procedure __U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert [2018-04-09 20:44:01,627 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-04-09 20:44:01,627 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-04-09 20:44:01,627 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-04-09 20:44:01,829 INFO L259 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-04-09 20:44:01,830 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.04 08:44:01 BoogieIcfgContainer [2018-04-09 20:44:01,830 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-04-09 20:44:01,831 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-04-09 20:44:01,831 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-04-09 20:44:01,834 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-04-09 20:44:01,834 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 09.04 08:44:01" (1/3) ... [2018-04-09 20:44:01,835 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4533da2b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.04 08:44:01, skipping insertion in model container [2018-04-09 20:44:01,835 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.04 08:44:01" (2/3) ... [2018-04-09 20:44:01,835 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4533da2b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.04 08:44:01, skipping insertion in model container [2018-04-09 20:44:01,835 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.04 08:44:01" (3/3) ... [2018-04-09 20:44:01,837 INFO L107 eAbstractionObserver]: Analyzing ICFG standard_strcpy_false-valid-deref_ground.i [2018-04-09 20:44:01,844 INFO L131 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-04-09 20:44:01,853 INFO L143 ceAbstractionStarter]: Appying trace abstraction to program that has 5 error locations. [2018-04-09 20:44:01,889 INFO L128 ementStrategyFactory]: Using default assertion order modulation [2018-04-09 20:44:01,890 INFO L369 AbstractCegarLoop]: Interprodecural is true [2018-04-09 20:44:01,890 INFO L370 AbstractCegarLoop]: Hoare is true [2018-04-09 20:44:01,890 INFO L371 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-04-09 20:44:01,890 INFO L372 AbstractCegarLoop]: Backedges is TWOTRACK [2018-04-09 20:44:01,890 INFO L373 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-04-09 20:44:01,891 INFO L374 AbstractCegarLoop]: Difference is false [2018-04-09 20:44:01,891 INFO L375 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-04-09 20:44:01,891 INFO L380 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-04-09 20:44:01,892 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-04-09 20:44:01,910 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states. [2018-04-09 20:44:01,917 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2018-04-09 20:44:01,917 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:01,918 INFO L355 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-09 20:44:01,918 INFO L408 AbstractCegarLoop]: === Iteration 1 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:01,923 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-09 20:44:01,935 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:01,953 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:01,960 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:01,988 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-09 20:44:01,988 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:02,023 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-09 20:44:02,047 INFO L320 seRefinementStrategy]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2018-04-09 20:44:02,047 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2, 2] imperfect sequences [] total 3 [2018-04-09 20:44:02,048 INFO L442 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-04-09 20:44:02,058 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-04-09 20:44:02,058 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-04-09 20:44:02,060 INFO L87 Difference]: Start difference. First operand 39 states. Second operand 4 states. [2018-04-09 20:44:02,149 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:02,149 INFO L93 Difference]: Finished difference Result 108 states and 130 transitions. [2018-04-09 20:44:02,150 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-04-09 20:44:02,151 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 9 [2018-04-09 20:44:02,152 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:02,161 INFO L225 Difference]: With dead ends: 108 [2018-04-09 20:44:02,161 INFO L226 Difference]: Without dead ends: 71 [2018-04-09 20:44:02,165 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-09 20:44:02,178 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2018-04-09 20:44:02,199 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 45. [2018-04-09 20:44:02,200 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 45 states. [2018-04-09 20:44:02,201 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 48 transitions. [2018-04-09 20:44:02,203 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 48 transitions. Word has length 9 [2018-04-09 20:44:02,203 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:02,203 INFO L459 AbstractCegarLoop]: Abstraction has 45 states and 48 transitions. [2018-04-09 20:44:02,203 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-04-09 20:44:02,203 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 48 transitions. [2018-04-09 20:44:02,204 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-04-09 20:44:02,204 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:02,204 INFO L355 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-09 20:44:02,205 INFO L408 AbstractCegarLoop]: === Iteration 2 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:02,205 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-09 20:44:02,217 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:02,223 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:02,224 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:02,239 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-09 20:44:02,239 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:02,259 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-09 20:44:02,286 INFO L320 seRefinementStrategy]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2018-04-09 20:44:02,286 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2, 2] imperfect sequences [] total 3 [2018-04-09 20:44:02,287 INFO L442 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-04-09 20:44:02,288 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-04-09 20:44:02,288 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-04-09 20:44:02,288 INFO L87 Difference]: Start difference. First operand 45 states and 48 transitions. Second operand 4 states. [2018-04-09 20:44:02,316 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:02,317 INFO L93 Difference]: Finished difference Result 54 states and 58 transitions. [2018-04-09 20:44:02,317 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-04-09 20:44:02,317 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 15 [2018-04-09 20:44:02,317 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:02,318 INFO L225 Difference]: With dead ends: 54 [2018-04-09 20:44:02,319 INFO L226 Difference]: Without dead ends: 52 [2018-04-09 20:44:02,320 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-09 20:44:02,320 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2018-04-09 20:44:02,325 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 49. [2018-04-09 20:44:02,326 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 49 states. [2018-04-09 20:44:02,327 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 52 transitions. [2018-04-09 20:44:02,327 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 52 transitions. Word has length 15 [2018-04-09 20:44:02,327 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:02,327 INFO L459 AbstractCegarLoop]: Abstraction has 49 states and 52 transitions. [2018-04-09 20:44:02,328 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-04-09 20:44:02,328 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 52 transitions. [2018-04-09 20:44:02,328 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2018-04-09 20:44:02,329 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:02,329 INFO L355 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-09 20:44:02,329 INFO L408 AbstractCegarLoop]: === Iteration 3 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:02,329 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-09 20:44:02,335 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:02,345 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:02,347 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:02,413 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-09 20:44:02,414 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:02,496 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-09 20:44:02,518 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:44:02,518 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 7 [2018-04-09 20:44:02,519 INFO L442 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-04-09 20:44:02,519 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-04-09 20:44:02,519 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=34, Unknown=0, NotChecked=0, Total=56 [2018-04-09 20:44:02,519 INFO L87 Difference]: Start difference. First operand 49 states and 52 transitions. Second operand 8 states. [2018-04-09 20:44:02,748 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:02,748 INFO L93 Difference]: Finished difference Result 178 states and 200 transitions. [2018-04-09 20:44:02,749 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-04-09 20:44:02,749 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 23 [2018-04-09 20:44:02,750 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:02,752 INFO L225 Difference]: With dead ends: 178 [2018-04-09 20:44:02,752 INFO L226 Difference]: Without dead ends: 175 [2018-04-09 20:44:02,753 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 39 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=38, Invalid=52, Unknown=0, NotChecked=0, Total=90 [2018-04-09 20:44:02,753 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 175 states. [2018-04-09 20:44:02,764 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 175 to 77. [2018-04-09 20:44:02,765 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 77 states. [2018-04-09 20:44:02,766 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 84 transitions. [2018-04-09 20:44:02,767 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 84 transitions. Word has length 23 [2018-04-09 20:44:02,767 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:02,767 INFO L459 AbstractCegarLoop]: Abstraction has 77 states and 84 transitions. [2018-04-09 20:44:02,767 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-04-09 20:44:02,767 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 84 transitions. [2018-04-09 20:44:02,768 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2018-04-09 20:44:02,768 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:02,768 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-09 20:44:02,768 INFO L408 AbstractCegarLoop]: === Iteration 4 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:02,768 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-09 20:44:02,776 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:02,784 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:02,787 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:02,825 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-09 20:44:02,826 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:02,898 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-09 20:44:02,932 INFO L320 seRefinementStrategy]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2018-04-09 20:44:02,933 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4, 4] imperfect sequences [] total 5 [2018-04-09 20:44:02,933 INFO L442 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-04-09 20:44:02,933 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-04-09 20:44:02,934 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-04-09 20:44:02,934 INFO L87 Difference]: Start difference. First operand 77 states and 84 transitions. Second operand 5 states. [2018-04-09 20:44:03,012 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:03,012 INFO L93 Difference]: Finished difference Result 97 states and 104 transitions. [2018-04-09 20:44:03,013 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-04-09 20:44:03,013 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 27 [2018-04-09 20:44:03,013 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:03,015 INFO L225 Difference]: With dead ends: 97 [2018-04-09 20:44:03,017 INFO L226 Difference]: Without dead ends: 77 [2018-04-09 20:44:03,018 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-09 20:44:03,018 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2018-04-09 20:44:03,026 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 77. [2018-04-09 20:44:03,026 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 77 states. [2018-04-09 20:44:03,027 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 83 transitions. [2018-04-09 20:44:03,028 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 83 transitions. Word has length 27 [2018-04-09 20:44:03,028 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:03,028 INFO L459 AbstractCegarLoop]: Abstraction has 77 states and 83 transitions. [2018-04-09 20:44:03,028 INFO L460 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-04-09 20:44:03,028 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 83 transitions. [2018-04-09 20:44:03,030 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2018-04-09 20:44:03,030 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:03,030 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-09 20:44:03,030 INFO L408 AbstractCegarLoop]: === Iteration 5 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:03,031 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-09 20:44:03,042 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:03,054 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:03,057 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:03,124 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-09 20:44:03,124 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:03,181 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-09 20:44:03,202 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:44:03,203 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2018-04-09 20:44:03,203 INFO L442 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-04-09 20:44:03,204 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-04-09 20:44:03,204 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=63, Unknown=0, NotChecked=0, Total=90 [2018-04-09 20:44:03,204 INFO L87 Difference]: Start difference. First operand 77 states and 83 transitions. Second operand 10 states. [2018-04-09 20:44:03,284 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:03,284 INFO L93 Difference]: Finished difference Result 103 states and 110 transitions. [2018-04-09 20:44:03,284 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-04-09 20:44:03,285 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 34 [2018-04-09 20:44:03,285 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:03,286 INFO L225 Difference]: With dead ends: 103 [2018-04-09 20:44:03,286 INFO L226 Difference]: Without dead ends: 77 [2018-04-09 20:44:03,286 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-09 20:44:03,287 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2018-04-09 20:44:03,292 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 77. [2018-04-09 20:44:03,292 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 77 states. [2018-04-09 20:44:03,293 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 82 transitions. [2018-04-09 20:44:03,294 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 82 transitions. Word has length 34 [2018-04-09 20:44:03,294 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:03,294 INFO L459 AbstractCegarLoop]: Abstraction has 77 states and 82 transitions. [2018-04-09 20:44:03,294 INFO L460 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-04-09 20:44:03,294 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 82 transitions. [2018-04-09 20:44:03,295 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2018-04-09 20:44:03,295 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:03,295 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-09 20:44:03,295 INFO L408 AbstractCegarLoop]: === Iteration 6 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:03,295 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-09 20:44:03,301 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:03,316 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:03,318 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:03,333 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-09 20:44:03,333 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:03,366 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-09 20:44:03,400 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:44:03,401 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 7 [2018-04-09 20:44:03,401 INFO L442 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-04-09 20:44:03,402 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-04-09 20:44:03,402 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-04-09 20:44:03,402 INFO L87 Difference]: Start difference. First operand 77 states and 82 transitions. Second operand 8 states. [2018-04-09 20:44:03,519 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:03,519 INFO L93 Difference]: Finished difference Result 98 states and 108 transitions. [2018-04-09 20:44:03,519 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-04-09 20:44:03,519 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 41 [2018-04-09 20:44:03,520 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:03,520 INFO L225 Difference]: With dead ends: 98 [2018-04-09 20:44:03,520 INFO L226 Difference]: Without dead ends: 96 [2018-04-09 20:44:03,521 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-09 20:44:03,521 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2018-04-09 20:44:03,526 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 93. [2018-04-09 20:44:03,526 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 93 states. [2018-04-09 20:44:03,527 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 100 transitions. [2018-04-09 20:44:03,527 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 100 transitions. Word has length 41 [2018-04-09 20:44:03,528 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:03,528 INFO L459 AbstractCegarLoop]: Abstraction has 93 states and 100 transitions. [2018-04-09 20:44:03,528 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-04-09 20:44:03,528 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 100 transitions. [2018-04-09 20:44:03,530 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2018-04-09 20:44:03,530 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:03,530 INFO L355 BasicCegarLoop]: trace histogram [7, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-09 20:44:03,530 INFO L408 AbstractCegarLoop]: === Iteration 7 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:03,530 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-09 20:44:03,538 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:03,547 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:03,550 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:03,612 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-09 20:44:03,612 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:03,703 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-09 20:44:03,724 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:44:03,724 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 15 [2018-04-09 20:44:03,725 INFO L442 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-04-09 20:44:03,725 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-04-09 20:44:03,725 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=162, Unknown=0, NotChecked=0, Total=240 [2018-04-09 20:44:03,726 INFO L87 Difference]: Start difference. First operand 93 states and 100 transitions. Second operand 16 states. [2018-04-09 20:44:04,112 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:04,113 INFO L93 Difference]: Finished difference Result 538 states and 610 transitions. [2018-04-09 20:44:04,113 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-04-09 20:44:04,113 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 51 [2018-04-09 20:44:04,114 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:04,116 INFO L225 Difference]: With dead ends: 538 [2018-04-09 20:44:04,116 INFO L226 Difference]: Without dead ends: 535 [2018-04-09 20:44:04,117 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-09 20:44:04,118 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 535 states. [2018-04-09 20:44:04,142 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 535 to 149. [2018-04-09 20:44:04,142 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 149 states. [2018-04-09 20:44:04,144 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 149 states to 149 states and 164 transitions. [2018-04-09 20:44:04,145 INFO L78 Accepts]: Start accepts. Automaton has 149 states and 164 transitions. Word has length 51 [2018-04-09 20:44:04,145 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:04,145 INFO L459 AbstractCegarLoop]: Abstraction has 149 states and 164 transitions. [2018-04-09 20:44:04,145 INFO L460 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-04-09 20:44:04,146 INFO L276 IsEmpty]: Start isEmpty. Operand 149 states and 164 transitions. [2018-04-09 20:44:04,147 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2018-04-09 20:44:04,147 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:04,148 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-09 20:44:04,148 INFO L408 AbstractCegarLoop]: === Iteration 8 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:04,148 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-09 20:44:04,162 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:04,185 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:04,188 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:04,285 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-09 20:44:04,285 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:04,342 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-09 20:44:04,363 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:44:04,364 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 15 [2018-04-09 20:44:04,364 INFO L442 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-04-09 20:44:04,364 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-04-09 20:44:04,364 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=158, Unknown=0, NotChecked=0, Total=210 [2018-04-09 20:44:04,365 INFO L87 Difference]: Start difference. First operand 149 states and 164 transitions. Second operand 15 states. [2018-04-09 20:44:04,463 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:04,463 INFO L93 Difference]: Finished difference Result 185 states and 202 transitions. [2018-04-09 20:44:04,464 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-04-09 20:44:04,464 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 65 [2018-04-09 20:44:04,464 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:04,465 INFO L225 Difference]: With dead ends: 185 [2018-04-09 20:44:04,465 INFO L226 Difference]: Without dead ends: 149 [2018-04-09 20:44:04,466 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-09 20:44:04,467 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 149 states. [2018-04-09 20:44:04,475 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 149 to 149. [2018-04-09 20:44:04,475 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 149 states. [2018-04-09 20:44:04,477 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 149 states to 149 states and 163 transitions. [2018-04-09 20:44:04,477 INFO L78 Accepts]: Start accepts. Automaton has 149 states and 163 transitions. Word has length 65 [2018-04-09 20:44:04,477 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:04,477 INFO L459 AbstractCegarLoop]: Abstraction has 149 states and 163 transitions. [2018-04-09 20:44:04,477 INFO L460 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-04-09 20:44:04,477 INFO L276 IsEmpty]: Start isEmpty. Operand 149 states and 163 transitions. [2018-04-09 20:44:04,478 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2018-04-09 20:44:04,478 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:04,478 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-09 20:44:04,478 INFO L408 AbstractCegarLoop]: === Iteration 9 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:04,479 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-09 20:44:04,486 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:04,499 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:04,501 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:04,624 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-09 20:44:04,624 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:04,724 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-09 20:44:04,745 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:44:04,745 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 20 [2018-04-09 20:44:04,745 INFO L442 AbstractCegarLoop]: Interpolant automaton has 20 states [2018-04-09 20:44:04,745 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2018-04-09 20:44:04,746 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=84, Invalid=296, Unknown=0, NotChecked=0, Total=380 [2018-04-09 20:44:04,746 INFO L87 Difference]: Start difference. First operand 149 states and 163 transitions. Second operand 20 states. [2018-04-09 20:44:04,894 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:04,894 INFO L93 Difference]: Finished difference Result 191 states and 208 transitions. [2018-04-09 20:44:04,895 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-04-09 20:44:04,895 INFO L78 Accepts]: Start accepts. Automaton has 20 states. Word has length 72 [2018-04-09 20:44:04,895 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:04,897 INFO L225 Difference]: With dead ends: 191 [2018-04-09 20:44:04,897 INFO L226 Difference]: Without dead ends: 149 [2018-04-09 20:44:04,898 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 121 SyntacticMatches, 4 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 137 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=171, Invalid=479, Unknown=0, NotChecked=0, Total=650 [2018-04-09 20:44:04,898 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 149 states. [2018-04-09 20:44:04,910 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 149 to 149. [2018-04-09 20:44:04,911 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 149 states. [2018-04-09 20:44:04,912 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 149 states to 149 states and 162 transitions. [2018-04-09 20:44:04,912 INFO L78 Accepts]: Start accepts. Automaton has 149 states and 162 transitions. Word has length 72 [2018-04-09 20:44:04,913 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:04,913 INFO L459 AbstractCegarLoop]: Abstraction has 149 states and 162 transitions. [2018-04-09 20:44:04,913 INFO L460 AbstractCegarLoop]: Interpolant automaton has 20 states. [2018-04-09 20:44:04,913 INFO L276 IsEmpty]: Start isEmpty. Operand 149 states and 162 transitions. [2018-04-09 20:44:04,914 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2018-04-09 20:44:04,915 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:04,915 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-09 20:44:04,915 INFO L408 AbstractCegarLoop]: === Iteration 10 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:04,915 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-09 20:44:04,927 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:04,945 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:04,948 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:05,002 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-09 20:44:05,002 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:05,109 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-09 20:44:05,130 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:44:05,131 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 15 [2018-04-09 20:44:05,131 INFO L442 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-04-09 20:44:05,131 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-04-09 20:44:05,131 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=186, Unknown=0, NotChecked=0, Total=240 [2018-04-09 20:44:05,132 INFO L87 Difference]: Start difference. First operand 149 states and 162 transitions. Second operand 16 states. [2018-04-09 20:44:05,384 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:05,384 INFO L93 Difference]: Finished difference Result 186 states and 210 transitions. [2018-04-09 20:44:05,385 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-04-09 20:44:05,385 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 79 [2018-04-09 20:44:05,385 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:05,386 INFO L225 Difference]: With dead ends: 186 [2018-04-09 20:44:05,386 INFO L226 Difference]: Without dead ends: 184 [2018-04-09 20:44:05,387 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-09 20:44:05,387 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 184 states. [2018-04-09 20:44:05,398 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 184 to 181. [2018-04-09 20:44:05,398 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 181 states. [2018-04-09 20:44:05,400 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 181 states to 181 states and 198 transitions. [2018-04-09 20:44:05,400 INFO L78 Accepts]: Start accepts. Automaton has 181 states and 198 transitions. Word has length 79 [2018-04-09 20:44:05,401 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:05,401 INFO L459 AbstractCegarLoop]: Abstraction has 181 states and 198 transitions. [2018-04-09 20:44:05,401 INFO L460 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-04-09 20:44:05,401 INFO L276 IsEmpty]: Start isEmpty. Operand 181 states and 198 transitions. [2018-04-09 20:44:05,402 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2018-04-09 20:44:05,402 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:05,403 INFO L355 BasicCegarLoop]: trace histogram [15, 14, 14, 14, 14, 14, 14, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-09 20:44:05,403 INFO L408 AbstractCegarLoop]: === Iteration 11 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:05,403 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-09 20:44:05,411 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:05,426 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:05,429 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:05,569 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-09 20:44:05,569 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:05,974 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-09 20:44:05,995 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:44:05,996 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 31 [2018-04-09 20:44:05,996 INFO L442 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-04-09 20:44:05,996 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-04-09 20:44:05,997 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=286, Invalid=706, Unknown=0, NotChecked=0, Total=992 [2018-04-09 20:44:05,997 INFO L87 Difference]: Start difference. First operand 181 states and 198 transitions. Second operand 32 states. [2018-04-09 20:44:07,392 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:07,393 INFO L93 Difference]: Finished difference Result 1962 states and 2222 transitions. [2018-04-09 20:44:07,393 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2018-04-09 20:44:07,393 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 107 [2018-04-09 20:44:07,394 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:07,405 INFO L225 Difference]: With dead ends: 1962 [2018-04-09 20:44:07,405 INFO L226 Difference]: Without dead ends: 1959 [2018-04-09 20:44:07,407 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 227 GetRequests, 183 SyntacticMatches, 0 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 91 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=734, Invalid=1336, Unknown=0, NotChecked=0, Total=2070 [2018-04-09 20:44:07,408 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1959 states. [2018-04-09 20:44:07,448 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1959 to 293. [2018-04-09 20:44:07,448 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 293 states. [2018-04-09 20:44:07,449 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 293 states to 293 states and 326 transitions. [2018-04-09 20:44:07,449 INFO L78 Accepts]: Start accepts. Automaton has 293 states and 326 transitions. Word has length 107 [2018-04-09 20:44:07,449 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:07,450 INFO L459 AbstractCegarLoop]: Abstraction has 293 states and 326 transitions. [2018-04-09 20:44:07,450 INFO L460 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-04-09 20:44:07,450 INFO L276 IsEmpty]: Start isEmpty. Operand 293 states and 326 transitions. [2018-04-09 20:44:07,451 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 128 [2018-04-09 20:44:07,451 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:07,451 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-09 20:44:07,451 INFO L408 AbstractCegarLoop]: === Iteration 12 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:07,451 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-09 20:44:07,457 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:07,476 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:07,479 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:07,613 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-09 20:44:07,613 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:07,722 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-09 20:44:07,743 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:44:07,743 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 25 [2018-04-09 20:44:07,743 INFO L442 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-04-09 20:44:07,743 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-04-09 20:44:07,744 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=123, Invalid=477, Unknown=0, NotChecked=0, Total=600 [2018-04-09 20:44:07,744 INFO L87 Difference]: Start difference. First operand 293 states and 326 transitions. Second operand 25 states. [2018-04-09 20:44:07,969 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:07,969 INFO L93 Difference]: Finished difference Result 361 states and 400 transitions. [2018-04-09 20:44:07,969 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2018-04-09 20:44:07,970 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 127 [2018-04-09 20:44:07,970 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:07,972 INFO L225 Difference]: With dead ends: 361 [2018-04-09 20:44:07,972 INFO L226 Difference]: Without dead ends: 293 [2018-04-09 20:44:07,973 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-09 20:44:07,973 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 293 states. [2018-04-09 20:44:07,995 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 293 to 293. [2018-04-09 20:44:07,995 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 293 states. [2018-04-09 20:44:07,997 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 293 states to 293 states and 325 transitions. [2018-04-09 20:44:07,998 INFO L78 Accepts]: Start accepts. Automaton has 293 states and 325 transitions. Word has length 127 [2018-04-09 20:44:07,998 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:07,998 INFO L459 AbstractCegarLoop]: Abstraction has 293 states and 325 transitions. [2018-04-09 20:44:07,998 INFO L460 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-04-09 20:44:07,998 INFO L276 IsEmpty]: Start isEmpty. Operand 293 states and 325 transitions. [2018-04-09 20:44:08,000 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 135 [2018-04-09 20:44:08,000 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:08,000 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-09 20:44:08,000 INFO L408 AbstractCegarLoop]: === Iteration 13 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:08,001 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-09 20:44:08,012 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:08,032 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:08,035 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:08,164 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-09 20:44:08,164 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:08,311 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-09 20:44:08,332 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:44:08,333 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19] total 30 [2018-04-09 20:44:08,333 INFO L442 AbstractCegarLoop]: Interpolant automaton has 30 states [2018-04-09 20:44:08,333 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2018-04-09 20:44:08,334 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=169, Invalid=701, Unknown=0, NotChecked=0, Total=870 [2018-04-09 20:44:08,334 INFO L87 Difference]: Start difference. First operand 293 states and 325 transitions. Second operand 30 states. [2018-04-09 20:44:08,612 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:08,613 INFO L93 Difference]: Finished difference Result 361 states and 399 transitions. [2018-04-09 20:44:08,613 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-04-09 20:44:08,613 INFO L78 Accepts]: Start accepts. Automaton has 30 states. Word has length 134 [2018-04-09 20:44:08,614 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:08,615 INFO L225 Difference]: With dead ends: 361 [2018-04-09 20:44:08,615 INFO L226 Difference]: Without dead ends: 293 [2018-04-09 20:44:08,616 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-09 20:44:08,617 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 293 states. [2018-04-09 20:44:08,637 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 293 to 293. [2018-04-09 20:44:08,637 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 293 states. [2018-04-09 20:44:08,639 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 293 states to 293 states and 324 transitions. [2018-04-09 20:44:08,640 INFO L78 Accepts]: Start accepts. Automaton has 293 states and 324 transitions. Word has length 134 [2018-04-09 20:44:08,640 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:08,640 INFO L459 AbstractCegarLoop]: Abstraction has 293 states and 324 transitions. [2018-04-09 20:44:08,640 INFO L460 AbstractCegarLoop]: Interpolant automaton has 30 states. [2018-04-09 20:44:08,640 INFO L276 IsEmpty]: Start isEmpty. Operand 293 states and 324 transitions. [2018-04-09 20:44:08,642 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 142 [2018-04-09 20:44:08,642 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:08,642 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-09 20:44:08,642 INFO L408 AbstractCegarLoop]: === Iteration 14 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:08,643 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-09 20:44:08,651 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:08,677 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:08,681 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:08,954 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-09 20:44:08,954 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:09,245 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-09 20:44:09,276 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:44:09,276 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 35 [2018-04-09 20:44:09,277 INFO L442 AbstractCegarLoop]: Interpolant automaton has 35 states [2018-04-09 20:44:09,277 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2018-04-09 20:44:09,278 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=222, Invalid=968, Unknown=0, NotChecked=0, Total=1190 [2018-04-09 20:44:09,278 INFO L87 Difference]: Start difference. First operand 293 states and 324 transitions. Second operand 35 states. [2018-04-09 20:44:09,838 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:09,839 INFO L93 Difference]: Finished difference Result 361 states and 398 transitions. [2018-04-09 20:44:09,839 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2018-04-09 20:44:09,839 INFO L78 Accepts]: Start accepts. Automaton has 35 states. Word has length 141 [2018-04-09 20:44:09,839 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:09,840 INFO L225 Difference]: With dead ends: 361 [2018-04-09 20:44:09,841 INFO L226 Difference]: Without dead ends: 293 [2018-04-09 20:44:09,842 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 293 GetRequests, 241 SyntacticMatches, 7 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 512 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=504, Invalid=1658, Unknown=0, NotChecked=0, Total=2162 [2018-04-09 20:44:09,842 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 293 states. [2018-04-09 20:44:09,854 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 293 to 293. [2018-04-09 20:44:09,854 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 293 states. [2018-04-09 20:44:09,855 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 293 states to 293 states and 323 transitions. [2018-04-09 20:44:09,855 INFO L78 Accepts]: Start accepts. Automaton has 293 states and 323 transitions. Word has length 141 [2018-04-09 20:44:09,855 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:09,855 INFO L459 AbstractCegarLoop]: Abstraction has 293 states and 323 transitions. [2018-04-09 20:44:09,855 INFO L460 AbstractCegarLoop]: Interpolant automaton has 35 states. [2018-04-09 20:44:09,855 INFO L276 IsEmpty]: Start isEmpty. Operand 293 states and 323 transitions. [2018-04-09 20:44:09,856 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 149 [2018-04-09 20:44:09,857 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:09,857 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-09 20:44:09,857 INFO L408 AbstractCegarLoop]: === Iteration 15 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:09,857 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-09 20:44:09,865 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:09,886 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:09,890 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:10,123 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-09 20:44:10,123 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:10,362 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-09 20:44:10,383 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:44:10,383 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 25] total 40 [2018-04-09 20:44:10,384 INFO L442 AbstractCegarLoop]: Interpolant automaton has 40 states [2018-04-09 20:44:10,384 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 40 interpolants. [2018-04-09 20:44:10,384 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=282, Invalid=1278, Unknown=0, NotChecked=0, Total=1560 [2018-04-09 20:44:10,385 INFO L87 Difference]: Start difference. First operand 293 states and 323 transitions. Second operand 40 states. [2018-04-09 20:44:10,689 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:10,689 INFO L93 Difference]: Finished difference Result 367 states and 404 transitions. [2018-04-09 20:44:10,689 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2018-04-09 20:44:10,689 INFO L78 Accepts]: Start accepts. Automaton has 40 states. Word has length 148 [2018-04-09 20:44:10,689 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:10,691 INFO L225 Difference]: With dead ends: 367 [2018-04-09 20:44:10,691 INFO L226 Difference]: Without dead ends: 293 [2018-04-09 20:44:10,692 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-09 20:44:10,692 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 293 states. [2018-04-09 20:44:10,704 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 293 to 293. [2018-04-09 20:44:10,704 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 293 states. [2018-04-09 20:44:10,705 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 293 states to 293 states and 322 transitions. [2018-04-09 20:44:10,705 INFO L78 Accepts]: Start accepts. Automaton has 293 states and 322 transitions. Word has length 148 [2018-04-09 20:44:10,706 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:10,706 INFO L459 AbstractCegarLoop]: Abstraction has 293 states and 322 transitions. [2018-04-09 20:44:10,706 INFO L460 AbstractCegarLoop]: Interpolant automaton has 40 states. [2018-04-09 20:44:10,706 INFO L276 IsEmpty]: Start isEmpty. Operand 293 states and 322 transitions. [2018-04-09 20:44:10,707 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 156 [2018-04-09 20:44:10,707 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:10,708 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-09 20:44:10,708 INFO L408 AbstractCegarLoop]: === Iteration 16 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:10,708 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-09 20:44:10,716 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:10,737 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:10,740 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:10,894 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-09 20:44:10,894 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:11,205 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-09 20:44:11,227 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:44:11,227 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 31 [2018-04-09 20:44:11,228 INFO L442 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-04-09 20:44:11,228 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-04-09 20:44:11,228 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=174, Invalid=818, Unknown=0, NotChecked=0, Total=992 [2018-04-09 20:44:11,228 INFO L87 Difference]: Start difference. First operand 293 states and 322 transitions. Second operand 32 states. [2018-04-09 20:44:12,352 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:12,352 INFO L93 Difference]: Finished difference Result 362 states and 414 transitions. [2018-04-09 20:44:12,353 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2018-04-09 20:44:12,353 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 155 [2018-04-09 20:44:12,353 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:12,354 INFO L225 Difference]: With dead ends: 362 [2018-04-09 20:44:12,355 INFO L226 Difference]: Without dead ends: 360 [2018-04-09 20:44:12,356 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 343 GetRequests, 279 SyntacticMatches, 0 SemanticMatches, 64 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 716 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=1096, Invalid=3194, Unknown=0, NotChecked=0, Total=4290 [2018-04-09 20:44:12,356 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 360 states. [2018-04-09 20:44:12,368 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 360 to 357. [2018-04-09 20:44:12,369 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 357 states. [2018-04-09 20:44:12,369 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 357 states to 357 states and 394 transitions. [2018-04-09 20:44:12,370 INFO L78 Accepts]: Start accepts. Automaton has 357 states and 394 transitions. Word has length 155 [2018-04-09 20:44:12,370 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:12,370 INFO L459 AbstractCegarLoop]: Abstraction has 357 states and 394 transitions. [2018-04-09 20:44:12,370 INFO L460 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-04-09 20:44:12,370 INFO L276 IsEmpty]: Start isEmpty. Operand 357 states and 394 transitions. [2018-04-09 20:44:12,372 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 220 [2018-04-09 20:44:12,372 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:12,372 INFO L355 BasicCegarLoop]: trace histogram [31, 30, 30, 30, 30, 30, 30, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-09 20:44:12,372 INFO L408 AbstractCegarLoop]: === Iteration 17 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:12,372 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-09 20:44:12,382 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:12,405 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:12,409 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:12,801 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-09 20:44:12,801 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:13,780 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-09 20:44:13,801 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:44:13,801 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [32, 32] total 63 [2018-04-09 20:44:13,801 INFO L442 AbstractCegarLoop]: Interpolant automaton has 64 states [2018-04-09 20:44:13,802 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 64 interpolants. [2018-04-09 20:44:13,802 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1086, Invalid=2946, Unknown=0, NotChecked=0, Total=4032 [2018-04-09 20:44:13,803 INFO L87 Difference]: Start difference. First operand 357 states and 394 transitions. Second operand 64 states. [2018-04-09 20:44:19,470 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:19,470 INFO L93 Difference]: Finished difference Result 7498 states and 8470 transitions. [2018-04-09 20:44:19,470 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 64 states. [2018-04-09 20:44:19,470 INFO L78 Accepts]: Start accepts. Automaton has 64 states. Word has length 219 [2018-04-09 20:44:19,471 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:19,505 INFO L225 Difference]: With dead ends: 7498 [2018-04-09 20:44:19,505 INFO L226 Difference]: Without dead ends: 7495 [2018-04-09 20:44:19,510 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 467 GetRequests, 375 SyntacticMatches, 0 SemanticMatches, 92 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 435 ImplicationChecksByTransitivity, 3.9s TimeCoverageRelationStatistics Valid=3006, Invalid=5736, Unknown=0, NotChecked=0, Total=8742 [2018-04-09 20:44:19,515 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 7495 states. [2018-04-09 20:44:19,685 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 7495 to 581. [2018-04-09 20:44:19,685 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-04-09 20:44:19,687 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 650 transitions. [2018-04-09 20:44:19,688 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 650 transitions. Word has length 219 [2018-04-09 20:44:19,688 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:19,688 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 650 transitions. [2018-04-09 20:44:19,688 INFO L460 AbstractCegarLoop]: Interpolant automaton has 64 states. [2018-04-09 20:44:19,688 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 650 transitions. [2018-04-09 20:44:19,690 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 252 [2018-04-09 20:44:19,690 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:19,691 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-09 20:44:19,691 INFO L408 AbstractCegarLoop]: === Iteration 18 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:19,691 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-09 20:44:19,700 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:19,734 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:19,740 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:20,118 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-09 20:44:20,118 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:20,430 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-09 20:44:20,451 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:44:20,451 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [28, 28] total 45 [2018-04-09 20:44:20,451 INFO L442 AbstractCegarLoop]: Interpolant automaton has 45 states [2018-04-09 20:44:20,451 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2018-04-09 20:44:20,452 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=349, Invalid=1631, Unknown=0, NotChecked=0, Total=1980 [2018-04-09 20:44:20,452 INFO L87 Difference]: Start difference. First operand 581 states and 650 transitions. Second operand 45 states. [2018-04-09 20:44:20,874 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:20,874 INFO L93 Difference]: Finished difference Result 713 states and 796 transitions. [2018-04-09 20:44:20,874 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2018-04-09 20:44:20,875 INFO L78 Accepts]: Start accepts. Automaton has 45 states. Word has length 251 [2018-04-09 20:44:20,875 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:20,877 INFO L225 Difference]: With dead ends: 713 [2018-04-09 20:44:20,877 INFO L226 Difference]: Without dead ends: 581 [2018-04-09 20:44:20,878 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 517 GetRequests, 449 SyntacticMatches, 9 SemanticMatches, 59 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 897 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=821, Invalid=2839, Unknown=0, NotChecked=0, Total=3660 [2018-04-09 20:44:20,878 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-04-09 20:44:20,948 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-04-09 20:44:20,948 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-04-09 20:44:20,950 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 649 transitions. [2018-04-09 20:44:20,950 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 649 transitions. Word has length 251 [2018-04-09 20:44:20,951 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:20,951 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 649 transitions. [2018-04-09 20:44:20,951 INFO L460 AbstractCegarLoop]: Interpolant automaton has 45 states. [2018-04-09 20:44:20,951 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 649 transitions. [2018-04-09 20:44:20,953 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 259 [2018-04-09 20:44:20,953 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:20,953 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-09 20:44:20,953 INFO L408 AbstractCegarLoop]: === Iteration 19 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:20,954 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-09 20:44:20,965 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:21,009 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:21,016 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:21,433 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-09 20:44:21,433 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:21,808 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-09 20:44:21,829 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:44:21,829 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [31, 31] total 50 [2018-04-09 20:44:21,830 INFO L442 AbstractCegarLoop]: Interpolant automaton has 50 states [2018-04-09 20:44:21,830 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 50 interpolants. [2018-04-09 20:44:21,831 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=423, Invalid=2027, Unknown=0, NotChecked=0, Total=2450 [2018-04-09 20:44:21,831 INFO L87 Difference]: Start difference. First operand 581 states and 649 transitions. Second operand 50 states. [2018-04-09 20:44:22,323 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:22,323 INFO L93 Difference]: Finished difference Result 713 states and 795 transitions. [2018-04-09 20:44:22,323 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2018-04-09 20:44:22,323 INFO L78 Accepts]: Start accepts. Automaton has 50 states. Word has length 258 [2018-04-09 20:44:22,324 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:22,325 INFO L225 Difference]: With dead ends: 713 [2018-04-09 20:44:22,325 INFO L226 Difference]: Without dead ends: 581 [2018-04-09 20:44:22,326 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-09 20:44:22,327 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-04-09 20:44:22,392 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-04-09 20:44:22,392 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-04-09 20:44:22,393 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 648 transitions. [2018-04-09 20:44:22,393 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 648 transitions. Word has length 258 [2018-04-09 20:44:22,393 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:22,393 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 648 transitions. [2018-04-09 20:44:22,393 INFO L460 AbstractCegarLoop]: Interpolant automaton has 50 states. [2018-04-09 20:44:22,394 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 648 transitions. [2018-04-09 20:44:22,395 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 266 [2018-04-09 20:44:22,395 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:22,395 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-09 20:44:22,395 INFO L408 AbstractCegarLoop]: === Iteration 20 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:22,395 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-09 20:44:22,401 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:22,435 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:22,439 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:22,895 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-09 20:44:22,895 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:23,308 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-09 20:44:23,329 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:44:23,329 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [34, 34] total 55 [2018-04-09 20:44:23,330 INFO L442 AbstractCegarLoop]: Interpolant automaton has 55 states [2018-04-09 20:44:23,330 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 55 interpolants. [2018-04-09 20:44:23,331 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=504, Invalid=2466, Unknown=0, NotChecked=0, Total=2970 [2018-04-09 20:44:23,331 INFO L87 Difference]: Start difference. First operand 581 states and 648 transitions. Second operand 55 states. [2018-04-09 20:44:23,983 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:23,983 INFO L93 Difference]: Finished difference Result 713 states and 794 transitions. [2018-04-09 20:44:23,983 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2018-04-09 20:44:23,983 INFO L78 Accepts]: Start accepts. Automaton has 55 states. Word has length 265 [2018-04-09 20:44:23,984 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:23,985 INFO L225 Difference]: With dead ends: 713 [2018-04-09 20:44:23,985 INFO L226 Difference]: Without dead ends: 581 [2018-04-09 20:44:23,986 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 549 GetRequests, 465 SyntacticMatches, 11 SemanticMatches, 73 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1390 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=1214, Invalid=4336, Unknown=0, NotChecked=0, Total=5550 [2018-04-09 20:44:23,987 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-04-09 20:44:24,039 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-04-09 20:44:24,039 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-04-09 20:44:24,041 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 647 transitions. [2018-04-09 20:44:24,041 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 647 transitions. Word has length 265 [2018-04-09 20:44:24,041 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:24,042 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 647 transitions. [2018-04-09 20:44:24,042 INFO L460 AbstractCegarLoop]: Interpolant automaton has 55 states. [2018-04-09 20:44:24,042 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 647 transitions. [2018-04-09 20:44:24,044 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 273 [2018-04-09 20:44:24,044 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:24,044 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-09 20:44:24,044 INFO L408 AbstractCegarLoop]: === Iteration 21 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:24,045 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-09 20:44:24,050 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:24,079 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:24,083 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:24,469 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-09 20:44:24,469 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:24,947 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-09 20:44:24,968 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:44:24,968 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [37, 37] total 60 [2018-04-09 20:44:24,969 INFO L442 AbstractCegarLoop]: Interpolant automaton has 60 states [2018-04-09 20:44:24,969 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 60 interpolants. [2018-04-09 20:44:24,970 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=592, Invalid=2948, Unknown=0, NotChecked=0, Total=3540 [2018-04-09 20:44:24,970 INFO L87 Difference]: Start difference. First operand 581 states and 647 transitions. Second operand 60 states. [2018-04-09 20:44:25,672 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:25,672 INFO L93 Difference]: Finished difference Result 713 states and 793 transitions. [2018-04-09 20:44:25,672 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 48 states. [2018-04-09 20:44:25,673 INFO L78 Accepts]: Start accepts. Automaton has 60 states. Word has length 272 [2018-04-09 20:44:25,673 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:25,674 INFO L225 Difference]: With dead ends: 713 [2018-04-09 20:44:25,675 INFO L226 Difference]: Without dead ends: 581 [2018-04-09 20:44:25,676 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 565 GetRequests, 473 SyntacticMatches, 12 SemanticMatches, 80 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1677 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=1439, Invalid=5203, Unknown=0, NotChecked=0, Total=6642 [2018-04-09 20:44:25,676 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-04-09 20:44:25,713 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-04-09 20:44:25,713 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-04-09 20:44:25,714 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 646 transitions. [2018-04-09 20:44:25,714 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 646 transitions. Word has length 272 [2018-04-09 20:44:25,714 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:25,714 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 646 transitions. [2018-04-09 20:44:25,715 INFO L460 AbstractCegarLoop]: Interpolant automaton has 60 states. [2018-04-09 20:44:25,715 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 646 transitions. [2018-04-09 20:44:25,716 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 280 [2018-04-09 20:44:25,716 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:25,716 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-09 20:44:25,716 INFO L408 AbstractCegarLoop]: === Iteration 22 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:25,717 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-09 20:44:25,723 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:25,774 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:25,778 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:26,267 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-09 20:44:26,267 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:27,091 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-09 20:44:27,112 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:44:27,112 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [40, 40] total 65 [2018-04-09 20:44:27,113 INFO L442 AbstractCegarLoop]: Interpolant automaton has 65 states [2018-04-09 20:44:27,113 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 65 interpolants. [2018-04-09 20:44:27,114 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=687, Invalid=3473, Unknown=0, NotChecked=0, Total=4160 [2018-04-09 20:44:27,114 INFO L87 Difference]: Start difference. First operand 581 states and 646 transitions. Second operand 65 states. [2018-04-09 20:44:28,038 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:28,038 INFO L93 Difference]: Finished difference Result 713 states and 792 transitions. [2018-04-09 20:44:28,039 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 52 states. [2018-04-09 20:44:28,039 INFO L78 Accepts]: Start accepts. Automaton has 65 states. Word has length 279 [2018-04-09 20:44:28,039 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:28,042 INFO L225 Difference]: With dead ends: 713 [2018-04-09 20:44:28,042 INFO L226 Difference]: Without dead ends: 581 [2018-04-09 20:44:28,043 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 581 GetRequests, 481 SyntacticMatches, 13 SemanticMatches, 87 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1991 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=1683, Invalid=6149, Unknown=0, NotChecked=0, Total=7832 [2018-04-09 20:44:28,043 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-04-09 20:44:28,079 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-04-09 20:44:28,080 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-04-09 20:44:28,081 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 645 transitions. [2018-04-09 20:44:28,081 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 645 transitions. Word has length 279 [2018-04-09 20:44:28,081 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:28,081 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 645 transitions. [2018-04-09 20:44:28,081 INFO L460 AbstractCegarLoop]: Interpolant automaton has 65 states. [2018-04-09 20:44:28,081 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 645 transitions. [2018-04-09 20:44:28,083 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 287 [2018-04-09 20:44:28,083 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:28,083 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-09 20:44:28,083 INFO L408 AbstractCegarLoop]: === Iteration 23 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:28,083 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-09 20:44:28,088 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:28,119 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:28,124 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:28,730 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-09 20:44:28,730 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:29,384 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-09 20:44:29,405 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:44:29,405 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [43, 43] total 70 [2018-04-09 20:44:29,406 INFO L442 AbstractCegarLoop]: Interpolant automaton has 70 states [2018-04-09 20:44:29,406 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 70 interpolants. [2018-04-09 20:44:29,406 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=789, Invalid=4041, Unknown=0, NotChecked=0, Total=4830 [2018-04-09 20:44:29,407 INFO L87 Difference]: Start difference. First operand 581 states and 645 transitions. Second operand 70 states. [2018-04-09 20:44:30,229 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:30,229 INFO L93 Difference]: Finished difference Result 713 states and 791 transitions. [2018-04-09 20:44:30,230 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 56 states. [2018-04-09 20:44:30,230 INFO L78 Accepts]: Start accepts. Automaton has 70 states. Word has length 286 [2018-04-09 20:44:30,230 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:30,232 INFO L225 Difference]: With dead ends: 713 [2018-04-09 20:44:30,232 INFO L226 Difference]: Without dead ends: 581 [2018-04-09 20:44:30,233 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-09 20:44:30,233 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-04-09 20:44:30,270 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-04-09 20:44:30,270 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-04-09 20:44:30,271 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 644 transitions. [2018-04-09 20:44:30,272 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 644 transitions. Word has length 286 [2018-04-09 20:44:30,272 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:30,272 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 644 transitions. [2018-04-09 20:44:30,272 INFO L460 AbstractCegarLoop]: Interpolant automaton has 70 states. [2018-04-09 20:44:30,272 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 644 transitions. [2018-04-09 20:44:30,273 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 294 [2018-04-09 20:44:30,273 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:30,274 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-09 20:44:30,274 INFO L408 AbstractCegarLoop]: === Iteration 24 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:30,274 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-09 20:44:30,280 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:30,318 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:30,322 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:30,926 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-09 20:44:30,926 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:31,639 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-09 20:44:31,660 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:44:31,660 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [46, 46] total 75 [2018-04-09 20:44:31,661 INFO L442 AbstractCegarLoop]: Interpolant automaton has 75 states [2018-04-09 20:44:31,661 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 75 interpolants. [2018-04-09 20:44:31,661 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=898, Invalid=4652, Unknown=0, NotChecked=0, Total=5550 [2018-04-09 20:44:31,662 INFO L87 Difference]: Start difference. First operand 581 states and 644 transitions. Second operand 75 states. [2018-04-09 20:44:32,492 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:32,493 INFO L93 Difference]: Finished difference Result 713 states and 790 transitions. [2018-04-09 20:44:32,493 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 60 states. [2018-04-09 20:44:32,493 INFO L78 Accepts]: Start accepts. Automaton has 75 states. Word has length 293 [2018-04-09 20:44:32,493 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:32,495 INFO L225 Difference]: With dead ends: 713 [2018-04-09 20:44:32,495 INFO L226 Difference]: Without dead ends: 581 [2018-04-09 20:44:32,496 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-09 20:44:32,497 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-04-09 20:44:32,531 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-04-09 20:44:32,531 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-04-09 20:44:32,533 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 643 transitions. [2018-04-09 20:44:32,533 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 643 transitions. Word has length 293 [2018-04-09 20:44:32,533 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:32,533 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 643 transitions. [2018-04-09 20:44:32,533 INFO L460 AbstractCegarLoop]: Interpolant automaton has 75 states. [2018-04-09 20:44:32,533 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 643 transitions. [2018-04-09 20:44:32,535 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 301 [2018-04-09 20:44:32,535 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:32,536 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-09 20:44:32,536 INFO L408 AbstractCegarLoop]: === Iteration 25 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:32,536 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-09 20:44:32,545 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:32,584 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:32,590 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:33,221 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-09 20:44:33,222 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:34,036 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-09 20:44:34,057 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:44:34,057 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [49, 49] total 80 [2018-04-09 20:44:34,058 INFO L442 AbstractCegarLoop]: Interpolant automaton has 80 states [2018-04-09 20:44:34,058 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 80 interpolants. [2018-04-09 20:44:34,058 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1014, Invalid=5306, Unknown=0, NotChecked=0, Total=6320 [2018-04-09 20:44:34,059 INFO L87 Difference]: Start difference. First operand 581 states and 643 transitions. Second operand 80 states. [2018-04-09 20:44:35,072 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:35,073 INFO L93 Difference]: Finished difference Result 719 states and 796 transitions. [2018-04-09 20:44:35,073 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 64 states. [2018-04-09 20:44:35,073 INFO L78 Accepts]: Start accepts. Automaton has 80 states. Word has length 300 [2018-04-09 20:44:35,073 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:35,075 INFO L225 Difference]: With dead ends: 719 [2018-04-09 20:44:35,075 INFO L226 Difference]: Without dead ends: 581 [2018-04-09 20:44:35,076 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-09 20:44:35,077 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-04-09 20:44:35,112 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-04-09 20:44:35,113 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-04-09 20:44:35,114 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 642 transitions. [2018-04-09 20:44:35,114 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 642 transitions. Word has length 300 [2018-04-09 20:44:35,114 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:35,114 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 642 transitions. [2018-04-09 20:44:35,114 INFO L460 AbstractCegarLoop]: Interpolant automaton has 80 states. [2018-04-09 20:44:35,114 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 642 transitions. [2018-04-09 20:44:35,116 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 308 [2018-04-09 20:44:35,116 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:35,116 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-09 20:44:35,116 INFO L408 AbstractCegarLoop]: === Iteration 26 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:35,116 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-09 20:44:35,122 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:35,156 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:35,160 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:35,490 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-09 20:44:35,490 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:36,461 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-09 20:44:36,482 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:44:36,483 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [32, 32] total 63 [2018-04-09 20:44:36,483 INFO L442 AbstractCegarLoop]: Interpolant automaton has 64 states [2018-04-09 20:44:36,483 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 64 interpolants. [2018-04-09 20:44:36,484 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=606, Invalid=3426, Unknown=0, NotChecked=0, Total=4032 [2018-04-09 20:44:36,484 INFO L87 Difference]: Start difference. First operand 581 states and 642 transitions. Second operand 64 states. [2018-04-09 20:44:41,022 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:41,022 INFO L93 Difference]: Finished difference Result 714 states and 822 transitions. [2018-04-09 20:44:41,022 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 93 states. [2018-04-09 20:44:41,022 INFO L78 Accepts]: Start accepts. Automaton has 64 states. Word has length 307 [2018-04-09 20:44:41,023 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:41,025 INFO L225 Difference]: With dead ends: 714 [2018-04-09 20:44:41,025 INFO L226 Difference]: Without dead ends: 712 [2018-04-09 20:44:41,026 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-09 20:44:41,026 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 712 states. [2018-04-09 20:44:41,063 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 712 to 709. [2018-04-09 20:44:41,063 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 709 states. [2018-04-09 20:44:41,065 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 709 states to 709 states and 786 transitions. [2018-04-09 20:44:41,066 INFO L78 Accepts]: Start accepts. Automaton has 709 states and 786 transitions. Word has length 307 [2018-04-09 20:44:41,066 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:41,066 INFO L459 AbstractCegarLoop]: Abstraction has 709 states and 786 transitions. [2018-04-09 20:44:41,066 INFO L460 AbstractCegarLoop]: Interpolant automaton has 64 states. [2018-04-09 20:44:41,066 INFO L276 IsEmpty]: Start isEmpty. Operand 709 states and 786 transitions. [2018-04-09 20:44:41,068 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 444 [2018-04-09 20:44:41,068 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:41,068 INFO L355 BasicCegarLoop]: trace histogram [63, 62, 62, 62, 62, 62, 62, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-09 20:44:41,069 INFO L408 AbstractCegarLoop]: === Iteration 27 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:41,069 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-09 20:44:41,077 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:41,118 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:41,123 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:42,375 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-09 20:44:42,375 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:46,112 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-09 20:44:46,135 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:44:46,135 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [64, 64] total 127 [2018-04-09 20:44:46,136 INFO L442 AbstractCegarLoop]: Interpolant automaton has 128 states [2018-04-09 20:44:46,136 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 128 interpolants. [2018-04-09 20:44:46,137 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=4222, Invalid=12034, Unknown=0, NotChecked=0, Total=16256 [2018-04-09 20:44:46,137 INFO L87 Difference]: Start difference. First operand 709 states and 786 transitions. Second operand 128 states. [2018-04-09 20:44:51,670 WARN L151 SmtUtils]: Spent 266ms on a formula simplification. DAG size of input: 316 DAG size of output 6 [2018-04-09 20:44:52,149 WARN L151 SmtUtils]: Spent 250ms on a formula simplification. DAG size of input: 311 DAG size of output 6 [2018-04-09 20:44:52,634 WARN L151 SmtUtils]: Spent 249ms on a formula simplification. DAG size of input: 306 DAG size of output 6 [2018-04-09 20:44:53,100 WARN L151 SmtUtils]: Spent 229ms on a formula simplification. DAG size of input: 301 DAG size of output 6 [2018-04-09 20:44:53,565 WARN L151 SmtUtils]: Spent 233ms on a formula simplification. DAG size of input: 296 DAG size of output 6 [2018-04-09 20:44:54,032 WARN L151 SmtUtils]: Spent 228ms on a formula simplification. DAG size of input: 291 DAG size of output 6 [2018-04-09 20:44:54,489 WARN L151 SmtUtils]: Spent 214ms on a formula simplification. DAG size of input: 286 DAG size of output 6 [2018-04-09 20:44:54,950 WARN L151 SmtUtils]: Spent 205ms on a formula simplification. DAG size of input: 281 DAG size of output 6 [2018-04-09 20:44:55,397 WARN L151 SmtUtils]: Spent 209ms on a formula simplification. DAG size of input: 276 DAG size of output 6 [2018-04-09 20:44:55,823 WARN L151 SmtUtils]: Spent 187ms on a formula simplification. DAG size of input: 271 DAG size of output 6 [2018-04-09 20:44:56,239 WARN L151 SmtUtils]: Spent 179ms on a formula simplification. DAG size of input: 266 DAG size of output 6 [2018-04-09 20:44:56,681 WARN L151 SmtUtils]: Spent 185ms on a formula simplification. DAG size of input: 261 DAG size of output 6 [2018-04-09 20:44:57,097 WARN L151 SmtUtils]: Spent 177ms on a formula simplification. DAG size of input: 256 DAG size of output 6 [2018-04-09 20:44:57,513 WARN L151 SmtUtils]: Spent 174ms on a formula simplification. DAG size of input: 251 DAG size of output 6 [2018-04-09 20:44:57,928 WARN L151 SmtUtils]: Spent 176ms on a formula simplification. DAG size of input: 246 DAG size of output 6 [2018-04-09 20:44:58,327 WARN L151 SmtUtils]: Spent 159ms on a formula simplification. DAG size of input: 241 DAG size of output 6 [2018-04-09 20:44:58,725 WARN L151 SmtUtils]: Spent 151ms on a formula simplification. DAG size of input: 236 DAG size of output 6 [2018-04-09 20:44:59,105 WARN L151 SmtUtils]: Spent 145ms on a formula simplification. DAG size of input: 231 DAG size of output 6 [2018-04-09 20:44:59,485 WARN L151 SmtUtils]: Spent 146ms on a formula simplification. DAG size of input: 226 DAG size of output 6 [2018-04-09 20:44:59,850 WARN L151 SmtUtils]: Spent 133ms on a formula simplification. DAG size of input: 221 DAG size of output 6 [2018-04-09 20:45:00,210 WARN L151 SmtUtils]: Spent 128ms on a formula simplification. DAG size of input: 216 DAG size of output 6 [2018-04-09 20:45:00,563 WARN L151 SmtUtils]: Spent 121ms on a formula simplification. DAG size of input: 211 DAG size of output 6 [2018-04-09 20:45:00,920 WARN L151 SmtUtils]: Spent 126ms on a formula simplification. DAG size of input: 206 DAG size of output 6 [2018-04-09 20:45:01,296 WARN L151 SmtUtils]: Spent 138ms on a formula simplification. DAG size of input: 201 DAG size of output 6 [2018-04-09 20:45:01,662 WARN L151 SmtUtils]: Spent 126ms on a formula simplification. DAG size of input: 196 DAG size of output 6 [2018-04-09 20:45:02,013 WARN L151 SmtUtils]: Spent 114ms on a formula simplification. DAG size of input: 191 DAG size of output 6 [2018-04-09 20:45:02,351 WARN L151 SmtUtils]: Spent 104ms on a formula simplification. DAG size of input: 186 DAG size of output 6 [2018-04-09 20:45:02,697 WARN L151 SmtUtils]: Spent 105ms on a formula simplification. DAG size of input: 181 DAG size of output 6 [2018-04-09 20:45:03,020 WARN L151 SmtUtils]: Spent 100ms on a formula simplification. DAG size of input: 176 DAG size of output 6 [2018-04-09 20:45:15,674 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:45:15,674 INFO L93 Difference]: Finished difference Result 29322 states and 33062 transitions. [2018-04-09 20:45:15,674 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 128 states. [2018-04-09 20:45:15,675 INFO L78 Accepts]: Start accepts. Automaton has 128 states. Word has length 443 [2018-04-09 20:45:15,675 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:45:15,760 INFO L225 Difference]: With dead ends: 29322 [2018-04-09 20:45:15,761 INFO L226 Difference]: Without dead ends: 29319 [2018-04-09 20:45:15,772 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 947 GetRequests, 759 SyntacticMatches, 0 SemanticMatches, 188 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1891 ImplicationChecksByTransitivity, 22.0s TimeCoverageRelationStatistics Valid=12158, Invalid=23752, Unknown=0, NotChecked=0, Total=35910 [2018-04-09 20:45:15,789 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29319 states. [2018-04-09 20:45:16,275 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29319 to 1157. [2018-04-09 20:45:16,275 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-09 20:45:16,277 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1298 transitions. [2018-04-09 20:45:16,277 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1298 transitions. Word has length 443 [2018-04-09 20:45:16,277 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:45:16,277 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1298 transitions. [2018-04-09 20:45:16,277 INFO L460 AbstractCegarLoop]: Interpolant automaton has 128 states. [2018-04-09 20:45:16,277 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1298 transitions. [2018-04-09 20:45:16,281 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 500 [2018-04-09 20:45:16,281 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:45:16,282 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-09 20:45:16,282 INFO L408 AbstractCegarLoop]: === Iteration 28 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:45:16,282 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-09 20:45:16,291 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:45:16,365 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:45:16,371 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:45:17,281 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-09 20:45:17,316 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:45:18,290 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-09 20:45:18,311 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:45:18,311 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [52, 52] total 85 [2018-04-09 20:45:18,312 INFO L442 AbstractCegarLoop]: Interpolant automaton has 85 states [2018-04-09 20:45:18,312 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 85 interpolants. [2018-04-09 20:45:18,312 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1137, Invalid=6003, Unknown=0, NotChecked=0, Total=7140 [2018-04-09 20:45:18,313 INFO L87 Difference]: Start difference. First operand 1157 states and 1298 transitions. Second operand 85 states. [2018-04-09 20:45:19,551 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:45:19,552 INFO L93 Difference]: Finished difference Result 1417 states and 1588 transitions. [2018-04-09 20:45:19,552 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 68 states. [2018-04-09 20:45:19,552 INFO L78 Accepts]: Start accepts. Automaton has 85 states. Word has length 499 [2018-04-09 20:45:19,552 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:45:19,554 INFO L225 Difference]: With dead ends: 1417 [2018-04-09 20:45:19,555 INFO L226 Difference]: Without dead ends: 1157 [2018-04-09 20:45:19,557 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1029 GetRequests, 897 SyntacticMatches, 17 SemanticMatches, 115 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3517 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=2849, Invalid=10723, Unknown=0, NotChecked=0, Total=13572 [2018-04-09 20:45:19,557 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-09 20:45:19,774 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-09 20:45:19,774 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-09 20:45:19,775 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1297 transitions. [2018-04-09 20:45:19,776 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1297 transitions. Word has length 499 [2018-04-09 20:45:19,776 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:45:19,776 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1297 transitions. [2018-04-09 20:45:19,776 INFO L460 AbstractCegarLoop]: Interpolant automaton has 85 states. [2018-04-09 20:45:19,776 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1297 transitions. [2018-04-09 20:45:19,778 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 507 [2018-04-09 20:45:19,779 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:45:19,779 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-09 20:45:19,779 INFO L408 AbstractCegarLoop]: === Iteration 29 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:45:19,779 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-09 20:45:19,785 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:45:19,850 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:45:19,856 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:45:20,841 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-09 20:45:20,842 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:45:21,959 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-09 20:45:21,981 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:45:21,981 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [55, 55] total 90 [2018-04-09 20:45:21,982 INFO L442 AbstractCegarLoop]: Interpolant automaton has 90 states [2018-04-09 20:45:21,982 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 90 interpolants. [2018-04-09 20:45:21,983 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1267, Invalid=6743, Unknown=0, NotChecked=0, Total=8010 [2018-04-09 20:45:21,983 INFO L87 Difference]: Start difference. First operand 1157 states and 1297 transitions. Second operand 90 states. [2018-04-09 20:45:23,427 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:45:23,427 INFO L93 Difference]: Finished difference Result 1417 states and 1587 transitions. [2018-04-09 20:45:23,427 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 72 states. [2018-04-09 20:45:23,427 INFO L78 Accepts]: Start accepts. Automaton has 90 states. Word has length 506 [2018-04-09 20:45:23,428 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:45:23,429 INFO L225 Difference]: With dead ends: 1417 [2018-04-09 20:45:23,429 INFO L226 Difference]: Without dead ends: 1157 [2018-04-09 20:45:23,431 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1045 GetRequests, 905 SyntacticMatches, 18 SemanticMatches, 122 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3966 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=3188, Invalid=12064, Unknown=0, NotChecked=0, Total=15252 [2018-04-09 20:45:23,432 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-09 20:45:23,571 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-09 20:45:23,571 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-09 20:45:23,572 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1296 transitions. [2018-04-09 20:45:23,573 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1296 transitions. Word has length 506 [2018-04-09 20:45:23,573 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:45:23,573 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1296 transitions. [2018-04-09 20:45:23,573 INFO L460 AbstractCegarLoop]: Interpolant automaton has 90 states. [2018-04-09 20:45:23,573 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1296 transitions. [2018-04-09 20:45:23,575 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 514 [2018-04-09 20:45:23,575 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:45:23,576 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-09 20:45:23,576 INFO L408 AbstractCegarLoop]: === Iteration 30 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:45:23,576 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-09 20:45:23,584 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:45:23,650 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:45:23,656 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:45:24,601 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-09 20:45:24,601 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:45:25,861 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-09 20:45:25,894 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:45:25,894 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [58, 58] total 95 [2018-04-09 20:45:25,895 INFO L442 AbstractCegarLoop]: Interpolant automaton has 95 states [2018-04-09 20:45:25,896 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 95 interpolants. [2018-04-09 20:45:25,897 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1404, Invalid=7526, Unknown=0, NotChecked=0, Total=8930 [2018-04-09 20:45:25,897 INFO L87 Difference]: Start difference. First operand 1157 states and 1296 transitions. Second operand 95 states. [2018-04-09 20:45:27,419 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:45:27,419 INFO L93 Difference]: Finished difference Result 1417 states and 1586 transitions. [2018-04-09 20:45:27,450 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 76 states. [2018-04-09 20:45:27,450 INFO L78 Accepts]: Start accepts. Automaton has 95 states. Word has length 513 [2018-04-09 20:45:27,451 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:45:27,453 INFO L225 Difference]: With dead ends: 1417 [2018-04-09 20:45:27,453 INFO L226 Difference]: Without dead ends: 1157 [2018-04-09 20:45:27,455 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1061 GetRequests, 913 SyntacticMatches, 19 SemanticMatches, 129 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4442 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=3546, Invalid=13484, Unknown=0, NotChecked=0, Total=17030 [2018-04-09 20:45:27,456 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-09 20:45:27,697 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-09 20:45:27,697 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-09 20:45:27,700 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1295 transitions. [2018-04-09 20:45:27,700 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1295 transitions. Word has length 513 [2018-04-09 20:45:27,700 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:45:27,700 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1295 transitions. [2018-04-09 20:45:27,700 INFO L460 AbstractCegarLoop]: Interpolant automaton has 95 states. [2018-04-09 20:45:27,701 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1295 transitions. [2018-04-09 20:45:27,704 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 521 [2018-04-09 20:45:27,704 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:45:27,705 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-09 20:45:27,705 INFO L408 AbstractCegarLoop]: === Iteration 31 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:45:27,705 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-09 20:45:27,714 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:45:27,797 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:45:27,807 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:45:29,157 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-09 20:45:29,158 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:45:30,470 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-09 20:45:30,491 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:45:30,491 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [61, 61] total 100 [2018-04-09 20:45:30,492 INFO L442 AbstractCegarLoop]: Interpolant automaton has 100 states [2018-04-09 20:45:30,492 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 100 interpolants. [2018-04-09 20:45:30,493 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1548, Invalid=8352, Unknown=0, NotChecked=0, Total=9900 [2018-04-09 20:45:30,493 INFO L87 Difference]: Start difference. First operand 1157 states and 1295 transitions. Second operand 100 states. [2018-04-09 20:45:32,171 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:45:32,171 INFO L93 Difference]: Finished difference Result 1417 states and 1585 transitions. [2018-04-09 20:45:32,171 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 80 states. [2018-04-09 20:45:32,171 INFO L78 Accepts]: Start accepts. Automaton has 100 states. Word has length 520 [2018-04-09 20:45:32,172 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:45:32,173 INFO L225 Difference]: With dead ends: 1417 [2018-04-09 20:45:32,174 INFO L226 Difference]: Without dead ends: 1157 [2018-04-09 20:45:32,175 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1077 GetRequests, 921 SyntacticMatches, 20 SemanticMatches, 136 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4945 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=3923, Invalid=14983, Unknown=0, NotChecked=0, Total=18906 [2018-04-09 20:45:32,176 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-09 20:45:32,317 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-09 20:45:32,317 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-09 20:45:32,318 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1294 transitions. [2018-04-09 20:45:32,319 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1294 transitions. Word has length 520 [2018-04-09 20:45:32,319 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:45:32,319 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1294 transitions. [2018-04-09 20:45:32,319 INFO L460 AbstractCegarLoop]: Interpolant automaton has 100 states. [2018-04-09 20:45:32,319 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1294 transitions. [2018-04-09 20:45:32,322 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 528 [2018-04-09 20:45:32,322 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:45:32,322 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-09 20:45:32,322 INFO L408 AbstractCegarLoop]: === Iteration 32 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:45:32,323 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-09 20:45:32,329 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:45:32,401 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:45:32,410 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:45:33,608 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-09 20:45:33,608 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:45:35,071 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-09 20:45:35,092 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:45:35,092 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [64, 64] total 105 [2018-04-09 20:45:35,093 INFO L442 AbstractCegarLoop]: Interpolant automaton has 105 states [2018-04-09 20:45:35,093 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 105 interpolants. [2018-04-09 20:45:35,094 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1699, Invalid=9221, Unknown=0, NotChecked=0, Total=10920 [2018-04-09 20:45:35,094 INFO L87 Difference]: Start difference. First operand 1157 states and 1294 transitions. Second operand 105 states. [2018-04-09 20:45:36,783 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:45:36,784 INFO L93 Difference]: Finished difference Result 1417 states and 1584 transitions. [2018-04-09 20:45:36,784 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 84 states. [2018-04-09 20:45:36,784 INFO L78 Accepts]: Start accepts. Automaton has 105 states. Word has length 527 [2018-04-09 20:45:36,784 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:45:36,785 INFO L225 Difference]: With dead ends: 1417 [2018-04-09 20:45:36,785 INFO L226 Difference]: Without dead ends: 1157 [2018-04-09 20:45:36,787 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1093 GetRequests, 929 SyntacticMatches, 21 SemanticMatches, 143 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5475 ImplicationChecksByTransitivity, 3.2s TimeCoverageRelationStatistics Valid=4319, Invalid=16561, Unknown=0, NotChecked=0, Total=20880 [2018-04-09 20:45:36,787 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-09 20:45:36,920 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-09 20:45:36,920 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-09 20:45:36,922 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1293 transitions. [2018-04-09 20:45:36,922 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1293 transitions. Word has length 527 [2018-04-09 20:45:36,922 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:45:36,922 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1293 transitions. [2018-04-09 20:45:36,922 INFO L460 AbstractCegarLoop]: Interpolant automaton has 105 states. [2018-04-09 20:45:36,922 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1293 transitions. [2018-04-09 20:45:36,924 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 535 [2018-04-09 20:45:36,925 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:45:36,925 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-09 20:45:36,925 INFO L408 AbstractCegarLoop]: === Iteration 33 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:45:36,925 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-09 20:45:36,931 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:45:36,985 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:45:36,990 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:45:38,140 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-09 20:45:38,140 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:45:39,741 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-09 20:45:39,762 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:45:39,762 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [67, 67] total 110 [2018-04-09 20:45:39,763 INFO L442 AbstractCegarLoop]: Interpolant automaton has 110 states [2018-04-09 20:45:39,763 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 110 interpolants. [2018-04-09 20:45:39,764 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1857, Invalid=10133, Unknown=0, NotChecked=0, Total=11990 [2018-04-09 20:45:39,764 INFO L87 Difference]: Start difference. First operand 1157 states and 1293 transitions. Second operand 110 states. [2018-04-09 20:45:41,633 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:45:41,633 INFO L93 Difference]: Finished difference Result 1417 states and 1583 transitions. [2018-04-09 20:45:41,633 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 88 states. [2018-04-09 20:45:41,633 INFO L78 Accepts]: Start accepts. Automaton has 110 states. Word has length 534 [2018-04-09 20:45:41,633 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:45:41,634 INFO L225 Difference]: With dead ends: 1417 [2018-04-09 20:45:41,634 INFO L226 Difference]: Without dead ends: 1157 [2018-04-09 20:45:41,636 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1109 GetRequests, 937 SyntacticMatches, 22 SemanticMatches, 150 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6032 ImplicationChecksByTransitivity, 3.3s TimeCoverageRelationStatistics Valid=4734, Invalid=18218, Unknown=0, NotChecked=0, Total=22952 [2018-04-09 20:45:41,637 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-09 20:45:41,769 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-09 20:45:41,769 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-09 20:45:41,770 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1292 transitions. [2018-04-09 20:45:41,770 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1292 transitions. Word has length 534 [2018-04-09 20:45:41,771 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:45:41,771 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1292 transitions. [2018-04-09 20:45:41,771 INFO L460 AbstractCegarLoop]: Interpolant automaton has 110 states. [2018-04-09 20:45:41,771 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1292 transitions. [2018-04-09 20:45:41,773 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 542 [2018-04-09 20:45:41,773 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:45:41,773 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-09 20:45:41,773 INFO L408 AbstractCegarLoop]: === Iteration 34 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:45:41,774 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-09 20:45:41,779 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:45:41,830 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:45:41,836 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:45:43,093 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-09 20:45:43,093 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:45:44,749 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-09 20:45:44,770 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:45:44,770 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [70, 70] total 115 [2018-04-09 20:45:44,771 INFO L442 AbstractCegarLoop]: Interpolant automaton has 115 states [2018-04-09 20:45:44,771 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 115 interpolants. [2018-04-09 20:45:44,772 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2022, Invalid=11088, Unknown=0, NotChecked=0, Total=13110 [2018-04-09 20:45:44,772 INFO L87 Difference]: Start difference. First operand 1157 states and 1292 transitions. Second operand 115 states. [2018-04-09 20:45:46,738 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:45:46,738 INFO L93 Difference]: Finished difference Result 1417 states and 1582 transitions. [2018-04-09 20:45:46,738 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 92 states. [2018-04-09 20:45:46,738 INFO L78 Accepts]: Start accepts. Automaton has 115 states. Word has length 541 [2018-04-09 20:45:46,739 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:45:46,739 INFO L225 Difference]: With dead ends: 1417 [2018-04-09 20:45:46,739 INFO L226 Difference]: Without dead ends: 1157 [2018-04-09 20:45:46,741 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1125 GetRequests, 945 SyntacticMatches, 23 SemanticMatches, 157 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6616 ImplicationChecksByTransitivity, 3.5s TimeCoverageRelationStatistics Valid=5168, Invalid=19954, Unknown=0, NotChecked=0, Total=25122 [2018-04-09 20:45:46,741 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-09 20:45:46,873 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-09 20:45:46,873 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-09 20:45:46,874 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1291 transitions. [2018-04-09 20:45:46,874 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1291 transitions. Word has length 541 [2018-04-09 20:45:46,874 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:45:46,874 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1291 transitions. [2018-04-09 20:45:46,875 INFO L460 AbstractCegarLoop]: Interpolant automaton has 115 states. [2018-04-09 20:45:46,875 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1291 transitions. [2018-04-09 20:45:46,877 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 549 [2018-04-09 20:45:46,877 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:45:46,877 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-09 20:45:46,877 INFO L408 AbstractCegarLoop]: === Iteration 35 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:45:46,878 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-09 20:45:46,883 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:45:46,940 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:45:46,946 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:45:48,259 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-09 20:45:48,259 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:45:50,079 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-09 20:45:50,100 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:45:50,106 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [73, 73] total 120 [2018-04-09 20:45:50,106 INFO L442 AbstractCegarLoop]: Interpolant automaton has 120 states [2018-04-09 20:45:50,107 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 120 interpolants. [2018-04-09 20:45:50,108 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2194, Invalid=12086, Unknown=0, NotChecked=0, Total=14280 [2018-04-09 20:45:50,108 INFO L87 Difference]: Start difference. First operand 1157 states and 1291 transitions. Second operand 120 states. [2018-04-09 20:45:52,439 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:45:52,439 INFO L93 Difference]: Finished difference Result 1417 states and 1581 transitions. [2018-04-09 20:45:52,439 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 96 states. [2018-04-09 20:45:52,439 INFO L78 Accepts]: Start accepts. Automaton has 120 states. Word has length 548 [2018-04-09 20:45:52,439 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:45:52,440 INFO L225 Difference]: With dead ends: 1417 [2018-04-09 20:45:52,440 INFO L226 Difference]: Without dead ends: 1157 [2018-04-09 20:45:52,442 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1141 GetRequests, 953 SyntacticMatches, 24 SemanticMatches, 164 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7227 ImplicationChecksByTransitivity, 3.8s TimeCoverageRelationStatistics Valid=5621, Invalid=21769, Unknown=0, NotChecked=0, Total=27390 [2018-04-09 20:45:52,443 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-09 20:45:52,575 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-09 20:45:52,575 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-09 20:45:52,576 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1290 transitions. [2018-04-09 20:45:52,576 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1290 transitions. Word has length 548 [2018-04-09 20:45:52,577 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:45:52,577 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1290 transitions. [2018-04-09 20:45:52,577 INFO L460 AbstractCegarLoop]: Interpolant automaton has 120 states. [2018-04-09 20:45:52,577 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1290 transitions. [2018-04-09 20:45:52,579 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 556 [2018-04-09 20:45:52,579 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:45:52,579 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-09 20:45:52,579 INFO L408 AbstractCegarLoop]: === Iteration 36 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:45:52,580 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-09 20:45:52,586 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:45:52,644 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:45:52,649 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:45:54,052 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-09 20:45:54,052 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:45:55,999 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-09 20:45:56,020 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:45:56,020 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [76, 76] total 125 [2018-04-09 20:45:56,021 INFO L442 AbstractCegarLoop]: Interpolant automaton has 125 states [2018-04-09 20:45:56,021 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 125 interpolants. [2018-04-09 20:45:56,022 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2373, Invalid=13127, Unknown=0, NotChecked=0, Total=15500 [2018-04-09 20:45:56,022 INFO L87 Difference]: Start difference. First operand 1157 states and 1290 transitions. Second operand 125 states. [2018-04-09 20:45:58,197 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:45:58,197 INFO L93 Difference]: Finished difference Result 1417 states and 1580 transitions. [2018-04-09 20:45:58,197 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 100 states. [2018-04-09 20:45:58,197 INFO L78 Accepts]: Start accepts. Automaton has 125 states. Word has length 555 [2018-04-09 20:45:58,198 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:45:58,198 INFO L225 Difference]: With dead ends: 1417 [2018-04-09 20:45:58,198 INFO L226 Difference]: Without dead ends: 1157 [2018-04-09 20:45:58,201 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1157 GetRequests, 961 SyntacticMatches, 25 SemanticMatches, 171 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7865 ImplicationChecksByTransitivity, 4.1s TimeCoverageRelationStatistics Valid=6093, Invalid=23663, Unknown=0, NotChecked=0, Total=29756 [2018-04-09 20:45:58,202 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-09 20:45:58,354 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-09 20:45:58,354 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-09 20:45:58,355 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1289 transitions. [2018-04-09 20:45:58,355 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1289 transitions. Word has length 555 [2018-04-09 20:45:58,356 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:45:58,356 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1289 transitions. [2018-04-09 20:45:58,356 INFO L460 AbstractCegarLoop]: Interpolant automaton has 125 states. [2018-04-09 20:45:58,356 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1289 transitions. [2018-04-09 20:45:58,358 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 563 [2018-04-09 20:45:58,358 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:45:58,358 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-09 20:45:58,359 INFO L408 AbstractCegarLoop]: === Iteration 37 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:45:58,359 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-09 20:45:58,364 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:45:58,419 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:45:58,424 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:45:59,933 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-09 20:45:59,933 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:46:02,258 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-09 20:46:02,279 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:46:02,279 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [79, 79] total 130 [2018-04-09 20:46:02,280 INFO L442 AbstractCegarLoop]: Interpolant automaton has 130 states [2018-04-09 20:46:02,280 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 130 interpolants. [2018-04-09 20:46:02,281 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2559, Invalid=14211, Unknown=0, NotChecked=0, Total=16770 [2018-04-09 20:46:02,281 INFO L87 Difference]: Start difference. First operand 1157 states and 1289 transitions. Second operand 130 states. [2018-04-09 20:46:04,804 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:46:04,804 INFO L93 Difference]: Finished difference Result 1417 states and 1579 transitions. [2018-04-09 20:46:04,804 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 104 states. [2018-04-09 20:46:04,804 INFO L78 Accepts]: Start accepts. Automaton has 130 states. Word has length 562 [2018-04-09 20:46:04,805 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:46:04,806 INFO L225 Difference]: With dead ends: 1417 [2018-04-09 20:46:04,806 INFO L226 Difference]: Without dead ends: 1157 [2018-04-09 20:46:04,807 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1173 GetRequests, 969 SyntacticMatches, 26 SemanticMatches, 178 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8530 ImplicationChecksByTransitivity, 4.7s TimeCoverageRelationStatistics Valid=6584, Invalid=25636, Unknown=0, NotChecked=0, Total=32220 [2018-04-09 20:46:04,808 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-09 20:46:04,945 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-09 20:46:04,945 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-09 20:46:04,946 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1288 transitions. [2018-04-09 20:46:04,947 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1288 transitions. Word has length 562 [2018-04-09 20:46:04,947 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:46:04,947 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1288 transitions. [2018-04-09 20:46:04,947 INFO L460 AbstractCegarLoop]: Interpolant automaton has 130 states. [2018-04-09 20:46:04,947 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1288 transitions. [2018-04-09 20:46:04,949 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 570 [2018-04-09 20:46:04,950 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:46:04,950 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-09 20:46:04,950 INFO L408 AbstractCegarLoop]: === Iteration 38 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:46:04,950 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-09 20:46:04,956 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:46:05,021 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:46:05,026 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:46:06,643 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-09 20:46:06,643 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:46:08,913 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-09 20:46:08,934 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:46:08,934 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [82, 82] total 135 [2018-04-09 20:46:08,935 INFO L442 AbstractCegarLoop]: Interpolant automaton has 135 states [2018-04-09 20:46:08,935 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 135 interpolants. [2018-04-09 20:46:08,936 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2752, Invalid=15338, Unknown=0, NotChecked=0, Total=18090 [2018-04-09 20:46:08,936 INFO L87 Difference]: Start difference. First operand 1157 states and 1288 transitions. Second operand 135 states. [2018-04-09 20:46:11,714 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:46:11,714 INFO L93 Difference]: Finished difference Result 1417 states and 1578 transitions. [2018-04-09 20:46:11,714 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 108 states. [2018-04-09 20:46:11,715 INFO L78 Accepts]: Start accepts. Automaton has 135 states. Word has length 569 [2018-04-09 20:46:11,715 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:46:11,716 INFO L225 Difference]: With dead ends: 1417 [2018-04-09 20:46:11,716 INFO L226 Difference]: Without dead ends: 1157 [2018-04-09 20:46:11,717 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1189 GetRequests, 977 SyntacticMatches, 27 SemanticMatches, 185 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9222 ImplicationChecksByTransitivity, 4.8s TimeCoverageRelationStatistics Valid=7094, Invalid=27688, Unknown=0, NotChecked=0, Total=34782 [2018-04-09 20:46:11,718 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-09 20:46:11,850 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-09 20:46:11,851 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-09 20:46:11,852 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1287 transitions. [2018-04-09 20:46:11,852 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1287 transitions. Word has length 569 [2018-04-09 20:46:11,852 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:46:11,852 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1287 transitions. [2018-04-09 20:46:11,852 INFO L460 AbstractCegarLoop]: Interpolant automaton has 135 states. [2018-04-09 20:46:11,852 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1287 transitions. [2018-04-09 20:46:11,854 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 577 [2018-04-09 20:46:11,855 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:46:11,855 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-09 20:46:11,855 INFO L408 AbstractCegarLoop]: === Iteration 39 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:46:11,855 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-09 20:46:11,861 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:46:11,917 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:46:11,923 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:46:13,665 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-09 20:46:13,665 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:46:16,182 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-09 20:46:16,203 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:46:16,203 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [85, 85] total 140 [2018-04-09 20:46:16,204 INFO L442 AbstractCegarLoop]: Interpolant automaton has 140 states [2018-04-09 20:46:16,204 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 140 interpolants. [2018-04-09 20:46:16,205 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2952, Invalid=16508, Unknown=0, NotChecked=0, Total=19460 [2018-04-09 20:46:16,205 INFO L87 Difference]: Start difference. First operand 1157 states and 1287 transitions. Second operand 140 states. [2018-04-09 20:46:18,820 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:46:18,820 INFO L93 Difference]: Finished difference Result 1417 states and 1577 transitions. [2018-04-09 20:46:18,820 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 112 states. [2018-04-09 20:46:18,820 INFO L78 Accepts]: Start accepts. Automaton has 140 states. Word has length 576 [2018-04-09 20:46:18,821 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:46:18,821 INFO L225 Difference]: With dead ends: 1417 [2018-04-09 20:46:18,822 INFO L226 Difference]: Without dead ends: 1157 [2018-04-09 20:46:18,823 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1205 GetRequests, 985 SyntacticMatches, 28 SemanticMatches, 192 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9941 ImplicationChecksByTransitivity, 5.3s TimeCoverageRelationStatistics Valid=7623, Invalid=29819, Unknown=0, NotChecked=0, Total=37442 [2018-04-09 20:46:18,824 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-09 20:46:18,969 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-09 20:46:18,969 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-09 20:46:18,970 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1286 transitions. [2018-04-09 20:46:18,971 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1286 transitions. Word has length 576 [2018-04-09 20:46:18,971 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:46:18,971 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1286 transitions. [2018-04-09 20:46:18,971 INFO L460 AbstractCegarLoop]: Interpolant automaton has 140 states. [2018-04-09 20:46:18,971 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1286 transitions. [2018-04-09 20:46:18,973 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 584 [2018-04-09 20:46:18,974 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:46:18,974 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-09 20:46:18,974 INFO L408 AbstractCegarLoop]: === Iteration 40 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:46:18,974 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-09 20:46:18,980 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:46:19,037 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:46:19,042 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:46:20,866 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-09 20:46:20,866 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:46:23,407 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-09 20:46:23,428 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:46:23,428 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [88, 88] total 145 [2018-04-09 20:46:23,429 INFO L442 AbstractCegarLoop]: Interpolant automaton has 145 states [2018-04-09 20:46:23,429 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 145 interpolants. [2018-04-09 20:46:23,430 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3159, Invalid=17721, Unknown=0, NotChecked=0, Total=20880 [2018-04-09 20:46:23,430 INFO L87 Difference]: Start difference. First operand 1157 states and 1286 transitions. Second operand 145 states. [2018-04-09 20:46:26,505 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:46:26,505 INFO L93 Difference]: Finished difference Result 1417 states and 1576 transitions. [2018-04-09 20:46:26,505 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 116 states. [2018-04-09 20:46:26,505 INFO L78 Accepts]: Start accepts. Automaton has 145 states. Word has length 583 [2018-04-09 20:46:26,506 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:46:26,506 INFO L225 Difference]: With dead ends: 1417 [2018-04-09 20:46:26,506 INFO L226 Difference]: Without dead ends: 1157 [2018-04-09 20:46:26,508 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1221 GetRequests, 993 SyntacticMatches, 29 SemanticMatches, 199 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10687 ImplicationChecksByTransitivity, 5.4s TimeCoverageRelationStatistics Valid=8171, Invalid=32029, Unknown=0, NotChecked=0, Total=40200 [2018-04-09 20:46:26,509 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-09 20:46:26,639 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-09 20:46:26,640 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-09 20:46:26,640 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1285 transitions. [2018-04-09 20:46:26,641 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1285 transitions. Word has length 583 [2018-04-09 20:46:26,641 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:46:26,641 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1285 transitions. [2018-04-09 20:46:26,641 INFO L460 AbstractCegarLoop]: Interpolant automaton has 145 states. [2018-04-09 20:46:26,641 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1285 transitions. [2018-04-09 20:46:26,643 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 591 [2018-04-09 20:46:26,644 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:46:26,644 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-09 20:46:26,644 INFO L408 AbstractCegarLoop]: === Iteration 41 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:46:26,644 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-09 20:46:26,650 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:46:26,710 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:46:26,716 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:46:28,625 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-09 20:46:28,626 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:46:31,354 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-09 20:46:31,375 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:46:31,376 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [91, 91] total 150 [2018-04-09 20:46:31,376 INFO L442 AbstractCegarLoop]: Interpolant automaton has 150 states [2018-04-09 20:46:31,377 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 150 interpolants. [2018-04-09 20:46:31,377 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3373, Invalid=18977, Unknown=0, NotChecked=0, Total=22350 [2018-04-09 20:46:31,378 INFO L87 Difference]: Start difference. First operand 1157 states and 1285 transitions. Second operand 150 states. [2018-04-09 20:46:34,148 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:46:34,148 INFO L93 Difference]: Finished difference Result 1417 states and 1575 transitions. [2018-04-09 20:46:34,148 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 120 states. [2018-04-09 20:46:34,149 INFO L78 Accepts]: Start accepts. Automaton has 150 states. Word has length 590 [2018-04-09 20:46:34,149 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:46:34,150 INFO L225 Difference]: With dead ends: 1417 [2018-04-09 20:46:34,150 INFO L226 Difference]: Without dead ends: 1157 [2018-04-09 20:46:34,152 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1237 GetRequests, 1001 SyntacticMatches, 30 SemanticMatches, 206 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11460 ImplicationChecksByTransitivity, 5.7s TimeCoverageRelationStatistics Valid=8738, Invalid=34318, Unknown=0, NotChecked=0, Total=43056 [2018-04-09 20:46:34,152 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-09 20:46:34,284 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-09 20:46:34,284 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-09 20:46:34,285 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1284 transitions. [2018-04-09 20:46:34,285 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1284 transitions. Word has length 590 [2018-04-09 20:46:34,286 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:46:34,286 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1284 transitions. [2018-04-09 20:46:34,286 INFO L460 AbstractCegarLoop]: Interpolant automaton has 150 states. [2018-04-09 20:46:34,286 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1284 transitions. [2018-04-09 20:46:34,288 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 598 [2018-04-09 20:46:34,288 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:46:34,289 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-09 20:46:34,289 INFO L408 AbstractCegarLoop]: === Iteration 42 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:46:34,289 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-09 20:46:34,295 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:46:34,355 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:46:34,360 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:46:36,387 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-09 20:46:36,387 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:46:39,241 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-09 20:46:39,262 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:46:39,263 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [94, 94] total 155 [2018-04-09 20:46:39,263 INFO L442 AbstractCegarLoop]: Interpolant automaton has 155 states [2018-04-09 20:46:39,264 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 155 interpolants. [2018-04-09 20:46:39,265 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3594, Invalid=20276, Unknown=0, NotChecked=0, Total=23870 [2018-04-09 20:46:39,265 INFO L87 Difference]: Start difference. First operand 1157 states and 1284 transitions. Second operand 155 states. [2018-04-09 20:46:42,557 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:46:42,557 INFO L93 Difference]: Finished difference Result 1417 states and 1574 transitions. [2018-04-09 20:46:42,557 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 124 states. [2018-04-09 20:46:42,557 INFO L78 Accepts]: Start accepts. Automaton has 155 states. Word has length 597 [2018-04-09 20:46:42,558 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:46:42,558 INFO L225 Difference]: With dead ends: 1417 [2018-04-09 20:46:42,558 INFO L226 Difference]: Without dead ends: 1157 [2018-04-09 20:46:42,560 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1253 GetRequests, 1009 SyntacticMatches, 31 SemanticMatches, 213 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12260 ImplicationChecksByTransitivity, 6.1s TimeCoverageRelationStatistics Valid=9324, Invalid=36686, Unknown=0, NotChecked=0, Total=46010 [2018-04-09 20:46:42,561 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-09 20:46:42,692 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-09 20:46:42,692 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-09 20:46:42,693 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1283 transitions. [2018-04-09 20:46:42,693 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1283 transitions. Word has length 597 [2018-04-09 20:46:42,693 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:46:42,693 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1283 transitions. [2018-04-09 20:46:42,693 INFO L460 AbstractCegarLoop]: Interpolant automaton has 155 states. [2018-04-09 20:46:42,693 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1283 transitions. [2018-04-09 20:46:42,696 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 605 [2018-04-09 20:46:42,696 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:46:42,696 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-09 20:46:42,696 INFO L408 AbstractCegarLoop]: === Iteration 43 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:46:42,697 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-09 20:46:42,705 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:46:42,770 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:46:42,776 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:46:44,905 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-09 20:46:44,905 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:46:47,968 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-09 20:46:47,989 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:46:47,989 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [97, 97] total 160 [2018-04-09 20:46:47,990 INFO L442 AbstractCegarLoop]: Interpolant automaton has 160 states [2018-04-09 20:46:47,991 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 160 interpolants. [2018-04-09 20:46:47,991 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3822, Invalid=21618, Unknown=0, NotChecked=0, Total=25440 [2018-04-09 20:46:47,992 INFO L87 Difference]: Start difference. First operand 1157 states and 1283 transitions. Second operand 160 states. [2018-04-09 20:46:51,409 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:46:51,409 INFO L93 Difference]: Finished difference Result 1423 states and 1580 transitions. [2018-04-09 20:46:51,409 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 128 states. [2018-04-09 20:46:51,409 INFO L78 Accepts]: Start accepts. Automaton has 160 states. Word has length 604 [2018-04-09 20:46:51,410 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:46:51,410 INFO L225 Difference]: With dead ends: 1423 [2018-04-09 20:46:51,410 INFO L226 Difference]: Without dead ends: 1157 [2018-04-09 20:46:51,413 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-09 20:46:51,413 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-04-09 20:46:51,544 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-04-09 20:46:51,544 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-04-09 20:46:51,545 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1282 transitions. [2018-04-09 20:46:51,545 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1282 transitions. Word has length 604 [2018-04-09 20:46:51,546 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:46:51,546 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1282 transitions. [2018-04-09 20:46:51,546 INFO L460 AbstractCegarLoop]: Interpolant automaton has 160 states. [2018-04-09 20:46:51,546 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1282 transitions. [2018-04-09 20:46:51,548 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 612 [2018-04-09 20:46:51,549 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:46:51,549 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-09 20:46:51,549 INFO L408 AbstractCegarLoop]: === Iteration 44 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:46:51,549 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-09 20:46:51,554 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:46:51,615 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:46:51,621 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:46:52,911 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-09 20:46:52,911 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:46:56,565 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-09 20:46:56,586 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:46:56,587 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [64, 64] total 127 [2018-04-09 20:46:56,587 INFO L442 AbstractCegarLoop]: Interpolant automaton has 128 states [2018-04-09 20:46:56,588 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 128 interpolants. [2018-04-09 20:46:56,588 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2238, Invalid=14018, Unknown=0, NotChecked=0, Total=16256 [2018-04-09 20:46:56,588 INFO L87 Difference]: Start difference. First operand 1157 states and 1282 transitions. Second operand 128 states. [2018-04-09 20:47:00,976 WARN L151 SmtUtils]: Spent 270ms on a formula simplification. DAG size of input: 252 DAG size of output 12 [2018-04-09 20:47:01,653 WARN L151 SmtUtils]: Spent 248ms on a formula simplification. DAG size of input: 247 DAG size of output 11 [2018-04-09 20:47:02,117 WARN L151 SmtUtils]: Spent 239ms on a formula simplification. DAG size of input: 244 DAG size of output 12 [2018-04-09 20:47:02,784 WARN L151 SmtUtils]: Spent 241ms on a formula simplification. DAG size of input: 239 DAG size of output 11 [2018-04-09 20:47:03,237 WARN L151 SmtUtils]: Spent 227ms on a formula simplification. DAG size of input: 236 DAG size of output 12 [2018-04-09 20:47:03,873 WARN L151 SmtUtils]: Spent 212ms on a formula simplification. DAG size of input: 231 DAG size of output 11 [2018-04-09 20:47:04,305 WARN L151 SmtUtils]: Spent 206ms on a formula simplification. DAG size of input: 228 DAG size of output 12 [2018-04-09 20:47:04,944 WARN L151 SmtUtils]: Spent 203ms on a formula simplification. DAG size of input: 223 DAG size of output 11 [2018-04-09 20:47:05,370 WARN L151 SmtUtils]: Spent 198ms on a formula simplification. DAG size of input: 220 DAG size of output 12 [2018-04-09 20:47:05,971 WARN L151 SmtUtils]: Spent 184ms on a formula simplification. DAG size of input: 215 DAG size of output 11 [2018-04-09 20:47:06,402 WARN L151 SmtUtils]: Spent 199ms on a formula simplification. DAG size of input: 212 DAG size of output 12 [2018-04-09 20:47:06,995 WARN L151 SmtUtils]: Spent 178ms on a formula simplification. DAG size of input: 207 DAG size of output 11 [2018-04-09 20:47:07,389 WARN L151 SmtUtils]: Spent 170ms on a formula simplification. DAG size of input: 204 DAG size of output 12 [2018-04-09 20:47:07,968 WARN L151 SmtUtils]: Spent 166ms on a formula simplification. DAG size of input: 199 DAG size of output 11 [2018-04-09 20:47:08,361 WARN L151 SmtUtils]: Spent 157ms on a formula simplification. DAG size of input: 196 DAG size of output 12 [2018-04-09 20:47:08,920 WARN L151 SmtUtils]: Spent 154ms on a formula simplification. DAG size of input: 191 DAG size of output 11 [2018-04-09 20:47:09,294 WARN L151 SmtUtils]: Spent 147ms on a formula simplification. DAG size of input: 188 DAG size of output 12 [2018-04-09 20:47:09,846 WARN L151 SmtUtils]: Spent 153ms on a formula simplification. DAG size of input: 183 DAG size of output 11 [2018-04-09 20:47:10,200 WARN L151 SmtUtils]: Spent 135ms on a formula simplification. DAG size of input: 180 DAG size of output 12 [2018-04-09 20:47:10,726 WARN L151 SmtUtils]: Spent 132ms on a formula simplification. DAG size of input: 175 DAG size of output 11 [2018-04-09 20:47:11,069 WARN L151 SmtUtils]: Spent 126ms on a formula simplification. DAG size of input: 172 DAG size of output 12 [2018-04-09 20:47:11,596 WARN L151 SmtUtils]: Spent 136ms on a formula simplification. DAG size of input: 167 DAG size of output 11 [2018-04-09 20:47:11,932 WARN L151 SmtUtils]: Spent 122ms on a formula simplification. DAG size of input: 164 DAG size of output 12 [2018-04-09 20:47:12,419 WARN L151 SmtUtils]: Spent 111ms on a formula simplification. DAG size of input: 159 DAG size of output 11 [2018-04-09 20:47:12,739 WARN L151 SmtUtils]: Spent 108ms on a formula simplification. DAG size of input: 156 DAG size of output 12 [2018-04-09 20:47:13,211 WARN L151 SmtUtils]: Spent 103ms on a formula simplification. DAG size of input: 151 DAG size of output 11 [2018-04-09 20:47:13,528 WARN L151 SmtUtils]: Spent 100ms on a formula simplification. DAG size of input: 148 DAG size of output 12 [2018-04-09 20:47:22,191 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:47:22,191 INFO L93 Difference]: Finished difference Result 1418 states and 1638 transitions. [2018-04-09 20:47:22,191 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 189 states. [2018-04-09 20:47:22,191 INFO L78 Accepts]: Start accepts. Automaton has 128 states. Word has length 611 [2018-04-09 20:47:22,192 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:47:22,193 INFO L225 Difference]: With dead ends: 1418 [2018-04-09 20:47:22,193 INFO L226 Difference]: Without dead ends: 1416 [2018-04-09 20:47:22,195 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1375 GetRequests, 1095 SyntacticMatches, 0 SemanticMatches, 280 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15068 ImplicationChecksByTransitivity, 26.9s TimeCoverageRelationStatistics Valid=18976, Invalid=60266, Unknown=0, NotChecked=0, Total=79242 [2018-04-09 20:47:22,196 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1416 states. [2018-04-09 20:47:22,332 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1416 to 1413. [2018-04-09 20:47:22,332 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1413 states. [2018-04-09 20:47:22,334 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1413 states to 1413 states and 1570 transitions. [2018-04-09 20:47:22,334 INFO L78 Accepts]: Start accepts. Automaton has 1413 states and 1570 transitions. Word has length 611 [2018-04-09 20:47:22,334 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:47:22,334 INFO L459 AbstractCegarLoop]: Abstraction has 1413 states and 1570 transitions. [2018-04-09 20:47:22,334 INFO L460 AbstractCegarLoop]: Interpolant automaton has 128 states. [2018-04-09 20:47:22,334 INFO L276 IsEmpty]: Start isEmpty. Operand 1413 states and 1570 transitions. [2018-04-09 20:47:22,339 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 892 [2018-04-09 20:47:22,339 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:47:22,340 INFO L355 BasicCegarLoop]: trace histogram [127, 126, 126, 126, 126, 126, 126, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-09 20:47:22,340 INFO L408 AbstractCegarLoop]: === Iteration 45 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:47:22,340 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-09 20:47:22,346 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:47:22,419 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:47:22,428 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:47:27,234 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-09 20:47:27,234 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:47:42,092 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-09 20:47:42,113 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:47:42,114 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [128, 128] total 255 [2018-04-09 20:47:42,115 INFO L442 AbstractCegarLoop]: Interpolant automaton has 256 states [2018-04-09 20:47:42,116 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 256 interpolants. [2018-04-09 20:47:42,118 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=16638, Invalid=48642, Unknown=0, NotChecked=0, Total=65280 [2018-04-09 20:47:42,118 INFO L87 Difference]: Start difference. First operand 1413 states and 1570 transitions. Second operand 256 states. Received shutdown request... [2018-04-09 20:47:48,799 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 53 states. [2018-04-09 20:47:48,799 WARN L519 AbstractCegarLoop]: Verification canceled [2018-04-09 20:47:48,804 WARN L197 ceAbstractionStarter]: Timeout [2018-04-09 20:47:48,804 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 09.04 08:47:48 BoogieIcfgContainer [2018-04-09 20:47:48,804 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-04-09 20:47:48,805 INFO L168 Benchmark]: Toolchain (without parser) took 227454.81 ms. Allocated memory was 299.9 MB in the beginning and 1.0 GB in the end (delta: 726.7 MB). Free memory was 240.4 MB in the beginning and 646.8 MB in the end (delta: -406.5 MB). Peak memory consumption was 320.2 MB. Max. memory is 5.3 GB. [2018-04-09 20:47:48,806 INFO L168 Benchmark]: CDTParser took 0.25 ms. Allocated memory is still 299.9 MB. Free memory is still 262.0 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-04-09 20:47:48,806 INFO L168 Benchmark]: CACSL2BoogieTranslator took 193.53 ms. Allocated memory is still 299.9 MB. Free memory was 240.4 MB in the beginning and 231.1 MB in the end (delta: 9.3 MB). Peak memory consumption was 9.3 MB. Max. memory is 5.3 GB. [2018-04-09 20:47:48,806 INFO L168 Benchmark]: Boogie Preprocessor took 22.93 ms. Allocated memory is still 299.9 MB. Free memory was 231.1 MB in the beginning and 230.1 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 5.3 GB. [2018-04-09 20:47:48,806 INFO L168 Benchmark]: RCFGBuilder took 260.21 ms. Allocated memory was 299.9 MB in the beginning and 458.2 MB in the end (delta: 158.3 MB). Free memory was 229.1 MB in the beginning and 427.9 MB in the end (delta: -198.8 MB). Peak memory consumption was 21.4 MB. Max. memory is 5.3 GB. [2018-04-09 20:47:48,807 INFO L168 Benchmark]: TraceAbstraction took 226973.38 ms. Allocated memory was 458.2 MB in the beginning and 1.0 GB in the end (delta: 568.3 MB). Free memory was 427.9 MB in the beginning and 646.8 MB in the end (delta: -218.9 MB). Peak memory consumption was 349.4 MB. Max. memory is 5.3 GB. [2018-04-09 20:47:48,809 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.25 ms. Allocated memory is still 299.9 MB. Free memory is still 262.0 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 193.53 ms. Allocated memory is still 299.9 MB. Free memory was 240.4 MB in the beginning and 231.1 MB in the end (delta: 9.3 MB). Peak memory consumption was 9.3 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 22.93 ms. Allocated memory is still 299.9 MB. Free memory was 231.1 MB in the beginning and 230.1 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 5.3 GB. * RCFGBuilder took 260.21 ms. Allocated memory was 299.9 MB in the beginning and 458.2 MB in the end (delta: 158.3 MB). Free memory was 229.1 MB in the beginning and 427.9 MB in the end (delta: -198.8 MB). Peak memory consumption was 21.4 MB. Max. memory is 5.3 GB. * TraceAbstraction took 226973.38 ms. Allocated memory was 458.2 MB in the beginning and 1.0 GB in the end (delta: 568.3 MB). Free memory was 427.9 MB in the beginning and 646.8 MB in the end (delta: -218.9 MB). Peak memory consumption was 349.4 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 53 states, 256 states before enhancement), while ReachableStatesComputation was computing reachable states (504 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 53 states, 256 states before enhancement), while ReachableStatesComputation was computing reachable states (504 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 53 states, 256 states before enhancement), while ReachableStatesComputation was computing reachable states (504 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 53 states, 256 states before enhancement), while ReachableStatesComputation was computing reachable states (504 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 53 states, 256 states before enhancement), while ReachableStatesComputation was computing reachable states (504 states constructedinput type IntersectNwa). - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 39 locations, 5 error locations. TIMEOUT Result, 226.9s OverallTime, 45 OverallIterations, 127 TraceHistogramMax, 120.0s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 6404 SDtfs, 52123 SDslu, 168632 SDs, 0 SdLazy, 105839 SolverSat, 8245 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 28.2s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 30795 GetRequests, 25571 SyntacticMatches, 528 SemanticMatches, 4696 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 164302 ImplicationChecksByTransitivity, 159.0s 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.8s AutomataMinimizationTime, 44 MinimizatonAttempts, 37270 StatesRemovedByMinimization, 12 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.3s SsaConstructionTime, 1.4s SatisfiabilityAnalysisTime, 99.5s 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-09_20-47-48-819.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-09_20-47-48-819.csv Completed graceful shutdown