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/AutomizerCTransformed.xml -s ../../../trunk/examples/settings/ai/eq-bench/svcomp-DerefFreeMemtrack-32bit-Automizer_Fixed_noBitfields+AI_EQ_SS.epf -i ../../../trunk/examples/svcomp/array-examples/sanfoundry_24_false-valid-deref.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-35b68b2 [2018-04-06 23:59:05,758 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-04-06 23:59:05,761 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-04-06 23:59:05,775 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-04-06 23:59:05,776 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-04-06 23:59:05,777 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-04-06 23:59:05,778 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-04-06 23:59:05,780 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-04-06 23:59:05,782 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-04-06 23:59:05,782 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-04-06 23:59:05,783 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-04-06 23:59:05,783 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-04-06 23:59:05,784 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-04-06 23:59:05,786 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-04-06 23:59:05,787 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-04-06 23:59:05,789 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-04-06 23:59:05,791 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-04-06 23:59:05,792 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-04-06 23:59:05,794 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-04-06 23:59:05,795 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-04-06 23:59:05,797 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-04-06 23:59:05,797 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-04-06 23:59:05,798 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-04-06 23:59:05,799 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-04-06 23:59:05,800 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-04-06 23:59:05,801 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-04-06 23:59:05,801 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-04-06 23:59:05,802 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-04-06 23:59:05,803 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-04-06 23:59:05,803 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-04-06 23:59:05,803 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-04-06 23:59:05,804 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-06 23:59:05,827 INFO L110 SettingsManager]: Loading preferences was successful [2018-04-06 23:59:05,828 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-04-06 23:59:05,828 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-04-06 23:59:05,828 INFO L133 SettingsManager]: * ultimate.logging.details=de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation=DEBUG; [2018-04-06 23:59:05,829 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-04-06 23:59:05,829 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-04-06 23:59:05,829 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-04-06 23:59:05,830 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-04-06 23:59:05,830 INFO L133 SettingsManager]: * Parallel states before merging=1 [2018-04-06 23:59:05,830 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-04-06 23:59:05,830 INFO L131 SettingsManager]: Preferences of LTL2Aut differ from their defaults: [2018-04-06 23:59:05,831 INFO L133 SettingsManager]: * Property to check=[] a a: x > 42 [2018-04-06 23:59:05,831 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-04-06 23:59:05,831 INFO L133 SettingsManager]: * sizeof long=4 [2018-04-06 23:59:05,831 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-04-06 23:59:05,831 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-04-06 23:59:05,832 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-04-06 23:59:05,832 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-04-06 23:59:05,832 INFO L133 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2018-04-06 23:59:05,832 INFO L133 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2018-04-06 23:59:05,832 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-04-06 23:59:05,832 INFO L133 SettingsManager]: * sizeof long double=12 [2018-04-06 23:59:05,833 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-04-06 23:59:05,833 INFO L133 SettingsManager]: * Size of a code block=SingleStatement [2018-04-06 23:59:05,833 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-04-06 23:59:05,833 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-04-06 23:59:05,833 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-04-06 23:59:05,834 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-04-06 23:59:05,834 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-04-06 23:59:05,834 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-04-06 23:59:05,834 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-04-06 23:59:05,834 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-04-06 23:59:05,835 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-06 23:59:05,835 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-04-06 23:59:05,836 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-04-06 23:59:05,836 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-04-06 23:59:05,836 INFO L131 SettingsManager]: Preferences of Boogie Printer differ from their defaults: [2018-04-06 23:59:05,836 INFO L133 SettingsManager]: * Dump path:=C:\Users\alex\AppData\Local\Temp\ [2018-04-06 23:59:05,870 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-04-06 23:59:05,882 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully (re)initialized [2018-04-06 23:59:05,886 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-04-06 23:59:05,887 INFO L271 PluginConnector]: Initializing CDTParser... [2018-04-06 23:59:05,888 INFO L276 PluginConnector]: CDTParser initialized [2018-04-06 23:59:05,888 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/array-examples/sanfoundry_24_false-valid-deref.i [2018-04-06 23:59:06,212 INFO L225 CDTParser]: Created temporary CDT project at /storage/ultimate/releaseScripts/default/UAutomizer-linux/data/FLAG4e27257ec [2018-04-06 23:59:06,336 INFO L287 CDTParser]: IsIndexed: true [2018-04-06 23:59:06,337 INFO L288 CDTParser]: Found 1 translation units. [2018-04-06 23:59:06,337 INFO L168 CDTParser]: Scanning sanfoundry_24_false-valid-deref.i [2018-04-06 23:59:06,338 INFO L210 ultiparseSymbolTable]: Include resolver: [2018-04-06 23:59:06,338 INFO L215 ultiparseSymbolTable]: [2018-04-06 23:59:06,339 INFO L218 ultiparseSymbolTable]: Function table: [2018-04-06 23:59:06,339 INFO L221 ultiparseSymbolTable]: Function definition of __U_MULTI_fsanfoundry____false_valid_deref_i__printOdd ('printOdd') in sanfoundry_24_false-valid-deref.i [2018-04-06 23:59:06,339 INFO L221 ultiparseSymbolTable]: Function definition of null ('main') in sanfoundry_24_false-valid-deref.i [2018-04-06 23:59:06,339 INFO L221 ultiparseSymbolTable]: Function definition of __U_MULTI_fsanfoundry____false_valid_deref_i____VERIFIER_assert ('__VERIFIER_assert') in sanfoundry_24_false-valid-deref.i [2018-04-06 23:59:06,339 INFO L221 ultiparseSymbolTable]: Function definition of __U_MULTI_fsanfoundry____false_valid_deref_i__printEven ('printEven') in sanfoundry_24_false-valid-deref.i [2018-04-06 23:59:06,339 INFO L227 ultiparseSymbolTable]: Global variable table: [2018-04-06 23:59:06,339 INFO L233 ultiparseSymbolTable]: [2018-04-06 23:59:06,353 INFO L330 CDTParser]: Deleted temporary CDT project at /storage/ultimate/releaseScripts/default/UAutomizer-linux/data/FLAG4e27257ec [2018-04-06 23:59:06,358 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-04-06 23:59:06,360 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2018-04-06 23:59:06,361 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-04-06 23:59:06,361 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-04-06 23:59:06,367 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-04-06 23:59:06,368 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 11:59:06" (1/1) ... [2018-04-06 23:59:06,370 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@254eeb18 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:59:06, skipping insertion in model container [2018-04-06 23:59:06,370 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 11:59:06" (1/1) ... [2018-04-06 23:59:06,383 INFO L167 Dispatcher]: Using SV-COMP mode [2018-04-06 23:59:06,396 INFO L167 Dispatcher]: Using SV-COMP mode [2018-04-06 23:59:06,527 INFO L175 PostProcessor]: Settings: Checked method=main [2018-04-06 23:59:06,544 INFO L175 PostProcessor]: Settings: Checked method=main [2018-04-06 23:59:06,548 INFO L100 SccComputation]: Graph consists of 0 InCaSumBalls and 8 non ball SCCs. Number of states in SCCs 8. [2018-04-06 23:59:06,556 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:59:06 WrapperNode [2018-04-06 23:59:06,557 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-04-06 23:59:06,557 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-04-06 23:59:06,558 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-04-06 23:59:06,558 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-04-06 23:59:06,568 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:59:06" (1/1) ... [2018-04-06 23:59:06,568 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:59:06" (1/1) ... [2018-04-06 23:59:06,573 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:59:06" (1/1) ... [2018-04-06 23:59:06,574 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:59:06" (1/1) ... [2018-04-06 23:59:06,576 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:59:06" (1/1) ... [2018-04-06 23:59:06,582 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:59:06" (1/1) ... [2018-04-06 23:59:06,583 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:59:06" (1/1) ... [2018-04-06 23:59:06,585 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-04-06 23:59:06,586 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-04-06 23:59:06,586 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-04-06 23:59:06,586 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-04-06 23:59:06,587 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:59:06" (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-06 23:59:06,647 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-04-06 23:59:06,647 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-04-06 23:59:06,647 INFO L136 BoogieDeclarations]: Found implementation of procedure __U_MULTI_fsanfoundry____false_valid_deref_i____VERIFIER_assert [2018-04-06 23:59:06,647 INFO L136 BoogieDeclarations]: Found implementation of procedure __U_MULTI_fsanfoundry____false_valid_deref_i__printEven [2018-04-06 23:59:06,648 INFO L136 BoogieDeclarations]: Found implementation of procedure __U_MULTI_fsanfoundry____false_valid_deref_i__printOdd [2018-04-06 23:59:06,648 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-04-06 23:59:06,648 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_error [2018-04-06 23:59:06,648 INFO L128 BoogieDeclarations]: Found specification of procedure __U_MULTI_fsanfoundry____false_valid_deref_i____VERIFIER_assert [2018-04-06 23:59:06,648 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-04-06 23:59:06,648 INFO L128 BoogieDeclarations]: Found specification of procedure __U_MULTI_fsanfoundry____false_valid_deref_i__printEven [2018-04-06 23:59:06,649 INFO L128 BoogieDeclarations]: Found specification of procedure __U_MULTI_fsanfoundry____false_valid_deref_i__printOdd [2018-04-06 23:59:06,649 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-04-06 23:59:06,649 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-04-06 23:59:06,649 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-04-06 23:59:06,845 INFO L259 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-04-06 23:59:06,846 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 11:59:06 BoogieIcfgContainer [2018-04-06 23:59:06,846 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-04-06 23:59:06,846 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2018-04-06 23:59:06,846 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2018-04-06 23:59:06,847 INFO L276 PluginConnector]: IcfgTransformer initialized [2018-04-06 23:59:06,850 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 11:59:06" (1/1) ... [2018-04-06 23:59:06,854 WARN L219 ansformationObserver]: HeapSeparator: input icfg has no '#valid' array -- returning unchanged Icfg! [2018-04-06 23:59:06,863 INFO L100 SccComputation]: Graph consists of 0 InCaSumBalls and 8 non ball SCCs. Number of states in SCCs 8. [2018-04-06 23:59:06,864 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 06.04 11:59:06 BasicIcfg [2018-04-06 23:59:06,864 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2018-04-06 23:59:06,864 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-04-06 23:59:06,864 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-04-06 23:59:06,868 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-04-06 23:59:06,868 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.04 11:59:06" (1/4) ... [2018-04-06 23:59:06,869 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@e6b1fc9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 11:59:06, skipping insertion in model container [2018-04-06 23:59:06,869 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:59:06" (2/4) ... [2018-04-06 23:59:06,869 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@e6b1fc9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 11:59:06, skipping insertion in model container [2018-04-06 23:59:06,870 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 11:59:06" (3/4) ... [2018-04-06 23:59:06,870 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@e6b1fc9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 06.04 11:59:06, skipping insertion in model container [2018-04-06 23:59:06,870 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 06.04 11:59:06" (4/4) ... [2018-04-06 23:59:06,872 INFO L107 eAbstractionObserver]: Analyzing ICFG sanfoundry_24_false-valid-deref.ileft_unchanged_by_heapseparator [2018-04-06 23:59:06,881 INFO L131 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-04-06 23:59:06,888 INFO L143 ceAbstractionStarter]: Appying trace abstraction to program that has 4 error locations. [2018-04-06 23:59:06,932 INFO L128 ementStrategyFactory]: Using default assertion order modulation [2018-04-06 23:59:06,933 INFO L369 AbstractCegarLoop]: Interprodecural is true [2018-04-06 23:59:06,933 INFO L370 AbstractCegarLoop]: Hoare is true [2018-04-06 23:59:06,933 INFO L371 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-04-06 23:59:06,933 INFO L372 AbstractCegarLoop]: Backedges is TWOTRACK [2018-04-06 23:59:06,933 INFO L373 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-04-06 23:59:06,933 INFO L374 AbstractCegarLoop]: Difference is false [2018-04-06 23:59:06,933 INFO L375 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-04-06 23:59:06,933 INFO L380 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-04-06 23:59:06,934 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-04-06 23:59:06,946 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states. [2018-04-06 23:59:06,950 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2018-04-06 23:59:06,950 INFO L347 BasicCegarLoop]: Found error trace [2018-04-06 23:59:06,950 INFO L355 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-06 23:59:06,951 INFO L408 AbstractCegarLoop]: === Iteration 1 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-06 23:59:06,954 INFO L82 PathProgramCache]: Analyzing trace with hash -968705159, 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-06 23:59:06,966 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-06 23:59:06,985 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-06 23:59:06,990 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-06 23:59:07,015 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-06 23:59:07,015 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-06 23:59:07,050 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-06 23:59:07,072 INFO L320 seRefinementStrategy]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2018-04-06 23:59:07,073 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2, 2] imperfect sequences [] total 3 [2018-04-06 23:59:07,074 INFO L442 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-04-06 23:59:07,084 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-04-06 23:59:07,084 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-04-06 23:59:07,086 INFO L87 Difference]: Start difference. First operand 51 states. Second operand 4 states. [2018-04-06 23:59:07,250 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-06 23:59:07,250 INFO L93 Difference]: Finished difference Result 112 states and 144 transitions. [2018-04-06 23:59:07,250 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-04-06 23:59:07,252 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 13 [2018-04-06 23:59:07,252 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-06 23:59:07,260 INFO L225 Difference]: With dead ends: 112 [2018-04-06 23:59:07,261 INFO L226 Difference]: Without dead ends: 62 [2018-04-06 23:59:07,264 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 25 GetRequests, 23 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-06 23:59:07,277 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2018-04-06 23:59:07,298 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 55. [2018-04-06 23:59:07,300 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 55 states. [2018-04-06 23:59:07,302 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 62 transitions. [2018-04-06 23:59:07,303 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 62 transitions. Word has length 13 [2018-04-06 23:59:07,304 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-06 23:59:07,304 INFO L459 AbstractCegarLoop]: Abstraction has 55 states and 62 transitions. [2018-04-06 23:59:07,304 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-04-06 23:59:07,304 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 62 transitions. [2018-04-06 23:59:07,306 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-04-06 23:59:07,306 INFO L347 BasicCegarLoop]: Found error trace [2018-04-06 23:59:07,306 INFO L355 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-06 23:59:07,306 INFO L408 AbstractCegarLoop]: === Iteration 2 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-06 23:59:07,307 INFO L82 PathProgramCache]: Analyzing trace with hash 1488179528, 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-06 23:59:07,326 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-06 23:59:07,335 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-06 23:59:07,337 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-06 23:59:07,364 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-06 23:59:07,364 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-06 23:59:07,449 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-06 23:59:07,472 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-06 23:59:07,472 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 7 [2018-04-06 23:59:07,474 INFO L442 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-04-06 23:59:07,474 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-04-06 23:59:07,474 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-04-06 23:59:07,475 INFO L87 Difference]: Start difference. First operand 55 states and 62 transitions. Second operand 8 states. [2018-04-06 23:59:07,683 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-06 23:59:07,683 INFO L93 Difference]: Finished difference Result 84 states and 101 transitions. [2018-04-06 23:59:07,683 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-04-06 23:59:07,683 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 20 [2018-04-06 23:59:07,684 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-06 23:59:07,686 INFO L225 Difference]: With dead ends: 84 [2018-04-06 23:59:07,686 INFO L226 Difference]: Without dead ends: 82 [2018-04-06 23:59:07,687 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2018-04-06 23:59:07,688 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2018-04-06 23:59:07,698 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 73. [2018-04-06 23:59:07,698 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 73 states. [2018-04-06 23:59:07,700 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 86 transitions. [2018-04-06 23:59:07,700 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 86 transitions. Word has length 20 [2018-04-06 23:59:07,701 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-06 23:59:07,701 INFO L459 AbstractCegarLoop]: Abstraction has 73 states and 86 transitions. [2018-04-06 23:59:07,701 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-04-06 23:59:07,701 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 86 transitions. [2018-04-06 23:59:07,702 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2018-04-06 23:59:07,702 INFO L347 BasicCegarLoop]: Found error trace [2018-04-06 23:59:07,703 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] [2018-04-06 23:59:07,703 INFO L408 AbstractCegarLoop]: === Iteration 3 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-06 23:59:07,703 INFO L82 PathProgramCache]: Analyzing trace with hash -1776919665, 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-06 23:59:07,709 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-06 23:59:07,716 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-06 23:59:07,717 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-06 23:59:07,745 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-06 23:59:07,745 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-06 23:59:07,762 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-06 23:59:07,783 INFO L320 seRefinementStrategy]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2018-04-06 23:59:07,783 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5, 5] imperfect sequences [] total 6 [2018-04-06 23:59:07,783 INFO L442 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-04-06 23:59:07,784 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-04-06 23:59:07,784 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2018-04-06 23:59:07,784 INFO L87 Difference]: Start difference. First operand 73 states and 86 transitions. Second operand 6 states. [2018-04-06 23:59:07,960 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-06 23:59:07,960 INFO L93 Difference]: Finished difference Result 101 states and 117 transitions. [2018-04-06 23:59:07,961 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-04-06 23:59:07,961 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 23 [2018-04-06 23:59:07,961 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-06 23:59:07,962 INFO L225 Difference]: With dead ends: 101 [2018-04-06 23:59:07,962 INFO L226 Difference]: Without dead ends: 76 [2018-04-06 23:59:07,963 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 39 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=23, Invalid=33, Unknown=0, NotChecked=0, Total=56 [2018-04-06 23:59:07,964 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2018-04-06 23:59:07,971 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 73. [2018-04-06 23:59:07,971 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 73 states. [2018-04-06 23:59:07,973 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 85 transitions. [2018-04-06 23:59:07,974 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 85 transitions. Word has length 23 [2018-04-06 23:59:07,974 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-06 23:59:07,974 INFO L459 AbstractCegarLoop]: Abstraction has 73 states and 85 transitions. [2018-04-06 23:59:07,974 INFO L460 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-04-06 23:59:07,974 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 85 transitions. [2018-04-06 23:59:07,976 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2018-04-06 23:59:07,976 INFO L347 BasicCegarLoop]: Found error trace [2018-04-06 23:59:07,976 INFO L355 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-06 23:59:07,976 INFO L408 AbstractCegarLoop]: === Iteration 4 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-06 23:59:07,977 INFO L82 PathProgramCache]: Analyzing trace with hash -1226982754, 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-06 23:59:07,985 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-06 23:59:07,993 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-06 23:59:07,995 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-06 23:59:08,066 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 3 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-06 23:59:08,066 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-06 23:59:08,147 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 3 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-06 23:59:08,174 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-06 23:59:08,174 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 12 [2018-04-06 23:59:08,174 INFO L442 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-04-06 23:59:08,175 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-04-06 23:59:08,175 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=101, Unknown=0, NotChecked=0, Total=132 [2018-04-06 23:59:08,175 INFO L87 Difference]: Start difference. First operand 73 states and 85 transitions. Second operand 12 states. [2018-04-06 23:59:08,388 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-06 23:59:08,389 INFO L93 Difference]: Finished difference Result 107 states and 123 transitions. [2018-04-06 23:59:08,389 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-04-06 23:59:08,389 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 30 [2018-04-06 23:59:08,390 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-06 23:59:08,391 INFO L225 Difference]: With dead ends: 107 [2018-04-06 23:59:08,391 INFO L226 Difference]: Without dead ends: 76 [2018-04-06 23:59:08,392 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 45 SyntacticMatches, 4 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 46 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=73, Invalid=233, Unknown=0, NotChecked=0, Total=306 [2018-04-06 23:59:08,392 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2018-04-06 23:59:08,399 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 73. [2018-04-06 23:59:08,399 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 73 states. [2018-04-06 23:59:08,400 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 84 transitions. [2018-04-06 23:59:08,401 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 84 transitions. Word has length 30 [2018-04-06 23:59:08,401 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-06 23:59:08,401 INFO L459 AbstractCegarLoop]: Abstraction has 73 states and 84 transitions. [2018-04-06 23:59:08,401 INFO L460 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-04-06 23:59:08,401 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 84 transitions. [2018-04-06 23:59:08,403 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2018-04-06 23:59:08,403 INFO L347 BasicCegarLoop]: Found error trace [2018-04-06 23:59:08,403 INFO L355 BasicCegarLoop]: trace histogram [4, 4, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-06 23:59:08,403 INFO L408 AbstractCegarLoop]: === Iteration 5 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-06 23:59:08,403 INFO L82 PathProgramCache]: Analyzing trace with hash 1840751656, now seen corresponding path program 2 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-06 23:59:08,413 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-06 23:59:08,422 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-06 23:59:08,424 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-06 23:59:08,474 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 0 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-06 23:59:08,474 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-06 23:59:08,596 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 0 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-06 23:59:08,630 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-06 23:59:08,630 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 15 [2018-04-06 23:59:08,630 INFO L442 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-04-06 23:59:08,631 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-04-06 23:59:08,631 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=186, Unknown=0, NotChecked=0, Total=240 [2018-04-06 23:59:08,631 INFO L87 Difference]: Start difference. First operand 73 states and 84 transitions. Second operand 16 states. [2018-04-06 23:59:09,075 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-06 23:59:09,075 INFO L93 Difference]: Finished difference Result 122 states and 153 transitions. [2018-04-06 23:59:09,075 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-04-06 23:59:09,076 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 34 [2018-04-06 23:59:09,076 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-06 23:59:09,077 INFO L225 Difference]: With dead ends: 122 [2018-04-06 23:59:09,078 INFO L226 Difference]: Without dead ends: 120 [2018-04-06 23:59:09,079 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 53 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 116 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=244, Invalid=626, Unknown=0, NotChecked=0, Total=870 [2018-04-06 23:59:09,079 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 120 states. [2018-04-06 23:59:09,089 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 120 to 109. [2018-04-06 23:59:09,089 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 109 states. [2018-04-06 23:59:09,091 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 132 transitions. [2018-04-06 23:59:09,091 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 132 transitions. Word has length 34 [2018-04-06 23:59:09,091 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-06 23:59:09,091 INFO L459 AbstractCegarLoop]: Abstraction has 109 states and 132 transitions. [2018-04-06 23:59:09,092 INFO L460 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-04-06 23:59:09,092 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 132 transitions. [2018-04-06 23:59:09,093 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2018-04-06 23:59:09,093 INFO L347 BasicCegarLoop]: Found error trace [2018-04-06 23:59:09,093 INFO L355 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-06 23:59:09,094 INFO L408 AbstractCegarLoop]: === Iteration 6 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-06 23:59:09,094 INFO L82 PathProgramCache]: Analyzing trace with hash 504306863, 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-06 23:59:09,100 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-06 23:59:09,111 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-06 23:59:09,113 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-06 23:59:09,124 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2018-04-06 23:59:09,124 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-06 23:59:09,151 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2018-04-06 23:59:09,172 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-06 23:59:09,172 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 7 [2018-04-06 23:59:09,173 INFO L442 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-04-06 23:59:09,173 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-04-06 23:59:09,173 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-04-06 23:59:09,173 INFO L87 Difference]: Start difference. First operand 109 states and 132 transitions. Second operand 8 states. [2018-04-06 23:59:09,253 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-06 23:59:09,253 INFO L93 Difference]: Finished difference Result 132 states and 162 transitions. [2018-04-06 23:59:09,254 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-04-06 23:59:09,254 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 37 [2018-04-06 23:59:09,254 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-06 23:59:09,255 INFO L225 Difference]: With dead ends: 132 [2018-04-06 23:59:09,255 INFO L226 Difference]: Without dead ends: 130 [2018-04-06 23:59:09,256 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 77 GetRequests, 67 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-06 23:59:09,256 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2018-04-06 23:59:09,267 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 127. [2018-04-06 23:59:09,267 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 127 states. [2018-04-06 23:59:09,269 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 154 transitions. [2018-04-06 23:59:09,269 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 154 transitions. Word has length 37 [2018-04-06 23:59:09,269 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-06 23:59:09,270 INFO L459 AbstractCegarLoop]: Abstraction has 127 states and 154 transitions. [2018-04-06 23:59:09,270 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-04-06 23:59:09,270 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 154 transitions. [2018-04-06 23:59:09,272 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2018-04-06 23:59:09,272 INFO L347 BasicCegarLoop]: Found error trace [2018-04-06 23:59:09,272 INFO L355 BasicCegarLoop]: trace histogram [4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-06 23:59:09,272 INFO L408 AbstractCegarLoop]: === Iteration 7 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-06 23:59:09,273 INFO L82 PathProgramCache]: Analyzing trace with hash -214482705, now seen corresponding path program 3 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-06 23:59:09,279 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-06 23:59:09,288 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-06 23:59:09,291 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-06 23:59:09,360 INFO L134 CoverageAnalysis]: Checked inductivity of 41 backedges. 29 proven. 11 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-04-06 23:59:09,360 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-06 23:59:09,421 INFO L134 CoverageAnalysis]: Checked inductivity of 41 backedges. 29 proven. 11 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-04-06 23:59:09,442 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-06 23:59:09,442 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 18 [2018-04-06 23:59:09,442 INFO L442 AbstractCegarLoop]: Interpolant automaton has 18 states [2018-04-06 23:59:09,442 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2018-04-06 23:59:09,443 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=59, Invalid=247, Unknown=0, NotChecked=0, Total=306 [2018-04-06 23:59:09,443 INFO L87 Difference]: Start difference. First operand 127 states and 154 transitions. Second operand 18 states. [2018-04-06 23:59:09,674 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-06 23:59:09,674 INFO L93 Difference]: Finished difference Result 170 states and 203 transitions. [2018-04-06 23:59:09,675 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-04-06 23:59:09,675 INFO L78 Accepts]: Start accepts. Automaton has 18 states. Word has length 51 [2018-04-06 23:59:09,675 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-06 23:59:09,677 INFO L225 Difference]: With dead ends: 170 [2018-04-06 23:59:09,677 INFO L226 Difference]: Without dead ends: 127 [2018-04-06 23:59:09,678 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 112 GetRequests, 79 SyntacticMatches, 6 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 168 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=160, Invalid=652, Unknown=0, NotChecked=0, Total=812 [2018-04-06 23:59:09,678 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states. [2018-04-06 23:59:09,693 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 127. [2018-04-06 23:59:09,693 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 127 states. [2018-04-06 23:59:09,694 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 153 transitions. [2018-04-06 23:59:09,694 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 153 transitions. Word has length 51 [2018-04-06 23:59:09,695 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-06 23:59:09,695 INFO L459 AbstractCegarLoop]: Abstraction has 127 states and 153 transitions. [2018-04-06 23:59:09,695 INFO L460 AbstractCegarLoop]: Interpolant automaton has 18 states. [2018-04-06 23:59:09,695 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 153 transitions. [2018-04-06 23:59:09,697 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2018-04-06 23:59:09,697 INFO L347 BasicCegarLoop]: Found error trace [2018-04-06 23:59:09,697 INFO L355 BasicCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-06 23:59:09,697 INFO L408 AbstractCegarLoop]: === Iteration 8 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-06 23:59:09,698 INFO L82 PathProgramCache]: Analyzing trace with hash -990346370, now seen corresponding path program 4 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-06 23:59:09,709 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-06 23:59:09,724 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-06 23:59:09,727 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-06 23:59:09,852 INFO L134 CoverageAnalysis]: Checked inductivity of 57 backedges. 30 proven. 27 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-06 23:59:09,852 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-06 23:59:09,961 INFO L134 CoverageAnalysis]: Checked inductivity of 57 backedges. 30 proven. 27 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-06 23:59:09,981 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-06 23:59:09,982 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17] total 24 [2018-04-06 23:59:09,982 INFO L442 AbstractCegarLoop]: Interpolant automaton has 24 states [2018-04-06 23:59:09,982 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2018-04-06 23:59:09,982 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=95, Invalid=457, Unknown=0, NotChecked=0, Total=552 [2018-04-06 23:59:09,983 INFO L87 Difference]: Start difference. First operand 127 states and 153 transitions. Second operand 24 states. [2018-04-06 23:59:10,303 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-06 23:59:10,303 INFO L93 Difference]: Finished difference Result 176 states and 209 transitions. [2018-04-06 23:59:10,303 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2018-04-06 23:59:10,303 INFO L78 Accepts]: Start accepts. Automaton has 24 states. Word has length 58 [2018-04-06 23:59:10,304 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-06 23:59:10,305 INFO L225 Difference]: With dead ends: 176 [2018-04-06 23:59:10,305 INFO L226 Difference]: Without dead ends: 127 [2018-04-06 23:59:10,307 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 131 GetRequests, 85 SyntacticMatches, 8 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 363 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=278, Invalid=1282, Unknown=0, NotChecked=0, Total=1560 [2018-04-06 23:59:10,307 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states. [2018-04-06 23:59:10,315 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 127. [2018-04-06 23:59:10,316 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 127 states. [2018-04-06 23:59:10,317 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 152 transitions. [2018-04-06 23:59:10,317 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 152 transitions. Word has length 58 [2018-04-06 23:59:10,317 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-06 23:59:10,317 INFO L459 AbstractCegarLoop]: Abstraction has 127 states and 152 transitions. [2018-04-06 23:59:10,317 INFO L460 AbstractCegarLoop]: Interpolant automaton has 24 states. [2018-04-06 23:59:10,317 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 152 transitions. [2018-04-06 23:59:10,319 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2018-04-06 23:59:10,319 INFO L347 BasicCegarLoop]: Found error trace [2018-04-06 23:59:10,319 INFO L355 BasicCegarLoop]: trace histogram [8, 8, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-06 23:59:10,319 INFO L408 AbstractCegarLoop]: === Iteration 9 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-06 23:59:10,320 INFO L82 PathProgramCache]: Analyzing trace with hash -1870810648, now seen corresponding path program 3 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-06 23:59:10,329 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-06 23:59:10,340 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-06 23:59:10,343 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-06 23:59:10,443 INFO L134 CoverageAnalysis]: Checked inductivity of 168 backedges. 0 proven. 168 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-06 23:59:10,444 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-06 23:59:10,679 INFO L134 CoverageAnalysis]: Checked inductivity of 168 backedges. 0 proven. 168 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-06 23:59:10,699 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-06 23:59:10,699 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 31 [2018-04-06 23:59:10,700 INFO L442 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-04-06 23:59:10,700 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-04-06 23:59:10,700 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=174, Invalid=818, Unknown=0, NotChecked=0, Total=992 [2018-04-06 23:59:10,700 INFO L87 Difference]: Start difference. First operand 127 states and 152 transitions. Second operand 32 states. [2018-04-06 23:59:11,981 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-06 23:59:11,981 INFO L93 Difference]: Finished difference Result 215 states and 279 transitions. [2018-04-06 23:59:11,981 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2018-04-06 23:59:11,981 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 62 [2018-04-06 23:59:11,982 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-06 23:59:11,983 INFO L225 Difference]: With dead ends: 215 [2018-04-06 23:59:11,983 INFO L226 Difference]: Without dead ends: 213 [2018-04-06 23:59:11,984 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 157 GetRequests, 93 SyntacticMatches, 0 SemanticMatches, 64 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 716 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=1096, Invalid=3194, Unknown=0, NotChecked=0, Total=4290 [2018-04-06 23:59:11,984 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 213 states. [2018-04-06 23:59:11,994 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 213 to 199. [2018-04-06 23:59:11,994 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 199 states. [2018-04-06 23:59:11,995 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 199 states to 199 states and 248 transitions. [2018-04-06 23:59:11,995 INFO L78 Accepts]: Start accepts. Automaton has 199 states and 248 transitions. Word has length 62 [2018-04-06 23:59:11,996 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-06 23:59:11,996 INFO L459 AbstractCegarLoop]: Abstraction has 199 states and 248 transitions. [2018-04-06 23:59:11,996 INFO L460 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-04-06 23:59:11,996 INFO L276 IsEmpty]: Start isEmpty. Operand 199 states and 248 transitions. [2018-04-06 23:59:11,997 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2018-04-06 23:59:11,998 INFO L347 BasicCegarLoop]: Found error trace [2018-04-06 23:59:11,998 INFO L355 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-06 23:59:11,998 INFO L408 AbstractCegarLoop]: === Iteration 10 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-06 23:59:11,998 INFO L82 PathProgramCache]: Analyzing trace with hash -1133440497, 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-06 23:59:12,006 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-06 23:59:12,019 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-06 23:59:12,021 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-06 23:59:12,056 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 0 proven. 30 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2018-04-06 23:59:12,056 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-06 23:59:12,125 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 0 proven. 30 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2018-04-06 23:59:12,155 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-06 23:59:12,156 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 15 [2018-04-06 23:59:12,156 INFO L442 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-04-06 23:59:12,156 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-04-06 23:59:12,156 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=186, Unknown=0, NotChecked=0, Total=240 [2018-04-06 23:59:12,156 INFO L87 Difference]: Start difference. First operand 199 states and 248 transitions. Second operand 16 states. [2018-04-06 23:59:12,439 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-06 23:59:12,439 INFO L93 Difference]: Finished difference Result 240 states and 304 transitions. [2018-04-06 23:59:12,439 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-04-06 23:59:12,439 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 65 [2018-04-06 23:59:12,440 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-06 23:59:12,441 INFO L225 Difference]: With dead ends: 240 [2018-04-06 23:59:12,441 INFO L226 Difference]: Without dead ends: 238 [2018-04-06 23:59:12,442 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 143 GetRequests, 115 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-06 23:59:12,442 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 238 states. [2018-04-06 23:59:12,454 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 238 to 235. [2018-04-06 23:59:12,454 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 235 states. [2018-04-06 23:59:12,456 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 292 transitions. [2018-04-06 23:59:12,456 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 292 transitions. Word has length 65 [2018-04-06 23:59:12,457 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-06 23:59:12,457 INFO L459 AbstractCegarLoop]: Abstraction has 235 states and 292 transitions. [2018-04-06 23:59:12,457 INFO L460 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-04-06 23:59:12,457 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 292 transitions. [2018-04-06 23:59:12,458 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2018-04-06 23:59:12,458 INFO L347 BasicCegarLoop]: Found error trace [2018-04-06 23:59:12,458 INFO L355 BasicCegarLoop]: trace histogram [8, 8, 7, 7, 7, 7, 7, 5, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-06 23:59:12,458 INFO L408 AbstractCegarLoop]: === Iteration 11 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-06 23:59:12,459 INFO L82 PathProgramCache]: Analyzing trace with hash 447814287, now seen corresponding path program 6 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-06 23:59:12,465 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-06 23:59:12,478 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-06 23:59:12,481 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-06 23:59:12,623 INFO L134 CoverageAnalysis]: Checked inductivity of 218 backedges. 144 proven. 50 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2018-04-06 23:59:12,623 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-06 23:59:12,836 INFO L134 CoverageAnalysis]: Checked inductivity of 218 backedges. 144 proven. 50 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2018-04-06 23:59:12,857 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-06 23:59:12,857 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21] total 30 [2018-04-06 23:59:12,857 INFO L442 AbstractCegarLoop]: Interpolant automaton has 30 states [2018-04-06 23:59:12,857 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2018-04-06 23:59:12,858 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=139, Invalid=731, Unknown=0, NotChecked=0, Total=870 [2018-04-06 23:59:12,858 INFO L87 Difference]: Start difference. First operand 235 states and 292 transitions. Second operand 30 states. [2018-04-06 23:59:13,329 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-06 23:59:13,329 INFO L93 Difference]: Finished difference Result 314 states and 385 transitions. [2018-04-06 23:59:13,329 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-04-06 23:59:13,329 INFO L78 Accepts]: Start accepts. Automaton has 30 states. Word has length 93 [2018-04-06 23:59:13,329 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-06 23:59:13,331 INFO L225 Difference]: With dead ends: 314 [2018-04-06 23:59:13,331 INFO L226 Difference]: Without dead ends: 235 [2018-04-06 23:59:13,332 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 206 GetRequests, 147 SyntacticMatches, 10 SemanticMatches, 49 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 631 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=427, Invalid=2123, Unknown=0, NotChecked=0, Total=2550 [2018-04-06 23:59:13,332 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 235 states. [2018-04-06 23:59:13,340 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 235 to 235. [2018-04-06 23:59:13,340 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 235 states. [2018-04-06 23:59:13,341 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 291 transitions. [2018-04-06 23:59:13,341 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 291 transitions. Word has length 93 [2018-04-06 23:59:13,342 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-06 23:59:13,342 INFO L459 AbstractCegarLoop]: Abstraction has 235 states and 291 transitions. [2018-04-06 23:59:13,342 INFO L460 AbstractCegarLoop]: Interpolant automaton has 30 states. [2018-04-06 23:59:13,342 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 291 transitions. [2018-04-06 23:59:13,343 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 101 [2018-04-06 23:59:13,343 INFO L347 BasicCegarLoop]: Found error trace [2018-04-06 23:59:13,343 INFO L355 BasicCegarLoop]: trace histogram [8, 8, 7, 7, 7, 7, 7, 6, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-06 23:59:13,343 INFO L408 AbstractCegarLoop]: === Iteration 12 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-06 23:59:13,343 INFO L82 PathProgramCache]: Analyzing trace with hash 424458846, now seen corresponding path program 7 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-06 23:59:13,349 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-06 23:59:13,366 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-06 23:59:13,368 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-06 23:59:13,576 INFO L134 CoverageAnalysis]: Checked inductivity of 248 backedges. 159 proven. 80 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2018-04-06 23:59:13,577 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-06 23:59:13,747 INFO L134 CoverageAnalysis]: Checked inductivity of 248 backedges. 159 proven. 80 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2018-04-06 23:59:13,768 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-06 23:59:13,768 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 25] total 36 [2018-04-06 23:59:13,769 INFO L442 AbstractCegarLoop]: Interpolant automaton has 36 states [2018-04-06 23:59:13,769 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2018-04-06 23:59:13,769 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=191, Invalid=1069, Unknown=0, NotChecked=0, Total=1260 [2018-04-06 23:59:13,769 INFO L87 Difference]: Start difference. First operand 235 states and 291 transitions. Second operand 36 states. [2018-04-06 23:59:14,245 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-06 23:59:14,245 INFO L93 Difference]: Finished difference Result 314 states and 384 transitions. [2018-04-06 23:59:14,245 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2018-04-06 23:59:14,245 INFO L78 Accepts]: Start accepts. Automaton has 36 states. Word has length 100 [2018-04-06 23:59:14,246 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-06 23:59:14,247 INFO L225 Difference]: With dead ends: 314 [2018-04-06 23:59:14,247 INFO L226 Difference]: Without dead ends: 235 [2018-04-06 23:59:14,253 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 225 GetRequests, 153 SyntacticMatches, 12 SemanticMatches, 60 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 972 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=607, Invalid=3175, Unknown=0, NotChecked=0, Total=3782 [2018-04-06 23:59:14,253 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 235 states. [2018-04-06 23:59:14,263 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 235 to 235. [2018-04-06 23:59:14,263 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 235 states. [2018-04-06 23:59:14,265 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 290 transitions. [2018-04-06 23:59:14,265 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 290 transitions. Word has length 100 [2018-04-06 23:59:14,266 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-06 23:59:14,266 INFO L459 AbstractCegarLoop]: Abstraction has 235 states and 290 transitions. [2018-04-06 23:59:14,266 INFO L460 AbstractCegarLoop]: Interpolant automaton has 36 states. [2018-04-06 23:59:14,266 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 290 transitions. [2018-04-06 23:59:14,268 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2018-04-06 23:59:14,268 INFO L347 BasicCegarLoop]: Found error trace [2018-04-06 23:59:14,268 INFO L355 BasicCegarLoop]: trace histogram [8, 8, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-06 23:59:14,268 INFO L408 AbstractCegarLoop]: === Iteration 13 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-06 23:59:14,268 INFO L82 PathProgramCache]: Analyzing trace with hash 1615037359, now seen corresponding path program 8 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-06 23:59:14,275 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-06 23:59:14,292 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-06 23:59:14,295 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-06 23:59:14,601 INFO L134 CoverageAnalysis]: Checked inductivity of 285 backedges. 167 proven. 117 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-04-06 23:59:14,601 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-06 23:59:14,836 INFO L134 CoverageAnalysis]: Checked inductivity of 285 backedges. 167 proven. 117 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-04-06 23:59:14,857 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-06 23:59:14,858 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [29, 29] total 42 [2018-04-06 23:59:14,858 INFO L442 AbstractCegarLoop]: Interpolant automaton has 42 states [2018-04-06 23:59:14,858 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 42 interpolants. [2018-04-06 23:59:14,859 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=251, Invalid=1471, Unknown=0, NotChecked=0, Total=1722 [2018-04-06 23:59:14,859 INFO L87 Difference]: Start difference. First operand 235 states and 290 transitions. Second operand 42 states. [2018-04-06 23:59:15,600 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-06 23:59:15,600 INFO L93 Difference]: Finished difference Result 314 states and 383 transitions. [2018-04-06 23:59:15,600 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 47 states. [2018-04-06 23:59:15,600 INFO L78 Accepts]: Start accepts. Automaton has 42 states. Word has length 107 [2018-04-06 23:59:15,600 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-06 23:59:15,601 INFO L225 Difference]: With dead ends: 314 [2018-04-06 23:59:15,601 INFO L226 Difference]: Without dead ends: 235 [2018-04-06 23:59:15,603 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 244 GetRequests, 159 SyntacticMatches, 14 SemanticMatches, 71 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1386 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=818, Invalid=4438, Unknown=0, NotChecked=0, Total=5256 [2018-04-06 23:59:15,604 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 235 states. [2018-04-06 23:59:15,609 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 235 to 235. [2018-04-06 23:59:15,610 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 235 states. [2018-04-06 23:59:15,611 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 289 transitions. [2018-04-06 23:59:15,611 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 289 transitions. Word has length 107 [2018-04-06 23:59:15,611 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-06 23:59:15,611 INFO L459 AbstractCegarLoop]: Abstraction has 235 states and 289 transitions. [2018-04-06 23:59:15,611 INFO L460 AbstractCegarLoop]: Interpolant automaton has 42 states. [2018-04-06 23:59:15,611 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 289 transitions. [2018-04-06 23:59:15,613 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 115 [2018-04-06 23:59:15,613 INFO L347 BasicCegarLoop]: Found error trace [2018-04-06 23:59:15,613 INFO L355 BasicCegarLoop]: trace histogram [8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-06 23:59:15,613 INFO L408 AbstractCegarLoop]: === Iteration 14 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-06 23:59:15,613 INFO L82 PathProgramCache]: Analyzing trace with hash 587713854, now seen corresponding path program 9 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-06 23:59:15,619 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-06 23:59:15,636 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-06 23:59:15,638 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-06 23:59:15,968 INFO L134 CoverageAnalysis]: Checked inductivity of 329 backedges. 168 proven. 161 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-06 23:59:15,968 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-06 23:59:16,293 INFO L134 CoverageAnalysis]: Checked inductivity of 329 backedges. 168 proven. 161 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-06 23:59:16,316 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-06 23:59:16,316 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [33, 33] total 48 [2018-04-06 23:59:16,316 INFO L442 AbstractCegarLoop]: Interpolant automaton has 48 states [2018-04-06 23:59:16,316 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 48 interpolants. [2018-04-06 23:59:16,317 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=319, Invalid=1937, Unknown=0, NotChecked=0, Total=2256 [2018-04-06 23:59:16,317 INFO L87 Difference]: Start difference. First operand 235 states and 289 transitions. Second operand 48 states. [2018-04-06 23:59:17,085 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-06 23:59:17,086 INFO L93 Difference]: Finished difference Result 320 states and 389 transitions. [2018-04-06 23:59:17,086 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 54 states. [2018-04-06 23:59:17,086 INFO L78 Accepts]: Start accepts. Automaton has 48 states. Word has length 114 [2018-04-06 23:59:17,086 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-06 23:59:17,087 INFO L225 Difference]: With dead ends: 320 [2018-04-06 23:59:17,088 INFO L226 Difference]: Without dead ends: 235 [2018-04-06 23:59:17,090 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 263 GetRequests, 165 SyntacticMatches, 16 SemanticMatches, 82 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1873 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=1060, Invalid=5912, Unknown=0, NotChecked=0, Total=6972 [2018-04-06 23:59:17,090 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 235 states. [2018-04-06 23:59:17,096 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 235 to 235. [2018-04-06 23:59:17,096 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 235 states. [2018-04-06 23:59:17,097 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 288 transitions. [2018-04-06 23:59:17,097 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 288 transitions. Word has length 114 [2018-04-06 23:59:17,098 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-06 23:59:17,098 INFO L459 AbstractCegarLoop]: Abstraction has 235 states and 288 transitions. [2018-04-06 23:59:17,098 INFO L460 AbstractCegarLoop]: Interpolant automaton has 48 states. [2018-04-06 23:59:17,098 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 288 transitions. [2018-04-06 23:59:17,099 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 119 [2018-04-06 23:59:17,099 INFO L347 BasicCegarLoop]: Found error trace [2018-04-06 23:59:17,099 INFO L355 BasicCegarLoop]: trace histogram [16, 16, 15, 15, 15, 15, 15, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-06 23:59:17,099 INFO L408 AbstractCegarLoop]: === Iteration 15 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-06 23:59:17,100 INFO L82 PathProgramCache]: Analyzing trace with hash 1158376808, now seen corresponding path program 4 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-06 23:59:17,115 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-06 23:59:17,130 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-06 23:59:17,134 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-06 23:59:17,509 INFO L134 CoverageAnalysis]: Checked inductivity of 780 backedges. 0 proven. 780 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-06 23:59:17,510 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-06 23:59:18,377 INFO L134 CoverageAnalysis]: Checked inductivity of 780 backedges. 0 proven. 780 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-06 23:59:18,412 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-06 23:59:18,412 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [32, 32] total 63 [2018-04-06 23:59:18,412 INFO L442 AbstractCegarLoop]: Interpolant automaton has 64 states [2018-04-06 23:59:18,413 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 64 interpolants. [2018-04-06 23:59:18,413 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=606, Invalid=3426, Unknown=0, NotChecked=0, Total=4032 [2018-04-06 23:59:18,414 INFO L87 Difference]: Start difference. First operand 235 states and 288 transitions. Second operand 64 states. [2018-04-06 23:59:23,870 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-06 23:59:23,871 INFO L93 Difference]: Finished difference Result 407 states and 539 transitions. [2018-04-06 23:59:23,913 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 93 states. [2018-04-06 23:59:23,914 INFO L78 Accepts]: Start accepts. Automaton has 64 states. Word has length 118 [2018-04-06 23:59:23,914 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-06 23:59:23,916 INFO L225 Difference]: With dead ends: 407 [2018-04-06 23:59:23,916 INFO L226 Difference]: Without dead ends: 405 [2018-04-06 23:59:23,921 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 309 GetRequests, 173 SyntacticMatches, 0 SemanticMatches, 136 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3452 ImplicationChecksByTransitivity, 4.9s TimeCoverageRelationStatistics Valid=4624, Invalid=14282, Unknown=0, NotChecked=0, Total=18906 [2018-04-06 23:59:23,922 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 405 states. [2018-04-06 23:59:23,935 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 405 to 379. [2018-04-06 23:59:23,935 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 379 states. [2018-04-06 23:59:23,938 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 379 states to 379 states and 480 transitions. [2018-04-06 23:59:23,939 INFO L78 Accepts]: Start accepts. Automaton has 379 states and 480 transitions. Word has length 118 [2018-04-06 23:59:23,939 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-06 23:59:23,939 INFO L459 AbstractCegarLoop]: Abstraction has 379 states and 480 transitions. [2018-04-06 23:59:23,939 INFO L460 AbstractCegarLoop]: Interpolant automaton has 64 states. [2018-04-06 23:59:23,939 INFO L276 IsEmpty]: Start isEmpty. Operand 379 states and 480 transitions. [2018-04-06 23:59:23,941 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 122 [2018-04-06 23:59:23,941 INFO L347 BasicCegarLoop]: Found error trace [2018-04-06 23:59:23,941 INFO L355 BasicCegarLoop]: trace histogram [9, 8, 8, 8, 8, 8, 8, 8, 8, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-06 23:59:23,942 INFO L408 AbstractCegarLoop]: === Iteration 16 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-06 23:59:23,942 INFO L82 PathProgramCache]: Analyzing trace with hash -1202228017, 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-06 23:59:23,950 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-06 23:59:23,971 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-06 23:59:23,974 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-06 23:59:24,111 INFO L134 CoverageAnalysis]: Checked inductivity of 380 backedges. 0 proven. 168 refuted. 0 times theorem prover too weak. 212 trivial. 0 not checked. [2018-04-06 23:59:24,111 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-06 23:59:24,360 INFO L134 CoverageAnalysis]: Checked inductivity of 380 backedges. 0 proven. 168 refuted. 0 times theorem prover too weak. 212 trivial. 0 not checked. [2018-04-06 23:59:24,380 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-06 23:59:24,381 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 31 [2018-04-06 23:59:24,381 INFO L442 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-04-06 23:59:24,381 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-04-06 23:59:24,381 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=174, Invalid=818, Unknown=0, NotChecked=0, Total=992 [2018-04-06 23:59:24,382 INFO L87 Difference]: Start difference. First operand 379 states and 480 transitions. Second operand 32 states. [2018-04-06 23:59:25,550 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-06 23:59:25,550 INFO L93 Difference]: Finished difference Result 456 states and 588 transitions. [2018-04-06 23:59:25,550 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2018-04-06 23:59:25,550 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 121 [2018-04-06 23:59:25,550 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-06 23:59:25,552 INFO L225 Difference]: With dead ends: 456 [2018-04-06 23:59:25,553 INFO L226 Difference]: Without dead ends: 454 [2018-04-06 23:59:25,554 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 275 GetRequests, 211 SyntacticMatches, 0 SemanticMatches, 64 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 716 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=1096, Invalid=3194, Unknown=0, NotChecked=0, Total=4290 [2018-04-06 23:59:25,555 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 454 states. [2018-04-06 23:59:25,574 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 454 to 451. [2018-04-06 23:59:25,574 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-04-06 23:59:25,577 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 568 transitions. [2018-04-06 23:59:25,577 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 568 transitions. Word has length 121 [2018-04-06 23:59:25,578 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-06 23:59:25,578 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 568 transitions. [2018-04-06 23:59:25,578 INFO L460 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-04-06 23:59:25,578 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 568 transitions. [2018-04-06 23:59:25,582 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 178 [2018-04-06 23:59:25,582 INFO L347 BasicCegarLoop]: Found error trace [2018-04-06 23:59:25,582 INFO L355 BasicCegarLoop]: trace histogram [16, 16, 15, 15, 15, 15, 15, 9, 8, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-06 23:59:25,582 INFO L408 AbstractCegarLoop]: === Iteration 17 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-06 23:59:25,582 INFO L82 PathProgramCache]: Analyzing trace with hash -1402567217, now seen corresponding path program 11 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-06 23:59:25,601 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-06 23:59:25,635 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-06 23:59:25,638 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-06 23:59:26,005 INFO L134 CoverageAnalysis]: Checked inductivity of 992 backedges. 626 proven. 212 refuted. 0 times theorem prover too weak. 154 trivial. 0 not checked. [2018-04-06 23:59:26,005 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-06 23:59:26,362 INFO L134 CoverageAnalysis]: Checked inductivity of 992 backedges. 626 proven. 212 refuted. 0 times theorem prover too weak. 154 trivial. 0 not checked. [2018-04-06 23:59:26,382 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-06 23:59:26,382 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [37, 37] total 54 [2018-04-06 23:59:26,383 INFO L442 AbstractCegarLoop]: Interpolant automaton has 54 states [2018-04-06 23:59:26,383 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 54 interpolants. [2018-04-06 23:59:26,383 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=395, Invalid=2467, Unknown=0, NotChecked=0, Total=2862 [2018-04-06 23:59:26,384 INFO L87 Difference]: Start difference. First operand 451 states and 568 transitions. Second operand 54 states. [2018-04-06 23:59:27,290 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-06 23:59:27,290 INFO L93 Difference]: Finished difference Result 602 states and 749 transitions. [2018-04-06 23:59:27,291 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 61 states. [2018-04-06 23:59:27,291 INFO L78 Accepts]: Start accepts. Automaton has 54 states. Word has length 177 [2018-04-06 23:59:27,291 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-06 23:59:27,293 INFO L225 Difference]: With dead ends: 602 [2018-04-06 23:59:27,294 INFO L226 Difference]: Without dead ends: 451 [2018-04-06 23:59:27,295 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 394 GetRequests, 283 SyntacticMatches, 18 SemanticMatches, 93 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2433 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=1333, Invalid=7597, Unknown=0, NotChecked=0, Total=8930 [2018-04-06 23:59:27,296 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-04-06 23:59:27,311 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-04-06 23:59:27,311 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-04-06 23:59:27,314 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 567 transitions. [2018-04-06 23:59:27,314 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 567 transitions. Word has length 177 [2018-04-06 23:59:27,314 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-06 23:59:27,314 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 567 transitions. [2018-04-06 23:59:27,314 INFO L460 AbstractCegarLoop]: Interpolant automaton has 54 states. [2018-04-06 23:59:27,314 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 567 transitions. [2018-04-06 23:59:27,317 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 185 [2018-04-06 23:59:27,318 INFO L347 BasicCegarLoop]: Found error trace [2018-04-06 23:59:27,318 INFO L355 BasicCegarLoop]: trace histogram [16, 16, 15, 15, 15, 15, 15, 10, 9, 9, 9, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-06 23:59:27,318 INFO L408 AbstractCegarLoop]: === Iteration 18 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-06 23:59:27,318 INFO L82 PathProgramCache]: Analyzing trace with hash -2018430946, now seen corresponding path program 12 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-06 23:59:27,327 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-06 23:59:27,357 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-06 23:59:27,360 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-06 23:59:27,747 INFO L134 CoverageAnalysis]: Checked inductivity of 1050 backedges. 669 proven. 270 refuted. 0 times theorem prover too weak. 111 trivial. 0 not checked. [2018-04-06 23:59:27,748 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-06 23:59:28,179 INFO L134 CoverageAnalysis]: Checked inductivity of 1050 backedges. 669 proven. 270 refuted. 0 times theorem prover too weak. 111 trivial. 0 not checked. [2018-04-06 23:59:28,200 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-06 23:59:28,200 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [41, 41] total 60 [2018-04-06 23:59:28,200 INFO L442 AbstractCegarLoop]: Interpolant automaton has 60 states [2018-04-06 23:59:28,201 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 60 interpolants. [2018-04-06 23:59:28,201 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=479, Invalid=3061, Unknown=0, NotChecked=0, Total=3540 [2018-04-06 23:59:28,201 INFO L87 Difference]: Start difference. First operand 451 states and 567 transitions. Second operand 60 states. [2018-04-06 23:59:29,431 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-06 23:59:29,431 INFO L93 Difference]: Finished difference Result 602 states and 748 transitions. [2018-04-06 23:59:29,432 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 68 states. [2018-04-06 23:59:29,432 INFO L78 Accepts]: Start accepts. Automaton has 60 states. Word has length 184 [2018-04-06 23:59:29,432 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-06 23:59:29,433 INFO L225 Difference]: With dead ends: 602 [2018-04-06 23:59:29,434 INFO L226 Difference]: Without dead ends: 451 [2018-04-06 23:59:29,435 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 413 GetRequests, 289 SyntacticMatches, 20 SemanticMatches, 104 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3066 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=1637, Invalid=9493, Unknown=0, NotChecked=0, Total=11130 [2018-04-06 23:59:29,435 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-04-06 23:59:29,444 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-04-06 23:59:29,445 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-04-06 23:59:29,447 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 566 transitions. [2018-04-06 23:59:29,447 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 566 transitions. Word has length 184 [2018-04-06 23:59:29,447 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-06 23:59:29,447 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 566 transitions. [2018-04-06 23:59:29,447 INFO L460 AbstractCegarLoop]: Interpolant automaton has 60 states. [2018-04-06 23:59:29,447 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 566 transitions. [2018-04-06 23:59:29,449 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 192 [2018-04-06 23:59:29,449 INFO L347 BasicCegarLoop]: Found error trace [2018-04-06 23:59:29,450 INFO L355 BasicCegarLoop]: trace histogram [16, 16, 15, 15, 15, 15, 15, 11, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-06 23:59:29,450 INFO L408 AbstractCegarLoop]: === Iteration 19 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-06 23:59:29,450 INFO L82 PathProgramCache]: Analyzing trace with hash -613409041, now seen corresponding path program 13 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-06 23:59:29,464 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-06 23:59:29,491 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-06 23:59:29,495 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-06 23:59:30,025 INFO L134 CoverageAnalysis]: Checked inductivity of 1115 backedges. 705 proven. 335 refuted. 0 times theorem prover too weak. 75 trivial. 0 not checked. [2018-04-06 23:59:30,026 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-06 23:59:30,553 INFO L134 CoverageAnalysis]: Checked inductivity of 1115 backedges. 705 proven. 335 refuted. 0 times theorem prover too weak. 75 trivial. 0 not checked. [2018-04-06 23:59:30,573 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-06 23:59:30,574 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [45, 45] total 66 [2018-04-06 23:59:30,574 INFO L442 AbstractCegarLoop]: Interpolant automaton has 66 states [2018-04-06 23:59:30,575 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 66 interpolants. [2018-04-06 23:59:30,575 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=571, Invalid=3719, Unknown=0, NotChecked=0, Total=4290 [2018-04-06 23:59:30,575 INFO L87 Difference]: Start difference. First operand 451 states and 566 transitions. Second operand 66 states. [2018-04-06 23:59:31,823 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-06 23:59:31,823 INFO L93 Difference]: Finished difference Result 602 states and 747 transitions. [2018-04-06 23:59:31,823 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 75 states. [2018-04-06 23:59:31,823 INFO L78 Accepts]: Start accepts. Automaton has 66 states. Word has length 191 [2018-04-06 23:59:31,824 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-06 23:59:31,825 INFO L225 Difference]: With dead ends: 602 [2018-04-06 23:59:31,825 INFO L226 Difference]: Without dead ends: 451 [2018-04-06 23:59:31,826 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 432 GetRequests, 295 SyntacticMatches, 22 SemanticMatches, 115 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3772 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=1972, Invalid=11600, Unknown=0, NotChecked=0, Total=13572 [2018-04-06 23:59:31,827 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-04-06 23:59:31,840 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-04-06 23:59:31,841 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-04-06 23:59:31,842 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 565 transitions. [2018-04-06 23:59:31,843 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 565 transitions. Word has length 191 [2018-04-06 23:59:31,843 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-06 23:59:31,843 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 565 transitions. [2018-04-06 23:59:31,843 INFO L460 AbstractCegarLoop]: Interpolant automaton has 66 states. [2018-04-06 23:59:31,843 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 565 transitions. [2018-04-06 23:59:31,846 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 199 [2018-04-06 23:59:31,846 INFO L347 BasicCegarLoop]: Found error trace [2018-04-06 23:59:31,846 INFO L355 BasicCegarLoop]: trace histogram [16, 16, 15, 15, 15, 15, 15, 12, 11, 11, 11, 11, 11, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-06 23:59:31,846 INFO L408 AbstractCegarLoop]: === Iteration 20 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-06 23:59:31,846 INFO L82 PathProgramCache]: Analyzing trace with hash -1669393666, now seen corresponding path program 14 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-06 23:59:31,856 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-06 23:59:31,894 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-06 23:59:31,899 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-06 23:59:32,509 INFO L134 CoverageAnalysis]: Checked inductivity of 1187 backedges. 734 proven. 407 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2018-04-06 23:59:32,509 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-06 23:59:33,134 INFO L134 CoverageAnalysis]: Checked inductivity of 1187 backedges. 734 proven. 407 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2018-04-06 23:59:33,155 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-06 23:59:33,155 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [49, 49] total 72 [2018-04-06 23:59:33,155 INFO L442 AbstractCegarLoop]: Interpolant automaton has 72 states [2018-04-06 23:59:33,156 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 72 interpolants. [2018-04-06 23:59:33,156 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=671, Invalid=4441, Unknown=0, NotChecked=0, Total=5112 [2018-04-06 23:59:33,156 INFO L87 Difference]: Start difference. First operand 451 states and 565 transitions. Second operand 72 states. [2018-04-06 23:59:34,618 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-06 23:59:34,619 INFO L93 Difference]: Finished difference Result 602 states and 746 transitions. [2018-04-06 23:59:34,658 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 82 states. [2018-04-06 23:59:34,658 INFO L78 Accepts]: Start accepts. Automaton has 72 states. Word has length 198 [2018-04-06 23:59:34,659 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-06 23:59:34,661 INFO L225 Difference]: With dead ends: 602 [2018-04-06 23:59:34,661 INFO L226 Difference]: Without dead ends: 451 [2018-04-06 23:59:34,663 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 451 GetRequests, 301 SyntacticMatches, 24 SemanticMatches, 126 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4551 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=2338, Invalid=13918, Unknown=0, NotChecked=0, Total=16256 [2018-04-06 23:59:34,664 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-04-06 23:59:34,677 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-04-06 23:59:34,677 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-04-06 23:59:34,679 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 564 transitions. [2018-04-06 23:59:34,679 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 564 transitions. Word has length 198 [2018-04-06 23:59:34,680 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-06 23:59:34,680 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 564 transitions. [2018-04-06 23:59:34,680 INFO L460 AbstractCegarLoop]: Interpolant automaton has 72 states. [2018-04-06 23:59:34,680 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 564 transitions. [2018-04-06 23:59:34,682 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 206 [2018-04-06 23:59:34,682 INFO L347 BasicCegarLoop]: Found error trace [2018-04-06 23:59:34,682 INFO L355 BasicCegarLoop]: trace histogram [16, 16, 15, 15, 15, 15, 15, 13, 12, 12, 12, 12, 12, 12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-06 23:59:34,683 INFO L408 AbstractCegarLoop]: === Iteration 21 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-06 23:59:34,683 INFO L82 PathProgramCache]: Analyzing trace with hash -458801137, now seen corresponding path program 15 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-06 23:59:34,691 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-06 23:59:34,725 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-06 23:59:34,729 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-06 23:59:35,436 INFO L134 CoverageAnalysis]: Checked inductivity of 1266 backedges. 756 proven. 486 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2018-04-06 23:59:35,436 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-06 23:59:36,146 INFO L134 CoverageAnalysis]: Checked inductivity of 1266 backedges. 756 proven. 486 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2018-04-06 23:59:36,166 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-06 23:59:36,167 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [53, 53] total 78 [2018-04-06 23:59:36,167 INFO L442 AbstractCegarLoop]: Interpolant automaton has 78 states [2018-04-06 23:59:36,167 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 78 interpolants. [2018-04-06 23:59:36,168 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=779, Invalid=5227, Unknown=0, NotChecked=0, Total=6006 [2018-04-06 23:59:36,168 INFO L87 Difference]: Start difference. First operand 451 states and 564 transitions. Second operand 78 states. [2018-04-06 23:59:37,937 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-06 23:59:37,937 INFO L93 Difference]: Finished difference Result 602 states and 745 transitions. [2018-04-06 23:59:37,938 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 89 states. [2018-04-06 23:59:37,938 INFO L78 Accepts]: Start accepts. Automaton has 78 states. Word has length 205 [2018-04-06 23:59:37,938 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-06 23:59:37,939 INFO L225 Difference]: With dead ends: 602 [2018-04-06 23:59:37,939 INFO L226 Difference]: Without dead ends: 451 [2018-04-06 23:59:37,941 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 470 GetRequests, 307 SyntacticMatches, 26 SemanticMatches, 137 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5403 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=2735, Invalid=16447, Unknown=0, NotChecked=0, Total=19182 [2018-04-06 23:59:37,941 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-04-06 23:59:37,954 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-04-06 23:59:37,954 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-04-06 23:59:37,956 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 563 transitions. [2018-04-06 23:59:37,956 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 563 transitions. Word has length 205 [2018-04-06 23:59:37,956 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-06 23:59:37,957 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 563 transitions. [2018-04-06 23:59:37,957 INFO L460 AbstractCegarLoop]: Interpolant automaton has 78 states. [2018-04-06 23:59:37,957 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 563 transitions. [2018-04-06 23:59:37,959 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 213 [2018-04-06 23:59:37,959 INFO L347 BasicCegarLoop]: Found error trace [2018-04-06 23:59:37,959 INFO L355 BasicCegarLoop]: trace histogram [16, 16, 15, 15, 15, 15, 15, 14, 13, 13, 13, 13, 13, 13, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-06 23:59:37,960 INFO L408 AbstractCegarLoop]: === Iteration 22 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-06 23:59:37,960 INFO L82 PathProgramCache]: Analyzing trace with hash 441871838, now seen corresponding path program 16 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-06 23:59:37,969 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-06 23:59:38,010 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-06 23:59:38,014 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-06 23:59:38,750 INFO L134 CoverageAnalysis]: Checked inductivity of 1352 backedges. 771 proven. 572 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2018-04-06 23:59:38,750 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-06 23:59:39,566 INFO L134 CoverageAnalysis]: Checked inductivity of 1352 backedges. 771 proven. 572 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2018-04-06 23:59:39,587 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-06 23:59:39,587 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [57, 57] total 84 [2018-04-06 23:59:39,588 INFO L442 AbstractCegarLoop]: Interpolant automaton has 84 states [2018-04-06 23:59:39,588 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 84 interpolants. [2018-04-06 23:59:39,588 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=895, Invalid=6077, Unknown=0, NotChecked=0, Total=6972 [2018-04-06 23:59:39,588 INFO L87 Difference]: Start difference. First operand 451 states and 563 transitions. Second operand 84 states. [2018-04-06 23:59:41,452 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-06 23:59:41,453 INFO L93 Difference]: Finished difference Result 602 states and 744 transitions. [2018-04-06 23:59:41,453 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 96 states. [2018-04-06 23:59:41,453 INFO L78 Accepts]: Start accepts. Automaton has 84 states. Word has length 212 [2018-04-06 23:59:41,454 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-06 23:59:41,456 INFO L225 Difference]: With dead ends: 602 [2018-04-06 23:59:41,456 INFO L226 Difference]: Without dead ends: 451 [2018-04-06 23:59:41,457 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 489 GetRequests, 313 SyntacticMatches, 28 SemanticMatches, 148 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6328 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=3163, Invalid=19187, Unknown=0, NotChecked=0, Total=22350 [2018-04-06 23:59:41,457 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-04-06 23:59:41,466 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-04-06 23:59:41,466 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-04-06 23:59:41,467 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 562 transitions. [2018-04-06 23:59:41,467 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 562 transitions. Word has length 212 [2018-04-06 23:59:41,468 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-06 23:59:41,468 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 562 transitions. [2018-04-06 23:59:41,468 INFO L460 AbstractCegarLoop]: Interpolant automaton has 84 states. [2018-04-06 23:59:41,468 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 562 transitions. [2018-04-06 23:59:41,469 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 220 [2018-04-06 23:59:41,469 INFO L347 BasicCegarLoop]: Found error trace [2018-04-06 23:59:41,469 INFO L355 BasicCegarLoop]: trace histogram [16, 16, 15, 15, 15, 15, 15, 15, 14, 14, 14, 14, 14, 14, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-06 23:59:41,469 INFO L408 AbstractCegarLoop]: === Iteration 23 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-06 23:59:41,470 INFO L82 PathProgramCache]: Analyzing trace with hash -2051151569, now seen corresponding path program 17 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-06 23:59:41,476 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-06 23:59:41,507 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-06 23:59:41,511 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-06 23:59:42,446 INFO L134 CoverageAnalysis]: Checked inductivity of 1445 backedges. 779 proven. 665 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-04-06 23:59:42,446 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-06 23:59:43,386 INFO L134 CoverageAnalysis]: Checked inductivity of 1445 backedges. 779 proven. 665 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-04-06 23:59:43,407 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-06 23:59:43,407 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [61, 61] total 90 [2018-04-06 23:59:43,408 INFO L442 AbstractCegarLoop]: Interpolant automaton has 90 states [2018-04-06 23:59:43,408 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 90 interpolants. [2018-04-06 23:59:43,408 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1019, Invalid=6991, Unknown=0, NotChecked=0, Total=8010 [2018-04-06 23:59:43,409 INFO L87 Difference]: Start difference. First operand 451 states and 562 transitions. Second operand 90 states. [2018-04-06 23:59:45,534 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-06 23:59:45,534 INFO L93 Difference]: Finished difference Result 602 states and 743 transitions. [2018-04-06 23:59:45,534 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 103 states. [2018-04-06 23:59:45,534 INFO L78 Accepts]: Start accepts. Automaton has 90 states. Word has length 219 [2018-04-06 23:59:45,535 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-06 23:59:45,536 INFO L225 Difference]: With dead ends: 602 [2018-04-06 23:59:45,536 INFO L226 Difference]: Without dead ends: 451 [2018-04-06 23:59:45,537 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 508 GetRequests, 319 SyntacticMatches, 30 SemanticMatches, 159 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7326 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=3622, Invalid=22138, Unknown=0, NotChecked=0, Total=25760 [2018-04-06 23:59:45,538 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-04-06 23:59:45,549 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-04-06 23:59:45,549 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-04-06 23:59:45,551 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 561 transitions. [2018-04-06 23:59:45,551 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 561 transitions. Word has length 219 [2018-04-06 23:59:45,552 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-06 23:59:45,552 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 561 transitions. [2018-04-06 23:59:45,552 INFO L460 AbstractCegarLoop]: Interpolant automaton has 90 states. [2018-04-06 23:59:45,552 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 561 transitions. [2018-04-06 23:59:45,555 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 227 [2018-04-06 23:59:45,555 INFO L347 BasicCegarLoop]: Found error trace [2018-04-06 23:59:45,555 INFO L355 BasicCegarLoop]: trace histogram [16, 16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-06 23:59:45,555 INFO L408 AbstractCegarLoop]: === Iteration 24 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-06 23:59:45,556 INFO L82 PathProgramCache]: Analyzing trace with hash -683327298, now seen corresponding path program 18 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-06 23:59:45,565 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-06 23:59:45,599 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-06 23:59:45,605 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-06 23:59:46,539 INFO L134 CoverageAnalysis]: Checked inductivity of 1545 backedges. 780 proven. 765 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-06 23:59:46,540 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-06 23:59:47,630 INFO L134 CoverageAnalysis]: Checked inductivity of 1545 backedges. 780 proven. 765 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-06 23:59:47,652 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-06 23:59:47,652 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [65, 65] total 96 [2018-04-06 23:59:47,652 INFO L442 AbstractCegarLoop]: Interpolant automaton has 96 states [2018-04-06 23:59:47,653 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 96 interpolants. [2018-04-06 23:59:47,654 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1151, Invalid=7969, Unknown=0, NotChecked=0, Total=9120 [2018-04-06 23:59:47,654 INFO L87 Difference]: Start difference. First operand 451 states and 561 transitions. Second operand 96 states. [2018-04-06 23:59:50,287 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-06 23:59:50,288 INFO L93 Difference]: Finished difference Result 608 states and 749 transitions. [2018-04-06 23:59:50,288 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 110 states. [2018-04-06 23:59:50,288 INFO L78 Accepts]: Start accepts. Automaton has 96 states. Word has length 226 [2018-04-06 23:59:50,288 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-06 23:59:50,290 INFO L225 Difference]: With dead ends: 608 [2018-04-06 23:59:50,290 INFO L226 Difference]: Without dead ends: 451 [2018-04-06 23:59:50,291 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 527 GetRequests, 325 SyntacticMatches, 32 SemanticMatches, 170 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8397 ImplicationChecksByTransitivity, 3.5s TimeCoverageRelationStatistics Valid=4112, Invalid=25300, Unknown=0, NotChecked=0, Total=29412 [2018-04-06 23:59:50,291 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-04-06 23:59:50,303 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-04-06 23:59:50,304 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-04-06 23:59:50,305 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 560 transitions. [2018-04-06 23:59:50,306 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 560 transitions. Word has length 226 [2018-04-06 23:59:50,306 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-06 23:59:50,306 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 560 transitions. [2018-04-06 23:59:50,306 INFO L460 AbstractCegarLoop]: Interpolant automaton has 96 states. [2018-04-06 23:59:50,306 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 560 transitions. [2018-04-06 23:59:50,309 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 231 [2018-04-06 23:59:50,309 INFO L347 BasicCegarLoop]: Found error trace [2018-04-06 23:59:50,309 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-06 23:59:50,309 INFO L408 AbstractCegarLoop]: === Iteration 25 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-06 23:59:50,309 INFO L82 PathProgramCache]: Analyzing trace with hash -1502780312, now seen corresponding path program 5 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-06 23:59:50,320 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-06 23:59:50,362 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-06 23:59:50,370 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-06 23:59:51,623 INFO L134 CoverageAnalysis]: Checked inductivity of 3348 backedges. 0 proven. 3348 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-06 23:59:51,623 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-06 23:59:55,120 INFO L134 CoverageAnalysis]: Checked inductivity of 3348 backedges. 0 proven. 3348 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-06 23:59:55,141 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-06 23:59:55,141 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [64, 64] total 127 [2018-04-06 23:59:55,142 INFO L442 AbstractCegarLoop]: Interpolant automaton has 128 states [2018-04-06 23:59:55,142 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 128 interpolants. [2018-04-06 23:59:55,143 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2238, Invalid=14018, Unknown=0, NotChecked=0, Total=16256 [2018-04-06 23:59:55,143 INFO L87 Difference]: Start difference. First operand 451 states and 560 transitions. Second operand 128 states. [2018-04-07 00:00:01,315 WARN L151 SmtUtils]: Spent 253ms on a formula simplification. DAG size of input: 252 DAG size of output 12 [2018-04-07 00:00:02,029 WARN L151 SmtUtils]: Spent 249ms on a formula simplification. DAG size of input: 247 DAG size of output 11 [2018-04-07 00:00:02,517 WARN L151 SmtUtils]: Spent 254ms on a formula simplification. DAG size of input: 244 DAG size of output 12 [2018-04-07 00:00:03,216 WARN L151 SmtUtils]: Spent 251ms on a formula simplification. DAG size of input: 239 DAG size of output 11 [2018-04-07 00:00:03,674 WARN L151 SmtUtils]: Spent 224ms on a formula simplification. DAG size of input: 236 DAG size of output 12 [2018-04-07 00:00:04,330 WARN L151 SmtUtils]: Spent 223ms on a formula simplification. DAG size of input: 231 DAG size of output 11 [2018-04-07 00:00:04,761 WARN L151 SmtUtils]: Spent 205ms on a formula simplification. DAG size of input: 228 DAG size of output 12 [2018-04-07 00:00:05,406 WARN L151 SmtUtils]: Spent 201ms on a formula simplification. DAG size of input: 223 DAG size of output 11 [2018-04-07 00:00:05,834 WARN L151 SmtUtils]: Spent 201ms on a formula simplification. DAG size of input: 220 DAG size of output 12 [2018-04-07 00:00:06,462 WARN L151 SmtUtils]: Spent 196ms on a formula simplification. DAG size of input: 215 DAG size of output 11 [2018-04-07 00:00:06,891 WARN L151 SmtUtils]: Spent 195ms on a formula simplification. DAG size of input: 212 DAG size of output 12 [2018-04-07 00:00:07,150 WARN L151 SmtUtils]: Spent 127ms on a formula simplification. DAG size of input: 131 DAG size of output 6 [2018-04-07 00:00:07,661 WARN L151 SmtUtils]: Spent 179ms on a formula simplification. DAG size of input: 207 DAG size of output 11 [2018-04-07 00:00:08,067 WARN L151 SmtUtils]: Spent 175ms on a formula simplification. DAG size of input: 204 DAG size of output 12 [2018-04-07 00:00:08,666 WARN L151 SmtUtils]: Spent 179ms on a formula simplification. DAG size of input: 199 DAG size of output 11 [2018-04-07 00:00:09,059 WARN L151 SmtUtils]: Spent 166ms on a formula simplification. DAG size of input: 196 DAG size of output 12 [2018-04-07 00:00:09,633 WARN L151 SmtUtils]: Spent 157ms on a formula simplification. DAG size of input: 191 DAG size of output 11 [2018-04-07 00:00:10,003 WARN L151 SmtUtils]: Spent 147ms on a formula simplification. DAG size of input: 188 DAG size of output 12 [2018-04-07 00:00:10,545 WARN L151 SmtUtils]: Spent 143ms on a formula simplification. DAG size of input: 183 DAG size of output 11 [2018-04-07 00:00:10,916 WARN L151 SmtUtils]: Spent 141ms on a formula simplification. DAG size of input: 180 DAG size of output 12 [2018-04-07 00:00:11,452 WARN L151 SmtUtils]: Spent 133ms on a formula simplification. DAG size of input: 175 DAG size of output 11 [2018-04-07 00:00:11,829 WARN L151 SmtUtils]: Spent 140ms on a formula simplification. DAG size of input: 172 DAG size of output 12 [2018-04-07 00:00:12,365 WARN L151 SmtUtils]: Spent 127ms on a formula simplification. DAG size of input: 167 DAG size of output 11 [2018-04-07 00:00:12,698 WARN L151 SmtUtils]: Spent 117ms on a formula simplification. DAG size of input: 164 DAG size of output 12 [2018-04-07 00:00:13,204 WARN L151 SmtUtils]: Spent 112ms on a formula simplification. DAG size of input: 159 DAG size of output 11 [2018-04-07 00:00:13,540 WARN L151 SmtUtils]: Spent 119ms on a formula simplification. DAG size of input: 156 DAG size of output 12 [2018-04-07 00:00:14,025 WARN L151 SmtUtils]: Spent 103ms on a formula simplification. DAG size of input: 151 DAG size of output 11 [2018-04-07 00:00:14,340 WARN L151 SmtUtils]: Spent 102ms on a formula simplification. DAG size of input: 148 DAG size of output 12 [2018-04-07 00:00:17,333 WARN L151 SmtUtils]: Spent 151ms on a formula simplification. DAG size of input: 116 DAG size of output 12 [2018-04-07 00:00:17,971 WARN L151 SmtUtils]: Spent 115ms on a formula simplification. DAG size of input: 71 DAG size of output 6 [2018-04-07 00:00:21,898 WARN L151 SmtUtils]: Spent 122ms on a formula simplification. DAG size of input: 79 DAG size of output 11 [2018-04-07 00:00:28,275 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-07 00:00:28,275 INFO L93 Difference]: Finished difference Result 791 states and 1059 transitions. [2018-04-07 00:00:28,275 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 189 states. [2018-04-07 00:00:28,275 INFO L78 Accepts]: Start accepts. Automaton has 128 states. Word has length 230 [2018-04-07 00:00:28,275 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-07 00:00:28,278 INFO L225 Difference]: With dead ends: 791 [2018-04-07 00:00:28,278 INFO L226 Difference]: Without dead ends: 789 [2018-04-07 00:00:28,280 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 613 GetRequests, 333 SyntacticMatches, 0 SemanticMatches, 280 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15068 ImplicationChecksByTransitivity, 31.6s TimeCoverageRelationStatistics Valid=18976, Invalid=60266, Unknown=0, NotChecked=0, Total=79242 [2018-04-07 00:00:28,281 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 789 states. [2018-04-07 00:00:28,298 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 789 to 739. [2018-04-07 00:00:28,298 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 739 states. [2018-04-07 00:00:28,301 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 739 states to 739 states and 944 transitions. [2018-04-07 00:00:28,302 INFO L78 Accepts]: Start accepts. Automaton has 739 states and 944 transitions. Word has length 230 [2018-04-07 00:00:28,302 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-07 00:00:28,303 INFO L459 AbstractCegarLoop]: Abstraction has 739 states and 944 transitions. [2018-04-07 00:00:28,303 INFO L460 AbstractCegarLoop]: Interpolant automaton has 128 states. [2018-04-07 00:00:28,303 INFO L276 IsEmpty]: Start isEmpty. Operand 739 states and 944 transitions. [2018-04-07 00:00:28,306 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 234 [2018-04-07 00:00:28,306 INFO L347 BasicCegarLoop]: Found error trace [2018-04-07 00:00:28,306 INFO L355 BasicCegarLoop]: trace histogram [17, 16, 16, 16, 16, 16, 16, 16, 16, 15, 15, 15, 15, 15, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-07 00:00:28,306 INFO L408 AbstractCegarLoop]: === Iteration 26 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-07 00:00:28,307 INFO L82 PathProgramCache]: Analyzing trace with hash -1662641585, 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-07 00:00:28,324 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-07 00:00:28,373 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-07 00:00:28,379 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-07 00:00:28,797 INFO L134 CoverageAnalysis]: Checked inductivity of 1652 backedges. 0 proven. 780 refuted. 0 times theorem prover too weak. 872 trivial. 0 not checked. [2018-04-07 00:00:28,798 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-07 00:00:29,924 INFO L134 CoverageAnalysis]: Checked inductivity of 1652 backedges. 0 proven. 780 refuted. 0 times theorem prover too weak. 872 trivial. 0 not checked. [2018-04-07 00:00:29,946 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-07 00:00:29,946 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [32, 32] total 63 [2018-04-07 00:00:29,947 INFO L442 AbstractCegarLoop]: Interpolant automaton has 64 states [2018-04-07 00:00:29,947 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 64 interpolants. [2018-04-07 00:00:29,948 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=606, Invalid=3426, Unknown=0, NotChecked=0, Total=4032 [2018-04-07 00:00:29,948 INFO L87 Difference]: Start difference. First operand 739 states and 944 transitions. Second operand 64 states. [2018-04-07 00:00:36,018 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-07 00:00:36,018 INFO L93 Difference]: Finished difference Result 888 states and 1156 transitions. [2018-04-07 00:00:36,019 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 93 states. [2018-04-07 00:00:36,019 INFO L78 Accepts]: Start accepts. Automaton has 64 states. Word has length 233 [2018-04-07 00:00:36,019 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-07 00:00:36,022 INFO L225 Difference]: With dead ends: 888 [2018-04-07 00:00:36,022 INFO L226 Difference]: Without dead ends: 886 [2018-04-07 00:00:36,023 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 539 GetRequests, 403 SyntacticMatches, 0 SemanticMatches, 136 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3452 ImplicationChecksByTransitivity, 5.9s TimeCoverageRelationStatistics Valid=4624, Invalid=14282, Unknown=0, NotChecked=0, Total=18906 [2018-04-07 00:00:36,023 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 886 states. [2018-04-07 00:00:36,043 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 886 to 883. [2018-04-07 00:00:36,043 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-07 00:00:36,046 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1120 transitions. [2018-04-07 00:00:36,047 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1120 transitions. Word has length 233 [2018-04-07 00:00:36,047 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-07 00:00:36,047 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1120 transitions. [2018-04-07 00:00:36,048 INFO L460 AbstractCegarLoop]: Interpolant automaton has 64 states. [2018-04-07 00:00:36,048 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1120 transitions. [2018-04-07 00:00:36,052 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 346 [2018-04-07 00:00:36,052 INFO L347 BasicCegarLoop]: Found error trace [2018-04-07 00:00:36,052 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 17, 16, 16, 16, 16, 16, 16, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-07 00:00:36,052 INFO L408 AbstractCegarLoop]: === Iteration 27 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-07 00:00:36,053 INFO L82 PathProgramCache]: Analyzing trace with hash -1581237169, now seen corresponding path program 20 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-07 00:00:36,068 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-07 00:00:36,140 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-07 00:00:36,149 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-07 00:00:37,270 INFO L134 CoverageAnalysis]: Checked inductivity of 4220 backedges. 2598 proven. 872 refuted. 0 times theorem prover too weak. 750 trivial. 0 not checked. [2018-04-07 00:00:37,270 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-07 00:00:38,560 INFO L134 CoverageAnalysis]: Checked inductivity of 4220 backedges. 2598 proven. 872 refuted. 0 times theorem prover too weak. 750 trivial. 0 not checked. [2018-04-07 00:00:38,581 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-07 00:00:38,582 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [69, 69] total 102 [2018-04-07 00:00:38,582 INFO L442 AbstractCegarLoop]: Interpolant automaton has 102 states [2018-04-07 00:00:38,583 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 102 interpolants. [2018-04-07 00:00:38,583 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1291, Invalid=9011, Unknown=0, NotChecked=0, Total=10302 [2018-04-07 00:00:38,583 INFO L87 Difference]: Start difference. First operand 883 states and 1120 transitions. Second operand 102 states. [2018-04-07 00:00:41,536 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-07 00:00:41,536 INFO L93 Difference]: Finished difference Result 1178 states and 1477 transitions. [2018-04-07 00:00:41,537 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 117 states. [2018-04-07 00:00:41,537 INFO L78 Accepts]: Start accepts. Automaton has 102 states. Word has length 345 [2018-04-07 00:00:41,537 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-07 00:00:41,540 INFO L225 Difference]: With dead ends: 1178 [2018-04-07 00:00:41,540 INFO L226 Difference]: Without dead ends: 883 [2018-04-07 00:00:41,542 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 770 GetRequests, 555 SyntacticMatches, 34 SemanticMatches, 181 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9541 ImplicationChecksByTransitivity, 4.0s TimeCoverageRelationStatistics Valid=4633, Invalid=28673, Unknown=0, NotChecked=0, Total=33306 [2018-04-07 00:00:41,542 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-07 00:00:41,564 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-07 00:00:41,564 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-07 00:00:41,567 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1119 transitions. [2018-04-07 00:00:41,568 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1119 transitions. Word has length 345 [2018-04-07 00:00:41,568 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-07 00:00:41,568 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1119 transitions. [2018-04-07 00:00:41,568 INFO L460 AbstractCegarLoop]: Interpolant automaton has 102 states. [2018-04-07 00:00:41,568 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1119 transitions. [2018-04-07 00:00:41,572 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 353 [2018-04-07 00:00:41,572 INFO L347 BasicCegarLoop]: Found error trace [2018-04-07 00:00:41,572 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 18, 17, 17, 17, 17, 17, 17, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-07 00:00:41,572 INFO L408 AbstractCegarLoop]: === Iteration 28 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-07 00:00:41,573 INFO L82 PathProgramCache]: Analyzing trace with hash -419284066, now seen corresponding path program 21 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-07 00:00:41,579 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-07 00:00:41,632 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-07 00:00:41,639 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-07 00:00:42,895 INFO L134 CoverageAnalysis]: Checked inductivity of 4334 backedges. 2697 proven. 986 refuted. 0 times theorem prover too weak. 651 trivial. 0 not checked. [2018-04-07 00:00:42,895 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-07 00:00:44,299 INFO L134 CoverageAnalysis]: Checked inductivity of 4334 backedges. 2697 proven. 986 refuted. 0 times theorem prover too weak. 651 trivial. 0 not checked. [2018-04-07 00:00:44,319 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-07 00:00:44,320 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [73, 73] total 108 [2018-04-07 00:00:44,320 INFO L442 AbstractCegarLoop]: Interpolant automaton has 108 states [2018-04-07 00:00:44,320 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 108 interpolants. [2018-04-07 00:00:44,321 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1439, Invalid=10117, Unknown=0, NotChecked=0, Total=11556 [2018-04-07 00:00:44,321 INFO L87 Difference]: Start difference. First operand 883 states and 1119 transitions. Second operand 108 states. [2018-04-07 00:00:47,708 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-07 00:00:47,708 INFO L93 Difference]: Finished difference Result 1178 states and 1476 transitions. [2018-04-07 00:00:47,708 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 124 states. [2018-04-07 00:00:47,708 INFO L78 Accepts]: Start accepts. Automaton has 108 states. Word has length 352 [2018-04-07 00:00:47,709 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-07 00:00:47,711 INFO L225 Difference]: With dead ends: 1178 [2018-04-07 00:00:47,711 INFO L226 Difference]: Without dead ends: 883 [2018-04-07 00:00:47,714 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 789 GetRequests, 561 SyntacticMatches, 36 SemanticMatches, 192 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10758 ImplicationChecksByTransitivity, 4.5s TimeCoverageRelationStatistics Valid=5185, Invalid=32257, Unknown=0, NotChecked=0, Total=37442 [2018-04-07 00:00:47,714 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-07 00:00:47,726 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-07 00:00:47,726 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-07 00:00:47,728 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1118 transitions. [2018-04-07 00:00:47,729 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1118 transitions. Word has length 352 [2018-04-07 00:00:47,729 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-07 00:00:47,729 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1118 transitions. [2018-04-07 00:00:47,729 INFO L460 AbstractCegarLoop]: Interpolant automaton has 108 states. [2018-04-07 00:00:47,729 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1118 transitions. [2018-04-07 00:00:47,732 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 360 [2018-04-07 00:00:47,732 INFO L347 BasicCegarLoop]: Found error trace [2018-04-07 00:00:47,733 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 19, 18, 18, 18, 18, 18, 18, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-07 00:00:47,733 INFO L408 AbstractCegarLoop]: === Iteration 29 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-07 00:00:47,733 INFO L82 PathProgramCache]: Analyzing trace with hash -1060096657, now seen corresponding path program 22 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-07 00:00:47,747 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-07 00:00:47,799 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-07 00:00:47,808 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-07 00:00:49,121 INFO L134 CoverageAnalysis]: Checked inductivity of 4455 backedges. 2789 proven. 1107 refuted. 0 times theorem prover too weak. 559 trivial. 0 not checked. [2018-04-07 00:00:49,121 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-07 00:00:50,672 INFO L134 CoverageAnalysis]: Checked inductivity of 4455 backedges. 2789 proven. 1107 refuted. 0 times theorem prover too weak. 559 trivial. 0 not checked. [2018-04-07 00:00:50,693 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-07 00:00:50,693 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [77, 77] total 114 [2018-04-07 00:00:50,694 INFO L442 AbstractCegarLoop]: Interpolant automaton has 114 states [2018-04-07 00:00:50,694 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 114 interpolants. [2018-04-07 00:00:50,694 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1595, Invalid=11287, Unknown=0, NotChecked=0, Total=12882 [2018-04-07 00:00:50,694 INFO L87 Difference]: Start difference. First operand 883 states and 1118 transitions. Second operand 114 states. [2018-04-07 00:00:54,447 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-07 00:00:54,449 INFO L93 Difference]: Finished difference Result 1178 states and 1475 transitions. [2018-04-07 00:00:54,449 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 131 states. [2018-04-07 00:00:54,449 INFO L78 Accepts]: Start accepts. Automaton has 114 states. Word has length 359 [2018-04-07 00:00:54,450 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-07 00:00:54,454 INFO L225 Difference]: With dead ends: 1178 [2018-04-07 00:00:54,454 INFO L226 Difference]: Without dead ends: 883 [2018-04-07 00:00:54,457 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 808 GetRequests, 567 SyntacticMatches, 38 SemanticMatches, 203 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12048 ImplicationChecksByTransitivity, 4.9s TimeCoverageRelationStatistics Valid=5768, Invalid=36052, Unknown=0, NotChecked=0, Total=41820 [2018-04-07 00:00:54,458 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-07 00:00:54,469 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-07 00:00:54,469 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-07 00:00:54,471 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1117 transitions. [2018-04-07 00:00:54,472 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1117 transitions. Word has length 359 [2018-04-07 00:00:54,472 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-07 00:00:54,472 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1117 transitions. [2018-04-07 00:00:54,472 INFO L460 AbstractCegarLoop]: Interpolant automaton has 114 states. [2018-04-07 00:00:54,472 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1117 transitions. [2018-04-07 00:00:54,474 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 367 [2018-04-07 00:00:54,474 INFO L347 BasicCegarLoop]: Found error trace [2018-04-07 00:00:54,474 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 20, 19, 19, 19, 19, 19, 19, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-07 00:00:54,474 INFO L408 AbstractCegarLoop]: === Iteration 30 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-07 00:00:54,474 INFO L82 PathProgramCache]: Analyzing trace with hash -1981956482, now seen corresponding path program 23 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-07 00:00:54,481 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-07 00:00:54,536 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-07 00:00:54,543 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-07 00:00:56,193 INFO L134 CoverageAnalysis]: Checked inductivity of 4583 backedges. 2874 proven. 1235 refuted. 0 times theorem prover too weak. 474 trivial. 0 not checked. [2018-04-07 00:00:56,193 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-07 00:00:57,999 INFO L134 CoverageAnalysis]: Checked inductivity of 4583 backedges. 2874 proven. 1235 refuted. 0 times theorem prover too weak. 474 trivial. 0 not checked. [2018-04-07 00:00:58,020 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-07 00:00:58,020 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [81, 81] total 120 [2018-04-07 00:00:58,020 INFO L442 AbstractCegarLoop]: Interpolant automaton has 120 states [2018-04-07 00:00:58,021 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 120 interpolants. [2018-04-07 00:00:58,021 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1759, Invalid=12521, Unknown=0, NotChecked=0, Total=14280 [2018-04-07 00:00:58,021 INFO L87 Difference]: Start difference. First operand 883 states and 1117 transitions. Second operand 120 states. [2018-04-07 00:01:02,227 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-07 00:01:02,227 INFO L93 Difference]: Finished difference Result 1178 states and 1474 transitions. [2018-04-07 00:01:02,228 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 138 states. [2018-04-07 00:01:02,228 INFO L78 Accepts]: Start accepts. Automaton has 120 states. Word has length 366 [2018-04-07 00:01:02,228 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-07 00:01:02,231 INFO L225 Difference]: With dead ends: 1178 [2018-04-07 00:01:02,231 INFO L226 Difference]: Without dead ends: 883 [2018-04-07 00:01:02,233 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 827 GetRequests, 573 SyntacticMatches, 40 SemanticMatches, 214 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13411 ImplicationChecksByTransitivity, 5.7s TimeCoverageRelationStatistics Valid=6382, Invalid=40058, Unknown=0, NotChecked=0, Total=46440 [2018-04-07 00:01:02,233 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-07 00:01:02,244 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-07 00:01:02,245 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-07 00:01:02,246 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1116 transitions. [2018-04-07 00:01:02,247 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1116 transitions. Word has length 366 [2018-04-07 00:01:02,247 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-07 00:01:02,247 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1116 transitions. [2018-04-07 00:01:02,247 INFO L460 AbstractCegarLoop]: Interpolant automaton has 120 states. [2018-04-07 00:01:02,247 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1116 transitions. [2018-04-07 00:01:02,249 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 374 [2018-04-07 00:01:02,249 INFO L347 BasicCegarLoop]: Found error trace [2018-04-07 00:01:02,249 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 21, 20, 20, 20, 20, 20, 20, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-07 00:01:02,249 INFO L408 AbstractCegarLoop]: === Iteration 31 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-07 00:01:02,249 INFO L82 PathProgramCache]: Analyzing trace with hash 2137372303, now seen corresponding path program 24 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-07 00:01:02,257 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-07 00:01:02,308 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-07 00:01:02,313 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-07 00:01:03,838 INFO L134 CoverageAnalysis]: Checked inductivity of 4718 backedges. 2952 proven. 1370 refuted. 0 times theorem prover too weak. 396 trivial. 0 not checked. [2018-04-07 00:01:03,838 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-07 00:01:05,700 INFO L134 CoverageAnalysis]: Checked inductivity of 4718 backedges. 2952 proven. 1370 refuted. 0 times theorem prover too weak. 396 trivial. 0 not checked. [2018-04-07 00:01:05,721 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-07 00:01:05,729 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [85, 85] total 126 [2018-04-07 00:01:05,730 INFO L442 AbstractCegarLoop]: Interpolant automaton has 126 states [2018-04-07 00:01:05,730 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 126 interpolants. [2018-04-07 00:01:05,731 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1931, Invalid=13819, Unknown=0, NotChecked=0, Total=15750 [2018-04-07 00:01:05,731 INFO L87 Difference]: Start difference. First operand 883 states and 1116 transitions. Second operand 126 states. [2018-04-07 00:01:09,860 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-07 00:01:09,861 INFO L93 Difference]: Finished difference Result 1178 states and 1473 transitions. [2018-04-07 00:01:09,861 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 145 states. [2018-04-07 00:01:09,861 INFO L78 Accepts]: Start accepts. Automaton has 126 states. Word has length 373 [2018-04-07 00:01:09,861 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-07 00:01:09,864 INFO L225 Difference]: With dead ends: 1178 [2018-04-07 00:01:09,864 INFO L226 Difference]: Without dead ends: 883 [2018-04-07 00:01:09,867 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 846 GetRequests, 579 SyntacticMatches, 42 SemanticMatches, 225 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14847 ImplicationChecksByTransitivity, 5.9s TimeCoverageRelationStatistics Valid=7027, Invalid=44275, Unknown=0, NotChecked=0, Total=51302 [2018-04-07 00:01:09,868 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-07 00:01:09,882 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-07 00:01:09,882 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-07 00:01:09,885 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1115 transitions. [2018-04-07 00:01:09,885 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1115 transitions. Word has length 373 [2018-04-07 00:01:09,885 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-07 00:01:09,885 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1115 transitions. [2018-04-07 00:01:09,885 INFO L460 AbstractCegarLoop]: Interpolant automaton has 126 states. [2018-04-07 00:01:09,886 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1115 transitions. [2018-04-07 00:01:09,888 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 381 [2018-04-07 00:01:09,888 INFO L347 BasicCegarLoop]: Found error trace [2018-04-07 00:01:09,888 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 22, 21, 21, 21, 21, 21, 21, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-07 00:01:09,888 INFO L408 AbstractCegarLoop]: === Iteration 32 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-07 00:01:09,889 INFO L82 PathProgramCache]: Analyzing trace with hash -1653950114, now seen corresponding path program 25 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-07 00:01:09,894 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-07 00:01:09,945 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-07 00:01:09,952 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-07 00:01:11,674 INFO L134 CoverageAnalysis]: Checked inductivity of 4860 backedges. 3023 proven. 1512 refuted. 0 times theorem prover too weak. 325 trivial. 0 not checked. [2018-04-07 00:01:11,675 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-07 00:01:13,684 INFO L134 CoverageAnalysis]: Checked inductivity of 4860 backedges. 3023 proven. 1512 refuted. 0 times theorem prover too weak. 325 trivial. 0 not checked. [2018-04-07 00:01:13,715 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-07 00:01:13,716 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [89, 89] total 132 [2018-04-07 00:01:13,716 INFO L442 AbstractCegarLoop]: Interpolant automaton has 132 states [2018-04-07 00:01:13,717 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 132 interpolants. [2018-04-07 00:01:13,717 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2111, Invalid=15181, Unknown=0, NotChecked=0, Total=17292 [2018-04-07 00:01:13,718 INFO L87 Difference]: Start difference. First operand 883 states and 1115 transitions. Second operand 132 states. [2018-04-07 00:01:17,988 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-07 00:01:17,988 INFO L93 Difference]: Finished difference Result 1178 states and 1472 transitions. [2018-04-07 00:01:17,988 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 152 states. [2018-04-07 00:01:17,988 INFO L78 Accepts]: Start accepts. Automaton has 132 states. Word has length 380 [2018-04-07 00:01:17,989 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-07 00:01:17,991 INFO L225 Difference]: With dead ends: 1178 [2018-04-07 00:01:17,991 INFO L226 Difference]: Without dead ends: 883 [2018-04-07 00:01:17,993 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 865 GetRequests, 585 SyntacticMatches, 44 SemanticMatches, 236 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16356 ImplicationChecksByTransitivity, 6.4s TimeCoverageRelationStatistics Valid=7703, Invalid=48703, Unknown=0, NotChecked=0, Total=56406 [2018-04-07 00:01:17,994 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-07 00:01:18,008 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-07 00:01:18,008 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-07 00:01:18,009 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1114 transitions. [2018-04-07 00:01:18,010 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1114 transitions. Word has length 380 [2018-04-07 00:01:18,010 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-07 00:01:18,010 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1114 transitions. [2018-04-07 00:01:18,010 INFO L460 AbstractCegarLoop]: Interpolant automaton has 132 states. [2018-04-07 00:01:18,010 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1114 transitions. [2018-04-07 00:01:18,012 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 388 [2018-04-07 00:01:18,012 INFO L347 BasicCegarLoop]: Found error trace [2018-04-07 00:01:18,012 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 23, 22, 22, 22, 22, 22, 22, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-07 00:01:18,012 INFO L408 AbstractCegarLoop]: === Iteration 33 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-07 00:01:18,012 INFO L82 PathProgramCache]: Analyzing trace with hash 1630715823, now seen corresponding path program 26 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-07 00:01:18,018 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-07 00:01:18,096 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-07 00:01:18,103 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-07 00:01:20,026 INFO L134 CoverageAnalysis]: Checked inductivity of 5009 backedges. 3087 proven. 1661 refuted. 0 times theorem prover too weak. 261 trivial. 0 not checked. [2018-04-07 00:01:20,026 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-07 00:01:22,219 INFO L134 CoverageAnalysis]: Checked inductivity of 5009 backedges. 3087 proven. 1661 refuted. 0 times theorem prover too weak. 261 trivial. 0 not checked. [2018-04-07 00:01:22,241 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-07 00:01:22,241 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [93, 93] total 138 [2018-04-07 00:01:22,241 INFO L442 AbstractCegarLoop]: Interpolant automaton has 138 states [2018-04-07 00:01:22,242 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 138 interpolants. [2018-04-07 00:01:22,242 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2299, Invalid=16607, Unknown=0, NotChecked=0, Total=18906 [2018-04-07 00:01:22,242 INFO L87 Difference]: Start difference. First operand 883 states and 1114 transitions. Second operand 138 states. [2018-04-07 00:01:27,336 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-07 00:01:27,336 INFO L93 Difference]: Finished difference Result 1178 states and 1471 transitions. [2018-04-07 00:01:27,372 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 159 states. [2018-04-07 00:01:27,372 INFO L78 Accepts]: Start accepts. Automaton has 138 states. Word has length 387 [2018-04-07 00:01:27,373 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-07 00:01:27,375 INFO L225 Difference]: With dead ends: 1178 [2018-04-07 00:01:27,375 INFO L226 Difference]: Without dead ends: 883 [2018-04-07 00:01:27,378 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 884 GetRequests, 591 SyntacticMatches, 46 SemanticMatches, 247 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17938 ImplicationChecksByTransitivity, 7.1s TimeCoverageRelationStatistics Valid=8410, Invalid=53342, Unknown=0, NotChecked=0, Total=61752 [2018-04-07 00:01:27,378 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-07 00:01:27,393 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-07 00:01:27,393 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-07 00:01:27,395 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1113 transitions. [2018-04-07 00:01:27,395 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1113 transitions. Word has length 387 [2018-04-07 00:01:27,396 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-07 00:01:27,396 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1113 transitions. [2018-04-07 00:01:27,396 INFO L460 AbstractCegarLoop]: Interpolant automaton has 138 states. [2018-04-07 00:01:27,396 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1113 transitions. [2018-04-07 00:01:27,398 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 395 [2018-04-07 00:01:27,398 INFO L347 BasicCegarLoop]: Found error trace [2018-04-07 00:01:27,398 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 24, 23, 23, 23, 23, 23, 23, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-07 00:01:27,398 INFO L408 AbstractCegarLoop]: === Iteration 34 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-07 00:01:27,398 INFO L82 PathProgramCache]: Analyzing trace with hash 1907829822, now seen corresponding path program 27 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-07 00:01:27,404 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-07 00:01:27,450 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-07 00:01:27,455 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-07 00:01:29,381 INFO L134 CoverageAnalysis]: Checked inductivity of 5165 backedges. 3144 proven. 1817 refuted. 0 times theorem prover too weak. 204 trivial. 0 not checked. [2018-04-07 00:01:29,381 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-07 00:01:31,774 INFO L134 CoverageAnalysis]: Checked inductivity of 5165 backedges. 3144 proven. 1817 refuted. 0 times theorem prover too weak. 204 trivial. 0 not checked. [2018-04-07 00:01:31,794 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-07 00:01:31,795 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [97, 97] total 144 [2018-04-07 00:01:31,795 INFO L442 AbstractCegarLoop]: Interpolant automaton has 144 states [2018-04-07 00:01:31,796 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 144 interpolants. [2018-04-07 00:01:31,796 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2495, Invalid=18097, Unknown=0, NotChecked=0, Total=20592 [2018-04-07 00:01:31,797 INFO L87 Difference]: Start difference. First operand 883 states and 1113 transitions. Second operand 144 states. [2018-04-07 00:01:36,981 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-07 00:01:36,981 INFO L93 Difference]: Finished difference Result 1178 states and 1470 transitions. [2018-04-07 00:01:36,981 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 166 states. [2018-04-07 00:01:36,981 INFO L78 Accepts]: Start accepts. Automaton has 144 states. Word has length 394 [2018-04-07 00:01:36,981 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-07 00:01:36,984 INFO L225 Difference]: With dead ends: 1178 [2018-04-07 00:01:36,984 INFO L226 Difference]: Without dead ends: 883 [2018-04-07 00:01:36,989 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 903 GetRequests, 597 SyntacticMatches, 48 SemanticMatches, 258 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19593 ImplicationChecksByTransitivity, 7.6s TimeCoverageRelationStatistics Valid=9148, Invalid=58192, Unknown=0, NotChecked=0, Total=67340 [2018-04-07 00:01:36,990 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-07 00:01:37,010 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-07 00:01:37,010 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-07 00:01:37,012 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1112 transitions. [2018-04-07 00:01:37,012 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1112 transitions. Word has length 394 [2018-04-07 00:01:37,012 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-07 00:01:37,012 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1112 transitions. [2018-04-07 00:01:37,012 INFO L460 AbstractCegarLoop]: Interpolant automaton has 144 states. [2018-04-07 00:01:37,012 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1112 transitions. [2018-04-07 00:01:37,016 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 402 [2018-04-07 00:01:37,016 INFO L347 BasicCegarLoop]: Found error trace [2018-04-07 00:01:37,016 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 25, 24, 24, 24, 24, 24, 24, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-07 00:01:37,016 INFO L408 AbstractCegarLoop]: === Iteration 35 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-07 00:01:37,017 INFO L82 PathProgramCache]: Analyzing trace with hash -1972809521, now seen corresponding path program 28 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-07 00:01:37,025 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-07 00:01:37,074 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-07 00:01:37,080 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-07 00:01:39,171 INFO L134 CoverageAnalysis]: Checked inductivity of 5328 backedges. 3194 proven. 1980 refuted. 0 times theorem prover too weak. 154 trivial. 0 not checked. [2018-04-07 00:01:39,172 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-07 00:01:41,758 INFO L134 CoverageAnalysis]: Checked inductivity of 5328 backedges. 3194 proven. 1980 refuted. 0 times theorem prover too weak. 154 trivial. 0 not checked. [2018-04-07 00:01:41,780 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-07 00:01:41,780 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [101, 101] total 150 [2018-04-07 00:01:41,780 INFO L442 AbstractCegarLoop]: Interpolant automaton has 150 states [2018-04-07 00:01:41,781 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 150 interpolants. [2018-04-07 00:01:41,781 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2699, Invalid=19651, Unknown=0, NotChecked=0, Total=22350 [2018-04-07 00:01:41,782 INFO L87 Difference]: Start difference. First operand 883 states and 1112 transitions. Second operand 150 states. [2018-04-07 00:01:47,991 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-07 00:01:47,992 INFO L93 Difference]: Finished difference Result 1178 states and 1469 transitions. [2018-04-07 00:01:47,992 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 173 states. [2018-04-07 00:01:47,992 INFO L78 Accepts]: Start accepts. Automaton has 150 states. Word has length 401 [2018-04-07 00:01:47,993 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-07 00:01:47,997 INFO L225 Difference]: With dead ends: 1178 [2018-04-07 00:01:47,997 INFO L226 Difference]: Without dead ends: 883 [2018-04-07 00:01:48,002 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 922 GetRequests, 603 SyntacticMatches, 50 SemanticMatches, 269 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21321 ImplicationChecksByTransitivity, 8.4s TimeCoverageRelationStatistics Valid=9917, Invalid=63253, Unknown=0, NotChecked=0, Total=73170 [2018-04-07 00:01:48,003 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-07 00:01:48,021 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-07 00:01:48,022 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-07 00:01:48,023 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1111 transitions. [2018-04-07 00:01:48,023 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1111 transitions. Word has length 401 [2018-04-07 00:01:48,023 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-07 00:01:48,023 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1111 transitions. [2018-04-07 00:01:48,023 INFO L460 AbstractCegarLoop]: Interpolant automaton has 150 states. [2018-04-07 00:01:48,023 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1111 transitions. [2018-04-07 00:01:48,026 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 409 [2018-04-07 00:01:48,026 INFO L347 BasicCegarLoop]: Found error trace [2018-04-07 00:01:48,026 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 26, 25, 25, 25, 25, 25, 25, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-07 00:01:48,026 INFO L408 AbstractCegarLoop]: === Iteration 36 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-07 00:01:48,026 INFO L82 PathProgramCache]: Analyzing trace with hash 642848542, now seen corresponding path program 29 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-07 00:01:48,032 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-07 00:01:48,081 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-07 00:01:48,087 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-07 00:01:50,321 INFO L134 CoverageAnalysis]: Checked inductivity of 5498 backedges. 3237 proven. 2150 refuted. 0 times theorem prover too weak. 111 trivial. 0 not checked. [2018-04-07 00:01:50,322 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-07 00:01:53,157 INFO L134 CoverageAnalysis]: Checked inductivity of 5498 backedges. 3237 proven. 2150 refuted. 0 times theorem prover too weak. 111 trivial. 0 not checked. [2018-04-07 00:01:53,178 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-07 00:01:53,178 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [105, 105] total 156 [2018-04-07 00:01:53,179 INFO L442 AbstractCegarLoop]: Interpolant automaton has 156 states [2018-04-07 00:01:53,179 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 156 interpolants. [2018-04-07 00:01:53,180 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2911, Invalid=21269, Unknown=0, NotChecked=0, Total=24180 [2018-04-07 00:01:53,180 INFO L87 Difference]: Start difference. First operand 883 states and 1111 transitions. Second operand 156 states. [2018-04-07 00:01:59,560 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-07 00:01:59,560 INFO L93 Difference]: Finished difference Result 1178 states and 1468 transitions. [2018-04-07 00:01:59,560 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 180 states. [2018-04-07 00:01:59,560 INFO L78 Accepts]: Start accepts. Automaton has 156 states. Word has length 408 [2018-04-07 00:01:59,560 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-07 00:01:59,563 INFO L225 Difference]: With dead ends: 1178 [2018-04-07 00:01:59,563 INFO L226 Difference]: Without dead ends: 883 [2018-04-07 00:01:59,566 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 941 GetRequests, 609 SyntacticMatches, 52 SemanticMatches, 280 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23122 ImplicationChecksByTransitivity, 9.0s TimeCoverageRelationStatistics Valid=10717, Invalid=68525, Unknown=0, NotChecked=0, Total=79242 [2018-04-07 00:01:59,566 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-07 00:01:59,579 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-07 00:01:59,579 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-07 00:01:59,580 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1110 transitions. [2018-04-07 00:01:59,580 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1110 transitions. Word has length 408 [2018-04-07 00:01:59,580 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-07 00:01:59,580 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1110 transitions. [2018-04-07 00:01:59,580 INFO L460 AbstractCegarLoop]: Interpolant automaton has 156 states. [2018-04-07 00:01:59,580 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1110 transitions. [2018-04-07 00:01:59,582 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 416 [2018-04-07 00:01:59,582 INFO L347 BasicCegarLoop]: Found error trace [2018-04-07 00:01:59,583 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 27, 26, 26, 26, 26, 26, 26, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-07 00:01:59,583 INFO L408 AbstractCegarLoop]: === Iteration 37 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-07 00:01:59,583 INFO L82 PathProgramCache]: Analyzing trace with hash -541365777, now seen corresponding path program 30 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-07 00:01:59,589 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-07 00:01:59,649 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-07 00:01:59,655 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-07 00:02:02,033 INFO L134 CoverageAnalysis]: Checked inductivity of 5675 backedges. 3273 proven. 2327 refuted. 0 times theorem prover too weak. 75 trivial. 0 not checked. [2018-04-07 00:02:02,034 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-07 00:02:05,056 INFO L134 CoverageAnalysis]: Checked inductivity of 5675 backedges. 3273 proven. 2327 refuted. 0 times theorem prover too weak. 75 trivial. 0 not checked. [2018-04-07 00:02:05,077 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-07 00:02:05,078 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [109, 109] total 162 [2018-04-07 00:02:05,078 INFO L442 AbstractCegarLoop]: Interpolant automaton has 162 states [2018-04-07 00:02:05,079 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 162 interpolants. [2018-04-07 00:02:05,079 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3131, Invalid=22951, Unknown=0, NotChecked=0, Total=26082 [2018-04-07 00:02:05,080 INFO L87 Difference]: Start difference. First operand 883 states and 1110 transitions. Second operand 162 states. [2018-04-07 00:02:12,085 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-07 00:02:12,085 INFO L93 Difference]: Finished difference Result 1178 states and 1467 transitions. [2018-04-07 00:02:12,086 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 187 states. [2018-04-07 00:02:12,086 INFO L78 Accepts]: Start accepts. Automaton has 162 states. Word has length 415 [2018-04-07 00:02:12,086 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-07 00:02:12,088 INFO L225 Difference]: With dead ends: 1178 [2018-04-07 00:02:12,088 INFO L226 Difference]: Without dead ends: 883 [2018-04-07 00:02:12,091 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 960 GetRequests, 615 SyntacticMatches, 54 SemanticMatches, 291 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24996 ImplicationChecksByTransitivity, 9.6s TimeCoverageRelationStatistics Valid=11548, Invalid=74008, Unknown=0, NotChecked=0, Total=85556 [2018-04-07 00:02:12,092 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-07 00:02:12,105 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-07 00:02:12,105 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-07 00:02:12,106 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1109 transitions. [2018-04-07 00:02:12,106 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1109 transitions. Word has length 415 [2018-04-07 00:02:12,107 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-07 00:02:12,107 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1109 transitions. [2018-04-07 00:02:12,107 INFO L460 AbstractCegarLoop]: Interpolant automaton has 162 states. [2018-04-07 00:02:12,107 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1109 transitions. [2018-04-07 00:02:12,111 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 423 [2018-04-07 00:02:12,111 INFO L347 BasicCegarLoop]: Found error trace [2018-04-07 00:02:12,111 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 28, 27, 27, 27, 27, 27, 27, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-07 00:02:12,111 INFO L408 AbstractCegarLoop]: === Iteration 38 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-07 00:02:12,111 INFO L82 PathProgramCache]: Analyzing trace with hash -1975092738, now seen corresponding path program 31 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-07 00:02:12,119 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-07 00:02:12,168 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-07 00:02:12,174 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-07 00:02:14,710 INFO L134 CoverageAnalysis]: Checked inductivity of 5859 backedges. 3302 proven. 2511 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2018-04-07 00:02:14,711 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-07 00:02:17,942 INFO L134 CoverageAnalysis]: Checked inductivity of 5859 backedges. 3302 proven. 2511 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2018-04-07 00:02:17,963 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-07 00:02:17,963 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [113, 113] total 168 [2018-04-07 00:02:17,963 INFO L442 AbstractCegarLoop]: Interpolant automaton has 168 states [2018-04-07 00:02:17,964 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 168 interpolants. [2018-04-07 00:02:17,965 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3359, Invalid=24697, Unknown=0, NotChecked=0, Total=28056 [2018-04-07 00:02:17,965 INFO L87 Difference]: Start difference. First operand 883 states and 1109 transitions. Second operand 168 states. [2018-04-07 00:02:25,258 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-07 00:02:25,258 INFO L93 Difference]: Finished difference Result 1178 states and 1466 transitions. [2018-04-07 00:02:25,258 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 194 states. [2018-04-07 00:02:25,259 INFO L78 Accepts]: Start accepts. Automaton has 168 states. Word has length 422 [2018-04-07 00:02:25,259 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-07 00:02:25,261 INFO L225 Difference]: With dead ends: 1178 [2018-04-07 00:02:25,261 INFO L226 Difference]: Without dead ends: 883 [2018-04-07 00:02:25,265 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 979 GetRequests, 621 SyntacticMatches, 56 SemanticMatches, 302 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26943 ImplicationChecksByTransitivity, 10.3s TimeCoverageRelationStatistics Valid=12410, Invalid=79702, Unknown=0, NotChecked=0, Total=92112 [2018-04-07 00:02:25,265 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-07 00:02:25,278 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-07 00:02:25,278 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-07 00:02:25,279 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1108 transitions. [2018-04-07 00:02:25,279 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1108 transitions. Word has length 422 [2018-04-07 00:02:25,280 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-07 00:02:25,280 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1108 transitions. [2018-04-07 00:02:25,280 INFO L460 AbstractCegarLoop]: Interpolant automaton has 168 states. [2018-04-07 00:02:25,280 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1108 transitions. [2018-04-07 00:02:25,282 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 430 [2018-04-07 00:02:25,282 INFO L347 BasicCegarLoop]: Found error trace [2018-04-07 00:02:25,282 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 29, 28, 28, 28, 28, 28, 28, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-07 00:02:25,282 INFO L408 AbstractCegarLoop]: === Iteration 39 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-07 00:02:25,282 INFO L82 PathProgramCache]: Analyzing trace with hash 643500815, now seen corresponding path program 32 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-07 00:02:25,288 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-07 00:02:25,340 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-07 00:02:25,361 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-07 00:02:28,088 INFO L134 CoverageAnalysis]: Checked inductivity of 6050 backedges. 3324 proven. 2702 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2018-04-07 00:02:28,089 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-07 00:02:31,557 INFO L134 CoverageAnalysis]: Checked inductivity of 6050 backedges. 3324 proven. 2702 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2018-04-07 00:02:31,578 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-07 00:02:31,578 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [117, 117] total 174 [2018-04-07 00:02:31,579 INFO L442 AbstractCegarLoop]: Interpolant automaton has 174 states [2018-04-07 00:02:31,579 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 174 interpolants. [2018-04-07 00:02:31,580 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3595, Invalid=26507, Unknown=0, NotChecked=0, Total=30102 [2018-04-07 00:02:31,580 INFO L87 Difference]: Start difference. First operand 883 states and 1108 transitions. Second operand 174 states. [2018-04-07 00:02:39,082 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-07 00:02:39,082 INFO L93 Difference]: Finished difference Result 1178 states and 1465 transitions. [2018-04-07 00:02:39,082 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 201 states. [2018-04-07 00:02:39,082 INFO L78 Accepts]: Start accepts. Automaton has 174 states. Word has length 429 [2018-04-07 00:02:39,083 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-07 00:02:39,085 INFO L225 Difference]: With dead ends: 1178 [2018-04-07 00:02:39,085 INFO L226 Difference]: Without dead ends: 883 [2018-04-07 00:02:39,088 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 998 GetRequests, 627 SyntacticMatches, 58 SemanticMatches, 313 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28963 ImplicationChecksByTransitivity, 11.1s TimeCoverageRelationStatistics Valid=13303, Invalid=85607, Unknown=0, NotChecked=0, Total=98910 [2018-04-07 00:02:39,089 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-07 00:02:39,102 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-07 00:02:39,102 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-07 00:02:39,103 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1107 transitions. [2018-04-07 00:02:39,104 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1107 transitions. Word has length 429 [2018-04-07 00:02:39,104 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-07 00:02:39,104 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1107 transitions. [2018-04-07 00:02:39,104 INFO L460 AbstractCegarLoop]: Interpolant automaton has 174 states. [2018-04-07 00:02:39,104 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1107 transitions. [2018-04-07 00:02:39,106 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 437 [2018-04-07 00:02:39,106 INFO L347 BasicCegarLoop]: Found error trace [2018-04-07 00:02:39,106 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 30, 29, 29, 29, 29, 29, 29, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-07 00:02:39,107 INFO L408 AbstractCegarLoop]: === Iteration 40 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-07 00:02:39,107 INFO L82 PathProgramCache]: Analyzing trace with hash -64662306, now seen corresponding path program 33 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-07 00:02:39,112 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-07 00:02:39,169 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-07 00:02:39,174 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-07 00:02:42,198 INFO L134 CoverageAnalysis]: Checked inductivity of 6248 backedges. 3339 proven. 2900 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2018-04-07 00:02:42,198 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-07 00:02:45,917 INFO L134 CoverageAnalysis]: Checked inductivity of 6248 backedges. 3339 proven. 2900 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2018-04-07 00:02:45,974 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-07 00:02:45,974 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [121, 121] total 180 [2018-04-07 00:02:45,975 INFO L442 AbstractCegarLoop]: Interpolant automaton has 180 states [2018-04-07 00:02:45,975 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 180 interpolants. [2018-04-07 00:02:45,976 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3839, Invalid=28381, Unknown=0, NotChecked=0, Total=32220 [2018-04-07 00:02:45,976 INFO L87 Difference]: Start difference. First operand 883 states and 1107 transitions. Second operand 180 states. [2018-04-07 00:02:53,616 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-07 00:02:53,616 INFO L93 Difference]: Finished difference Result 1178 states and 1464 transitions. [2018-04-07 00:02:53,617 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 208 states. [2018-04-07 00:02:53,617 INFO L78 Accepts]: Start accepts. Automaton has 180 states. Word has length 436 [2018-04-07 00:02:53,617 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-07 00:02:53,619 INFO L225 Difference]: With dead ends: 1178 [2018-04-07 00:02:53,620 INFO L226 Difference]: Without dead ends: 883 [2018-04-07 00:02:53,623 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1017 GetRequests, 633 SyntacticMatches, 60 SemanticMatches, 324 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31056 ImplicationChecksByTransitivity, 12.0s TimeCoverageRelationStatistics Valid=14227, Invalid=91723, Unknown=0, NotChecked=0, Total=105950 [2018-04-07 00:02:53,623 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-07 00:02:53,635 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-07 00:02:53,635 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-07 00:02:53,636 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1106 transitions. [2018-04-07 00:02:53,636 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1106 transitions. Word has length 436 [2018-04-07 00:02:53,636 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-07 00:02:53,636 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1106 transitions. [2018-04-07 00:02:53,636 INFO L460 AbstractCegarLoop]: Interpolant automaton has 180 states. [2018-04-07 00:02:53,636 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1106 transitions. [2018-04-07 00:02:53,638 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 444 [2018-04-07 00:02:53,638 INFO L347 BasicCegarLoop]: Found error trace [2018-04-07 00:02:53,639 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 31, 30, 30, 30, 30, 30, 30, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-07 00:02:53,639 INFO L408 AbstractCegarLoop]: === Iteration 41 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-07 00:02:53,639 INFO L82 PathProgramCache]: Analyzing trace with hash 603599919, now seen corresponding path program 34 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-07 00:02:53,644 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-07 00:02:53,696 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-07 00:02:53,701 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-07 00:02:56,791 INFO L134 CoverageAnalysis]: Checked inductivity of 6453 backedges. 3347 proven. 3105 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-04-07 00:02:56,791 INFO L314 TraceCheckSpWp]: Computing backward predicates... Received shutdown request... [2018-04-07 00:02:58,875 INFO L175 TraceCheckSpWp]: Timeout while computing interpolants [2018-04-07 00:02:58,875 WARN L519 AbstractCegarLoop]: Verification canceled [2018-04-07 00:02:58,878 WARN L197 ceAbstractionStarter]: Timeout [2018-04-07 00:02:58,879 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 07.04 12:02:58 BasicIcfg [2018-04-07 00:02:58,879 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-04-07 00:02:58,879 INFO L168 Benchmark]: Toolchain (without parser) took 232521.04 ms. Allocated memory was 296.2 MB in the beginning and 944.2 MB in the end (delta: 648.0 MB). Free memory was 238.3 MB in the beginning and 518.6 MB in the end (delta: -280.3 MB). Peak memory consumption was 367.7 MB. Max. memory is 5.3 GB. [2018-04-07 00:02:58,881 INFO L168 Benchmark]: CDTParser took 0.29 ms. Allocated memory is still 296.2 MB. Free memory is still 258.5 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-04-07 00:02:58,881 INFO L168 Benchmark]: CACSL2BoogieTranslator took 196.36 ms. Allocated memory is still 296.2 MB. Free memory was 238.3 MB in the beginning and 228.3 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 5.3 GB. [2018-04-07 00:02:58,881 INFO L168 Benchmark]: Boogie Preprocessor took 27.95 ms. Allocated memory is still 296.2 MB. Free memory was 228.3 MB in the beginning and 226.3 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. [2018-04-07 00:02:58,882 INFO L168 Benchmark]: RCFGBuilder took 260.22 ms. Allocated memory was 296.2 MB in the beginning and 450.4 MB in the end (delta: 154.1 MB). Free memory was 226.3 MB in the beginning and 418.3 MB in the end (delta: -192.0 MB). Peak memory consumption was 22.1 MB. Max. memory is 5.3 GB. [2018-04-07 00:02:58,882 INFO L168 Benchmark]: IcfgTransformer took 17.61 ms. Allocated memory is still 450.4 MB. Free memory was 418.3 MB in the beginning and 417.0 MB in the end (delta: 1.3 MB). Peak memory consumption was 1.3 MB. Max. memory is 5.3 GB. [2018-04-07 00:02:58,882 INFO L168 Benchmark]: TraceAbstraction took 232014.40 ms. Allocated memory was 450.4 MB in the beginning and 944.2 MB in the end (delta: 493.9 MB). Free memory was 417.0 MB in the beginning and 518.6 MB in the end (delta: -101.5 MB). Peak memory consumption was 392.3 MB. Max. memory is 5.3 GB. [2018-04-07 00:02:58,885 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.29 ms. Allocated memory is still 296.2 MB. Free memory is still 258.5 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 196.36 ms. Allocated memory is still 296.2 MB. Free memory was 238.3 MB in the beginning and 228.3 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 27.95 ms. Allocated memory is still 296.2 MB. Free memory was 228.3 MB in the beginning and 226.3 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. * RCFGBuilder took 260.22 ms. Allocated memory was 296.2 MB in the beginning and 450.4 MB in the end (delta: 154.1 MB). Free memory was 226.3 MB in the beginning and 418.3 MB in the end (delta: -192.0 MB). Peak memory consumption was 22.1 MB. Max. memory is 5.3 GB. * IcfgTransformer took 17.61 ms. Allocated memory is still 450.4 MB. Free memory was 418.3 MB in the beginning and 417.0 MB in the end (delta: 1.3 MB). Peak memory consumption was 1.3 MB. Max. memory is 5.3 GB. * TraceAbstraction took 232014.40 ms. Allocated memory was 450.4 MB in the beginning and 944.2 MB in the end (delta: 493.9 MB). Free memory was 417.0 MB in the beginning and 518.6 MB in the end (delta: -101.5 MB). Peak memory consumption was 392.3 MB. Max. memory is 5.3 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 26]: Timeout (TraceAbstraction) Unable to prove that array index is always in bounds (line 26). Cancelled while BasicCegarLoop was analyzing trace of length 444 with TraceHistMax 32, while TraceCheckSpWp was constructing backward predicates, while PredicateComparison was comparing new predicate (quantifier-free) to 169 known predicates. - TimeoutResultAtElement [Line: 19]: Timeout (TraceAbstraction) Unable to prove that array index is always in bounds (line 19). Cancelled while BasicCegarLoop was analyzing trace of length 444 with TraceHistMax 32, while TraceCheckSpWp was constructing backward predicates, while PredicateComparison was comparing new predicate (quantifier-free) to 169 known predicates. - TimeoutResultAtElement [Line: 24]: Timeout (TraceAbstraction) Unable to prove that array index is always in bounds (line 24). Cancelled while BasicCegarLoop was analyzing trace of length 444 with TraceHistMax 32, while TraceCheckSpWp was constructing backward predicates, while PredicateComparison was comparing new predicate (quantifier-free) to 169 known predicates. - TimeoutResultAtElement [Line: 17]: Timeout (TraceAbstraction) Unable to prove that array index is always in bounds (line 17). Cancelled while BasicCegarLoop was analyzing trace of length 444 with TraceHistMax 32, while TraceCheckSpWp was constructing backward predicates, while PredicateComparison was comparing new predicate (quantifier-free) to 169 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 6 procedures, 51 locations, 4 error locations. TIMEOUT Result, 231.9s OverallTime, 41 OverallIterations, 32 TraceHistogramMax, 140.2s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 5150 SDtfs, 14840 SDslu, 100217 SDs, 0 SdLazy, 99978 SolverSat, 10508 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 30.9s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 19748 GetRequests, 13124 SyntacticMatches, 930 SemanticMatches, 5694 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 341262 ImplicationChecksByTransitivity, 174.4s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=883occurred in iteration=26, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.6s AutomataMinimizationTime, 40 MinimizatonAttempts, 135 StatesRemovedByMinimization, 12 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.2s SsaConstructionTime, 1.0s SatisfiabilityAnalysisTime, 82.9s InterpolantComputationTime, 8588 NumberOfCodeBlocks, 8588 NumberOfCodeBlocksAsserted, 40 NumberOfCheckSat, 17096 ConstructedInterpolants, 0 QuantifiedInterpolants, 20771496 SizeOfPredicates, 2026 NumberOfNonLiveVariables, 11874 ConjunctsInSsa, 2222 ConjunctsInUnsatCore, 80 InterpolantComputations, 4 PerfectInterpolantSequences, 109990/179190 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/sanfoundry_24_false-valid-deref.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Fixed_noBitfields+AI_EQ_SS.epf_AutomizerCTransformed.xml/Csv-Benchmark-0-2018-04-07_00-02-58-895.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/sanfoundry_24_false-valid-deref.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Fixed_noBitfields+AI_EQ_SS.epf_AutomizerCTransformed.xml/Csv-TraceAbstractionBenchmarks-0-2018-04-07_00-02-58-895.csv Completed graceful shutdown