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-453dfda-m [2018-04-10 00:45:36,921 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-04-10 00:45:36,923 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-04-10 00:45:36,938 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-04-10 00:45:36,938 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-04-10 00:45:36,939 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-04-10 00:45:36,940 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-04-10 00:45:36,942 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-04-10 00:45:36,944 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-04-10 00:45:36,945 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-04-10 00:45:36,946 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-04-10 00:45:36,946 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-04-10 00:45:36,947 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-04-10 00:45:36,948 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-04-10 00:45:36,949 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-04-10 00:45:36,951 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-04-10 00:45:36,953 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-04-10 00:45:36,955 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-04-10 00:45:36,956 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-04-10 00:45:36,958 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-04-10 00:45:36,960 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-04-10 00:45:36,960 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-04-10 00:45:36,960 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-04-10 00:45:36,961 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-04-10 00:45:36,962 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-04-10 00:45:36,964 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-04-10 00:45:36,964 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-04-10 00:45:36,965 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-04-10 00:45:36,965 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-04-10 00:45:36,965 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-04-10 00:45:36,966 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-04-10 00:45:36,966 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-10 00:45:36,990 INFO L110 SettingsManager]: Loading preferences was successful [2018-04-10 00:45:36,990 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-04-10 00:45:36,990 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-04-10 00:45:36,991 INFO L133 SettingsManager]: * ultimate.logging.details=de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation=DEBUG; [2018-04-10 00:45:36,991 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-04-10 00:45:36,991 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-04-10 00:45:36,992 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-04-10 00:45:36,992 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-04-10 00:45:36,992 INFO L133 SettingsManager]: * Parallel states before merging=1 [2018-04-10 00:45:36,992 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-04-10 00:45:36,993 INFO L131 SettingsManager]: Preferences of LTL2Aut differ from their defaults: [2018-04-10 00:45:36,993 INFO L133 SettingsManager]: * Property to check=[] a a: x > 42 [2018-04-10 00:45:36,993 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-04-10 00:45:36,993 INFO L133 SettingsManager]: * sizeof long=4 [2018-04-10 00:45:36,993 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-04-10 00:45:36,994 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-04-10 00:45:36,994 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-04-10 00:45:36,994 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-04-10 00:45:36,994 INFO L133 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2018-04-10 00:45:36,994 INFO L133 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2018-04-10 00:45:36,994 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-04-10 00:45:36,995 INFO L133 SettingsManager]: * sizeof long double=12 [2018-04-10 00:45:36,995 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-04-10 00:45:36,995 INFO L133 SettingsManager]: * Size of a code block=SingleStatement [2018-04-10 00:45:36,995 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-04-10 00:45:36,995 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-04-10 00:45:36,996 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-04-10 00:45:36,996 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-04-10 00:45:36,996 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-04-10 00:45:36,996 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-04-10 00:45:36,996 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-04-10 00:45:36,997 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-04-10 00:45:36,997 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-10 00:45:36,997 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-04-10 00:45:36,998 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-04-10 00:45:36,998 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-04-10 00:45:36,998 INFO L131 SettingsManager]: Preferences of Boogie Printer differ from their defaults: [2018-04-10 00:45:36,998 INFO L133 SettingsManager]: * Dump path:=C:\Users\alex\AppData\Local\Temp\ [2018-04-10 00:45:37,033 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-04-10 00:45:37,045 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully (re)initialized [2018-04-10 00:45:37,049 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-04-10 00:45:37,051 INFO L271 PluginConnector]: Initializing CDTParser... [2018-04-10 00:45:37,051 INFO L276 PluginConnector]: CDTParser initialized [2018-04-10 00:45:37,052 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-10 00:45:37,385 INFO L225 CDTParser]: Created temporary CDT project at /storage/ultimate/releaseScripts/default/UAutomizer-linux/data/FLAG870204d2c [2018-04-10 00:45:37,509 INFO L287 CDTParser]: IsIndexed: true [2018-04-10 00:45:37,509 INFO L288 CDTParser]: Found 1 translation units. [2018-04-10 00:45:37,510 INFO L168 CDTParser]: Scanning sanfoundry_24_false-valid-deref.i [2018-04-10 00:45:37,511 INFO L210 ultiparseSymbolTable]: Include resolver: [2018-04-10 00:45:37,512 INFO L215 ultiparseSymbolTable]: [2018-04-10 00:45:37,512 INFO L218 ultiparseSymbolTable]: Function table: [2018-04-10 00:45:37,512 INFO L221 ultiparseSymbolTable]: Function definition of __U_MULTI_fsanfoundry____false_valid_deref_i__printOdd ('printOdd') in sanfoundry_24_false-valid-deref.i [2018-04-10 00:45:37,512 INFO L221 ultiparseSymbolTable]: Function definition of null ('main') in sanfoundry_24_false-valid-deref.i [2018-04-10 00:45:37,512 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-10 00:45:37,512 INFO L221 ultiparseSymbolTable]: Function definition of __U_MULTI_fsanfoundry____false_valid_deref_i__printEven ('printEven') in sanfoundry_24_false-valid-deref.i [2018-04-10 00:45:37,512 INFO L227 ultiparseSymbolTable]: Global variable table: [2018-04-10 00:45:37,512 INFO L233 ultiparseSymbolTable]: [2018-04-10 00:45:37,541 INFO L330 CDTParser]: Deleted temporary CDT project at /storage/ultimate/releaseScripts/default/UAutomizer-linux/data/FLAG870204d2c [2018-04-10 00:45:37,546 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-04-10 00:45:37,549 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2018-04-10 00:45:37,550 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-04-10 00:45:37,550 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-04-10 00:45:37,557 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-04-10 00:45:37,557 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 10.04 12:45:37" (1/1) ... [2018-04-10 00:45:37,560 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@65b1d7c3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.04 12:45:37, skipping insertion in model container [2018-04-10 00:45:37,560 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 10.04 12:45:37" (1/1) ... [2018-04-10 00:45:37,574 INFO L167 Dispatcher]: Using SV-COMP mode [2018-04-10 00:45:37,588 INFO L167 Dispatcher]: Using SV-COMP mode [2018-04-10 00:45:37,728 INFO L175 PostProcessor]: Settings: Checked method=main [2018-04-10 00:45:37,746 INFO L175 PostProcessor]: Settings: Checked method=main [2018-04-10 00:45:37,750 INFO L100 SccComputation]: Graph consists of 0 InCaSumBalls and 8 non ball SCCs. Number of states in SCCs 8. [2018-04-10 00:45:37,758 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.04 12:45:37 WrapperNode [2018-04-10 00:45:37,758 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-04-10 00:45:37,759 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-04-10 00:45:37,759 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-04-10 00:45:37,759 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-04-10 00:45:37,770 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.04 12:45:37" (1/1) ... [2018-04-10 00:45:37,770 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.04 12:45:37" (1/1) ... [2018-04-10 00:45:37,775 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.04 12:45:37" (1/1) ... [2018-04-10 00:45:37,775 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.04 12:45:37" (1/1) ... [2018-04-10 00:45:37,777 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.04 12:45:37" (1/1) ... [2018-04-10 00:45:37,782 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.04 12:45:37" (1/1) ... [2018-04-10 00:45:37,783 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.04 12:45:37" (1/1) ... [2018-04-10 00:45:37,785 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-04-10 00:45:37,785 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-04-10 00:45:37,786 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-04-10 00:45:37,786 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-04-10 00:45:37,787 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.04 12:45:37" (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-10 00:45:37,845 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-04-10 00:45:37,845 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-04-10 00:45:37,846 INFO L136 BoogieDeclarations]: Found implementation of procedure __U_MULTI_fsanfoundry____false_valid_deref_i____VERIFIER_assert [2018-04-10 00:45:37,846 INFO L136 BoogieDeclarations]: Found implementation of procedure __U_MULTI_fsanfoundry____false_valid_deref_i__printEven [2018-04-10 00:45:37,846 INFO L136 BoogieDeclarations]: Found implementation of procedure __U_MULTI_fsanfoundry____false_valid_deref_i__printOdd [2018-04-10 00:45:37,846 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-04-10 00:45:37,846 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_error [2018-04-10 00:45:37,846 INFO L128 BoogieDeclarations]: Found specification of procedure __U_MULTI_fsanfoundry____false_valid_deref_i____VERIFIER_assert [2018-04-10 00:45:37,847 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-04-10 00:45:37,847 INFO L128 BoogieDeclarations]: Found specification of procedure __U_MULTI_fsanfoundry____false_valid_deref_i__printEven [2018-04-10 00:45:37,847 INFO L128 BoogieDeclarations]: Found specification of procedure __U_MULTI_fsanfoundry____false_valid_deref_i__printOdd [2018-04-10 00:45:37,847 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-04-10 00:45:37,847 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-04-10 00:45:37,847 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-04-10 00:45:38,091 INFO L259 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-04-10 00:45:38,092 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 10.04 12:45:38 BoogieIcfgContainer [2018-04-10 00:45:38,092 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-04-10 00:45:38,093 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2018-04-10 00:45:38,093 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2018-04-10 00:45:38,094 INFO L276 PluginConnector]: IcfgTransformer initialized [2018-04-10 00:45:38,097 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 10.04 12:45:38" (1/1) ... [2018-04-10 00:45:38,101 WARN L219 ansformationObserver]: HeapSeparator: input icfg has no '#valid' array -- returning unchanged Icfg! [2018-04-10 00:45:38,114 INFO L100 SccComputation]: Graph consists of 0 InCaSumBalls and 8 non ball SCCs. Number of states in SCCs 8. [2018-04-10 00:45:38,115 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 10.04 12:45:38 BasicIcfg [2018-04-10 00:45:38,115 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2018-04-10 00:45:38,116 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-04-10 00:45:38,116 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-04-10 00:45:38,120 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-04-10 00:45:38,120 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 10.04 12:45:37" (1/4) ... [2018-04-10 00:45:38,121 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@37203f40 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 10.04 12:45:38, skipping insertion in model container [2018-04-10 00:45:38,121 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.04 12:45:37" (2/4) ... [2018-04-10 00:45:38,122 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@37203f40 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 10.04 12:45:38, skipping insertion in model container [2018-04-10 00:45:38,122 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 10.04 12:45:38" (3/4) ... [2018-04-10 00:45:38,122 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@37203f40 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 10.04 12:45:38, skipping insertion in model container [2018-04-10 00:45:38,123 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 10.04 12:45:38" (4/4) ... [2018-04-10 00:45:38,124 INFO L107 eAbstractionObserver]: Analyzing ICFG sanfoundry_24_false-valid-deref.ileft_unchanged_by_heapseparator [2018-04-10 00:45:38,135 INFO L131 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-04-10 00:45:38,143 INFO L143 ceAbstractionStarter]: Appying trace abstraction to program that has 4 error locations. [2018-04-10 00:45:38,184 INFO L128 ementStrategyFactory]: Using default assertion order modulation [2018-04-10 00:45:38,185 INFO L369 AbstractCegarLoop]: Interprodecural is true [2018-04-10 00:45:38,185 INFO L370 AbstractCegarLoop]: Hoare is true [2018-04-10 00:45:38,185 INFO L371 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-04-10 00:45:38,185 INFO L372 AbstractCegarLoop]: Backedges is TWOTRACK [2018-04-10 00:45:38,185 INFO L373 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-04-10 00:45:38,185 INFO L374 AbstractCegarLoop]: Difference is false [2018-04-10 00:45:38,185 INFO L375 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-04-10 00:45:38,186 INFO L380 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-04-10 00:45:38,186 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-04-10 00:45:38,198 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states. [2018-04-10 00:45:38,202 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2018-04-10 00:45:38,202 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:45:38,203 INFO L355 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-10 00:45:38,203 INFO L408 AbstractCegarLoop]: === Iteration 1 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:45:38,207 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-10 00:45:38,220 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:45:38,236 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:45:38,242 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:45:38,270 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-10 00:45:38,270 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:45:38,302 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-10 00:45:38,324 INFO L320 seRefinementStrategy]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2018-04-10 00:45:38,325 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2, 2] imperfect sequences [] total 3 [2018-04-10 00:45:38,326 INFO L442 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-04-10 00:45:38,336 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-04-10 00:45:38,337 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-04-10 00:45:38,339 INFO L87 Difference]: Start difference. First operand 51 states. Second operand 4 states. [2018-04-10 00:45:38,466 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:45:38,467 INFO L93 Difference]: Finished difference Result 112 states and 144 transitions. [2018-04-10 00:45:38,467 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-04-10 00:45:38,468 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 13 [2018-04-10 00:45:38,469 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:45:38,478 INFO L225 Difference]: With dead ends: 112 [2018-04-10 00:45:38,478 INFO L226 Difference]: Without dead ends: 62 [2018-04-10 00:45:38,482 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-10 00:45:38,496 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2018-04-10 00:45:38,518 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 55. [2018-04-10 00:45:38,519 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 55 states. [2018-04-10 00:45:38,521 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 62 transitions. [2018-04-10 00:45:38,523 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 62 transitions. Word has length 13 [2018-04-10 00:45:38,523 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:45:38,523 INFO L459 AbstractCegarLoop]: Abstraction has 55 states and 62 transitions. [2018-04-10 00:45:38,523 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-04-10 00:45:38,524 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 62 transitions. [2018-04-10 00:45:38,525 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-04-10 00:45:38,525 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:45:38,526 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-10 00:45:38,526 INFO L408 AbstractCegarLoop]: === Iteration 2 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:45:38,526 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-10 00:45:38,535 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:45:38,543 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:45:38,545 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:45:38,573 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-10 00:45:38,573 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:45:38,639 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-10 00:45:38,662 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:45:38,662 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 7 [2018-04-10 00:45:38,663 INFO L442 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-04-10 00:45:38,664 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-04-10 00:45:38,664 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-04-10 00:45:38,664 INFO L87 Difference]: Start difference. First operand 55 states and 62 transitions. Second operand 8 states. [2018-04-10 00:45:38,862 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:45:38,863 INFO L93 Difference]: Finished difference Result 84 states and 101 transitions. [2018-04-10 00:45:38,863 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-04-10 00:45:38,863 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 20 [2018-04-10 00:45:38,864 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:45:38,866 INFO L225 Difference]: With dead ends: 84 [2018-04-10 00:45:38,867 INFO L226 Difference]: Without dead ends: 82 [2018-04-10 00:45:38,868 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-10 00:45:38,868 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2018-04-10 00:45:38,878 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 73. [2018-04-10 00:45:38,878 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 73 states. [2018-04-10 00:45:38,880 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 86 transitions. [2018-04-10 00:45:38,881 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 86 transitions. Word has length 20 [2018-04-10 00:45:38,881 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:45:38,881 INFO L459 AbstractCegarLoop]: Abstraction has 73 states and 86 transitions. [2018-04-10 00:45:38,881 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-04-10 00:45:38,881 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 86 transitions. [2018-04-10 00:45:38,883 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2018-04-10 00:45:38,883 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:45:38,883 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-10 00:45:38,883 INFO L408 AbstractCegarLoop]: === Iteration 3 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:45:38,883 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-10 00:45:38,894 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:45:38,901 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:45:38,904 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:45:38,934 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-10 00:45:38,934 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:45:38,953 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-10 00:45:38,974 INFO L320 seRefinementStrategy]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2018-04-10 00:45:38,974 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5, 5] imperfect sequences [] total 6 [2018-04-10 00:45:38,975 INFO L442 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-04-10 00:45:38,975 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-04-10 00:45:38,975 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2018-04-10 00:45:38,975 INFO L87 Difference]: Start difference. First operand 73 states and 86 transitions. Second operand 6 states. [2018-04-10 00:45:39,082 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:45:39,082 INFO L93 Difference]: Finished difference Result 101 states and 117 transitions. [2018-04-10 00:45:39,083 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-04-10 00:45:39,083 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 23 [2018-04-10 00:45:39,083 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:45:39,084 INFO L225 Difference]: With dead ends: 101 [2018-04-10 00:45:39,085 INFO L226 Difference]: Without dead ends: 76 [2018-04-10 00:45:39,086 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-10 00:45:39,086 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2018-04-10 00:45:39,093 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 73. [2018-04-10 00:45:39,093 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 73 states. [2018-04-10 00:45:39,095 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 85 transitions. [2018-04-10 00:45:39,095 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 85 transitions. Word has length 23 [2018-04-10 00:45:39,095 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:45:39,096 INFO L459 AbstractCegarLoop]: Abstraction has 73 states and 85 transitions. [2018-04-10 00:45:39,096 INFO L460 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-04-10 00:45:39,096 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 85 transitions. [2018-04-10 00:45:39,097 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2018-04-10 00:45:39,097 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:45:39,098 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-10 00:45:39,098 INFO L408 AbstractCegarLoop]: === Iteration 4 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:45:39,098 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-10 00:45:39,111 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:45:39,121 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:45:39,124 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:45:39,192 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-10 00:45:39,192 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:45:39,267 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-10 00:45:39,291 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:45:39,291 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 12 [2018-04-10 00:45:39,291 INFO L442 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-04-10 00:45:39,292 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-04-10 00:45:39,292 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=101, Unknown=0, NotChecked=0, Total=132 [2018-04-10 00:45:39,292 INFO L87 Difference]: Start difference. First operand 73 states and 85 transitions. Second operand 12 states. [2018-04-10 00:45:39,497 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:45:39,497 INFO L93 Difference]: Finished difference Result 107 states and 123 transitions. [2018-04-10 00:45:39,497 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-04-10 00:45:39,497 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 30 [2018-04-10 00:45:39,498 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:45:39,499 INFO L225 Difference]: With dead ends: 107 [2018-04-10 00:45:39,499 INFO L226 Difference]: Without dead ends: 76 [2018-04-10 00:45:39,500 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-10 00:45:39,500 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2018-04-10 00:45:39,508 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 73. [2018-04-10 00:45:39,508 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 73 states. [2018-04-10 00:45:39,510 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 84 transitions. [2018-04-10 00:45:39,510 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 84 transitions. Word has length 30 [2018-04-10 00:45:39,510 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:45:39,510 INFO L459 AbstractCegarLoop]: Abstraction has 73 states and 84 transitions. [2018-04-10 00:45:39,511 INFO L460 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-04-10 00:45:39,511 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 84 transitions. [2018-04-10 00:45:39,512 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2018-04-10 00:45:39,512 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:45:39,512 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-10 00:45:39,513 INFO L408 AbstractCegarLoop]: === Iteration 5 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:45:39,513 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-10 00:45:39,522 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:45:39,530 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:45:39,533 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:45:39,632 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-10 00:45:39,632 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:45:39,761 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-10 00:45:39,795 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:45:39,795 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 15 [2018-04-10 00:45:39,796 INFO L442 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-04-10 00:45:39,796 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-04-10 00:45:39,796 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=186, Unknown=0, NotChecked=0, Total=240 [2018-04-10 00:45:39,796 INFO L87 Difference]: Start difference. First operand 73 states and 84 transitions. Second operand 16 states. [2018-04-10 00:45:40,272 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:45:40,273 INFO L93 Difference]: Finished difference Result 122 states and 153 transitions. [2018-04-10 00:45:40,273 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-04-10 00:45:40,273 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 34 [2018-04-10 00:45:40,274 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:45:40,275 INFO L225 Difference]: With dead ends: 122 [2018-04-10 00:45:40,275 INFO L226 Difference]: Without dead ends: 120 [2018-04-10 00:45:40,276 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 53 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 116 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=244, Invalid=626, Unknown=0, NotChecked=0, Total=870 [2018-04-10 00:45:40,276 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 120 states. [2018-04-10 00:45:40,285 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 120 to 109. [2018-04-10 00:45:40,286 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 109 states. [2018-04-10 00:45:40,288 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 132 transitions. [2018-04-10 00:45:40,288 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 132 transitions. Word has length 34 [2018-04-10 00:45:40,288 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:45:40,288 INFO L459 AbstractCegarLoop]: Abstraction has 109 states and 132 transitions. [2018-04-10 00:45:40,289 INFO L460 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-04-10 00:45:40,289 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 132 transitions. [2018-04-10 00:45:40,290 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2018-04-10 00:45:40,290 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:45:40,291 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-10 00:45:40,291 INFO L408 AbstractCegarLoop]: === Iteration 6 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:45:40,291 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-10 00:45:40,302 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:45:40,311 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:45:40,313 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:45:40,325 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-10 00:45:40,326 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:45:40,355 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-10 00:45:40,377 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:45:40,377 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 7 [2018-04-10 00:45:40,377 INFO L442 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-04-10 00:45:40,378 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-04-10 00:45:40,378 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-04-10 00:45:40,378 INFO L87 Difference]: Start difference. First operand 109 states and 132 transitions. Second operand 8 states. [2018-04-10 00:45:40,468 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:45:40,469 INFO L93 Difference]: Finished difference Result 132 states and 162 transitions. [2018-04-10 00:45:40,469 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-04-10 00:45:40,469 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 37 [2018-04-10 00:45:40,469 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:45:40,470 INFO L225 Difference]: With dead ends: 132 [2018-04-10 00:45:40,470 INFO L226 Difference]: Without dead ends: 130 [2018-04-10 00:45:40,471 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-10 00:45:40,471 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2018-04-10 00:45:40,478 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 127. [2018-04-10 00:45:40,478 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 127 states. [2018-04-10 00:45:40,479 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 154 transitions. [2018-04-10 00:45:40,479 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 154 transitions. Word has length 37 [2018-04-10 00:45:40,480 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:45:40,480 INFO L459 AbstractCegarLoop]: Abstraction has 127 states and 154 transitions. [2018-04-10 00:45:40,480 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-04-10 00:45:40,480 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 154 transitions. [2018-04-10 00:45:40,481 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2018-04-10 00:45:40,481 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:45:40,482 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-10 00:45:40,482 INFO L408 AbstractCegarLoop]: === Iteration 7 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:45:40,482 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-10 00:45:40,488 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:45:40,499 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:45:40,501 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:45:40,563 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-10 00:45:40,563 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:45:40,628 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-10 00:45:40,650 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:45:40,650 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 18 [2018-04-10 00:45:40,650 INFO L442 AbstractCegarLoop]: Interpolant automaton has 18 states [2018-04-10 00:45:40,650 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2018-04-10 00:45:40,651 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=59, Invalid=247, Unknown=0, NotChecked=0, Total=306 [2018-04-10 00:45:40,651 INFO L87 Difference]: Start difference. First operand 127 states and 154 transitions. Second operand 18 states. [2018-04-10 00:45:40,983 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:45:40,984 INFO L93 Difference]: Finished difference Result 170 states and 203 transitions. [2018-04-10 00:45:40,984 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-04-10 00:45:40,984 INFO L78 Accepts]: Start accepts. Automaton has 18 states. Word has length 51 [2018-04-10 00:45:40,984 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:45:40,986 INFO L225 Difference]: With dead ends: 170 [2018-04-10 00:45:40,986 INFO L226 Difference]: Without dead ends: 127 [2018-04-10 00:45:40,987 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-10 00:45:40,987 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states. [2018-04-10 00:45:40,997 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 127. [2018-04-10 00:45:40,997 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 127 states. [2018-04-10 00:45:40,999 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 153 transitions. [2018-04-10 00:45:40,999 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 153 transitions. Word has length 51 [2018-04-10 00:45:41,000 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:45:41,000 INFO L459 AbstractCegarLoop]: Abstraction has 127 states and 153 transitions. [2018-04-10 00:45:41,000 INFO L460 AbstractCegarLoop]: Interpolant automaton has 18 states. [2018-04-10 00:45:41,000 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 153 transitions. [2018-04-10 00:45:41,002 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2018-04-10 00:45:41,002 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:45:41,003 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-10 00:45:41,003 INFO L408 AbstractCegarLoop]: === Iteration 8 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:45:41,003 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-10 00:45:41,020 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:45:41,034 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:45:41,038 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:45:41,150 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-10 00:45:41,150 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:45:41,274 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-10 00:45:41,295 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:45:41,295 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17] total 24 [2018-04-10 00:45:41,296 INFO L442 AbstractCegarLoop]: Interpolant automaton has 24 states [2018-04-10 00:45:41,296 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2018-04-10 00:45:41,296 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=95, Invalid=457, Unknown=0, NotChecked=0, Total=552 [2018-04-10 00:45:41,296 INFO L87 Difference]: Start difference. First operand 127 states and 153 transitions. Second operand 24 states. [2018-04-10 00:45:41,613 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:45:41,613 INFO L93 Difference]: Finished difference Result 176 states and 209 transitions. [2018-04-10 00:45:41,613 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2018-04-10 00:45:41,614 INFO L78 Accepts]: Start accepts. Automaton has 24 states. Word has length 58 [2018-04-10 00:45:41,614 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:45:41,615 INFO L225 Difference]: With dead ends: 176 [2018-04-10 00:45:41,615 INFO L226 Difference]: Without dead ends: 127 [2018-04-10 00:45:41,616 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-10 00:45:41,616 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states. [2018-04-10 00:45:41,625 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 127. [2018-04-10 00:45:41,626 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 127 states. [2018-04-10 00:45:41,627 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 152 transitions. [2018-04-10 00:45:41,627 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 152 transitions. Word has length 58 [2018-04-10 00:45:41,628 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:45:41,628 INFO L459 AbstractCegarLoop]: Abstraction has 127 states and 152 transitions. [2018-04-10 00:45:41,628 INFO L460 AbstractCegarLoop]: Interpolant automaton has 24 states. [2018-04-10 00:45:41,628 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 152 transitions. [2018-04-10 00:45:41,630 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2018-04-10 00:45:41,630 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:45:41,631 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-10 00:45:41,631 INFO L408 AbstractCegarLoop]: === Iteration 9 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:45:41,631 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-10 00:45:41,637 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:45:41,650 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:45:41,654 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:45:41,787 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-10 00:45:41,787 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:45:42,068 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-10 00:45:42,090 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:45:42,090 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 31 [2018-04-10 00:45:42,090 INFO L442 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-04-10 00:45:42,091 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-04-10 00:45:42,091 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=174, Invalid=818, Unknown=0, NotChecked=0, Total=992 [2018-04-10 00:45:42,091 INFO L87 Difference]: Start difference. First operand 127 states and 152 transitions. Second operand 32 states. [2018-04-10 00:45:43,438 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:45:43,438 INFO L93 Difference]: Finished difference Result 215 states and 279 transitions. [2018-04-10 00:45:43,438 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2018-04-10 00:45:43,438 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 62 [2018-04-10 00:45:43,439 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:45:43,440 INFO L225 Difference]: With dead ends: 215 [2018-04-10 00:45:43,440 INFO L226 Difference]: Without dead ends: 213 [2018-04-10 00:45:43,442 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 157 GetRequests, 93 SyntacticMatches, 0 SemanticMatches, 64 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 716 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=1096, Invalid=3194, Unknown=0, NotChecked=0, Total=4290 [2018-04-10 00:45:43,442 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 213 states. [2018-04-10 00:45:43,452 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 213 to 199. [2018-04-10 00:45:43,452 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 199 states. [2018-04-10 00:45:43,453 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 199 states to 199 states and 248 transitions. [2018-04-10 00:45:43,454 INFO L78 Accepts]: Start accepts. Automaton has 199 states and 248 transitions. Word has length 62 [2018-04-10 00:45:43,454 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:45:43,454 INFO L459 AbstractCegarLoop]: Abstraction has 199 states and 248 transitions. [2018-04-10 00:45:43,454 INFO L460 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-04-10 00:45:43,454 INFO L276 IsEmpty]: Start isEmpty. Operand 199 states and 248 transitions. [2018-04-10 00:45:43,455 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2018-04-10 00:45:43,455 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:45:43,455 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-10 00:45:43,455 INFO L408 AbstractCegarLoop]: === Iteration 10 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:45:43,455 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-10 00:45:43,462 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:45:43,474 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:45:43,477 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:45:43,521 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-10 00:45:43,522 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:45:43,589 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-10 00:45:43,626 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:45:43,626 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 15 [2018-04-10 00:45:43,626 INFO L442 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-04-10 00:45:43,627 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-04-10 00:45:43,627 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=186, Unknown=0, NotChecked=0, Total=240 [2018-04-10 00:45:43,627 INFO L87 Difference]: Start difference. First operand 199 states and 248 transitions. Second operand 16 states. [2018-04-10 00:45:43,950 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:45:43,950 INFO L93 Difference]: Finished difference Result 240 states and 304 transitions. [2018-04-10 00:45:43,950 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-04-10 00:45:43,950 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 65 [2018-04-10 00:45:43,950 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:45:43,952 INFO L225 Difference]: With dead ends: 240 [2018-04-10 00:45:43,952 INFO L226 Difference]: Without dead ends: 238 [2018-04-10 00:45:43,952 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-10 00:45:43,953 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 238 states. [2018-04-10 00:45:43,962 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 238 to 235. [2018-04-10 00:45:43,962 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 235 states. [2018-04-10 00:45:43,963 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 292 transitions. [2018-04-10 00:45:43,964 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 292 transitions. Word has length 65 [2018-04-10 00:45:43,964 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:45:43,964 INFO L459 AbstractCegarLoop]: Abstraction has 235 states and 292 transitions. [2018-04-10 00:45:43,964 INFO L460 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-04-10 00:45:43,964 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 292 transitions. [2018-04-10 00:45:43,965 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2018-04-10 00:45:43,966 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:45:43,966 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-10 00:45:43,966 INFO L408 AbstractCegarLoop]: === Iteration 11 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:45:43,966 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-10 00:45:43,973 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:45:43,989 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:45:43,993 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:45:44,154 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-10 00:45:44,154 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:45:44,361 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-10 00:45:44,384 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:45:44,384 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21] total 30 [2018-04-10 00:45:44,385 INFO L442 AbstractCegarLoop]: Interpolant automaton has 30 states [2018-04-10 00:45:44,385 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2018-04-10 00:45:44,385 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=139, Invalid=731, Unknown=0, NotChecked=0, Total=870 [2018-04-10 00:45:44,386 INFO L87 Difference]: Start difference. First operand 235 states and 292 transitions. Second operand 30 states. [2018-04-10 00:45:44,872 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:45:44,872 INFO L93 Difference]: Finished difference Result 314 states and 385 transitions. [2018-04-10 00:45:44,872 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-04-10 00:45:44,872 INFO L78 Accepts]: Start accepts. Automaton has 30 states. Word has length 93 [2018-04-10 00:45:44,872 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:45:44,873 INFO L225 Difference]: With dead ends: 314 [2018-04-10 00:45:44,874 INFO L226 Difference]: Without dead ends: 235 [2018-04-10 00:45:44,875 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-10 00:45:44,875 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 235 states. [2018-04-10 00:45:44,883 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 235 to 235. [2018-04-10 00:45:44,883 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 235 states. [2018-04-10 00:45:44,885 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 291 transitions. [2018-04-10 00:45:44,886 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 291 transitions. Word has length 93 [2018-04-10 00:45:44,886 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:45:44,886 INFO L459 AbstractCegarLoop]: Abstraction has 235 states and 291 transitions. [2018-04-10 00:45:44,886 INFO L460 AbstractCegarLoop]: Interpolant automaton has 30 states. [2018-04-10 00:45:44,886 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 291 transitions. [2018-04-10 00:45:44,888 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 101 [2018-04-10 00:45:44,888 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:45:44,888 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-10 00:45:44,888 INFO L408 AbstractCegarLoop]: === Iteration 12 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:45:44,889 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-10 00:45:44,898 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:45:44,914 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:45:44,917 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:45:45,125 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-10 00:45:45,125 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:45:45,304 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-10 00:45:45,325 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:45:45,325 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 25] total 36 [2018-04-10 00:45:45,326 INFO L442 AbstractCegarLoop]: Interpolant automaton has 36 states [2018-04-10 00:45:45,326 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2018-04-10 00:45:45,326 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=191, Invalid=1069, Unknown=0, NotChecked=0, Total=1260 [2018-04-10 00:45:45,326 INFO L87 Difference]: Start difference. First operand 235 states and 291 transitions. Second operand 36 states. [2018-04-10 00:45:45,845 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:45:45,845 INFO L93 Difference]: Finished difference Result 314 states and 384 transitions. [2018-04-10 00:45:45,845 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2018-04-10 00:45:45,845 INFO L78 Accepts]: Start accepts. Automaton has 36 states. Word has length 100 [2018-04-10 00:45:45,846 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:45:45,847 INFO L225 Difference]: With dead ends: 314 [2018-04-10 00:45:45,847 INFO L226 Difference]: Without dead ends: 235 [2018-04-10 00:45:45,849 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 225 GetRequests, 153 SyntacticMatches, 12 SemanticMatches, 60 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 972 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=607, Invalid=3175, Unknown=0, NotChecked=0, Total=3782 [2018-04-10 00:45:45,849 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 235 states. [2018-04-10 00:45:45,857 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 235 to 235. [2018-04-10 00:45:45,857 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 235 states. [2018-04-10 00:45:45,858 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 290 transitions. [2018-04-10 00:45:45,859 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 290 transitions. Word has length 100 [2018-04-10 00:45:45,859 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:45:45,859 INFO L459 AbstractCegarLoop]: Abstraction has 235 states and 290 transitions. [2018-04-10 00:45:45,859 INFO L460 AbstractCegarLoop]: Interpolant automaton has 36 states. [2018-04-10 00:45:45,859 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 290 transitions. [2018-04-10 00:45:45,861 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2018-04-10 00:45:45,861 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:45:45,861 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-10 00:45:45,861 INFO L408 AbstractCegarLoop]: === Iteration 13 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:45:45,861 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-10 00:45:45,874 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:45:45,892 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:45:45,895 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:45:46,312 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-10 00:45:46,313 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:45:46,561 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-10 00:45:46,582 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:45:46,582 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [29, 29] total 42 [2018-04-10 00:45:46,582 INFO L442 AbstractCegarLoop]: Interpolant automaton has 42 states [2018-04-10 00:45:46,582 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 42 interpolants. [2018-04-10 00:45:46,583 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=251, Invalid=1471, Unknown=0, NotChecked=0, Total=1722 [2018-04-10 00:45:46,583 INFO L87 Difference]: Start difference. First operand 235 states and 290 transitions. Second operand 42 states. [2018-04-10 00:45:47,374 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:45:47,374 INFO L93 Difference]: Finished difference Result 314 states and 383 transitions. [2018-04-10 00:45:47,375 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 47 states. [2018-04-10 00:45:47,375 INFO L78 Accepts]: Start accepts. Automaton has 42 states. Word has length 107 [2018-04-10 00:45:47,375 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:45:47,376 INFO L225 Difference]: With dead ends: 314 [2018-04-10 00:45:47,376 INFO L226 Difference]: Without dead ends: 235 [2018-04-10 00:45:47,377 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 244 GetRequests, 159 SyntacticMatches, 14 SemanticMatches, 71 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1386 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=818, Invalid=4438, Unknown=0, NotChecked=0, Total=5256 [2018-04-10 00:45:47,378 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 235 states. [2018-04-10 00:45:47,384 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 235 to 235. [2018-04-10 00:45:47,384 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 235 states. [2018-04-10 00:45:47,385 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 289 transitions. [2018-04-10 00:45:47,385 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 289 transitions. Word has length 107 [2018-04-10 00:45:47,386 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:45:47,386 INFO L459 AbstractCegarLoop]: Abstraction has 235 states and 289 transitions. [2018-04-10 00:45:47,386 INFO L460 AbstractCegarLoop]: Interpolant automaton has 42 states. [2018-04-10 00:45:47,386 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 289 transitions. [2018-04-10 00:45:47,387 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 115 [2018-04-10 00:45:47,387 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:45:47,387 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-10 00:45:47,387 INFO L408 AbstractCegarLoop]: === Iteration 14 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:45:47,388 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-10 00:45:47,398 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:45:47,416 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:45:47,418 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:45:47,759 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-10 00:45:47,759 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:45:48,101 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-10 00:45:48,123 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:45:48,123 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [33, 33] total 48 [2018-04-10 00:45:48,123 INFO L442 AbstractCegarLoop]: Interpolant automaton has 48 states [2018-04-10 00:45:48,124 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 48 interpolants. [2018-04-10 00:45:48,124 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=319, Invalid=1937, Unknown=0, NotChecked=0, Total=2256 [2018-04-10 00:45:48,124 INFO L87 Difference]: Start difference. First operand 235 states and 289 transitions. Second operand 48 states. [2018-04-10 00:45:48,930 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:45:48,931 INFO L93 Difference]: Finished difference Result 320 states and 389 transitions. [2018-04-10 00:45:48,931 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 54 states. [2018-04-10 00:45:48,931 INFO L78 Accepts]: Start accepts. Automaton has 48 states. Word has length 114 [2018-04-10 00:45:48,931 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:45:48,932 INFO L225 Difference]: With dead ends: 320 [2018-04-10 00:45:48,932 INFO L226 Difference]: Without dead ends: 235 [2018-04-10 00:45:48,934 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-10 00:45:48,935 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 235 states. [2018-04-10 00:45:48,941 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 235 to 235. [2018-04-10 00:45:48,941 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 235 states. [2018-04-10 00:45:48,942 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 288 transitions. [2018-04-10 00:45:48,942 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 288 transitions. Word has length 114 [2018-04-10 00:45:48,943 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:45:48,943 INFO L459 AbstractCegarLoop]: Abstraction has 235 states and 288 transitions. [2018-04-10 00:45:48,943 INFO L460 AbstractCegarLoop]: Interpolant automaton has 48 states. [2018-04-10 00:45:48,943 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 288 transitions. [2018-04-10 00:45:48,944 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 119 [2018-04-10 00:45:48,944 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:45:48,944 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-10 00:45:48,944 INFO L408 AbstractCegarLoop]: === Iteration 15 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:45:48,944 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-10 00:45:48,966 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:45:48,983 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:45:48,986 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:45:49,340 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-10 00:45:49,340 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:45:50,248 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-10 00:45:50,270 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:45:50,270 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [32, 32] total 63 [2018-04-10 00:45:50,270 INFO L442 AbstractCegarLoop]: Interpolant automaton has 64 states [2018-04-10 00:45:50,270 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 64 interpolants. [2018-04-10 00:45:50,271 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=606, Invalid=3426, Unknown=0, NotChecked=0, Total=4032 [2018-04-10 00:45:50,271 INFO L87 Difference]: Start difference. First operand 235 states and 288 transitions. Second operand 64 states. [2018-04-10 00:45:56,011 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:45:56,011 INFO L93 Difference]: Finished difference Result 407 states and 539 transitions. [2018-04-10 00:45:56,012 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 93 states. [2018-04-10 00:45:56,012 INFO L78 Accepts]: Start accepts. Automaton has 64 states. Word has length 118 [2018-04-10 00:45:56,012 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:45:56,014 INFO L225 Difference]: With dead ends: 407 [2018-04-10 00:45:56,014 INFO L226 Difference]: Without dead ends: 405 [2018-04-10 00:45:56,018 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 309 GetRequests, 173 SyntacticMatches, 0 SemanticMatches, 136 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3452 ImplicationChecksByTransitivity, 5.1s TimeCoverageRelationStatistics Valid=4624, Invalid=14282, Unknown=0, NotChecked=0, Total=18906 [2018-04-10 00:45:56,019 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 405 states. [2018-04-10 00:45:56,030 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 405 to 379. [2018-04-10 00:45:56,030 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 379 states. [2018-04-10 00:45:56,032 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 379 states to 379 states and 480 transitions. [2018-04-10 00:45:56,032 INFO L78 Accepts]: Start accepts. Automaton has 379 states and 480 transitions. Word has length 118 [2018-04-10 00:45:56,033 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:45:56,033 INFO L459 AbstractCegarLoop]: Abstraction has 379 states and 480 transitions. [2018-04-10 00:45:56,033 INFO L460 AbstractCegarLoop]: Interpolant automaton has 64 states. [2018-04-10 00:45:56,033 INFO L276 IsEmpty]: Start isEmpty. Operand 379 states and 480 transitions. [2018-04-10 00:45:56,035 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 122 [2018-04-10 00:45:56,035 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:45:56,035 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-10 00:45:56,035 INFO L408 AbstractCegarLoop]: === Iteration 16 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:45:56,035 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-10 00:45:56,049 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:45:56,067 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:45:56,070 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:45:56,165 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-10 00:45:56,165 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:45:56,407 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-10 00:45:56,428 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:45:56,428 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 31 [2018-04-10 00:45:56,429 INFO L442 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-04-10 00:45:56,429 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-04-10 00:45:56,429 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=174, Invalid=818, Unknown=0, NotChecked=0, Total=992 [2018-04-10 00:45:56,429 INFO L87 Difference]: Start difference. First operand 379 states and 480 transitions. Second operand 32 states. [2018-04-10 00:45:57,774 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:45:57,774 INFO L93 Difference]: Finished difference Result 456 states and 588 transitions. [2018-04-10 00:45:57,774 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2018-04-10 00:45:57,774 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 121 [2018-04-10 00:45:57,774 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:45:57,777 INFO L225 Difference]: With dead ends: 456 [2018-04-10 00:45:57,777 INFO L226 Difference]: Without dead ends: 454 [2018-04-10 00:45:57,778 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-10 00:45:57,779 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 454 states. [2018-04-10 00:45:57,796 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 454 to 451. [2018-04-10 00:45:57,796 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-04-10 00:45:57,799 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 568 transitions. [2018-04-10 00:45:57,799 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 568 transitions. Word has length 121 [2018-04-10 00:45:57,800 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:45:57,800 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 568 transitions. [2018-04-10 00:45:57,800 INFO L460 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-04-10 00:45:57,800 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 568 transitions. [2018-04-10 00:45:57,803 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 178 [2018-04-10 00:45:57,803 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:45:57,803 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-10 00:45:57,803 INFO L408 AbstractCegarLoop]: === Iteration 17 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:45:57,804 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-10 00:45:57,813 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:45:57,851 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:45:57,855 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:45:58,305 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-10 00:45:58,305 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:45:58,679 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-10 00:45:58,700 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:45:58,700 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [37, 37] total 54 [2018-04-10 00:45:58,701 INFO L442 AbstractCegarLoop]: Interpolant automaton has 54 states [2018-04-10 00:45:58,701 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 54 interpolants. [2018-04-10 00:45:58,701 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=395, Invalid=2467, Unknown=0, NotChecked=0, Total=2862 [2018-04-10 00:45:58,701 INFO L87 Difference]: Start difference. First operand 451 states and 568 transitions. Second operand 54 states. [2018-04-10 00:45:59,682 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:45:59,682 INFO L93 Difference]: Finished difference Result 602 states and 749 transitions. [2018-04-10 00:45:59,683 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 61 states. [2018-04-10 00:45:59,683 INFO L78 Accepts]: Start accepts. Automaton has 54 states. Word has length 177 [2018-04-10 00:45:59,683 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:45:59,685 INFO L225 Difference]: With dead ends: 602 [2018-04-10 00:45:59,685 INFO L226 Difference]: Without dead ends: 451 [2018-04-10 00:45:59,686 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 394 GetRequests, 283 SyntacticMatches, 18 SemanticMatches, 93 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2433 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=1333, Invalid=7597, Unknown=0, NotChecked=0, Total=8930 [2018-04-10 00:45:59,687 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-04-10 00:45:59,698 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-04-10 00:45:59,698 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-04-10 00:45:59,700 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 567 transitions. [2018-04-10 00:45:59,700 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 567 transitions. Word has length 177 [2018-04-10 00:45:59,700 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:45:59,700 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 567 transitions. [2018-04-10 00:45:59,700 INFO L460 AbstractCegarLoop]: Interpolant automaton has 54 states. [2018-04-10 00:45:59,700 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 567 transitions. [2018-04-10 00:45:59,702 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 185 [2018-04-10 00:45:59,702 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:45:59,702 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-10 00:45:59,702 INFO L408 AbstractCegarLoop]: === Iteration 18 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:45:59,703 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-10 00:45:59,712 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:45:59,740 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:45:59,743 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:46:00,447 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-10 00:46:00,447 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:46:00,902 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-10 00:46:00,923 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:46:00,923 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [41, 41] total 60 [2018-04-10 00:46:00,924 INFO L442 AbstractCegarLoop]: Interpolant automaton has 60 states [2018-04-10 00:46:00,924 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 60 interpolants. [2018-04-10 00:46:00,924 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=479, Invalid=3061, Unknown=0, NotChecked=0, Total=3540 [2018-04-10 00:46:00,925 INFO L87 Difference]: Start difference. First operand 451 states and 567 transitions. Second operand 60 states. [2018-04-10 00:46:02,065 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:46:02,066 INFO L93 Difference]: Finished difference Result 602 states and 748 transitions. [2018-04-10 00:46:02,066 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 68 states. [2018-04-10 00:46:02,066 INFO L78 Accepts]: Start accepts. Automaton has 60 states. Word has length 184 [2018-04-10 00:46:02,066 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:46:02,068 INFO L225 Difference]: With dead ends: 602 [2018-04-10 00:46:02,069 INFO L226 Difference]: Without dead ends: 451 [2018-04-10 00:46:02,071 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 413 GetRequests, 289 SyntacticMatches, 20 SemanticMatches, 104 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3066 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=1637, Invalid=9493, Unknown=0, NotChecked=0, Total=11130 [2018-04-10 00:46:02,071 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-04-10 00:46:02,086 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-04-10 00:46:02,086 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-04-10 00:46:02,089 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 566 transitions. [2018-04-10 00:46:02,089 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 566 transitions. Word has length 184 [2018-04-10 00:46:02,089 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:46:02,089 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 566 transitions. [2018-04-10 00:46:02,089 INFO L460 AbstractCegarLoop]: Interpolant automaton has 60 states. [2018-04-10 00:46:02,089 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 566 transitions. [2018-04-10 00:46:02,093 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 192 [2018-04-10 00:46:02,093 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:46:02,093 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-10 00:46:02,094 INFO L408 AbstractCegarLoop]: === Iteration 19 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:46:02,094 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-10 00:46:02,104 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:46:02,138 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:46:02,143 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:46:02,698 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-10 00:46:02,698 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:46:03,239 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-10 00:46:03,260 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:46:03,260 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [45, 45] total 66 [2018-04-10 00:46:03,260 INFO L442 AbstractCegarLoop]: Interpolant automaton has 66 states [2018-04-10 00:46:03,261 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 66 interpolants. [2018-04-10 00:46:03,261 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=571, Invalid=3719, Unknown=0, NotChecked=0, Total=4290 [2018-04-10 00:46:03,261 INFO L87 Difference]: Start difference. First operand 451 states and 566 transitions. Second operand 66 states. [2018-04-10 00:46:04,553 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:46:04,553 INFO L93 Difference]: Finished difference Result 602 states and 747 transitions. [2018-04-10 00:46:04,553 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 75 states. [2018-04-10 00:46:04,553 INFO L78 Accepts]: Start accepts. Automaton has 66 states. Word has length 191 [2018-04-10 00:46:04,553 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:46:04,555 INFO L225 Difference]: With dead ends: 602 [2018-04-10 00:46:04,555 INFO L226 Difference]: Without dead ends: 451 [2018-04-10 00:46:04,556 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-10 00:46:04,557 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-04-10 00:46:04,570 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-04-10 00:46:04,571 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-04-10 00:46:04,572 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 565 transitions. [2018-04-10 00:46:04,573 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 565 transitions. Word has length 191 [2018-04-10 00:46:04,573 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:46:04,573 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 565 transitions. [2018-04-10 00:46:04,573 INFO L460 AbstractCegarLoop]: Interpolant automaton has 66 states. [2018-04-10 00:46:04,573 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 565 transitions. [2018-04-10 00:46:04,576 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 199 [2018-04-10 00:46:04,576 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:46:04,576 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-10 00:46:04,577 INFO L408 AbstractCegarLoop]: === Iteration 20 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:46:04,577 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-10 00:46:04,585 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:46:04,620 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:46:04,625 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:46:05,252 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-10 00:46:05,252 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:46:05,883 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-10 00:46:05,904 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:46:05,904 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [49, 49] total 72 [2018-04-10 00:46:05,905 INFO L442 AbstractCegarLoop]: Interpolant automaton has 72 states [2018-04-10 00:46:05,905 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 72 interpolants. [2018-04-10 00:46:05,906 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=671, Invalid=4441, Unknown=0, NotChecked=0, Total=5112 [2018-04-10 00:46:05,906 INFO L87 Difference]: Start difference. First operand 451 states and 565 transitions. Second operand 72 states. [2018-04-10 00:46:07,409 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:46:07,409 INFO L93 Difference]: Finished difference Result 602 states and 746 transitions. [2018-04-10 00:46:07,409 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 82 states. [2018-04-10 00:46:07,410 INFO L78 Accepts]: Start accepts. Automaton has 72 states. Word has length 198 [2018-04-10 00:46:07,410 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:46:07,412 INFO L225 Difference]: With dead ends: 602 [2018-04-10 00:46:07,412 INFO L226 Difference]: Without dead ends: 451 [2018-04-10 00:46:07,413 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-10 00:46:07,413 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-04-10 00:46:07,422 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-04-10 00:46:07,422 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-04-10 00:46:07,432 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 564 transitions. [2018-04-10 00:46:07,433 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 564 transitions. Word has length 198 [2018-04-10 00:46:07,433 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:46:07,433 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 564 transitions. [2018-04-10 00:46:07,433 INFO L460 AbstractCegarLoop]: Interpolant automaton has 72 states. [2018-04-10 00:46:07,433 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 564 transitions. [2018-04-10 00:46:07,435 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 206 [2018-04-10 00:46:07,435 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:46:07,436 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-10 00:46:07,436 INFO L408 AbstractCegarLoop]: === Iteration 21 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:46:07,436 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-10 00:46:07,444 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:46:07,475 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:46:07,480 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:46:08,197 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-10 00:46:08,197 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:46:08,941 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-10 00:46:08,962 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:46:08,979 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [53, 53] total 78 [2018-04-10 00:46:08,980 INFO L442 AbstractCegarLoop]: Interpolant automaton has 78 states [2018-04-10 00:46:08,980 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 78 interpolants. [2018-04-10 00:46:08,981 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=779, Invalid=5227, Unknown=0, NotChecked=0, Total=6006 [2018-04-10 00:46:08,981 INFO L87 Difference]: Start difference. First operand 451 states and 564 transitions. Second operand 78 states. [2018-04-10 00:46:10,851 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:46:10,851 INFO L93 Difference]: Finished difference Result 602 states and 745 transitions. [2018-04-10 00:46:10,851 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 89 states. [2018-04-10 00:46:10,851 INFO L78 Accepts]: Start accepts. Automaton has 78 states. Word has length 205 [2018-04-10 00:46:10,852 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:46:10,853 INFO L225 Difference]: With dead ends: 602 [2018-04-10 00:46:10,853 INFO L226 Difference]: Without dead ends: 451 [2018-04-10 00:46:10,855 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 470 GetRequests, 307 SyntacticMatches, 26 SemanticMatches, 137 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5403 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=2735, Invalid=16447, Unknown=0, NotChecked=0, Total=19182 [2018-04-10 00:46:10,855 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-04-10 00:46:10,868 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-04-10 00:46:10,868 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-04-10 00:46:10,870 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 563 transitions. [2018-04-10 00:46:10,870 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 563 transitions. Word has length 205 [2018-04-10 00:46:10,870 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:46:10,871 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 563 transitions. [2018-04-10 00:46:10,871 INFO L460 AbstractCegarLoop]: Interpolant automaton has 78 states. [2018-04-10 00:46:10,871 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 563 transitions. [2018-04-10 00:46:10,873 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 213 [2018-04-10 00:46:10,873 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:46:10,874 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-10 00:46:10,874 INFO L408 AbstractCegarLoop]: === Iteration 22 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:46:10,874 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-10 00:46:10,882 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:46:10,918 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:46:10,922 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:46:11,701 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-10 00:46:11,701 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:46:12,551 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-10 00:46:12,572 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:46:12,572 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [57, 57] total 84 [2018-04-10 00:46:12,573 INFO L442 AbstractCegarLoop]: Interpolant automaton has 84 states [2018-04-10 00:46:12,573 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 84 interpolants. [2018-04-10 00:46:12,573 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=895, Invalid=6077, Unknown=0, NotChecked=0, Total=6972 [2018-04-10 00:46:12,574 INFO L87 Difference]: Start difference. First operand 451 states and 563 transitions. Second operand 84 states. [2018-04-10 00:46:14,533 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:46:14,533 INFO L93 Difference]: Finished difference Result 602 states and 744 transitions. [2018-04-10 00:46:14,534 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 96 states. [2018-04-10 00:46:14,534 INFO L78 Accepts]: Start accepts. Automaton has 84 states. Word has length 212 [2018-04-10 00:46:14,534 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:46:14,536 INFO L225 Difference]: With dead ends: 602 [2018-04-10 00:46:14,536 INFO L226 Difference]: Without dead ends: 451 [2018-04-10 00:46:14,537 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 489 GetRequests, 313 SyntacticMatches, 28 SemanticMatches, 148 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6328 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=3163, Invalid=19187, Unknown=0, NotChecked=0, Total=22350 [2018-04-10 00:46:14,538 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-04-10 00:46:14,550 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-04-10 00:46:14,551 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-04-10 00:46:14,552 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 562 transitions. [2018-04-10 00:46:14,552 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 562 transitions. Word has length 212 [2018-04-10 00:46:14,553 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:46:14,553 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 562 transitions. [2018-04-10 00:46:14,553 INFO L460 AbstractCegarLoop]: Interpolant automaton has 84 states. [2018-04-10 00:46:14,553 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 562 transitions. [2018-04-10 00:46:14,555 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 220 [2018-04-10 00:46:14,555 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:46:14,556 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-10 00:46:14,556 INFO L408 AbstractCegarLoop]: === Iteration 23 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:46:14,556 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-10 00:46:14,569 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:46:14,600 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:46:14,604 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:46:15,432 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-10 00:46:15,432 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:46:16,538 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-10 00:46:16,560 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:46:16,560 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [61, 61] total 90 [2018-04-10 00:46:16,560 INFO L442 AbstractCegarLoop]: Interpolant automaton has 90 states [2018-04-10 00:46:16,561 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 90 interpolants. [2018-04-10 00:46:16,561 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1019, Invalid=6991, Unknown=0, NotChecked=0, Total=8010 [2018-04-10 00:46:16,561 INFO L87 Difference]: Start difference. First operand 451 states and 562 transitions. Second operand 90 states. [2018-04-10 00:46:18,804 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:46:18,804 INFO L93 Difference]: Finished difference Result 602 states and 743 transitions. [2018-04-10 00:46:18,804 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 103 states. [2018-04-10 00:46:18,804 INFO L78 Accepts]: Start accepts. Automaton has 90 states. Word has length 219 [2018-04-10 00:46:18,805 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:46:18,807 INFO L225 Difference]: With dead ends: 602 [2018-04-10 00:46:18,808 INFO L226 Difference]: Without dead ends: 451 [2018-04-10 00:46:18,810 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 508 GetRequests, 319 SyntacticMatches, 30 SemanticMatches, 159 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7326 ImplicationChecksByTransitivity, 3.2s TimeCoverageRelationStatistics Valid=3622, Invalid=22138, Unknown=0, NotChecked=0, Total=25760 [2018-04-10 00:46:18,811 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-04-10 00:46:18,825 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-04-10 00:46:18,825 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-04-10 00:46:18,827 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 561 transitions. [2018-04-10 00:46:18,828 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 561 transitions. Word has length 219 [2018-04-10 00:46:18,828 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:46:18,828 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 561 transitions. [2018-04-10 00:46:18,828 INFO L460 AbstractCegarLoop]: Interpolant automaton has 90 states. [2018-04-10 00:46:18,828 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 561 transitions. [2018-04-10 00:46:18,831 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 227 [2018-04-10 00:46:18,831 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:46:18,831 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-10 00:46:18,831 INFO L408 AbstractCegarLoop]: === Iteration 24 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:46:18,831 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-10 00:46:18,840 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:46:18,877 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:46:18,883 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:46:19,862 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-10 00:46:19,862 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:46:20,965 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-10 00:46:20,986 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:46:20,987 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [65, 65] total 96 [2018-04-10 00:46:20,987 INFO L442 AbstractCegarLoop]: Interpolant automaton has 96 states [2018-04-10 00:46:20,987 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 96 interpolants. [2018-04-10 00:46:20,988 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1151, Invalid=7969, Unknown=0, NotChecked=0, Total=9120 [2018-04-10 00:46:20,988 INFO L87 Difference]: Start difference. First operand 451 states and 561 transitions. Second operand 96 states. [2018-04-10 00:46:23,619 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:46:23,619 INFO L93 Difference]: Finished difference Result 608 states and 749 transitions. [2018-04-10 00:46:23,619 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 110 states. [2018-04-10 00:46:23,619 INFO L78 Accepts]: Start accepts. Automaton has 96 states. Word has length 226 [2018-04-10 00:46:23,620 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:46:23,621 INFO L225 Difference]: With dead ends: 608 [2018-04-10 00:46:23,622 INFO L226 Difference]: Without dead ends: 451 [2018-04-10 00:46:23,623 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-10 00:46:23,623 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-04-10 00:46:23,631 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-04-10 00:46:23,631 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-04-10 00:46:23,632 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 560 transitions. [2018-04-10 00:46:23,632 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 560 transitions. Word has length 226 [2018-04-10 00:46:23,632 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:46:23,632 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 560 transitions. [2018-04-10 00:46:23,633 INFO L460 AbstractCegarLoop]: Interpolant automaton has 96 states. [2018-04-10 00:46:23,633 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 560 transitions. [2018-04-10 00:46:23,634 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 231 [2018-04-10 00:46:23,634 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:46:23,634 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-10 00:46:23,634 INFO L408 AbstractCegarLoop]: === Iteration 25 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:46:23,634 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-10 00:46:23,640 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:46:23,673 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:46:23,678 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:46:25,105 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-10 00:46:25,106 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:46:28,586 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-10 00:46:28,607 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:46:28,608 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [64, 64] total 127 [2018-04-10 00:46:28,608 INFO L442 AbstractCegarLoop]: Interpolant automaton has 128 states [2018-04-10 00:46:28,609 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 128 interpolants. [2018-04-10 00:46:28,610 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2238, Invalid=14018, Unknown=0, NotChecked=0, Total=16256 [2018-04-10 00:46:28,610 INFO L87 Difference]: Start difference. First operand 451 states and 560 transitions. Second operand 128 states. [2018-04-10 00:46:34,896 WARN L151 SmtUtils]: Spent 261ms on a formula simplification. DAG size of input: 252 DAG size of output 12 [2018-04-10 00:46:35,599 WARN L151 SmtUtils]: Spent 251ms on a formula simplification. DAG size of input: 247 DAG size of output 11 [2018-04-10 00:46:36,086 WARN L151 SmtUtils]: Spent 262ms on a formula simplification. DAG size of input: 244 DAG size of output 12 [2018-04-10 00:46:36,753 WARN L151 SmtUtils]: Spent 232ms on a formula simplification. DAG size of input: 239 DAG size of output 11 [2018-04-10 00:46:37,212 WARN L151 SmtUtils]: Spent 230ms on a formula simplification. DAG size of input: 236 DAG size of output 12 [2018-04-10 00:46:37,863 WARN L151 SmtUtils]: Spent 218ms on a formula simplification. DAG size of input: 231 DAG size of output 11 [2018-04-10 00:46:38,305 WARN L151 SmtUtils]: Spent 207ms on a formula simplification. DAG size of input: 228 DAG size of output 12 [2018-04-10 00:46:38,947 WARN L151 SmtUtils]: Spent 206ms on a formula simplification. DAG size of input: 223 DAG size of output 11 [2018-04-10 00:46:39,376 WARN L151 SmtUtils]: Spent 200ms on a formula simplification. DAG size of input: 220 DAG size of output 12 [2018-04-10 00:46:40,011 WARN L151 SmtUtils]: Spent 198ms on a formula simplification. DAG size of input: 215 DAG size of output 11 [2018-04-10 00:46:40,435 WARN L151 SmtUtils]: Spent 194ms on a formula simplification. DAG size of input: 212 DAG size of output 12 [2018-04-10 00:46:41,041 WARN L151 SmtUtils]: Spent 186ms on a formula simplification. DAG size of input: 207 DAG size of output 11 [2018-04-10 00:46:41,441 WARN L151 SmtUtils]: Spent 173ms on a formula simplification. DAG size of input: 204 DAG size of output 12 [2018-04-10 00:46:42,043 WARN L151 SmtUtils]: Spent 174ms on a formula simplification. DAG size of input: 199 DAG size of output 11 [2018-04-10 00:46:42,438 WARN L151 SmtUtils]: Spent 170ms on a formula simplification. DAG size of input: 196 DAG size of output 12 [2018-04-10 00:46:43,001 WARN L151 SmtUtils]: Spent 152ms on a formula simplification. DAG size of input: 191 DAG size of output 11 [2018-04-10 00:46:43,379 WARN L151 SmtUtils]: Spent 154ms on a formula simplification. DAG size of input: 188 DAG size of output 12 [2018-04-10 00:46:43,947 WARN L151 SmtUtils]: Spent 160ms on a formula simplification. DAG size of input: 183 DAG size of output 11 [2018-04-10 00:46:44,307 WARN L151 SmtUtils]: Spent 138ms on a formula simplification. DAG size of input: 180 DAG size of output 12 [2018-04-10 00:46:44,840 WARN L151 SmtUtils]: Spent 135ms on a formula simplification. DAG size of input: 175 DAG size of output 11 [2018-04-10 00:46:45,196 WARN L151 SmtUtils]: Spent 128ms on a formula simplification. DAG size of input: 172 DAG size of output 12 [2018-04-10 00:46:45,723 WARN L151 SmtUtils]: Spent 123ms on a formula simplification. DAG size of input: 167 DAG size of output 11 [2018-04-10 00:46:46,056 WARN L151 SmtUtils]: Spent 116ms on a formula simplification. DAG size of input: 164 DAG size of output 12 [2018-04-10 00:46:46,562 WARN L151 SmtUtils]: Spent 114ms on a formula simplification. DAG size of input: 159 DAG size of output 11 [2018-04-10 00:46:46,895 WARN L151 SmtUtils]: Spent 120ms on a formula simplification. DAG size of input: 156 DAG size of output 12 [2018-04-10 00:46:47,374 WARN L151 SmtUtils]: Spent 103ms on a formula simplification. DAG size of input: 151 DAG size of output 11 [2018-04-10 00:46:57,076 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:46:57,077 INFO L93 Difference]: Finished difference Result 791 states and 1059 transitions. [2018-04-10 00:46:57,077 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 189 states. [2018-04-10 00:46:57,077 INFO L78 Accepts]: Start accepts. Automaton has 128 states. Word has length 230 [2018-04-10 00:46:57,077 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:46:57,080 INFO L225 Difference]: With dead ends: 791 [2018-04-10 00:46:57,080 INFO L226 Difference]: Without dead ends: 789 [2018-04-10 00:46:57,082 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 613 GetRequests, 333 SyntacticMatches, 0 SemanticMatches, 280 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15068 ImplicationChecksByTransitivity, 27.5s TimeCoverageRelationStatistics Valid=18976, Invalid=60266, Unknown=0, NotChecked=0, Total=79242 [2018-04-10 00:46:57,083 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 789 states. [2018-04-10 00:46:57,101 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 789 to 739. [2018-04-10 00:46:57,101 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 739 states. [2018-04-10 00:46:57,104 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 739 states to 739 states and 944 transitions. [2018-04-10 00:46:57,104 INFO L78 Accepts]: Start accepts. Automaton has 739 states and 944 transitions. Word has length 230 [2018-04-10 00:46:57,105 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:46:57,105 INFO L459 AbstractCegarLoop]: Abstraction has 739 states and 944 transitions. [2018-04-10 00:46:57,105 INFO L460 AbstractCegarLoop]: Interpolant automaton has 128 states. [2018-04-10 00:46:57,105 INFO L276 IsEmpty]: Start isEmpty. Operand 739 states and 944 transitions. [2018-04-10 00:46:57,107 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 234 [2018-04-10 00:46:57,107 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:46:57,108 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-10 00:46:57,108 INFO L408 AbstractCegarLoop]: === Iteration 26 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:46:57,108 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-10 00:46:57,117 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:46:57,165 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:46:57,171 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:46:57,566 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-10 00:46:57,566 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:46:58,471 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-10 00:46:58,492 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:46:58,493 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [32, 32] total 63 [2018-04-10 00:46:58,493 INFO L442 AbstractCegarLoop]: Interpolant automaton has 64 states [2018-04-10 00:46:58,493 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 64 interpolants. [2018-04-10 00:46:58,494 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=606, Invalid=3426, Unknown=0, NotChecked=0, Total=4032 [2018-04-10 00:46:58,494 INFO L87 Difference]: Start difference. First operand 739 states and 944 transitions. Second operand 64 states. [2018-04-10 00:47:03,572 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:47:03,572 INFO L93 Difference]: Finished difference Result 888 states and 1156 transitions. [2018-04-10 00:47:03,572 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 93 states. [2018-04-10 00:47:03,572 INFO L78 Accepts]: Start accepts. Automaton has 64 states. Word has length 233 [2018-04-10 00:47:03,573 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:47:03,575 INFO L225 Difference]: With dead ends: 888 [2018-04-10 00:47:03,575 INFO L226 Difference]: Without dead ends: 886 [2018-04-10 00:47:03,576 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 539 GetRequests, 403 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-10 00:47:03,577 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 886 states. [2018-04-10 00:47:03,590 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 886 to 883. [2018-04-10 00:47:03,590 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-10 00:47:03,592 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1120 transitions. [2018-04-10 00:47:03,593 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1120 transitions. Word has length 233 [2018-04-10 00:47:03,593 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:47:03,593 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1120 transitions. [2018-04-10 00:47:03,593 INFO L460 AbstractCegarLoop]: Interpolant automaton has 64 states. [2018-04-10 00:47:03,593 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1120 transitions. [2018-04-10 00:47:03,597 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 346 [2018-04-10 00:47:03,597 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:47:03,597 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-10 00:47:03,597 INFO L408 AbstractCegarLoop]: === Iteration 27 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:47:03,597 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-10 00:47:03,611 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:47:03,678 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:47:03,686 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:47:04,721 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-10 00:47:04,721 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:47:06,004 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-10 00:47:06,025 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:47:06,025 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [69, 69] total 102 [2018-04-10 00:47:06,025 INFO L442 AbstractCegarLoop]: Interpolant automaton has 102 states [2018-04-10 00:47:06,026 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 102 interpolants. [2018-04-10 00:47:06,026 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1291, Invalid=9011, Unknown=0, NotChecked=0, Total=10302 [2018-04-10 00:47:06,026 INFO L87 Difference]: Start difference. First operand 883 states and 1120 transitions. Second operand 102 states. [2018-04-10 00:47:08,974 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:47:08,974 INFO L93 Difference]: Finished difference Result 1178 states and 1477 transitions. [2018-04-10 00:47:08,974 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 117 states. [2018-04-10 00:47:08,974 INFO L78 Accepts]: Start accepts. Automaton has 102 states. Word has length 345 [2018-04-10 00:47:08,975 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:47:08,979 INFO L225 Difference]: With dead ends: 1178 [2018-04-10 00:47:08,979 INFO L226 Difference]: Without dead ends: 883 [2018-04-10 00:47:08,982 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 770 GetRequests, 555 SyntacticMatches, 34 SemanticMatches, 181 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9541 ImplicationChecksByTransitivity, 3.9s TimeCoverageRelationStatistics Valid=4633, Invalid=28673, Unknown=0, NotChecked=0, Total=33306 [2018-04-10 00:47:08,983 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-10 00:47:09,001 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-10 00:47:09,001 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-10 00:47:09,003 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1119 transitions. [2018-04-10 00:47:09,004 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1119 transitions. Word has length 345 [2018-04-10 00:47:09,004 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:47:09,004 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1119 transitions. [2018-04-10 00:47:09,004 INFO L460 AbstractCegarLoop]: Interpolant automaton has 102 states. [2018-04-10 00:47:09,004 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1119 transitions. [2018-04-10 00:47:09,008 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 353 [2018-04-10 00:47:09,008 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:47:09,009 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-10 00:47:09,009 INFO L408 AbstractCegarLoop]: === Iteration 28 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:47:09,009 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-10 00:47:09,018 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:47:09,087 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:47:09,098 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:47:10,269 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-10 00:47:10,269 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:47:11,673 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-10 00:47:11,694 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:47:11,695 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [73, 73] total 108 [2018-04-10 00:47:11,695 INFO L442 AbstractCegarLoop]: Interpolant automaton has 108 states [2018-04-10 00:47:11,695 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 108 interpolants. [2018-04-10 00:47:11,696 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1439, Invalid=10117, Unknown=0, NotChecked=0, Total=11556 [2018-04-10 00:47:11,696 INFO L87 Difference]: Start difference. First operand 883 states and 1119 transitions. Second operand 108 states. [2018-04-10 00:47:15,080 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:47:15,080 INFO L93 Difference]: Finished difference Result 1178 states and 1476 transitions. [2018-04-10 00:47:15,080 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 124 states. [2018-04-10 00:47:15,080 INFO L78 Accepts]: Start accepts. Automaton has 108 states. Word has length 352 [2018-04-10 00:47:15,081 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:47:15,083 INFO L225 Difference]: With dead ends: 1178 [2018-04-10 00:47:15,083 INFO L226 Difference]: Without dead ends: 883 [2018-04-10 00:47:15,086 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 789 GetRequests, 561 SyntacticMatches, 36 SemanticMatches, 192 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10758 ImplicationChecksByTransitivity, 4.4s TimeCoverageRelationStatistics Valid=5185, Invalid=32257, Unknown=0, NotChecked=0, Total=37442 [2018-04-10 00:47:15,086 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-10 00:47:15,098 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-10 00:47:15,099 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-10 00:47:15,100 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1118 transitions. [2018-04-10 00:47:15,101 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1118 transitions. Word has length 352 [2018-04-10 00:47:15,101 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:47:15,101 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1118 transitions. [2018-04-10 00:47:15,101 INFO L460 AbstractCegarLoop]: Interpolant automaton has 108 states. [2018-04-10 00:47:15,101 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1118 transitions. [2018-04-10 00:47:15,103 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 360 [2018-04-10 00:47:15,103 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:47:15,104 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-10 00:47:15,104 INFO L408 AbstractCegarLoop]: === Iteration 29 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:47:15,104 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-10 00:47:15,111 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:47:15,158 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:47:15,164 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:47:16,448 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-10 00:47:16,448 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:47:18,013 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-10 00:47:18,034 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:47:18,034 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [77, 77] total 114 [2018-04-10 00:47:18,035 INFO L442 AbstractCegarLoop]: Interpolant automaton has 114 states [2018-04-10 00:47:18,035 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 114 interpolants. [2018-04-10 00:47:18,036 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1595, Invalid=11287, Unknown=0, NotChecked=0, Total=12882 [2018-04-10 00:47:18,036 INFO L87 Difference]: Start difference. First operand 883 states and 1118 transitions. Second operand 114 states. [2018-04-10 00:47:21,805 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:47:21,805 INFO L93 Difference]: Finished difference Result 1178 states and 1475 transitions. [2018-04-10 00:47:21,805 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 131 states. [2018-04-10 00:47:21,805 INFO L78 Accepts]: Start accepts. Automaton has 114 states. Word has length 359 [2018-04-10 00:47:21,805 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:47:21,808 INFO L225 Difference]: With dead ends: 1178 [2018-04-10 00:47:21,808 INFO L226 Difference]: Without dead ends: 883 [2018-04-10 00:47:21,811 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-10 00:47:21,812 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-10 00:47:21,825 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-10 00:47:21,825 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-10 00:47:21,827 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1117 transitions. [2018-04-10 00:47:21,827 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1117 transitions. Word has length 359 [2018-04-10 00:47:21,827 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:47:21,827 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1117 transitions. [2018-04-10 00:47:21,827 INFO L460 AbstractCegarLoop]: Interpolant automaton has 114 states. [2018-04-10 00:47:21,827 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1117 transitions. [2018-04-10 00:47:21,829 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 367 [2018-04-10 00:47:21,829 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:47:21,829 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-10 00:47:21,829 INFO L408 AbstractCegarLoop]: === Iteration 30 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:47:21,829 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-10 00:47:21,835 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:47:21,878 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:47:21,884 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:47:23,644 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-10 00:47:23,644 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:47:25,435 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-10 00:47:25,456 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:47:25,456 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [81, 81] total 120 [2018-04-10 00:47:25,457 INFO L442 AbstractCegarLoop]: Interpolant automaton has 120 states [2018-04-10 00:47:25,457 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 120 interpolants. [2018-04-10 00:47:25,458 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1759, Invalid=12521, Unknown=0, NotChecked=0, Total=14280 [2018-04-10 00:47:25,458 INFO L87 Difference]: Start difference. First operand 883 states and 1117 transitions. Second operand 120 states. [2018-04-10 00:47:29,638 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:47:29,638 INFO L93 Difference]: Finished difference Result 1178 states and 1474 transitions. [2018-04-10 00:47:29,638 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 138 states. [2018-04-10 00:47:29,639 INFO L78 Accepts]: Start accepts. Automaton has 120 states. Word has length 366 [2018-04-10 00:47:29,639 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:47:29,641 INFO L225 Difference]: With dead ends: 1178 [2018-04-10 00:47:29,641 INFO L226 Difference]: Without dead ends: 883 [2018-04-10 00:47:29,644 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 827 GetRequests, 573 SyntacticMatches, 40 SemanticMatches, 214 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13411 ImplicationChecksByTransitivity, 5.8s TimeCoverageRelationStatistics Valid=6382, Invalid=40058, Unknown=0, NotChecked=0, Total=46440 [2018-04-10 00:47:29,645 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-10 00:47:29,656 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-10 00:47:29,657 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-10 00:47:29,658 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1116 transitions. [2018-04-10 00:47:29,658 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1116 transitions. Word has length 366 [2018-04-10 00:47:29,659 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:47:29,659 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1116 transitions. [2018-04-10 00:47:29,659 INFO L460 AbstractCegarLoop]: Interpolant automaton has 120 states. [2018-04-10 00:47:29,659 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1116 transitions. [2018-04-10 00:47:29,661 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 374 [2018-04-10 00:47:29,661 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:47:29,661 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-10 00:47:29,661 INFO L408 AbstractCegarLoop]: === Iteration 31 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:47:29,661 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-10 00:47:29,667 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:47:29,712 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:47:29,717 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:47:31,239 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-10 00:47:31,239 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:47:33,111 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-10 00:47:33,132 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:47:33,133 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [85, 85] total 126 [2018-04-10 00:47:33,133 INFO L442 AbstractCegarLoop]: Interpolant automaton has 126 states [2018-04-10 00:47:33,134 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 126 interpolants. [2018-04-10 00:47:33,134 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1931, Invalid=13819, Unknown=0, NotChecked=0, Total=15750 [2018-04-10 00:47:33,134 INFO L87 Difference]: Start difference. First operand 883 states and 1116 transitions. Second operand 126 states. [2018-04-10 00:47:37,294 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:47:37,294 INFO L93 Difference]: Finished difference Result 1178 states and 1473 transitions. [2018-04-10 00:47:37,294 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 145 states. [2018-04-10 00:47:37,294 INFO L78 Accepts]: Start accepts. Automaton has 126 states. Word has length 373 [2018-04-10 00:47:37,295 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:47:37,298 INFO L225 Difference]: With dead ends: 1178 [2018-04-10 00:47:37,298 INFO L226 Difference]: Without dead ends: 883 [2018-04-10 00:47:37,303 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-10 00:47:37,304 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-10 00:47:37,324 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-10 00:47:37,324 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-10 00:47:37,326 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1115 transitions. [2018-04-10 00:47:37,327 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1115 transitions. Word has length 373 [2018-04-10 00:47:37,327 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:47:37,327 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1115 transitions. [2018-04-10 00:47:37,327 INFO L460 AbstractCegarLoop]: Interpolant automaton has 126 states. [2018-04-10 00:47:37,327 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1115 transitions. [2018-04-10 00:47:37,329 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 381 [2018-04-10 00:47:37,329 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:47:37,329 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-10 00:47:37,329 INFO L408 AbstractCegarLoop]: === Iteration 32 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:47:37,329 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-10 00:47:37,335 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:47:37,401 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:47:37,407 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:47:39,181 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-10 00:47:39,182 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:47:41,257 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-10 00:47:41,291 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:47:41,291 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [89, 89] total 132 [2018-04-10 00:47:41,292 INFO L442 AbstractCegarLoop]: Interpolant automaton has 132 states [2018-04-10 00:47:41,292 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 132 interpolants. [2018-04-10 00:47:41,292 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2111, Invalid=15181, Unknown=0, NotChecked=0, Total=17292 [2018-04-10 00:47:41,293 INFO L87 Difference]: Start difference. First operand 883 states and 1115 transitions. Second operand 132 states. [2018-04-10 00:47:45,680 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:47:45,680 INFO L93 Difference]: Finished difference Result 1178 states and 1472 transitions. [2018-04-10 00:47:45,681 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 152 states. [2018-04-10 00:47:45,681 INFO L78 Accepts]: Start accepts. Automaton has 132 states. Word has length 380 [2018-04-10 00:47:45,681 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:47:45,684 INFO L225 Difference]: With dead ends: 1178 [2018-04-10 00:47:45,684 INFO L226 Difference]: Without dead ends: 883 [2018-04-10 00:47:45,686 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 865 GetRequests, 585 SyntacticMatches, 44 SemanticMatches, 236 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16356 ImplicationChecksByTransitivity, 6.6s TimeCoverageRelationStatistics Valid=7703, Invalid=48703, Unknown=0, NotChecked=0, Total=56406 [2018-04-10 00:47:45,687 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-10 00:47:45,699 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-10 00:47:45,699 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-10 00:47:45,700 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1114 transitions. [2018-04-10 00:47:45,701 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1114 transitions. Word has length 380 [2018-04-10 00:47:45,701 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:47:45,701 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1114 transitions. [2018-04-10 00:47:45,701 INFO L460 AbstractCegarLoop]: Interpolant automaton has 132 states. [2018-04-10 00:47:45,701 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1114 transitions. [2018-04-10 00:47:45,703 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 388 [2018-04-10 00:47:45,703 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:47:45,704 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-10 00:47:45,704 INFO L408 AbstractCegarLoop]: === Iteration 33 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:47:45,704 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-10 00:47:45,712 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:47:45,772 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:47:45,779 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:47:47,713 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-10 00:47:47,713 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:47:49,945 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-10 00:47:49,967 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:47:49,967 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [93, 93] total 138 [2018-04-10 00:47:49,968 INFO L442 AbstractCegarLoop]: Interpolant automaton has 138 states [2018-04-10 00:47:49,968 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 138 interpolants. [2018-04-10 00:47:49,969 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2299, Invalid=16607, Unknown=0, NotChecked=0, Total=18906 [2018-04-10 00:47:49,969 INFO L87 Difference]: Start difference. First operand 883 states and 1114 transitions. Second operand 138 states. [2018-04-10 00:47:55,194 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:47:55,194 INFO L93 Difference]: Finished difference Result 1178 states and 1471 transitions. [2018-04-10 00:47:55,195 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 159 states. [2018-04-10 00:47:55,195 INFO L78 Accepts]: Start accepts. Automaton has 138 states. Word has length 387 [2018-04-10 00:47:55,195 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:47:55,198 INFO L225 Difference]: With dead ends: 1178 [2018-04-10 00:47:55,198 INFO L226 Difference]: Without dead ends: 883 [2018-04-10 00:47:55,200 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 884 GetRequests, 591 SyntacticMatches, 46 SemanticMatches, 247 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17938 ImplicationChecksByTransitivity, 7.2s TimeCoverageRelationStatistics Valid=8410, Invalid=53342, Unknown=0, NotChecked=0, Total=61752 [2018-04-10 00:47:55,201 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-10 00:47:55,216 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-10 00:47:55,216 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-10 00:47:55,218 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1113 transitions. [2018-04-10 00:47:55,218 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1113 transitions. Word has length 387 [2018-04-10 00:47:55,218 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:47:55,218 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1113 transitions. [2018-04-10 00:47:55,218 INFO L460 AbstractCegarLoop]: Interpolant automaton has 138 states. [2018-04-10 00:47:55,218 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1113 transitions. [2018-04-10 00:47:55,220 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 395 [2018-04-10 00:47:55,220 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:47:55,221 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-10 00:47:55,221 INFO L408 AbstractCegarLoop]: === Iteration 34 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:47:55,221 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-10 00:47:55,227 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:47:55,273 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:47:55,278 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:47:57,192 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-10 00:47:57,192 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:47:59,656 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-10 00:47:59,678 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:47:59,678 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [97, 97] total 144 [2018-04-10 00:47:59,678 INFO L442 AbstractCegarLoop]: Interpolant automaton has 144 states [2018-04-10 00:47:59,679 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 144 interpolants. [2018-04-10 00:47:59,679 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2495, Invalid=18097, Unknown=0, NotChecked=0, Total=20592 [2018-04-10 00:47:59,679 INFO L87 Difference]: Start difference. First operand 883 states and 1113 transitions. Second operand 144 states. [2018-04-10 00:48:04,985 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:48:04,985 INFO L93 Difference]: Finished difference Result 1178 states and 1470 transitions. [2018-04-10 00:48:04,985 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 166 states. [2018-04-10 00:48:04,985 INFO L78 Accepts]: Start accepts. Automaton has 144 states. Word has length 394 [2018-04-10 00:48:04,986 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:48:04,988 INFO L225 Difference]: With dead ends: 1178 [2018-04-10 00:48:04,988 INFO L226 Difference]: Without dead ends: 883 [2018-04-10 00:48:04,992 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 903 GetRequests, 597 SyntacticMatches, 48 SemanticMatches, 258 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19593 ImplicationChecksByTransitivity, 7.7s TimeCoverageRelationStatistics Valid=9148, Invalid=58192, Unknown=0, NotChecked=0, Total=67340 [2018-04-10 00:48:04,993 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-10 00:48:05,013 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-10 00:48:05,013 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-10 00:48:05,015 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1112 transitions. [2018-04-10 00:48:05,015 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1112 transitions. Word has length 394 [2018-04-10 00:48:05,015 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:48:05,016 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1112 transitions. [2018-04-10 00:48:05,016 INFO L460 AbstractCegarLoop]: Interpolant automaton has 144 states. [2018-04-10 00:48:05,016 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1112 transitions. [2018-04-10 00:48:05,019 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 402 [2018-04-10 00:48:05,019 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:48:05,019 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-10 00:48:05,019 INFO L408 AbstractCegarLoop]: === Iteration 35 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:48:05,019 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-10 00:48:05,025 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:48:05,074 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:48:05,079 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:48:07,173 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-10 00:48:07,173 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:48:09,794 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-10 00:48:09,815 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:48:09,816 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [101, 101] total 150 [2018-04-10 00:48:09,816 INFO L442 AbstractCegarLoop]: Interpolant automaton has 150 states [2018-04-10 00:48:09,817 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 150 interpolants. [2018-04-10 00:48:09,817 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2699, Invalid=19651, Unknown=0, NotChecked=0, Total=22350 [2018-04-10 00:48:09,818 INFO L87 Difference]: Start difference. First operand 883 states and 1112 transitions. Second operand 150 states. [2018-04-10 00:48:15,992 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:48:15,992 INFO L93 Difference]: Finished difference Result 1178 states and 1469 transitions. [2018-04-10 00:48:15,992 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 173 states. [2018-04-10 00:48:15,992 INFO L78 Accepts]: Start accepts. Automaton has 150 states. Word has length 401 [2018-04-10 00:48:15,993 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:48:15,996 INFO L225 Difference]: With dead ends: 1178 [2018-04-10 00:48:15,997 INFO L226 Difference]: Without dead ends: 883 [2018-04-10 00:48:16,001 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-10 00:48:16,001 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-10 00:48:16,015 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-10 00:48:16,015 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-10 00:48:16,017 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1111 transitions. [2018-04-10 00:48:16,017 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1111 transitions. Word has length 401 [2018-04-10 00:48:16,018 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:48:16,018 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1111 transitions. [2018-04-10 00:48:16,018 INFO L460 AbstractCegarLoop]: Interpolant automaton has 150 states. [2018-04-10 00:48:16,018 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1111 transitions. [2018-04-10 00:48:16,021 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 409 [2018-04-10 00:48:16,021 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:48:16,022 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-10 00:48:16,022 INFO L408 AbstractCegarLoop]: === Iteration 36 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:48:16,022 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-10 00:48:16,031 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:48:16,078 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:48:16,084 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:48:18,308 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-10 00:48:18,308 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:48:21,127 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-10 00:48:21,148 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:48:21,149 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [105, 105] total 156 [2018-04-10 00:48:21,149 INFO L442 AbstractCegarLoop]: Interpolant automaton has 156 states [2018-04-10 00:48:21,150 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 156 interpolants. [2018-04-10 00:48:21,151 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2911, Invalid=21269, Unknown=0, NotChecked=0, Total=24180 [2018-04-10 00:48:21,151 INFO L87 Difference]: Start difference. First operand 883 states and 1111 transitions. Second operand 156 states. [2018-04-10 00:48:27,520 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:48:27,520 INFO L93 Difference]: Finished difference Result 1178 states and 1468 transitions. [2018-04-10 00:48:27,521 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 180 states. [2018-04-10 00:48:27,521 INFO L78 Accepts]: Start accepts. Automaton has 156 states. Word has length 408 [2018-04-10 00:48:27,521 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:48:27,524 INFO L225 Difference]: With dead ends: 1178 [2018-04-10 00:48:27,524 INFO L226 Difference]: Without dead ends: 883 [2018-04-10 00:48:27,527 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-10 00:48:27,528 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-10 00:48:27,539 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-10 00:48:27,539 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-10 00:48:27,540 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1110 transitions. [2018-04-10 00:48:27,541 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1110 transitions. Word has length 408 [2018-04-10 00:48:27,541 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:48:27,541 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1110 transitions. [2018-04-10 00:48:27,541 INFO L460 AbstractCegarLoop]: Interpolant automaton has 156 states. [2018-04-10 00:48:27,541 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1110 transitions. [2018-04-10 00:48:27,543 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 416 [2018-04-10 00:48:27,543 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:48:27,543 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-10 00:48:27,543 INFO L408 AbstractCegarLoop]: === Iteration 37 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:48:27,544 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-10 00:48:27,549 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:48:27,608 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:48:27,614 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:48:30,011 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-10 00:48:30,011 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:48:33,045 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-10 00:48:33,066 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:48:33,066 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [109, 109] total 162 [2018-04-10 00:48:33,067 INFO L442 AbstractCegarLoop]: Interpolant automaton has 162 states [2018-04-10 00:48:33,067 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 162 interpolants. [2018-04-10 00:48:33,068 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3131, Invalid=22951, Unknown=0, NotChecked=0, Total=26082 [2018-04-10 00:48:33,068 INFO L87 Difference]: Start difference. First operand 883 states and 1110 transitions. Second operand 162 states. [2018-04-10 00:48:40,116 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:48:40,116 INFO L93 Difference]: Finished difference Result 1178 states and 1467 transitions. [2018-04-10 00:48:40,117 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 187 states. [2018-04-10 00:48:40,117 INFO L78 Accepts]: Start accepts. Automaton has 162 states. Word has length 415 [2018-04-10 00:48:40,117 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:48:40,120 INFO L225 Difference]: With dead ends: 1178 [2018-04-10 00:48:40,120 INFO L226 Difference]: Without dead ends: 883 [2018-04-10 00:48:40,125 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 960 GetRequests, 615 SyntacticMatches, 54 SemanticMatches, 291 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24996 ImplicationChecksByTransitivity, 9.7s TimeCoverageRelationStatistics Valid=11548, Invalid=74008, Unknown=0, NotChecked=0, Total=85556 [2018-04-10 00:48:40,125 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-10 00:48:40,145 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-10 00:48:40,146 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-10 00:48:40,148 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1109 transitions. [2018-04-10 00:48:40,148 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1109 transitions. Word has length 415 [2018-04-10 00:48:40,148 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:48:40,148 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1109 transitions. [2018-04-10 00:48:40,148 INFO L460 AbstractCegarLoop]: Interpolant automaton has 162 states. [2018-04-10 00:48:40,148 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1109 transitions. [2018-04-10 00:48:40,152 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 423 [2018-04-10 00:48:40,152 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:48:40,152 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-10 00:48:40,152 INFO L408 AbstractCegarLoop]: === Iteration 38 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:48:40,153 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-10 00:48:40,161 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:48:40,214 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:48:40,219 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:48:42,762 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-10 00:48:42,762 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:48:46,024 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-10 00:48:46,045 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:48:46,045 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [113, 113] total 168 [2018-04-10 00:48:46,046 INFO L442 AbstractCegarLoop]: Interpolant automaton has 168 states [2018-04-10 00:48:46,046 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 168 interpolants. [2018-04-10 00:48:46,047 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3359, Invalid=24697, Unknown=0, NotChecked=0, Total=28056 [2018-04-10 00:48:46,047 INFO L87 Difference]: Start difference. First operand 883 states and 1109 transitions. Second operand 168 states. [2018-04-10 00:48:53,333 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:48:53,334 INFO L93 Difference]: Finished difference Result 1178 states and 1466 transitions. [2018-04-10 00:48:53,334 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 194 states. [2018-04-10 00:48:53,334 INFO L78 Accepts]: Start accepts. Automaton has 168 states. Word has length 422 [2018-04-10 00:48:53,334 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:48:53,337 INFO L225 Difference]: With dead ends: 1178 [2018-04-10 00:48:53,337 INFO L226 Difference]: Without dead ends: 883 [2018-04-10 00:48:53,340 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 979 GetRequests, 621 SyntacticMatches, 56 SemanticMatches, 302 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26943 ImplicationChecksByTransitivity, 10.4s TimeCoverageRelationStatistics Valid=12410, Invalid=79702, Unknown=0, NotChecked=0, Total=92112 [2018-04-10 00:48:53,340 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-10 00:48:53,353 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-10 00:48:53,353 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-10 00:48:53,354 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1108 transitions. [2018-04-10 00:48:53,354 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1108 transitions. Word has length 422 [2018-04-10 00:48:53,354 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:48:53,355 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1108 transitions. [2018-04-10 00:48:53,355 INFO L460 AbstractCegarLoop]: Interpolant automaton has 168 states. [2018-04-10 00:48:53,355 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1108 transitions. [2018-04-10 00:48:53,357 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 430 [2018-04-10 00:48:53,357 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:48:53,357 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-10 00:48:53,357 INFO L408 AbstractCegarLoop]: === Iteration 39 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:48:53,357 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-10 00:48:53,363 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:48:53,411 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:48:53,416 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:48:56,097 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-10 00:48:56,097 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:48:59,544 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-10 00:48:59,565 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:48:59,565 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [117, 117] total 174 [2018-04-10 00:48:59,566 INFO L442 AbstractCegarLoop]: Interpolant automaton has 174 states [2018-04-10 00:48:59,566 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 174 interpolants. [2018-04-10 00:48:59,567 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3595, Invalid=26507, Unknown=0, NotChecked=0, Total=30102 [2018-04-10 00:48:59,567 INFO L87 Difference]: Start difference. First operand 883 states and 1108 transitions. Second operand 174 states. [2018-04-10 00:49:06,957 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:49:06,957 INFO L93 Difference]: Finished difference Result 1178 states and 1465 transitions. [2018-04-10 00:49:06,957 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 201 states. [2018-04-10 00:49:06,957 INFO L78 Accepts]: Start accepts. Automaton has 174 states. Word has length 429 [2018-04-10 00:49:06,958 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:49:06,960 INFO L225 Difference]: With dead ends: 1178 [2018-04-10 00:49:06,960 INFO L226 Difference]: Without dead ends: 883 [2018-04-10 00:49:06,964 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 998 GetRequests, 627 SyntacticMatches, 58 SemanticMatches, 313 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28963 ImplicationChecksByTransitivity, 11.0s TimeCoverageRelationStatistics Valid=13303, Invalid=85607, Unknown=0, NotChecked=0, Total=98910 [2018-04-10 00:49:06,965 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-10 00:49:06,977 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-10 00:49:06,977 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-10 00:49:06,978 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1107 transitions. [2018-04-10 00:49:06,978 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1107 transitions. Word has length 429 [2018-04-10 00:49:06,978 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:49:06,978 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1107 transitions. [2018-04-10 00:49:06,978 INFO L460 AbstractCegarLoop]: Interpolant automaton has 174 states. [2018-04-10 00:49:06,978 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1107 transitions. [2018-04-10 00:49:06,980 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 437 [2018-04-10 00:49:06,981 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:49:06,981 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-10 00:49:06,981 INFO L408 AbstractCegarLoop]: === Iteration 40 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:49:06,981 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-10 00:49:06,987 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:49:07,047 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:49:07,055 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:49:10,037 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-10 00:49:10,037 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:49:13,761 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-10 00:49:13,782 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:49:13,782 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [121, 121] total 180 [2018-04-10 00:49:13,783 INFO L442 AbstractCegarLoop]: Interpolant automaton has 180 states [2018-04-10 00:49:13,783 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 180 interpolants. [2018-04-10 00:49:13,784 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3839, Invalid=28381, Unknown=0, NotChecked=0, Total=32220 [2018-04-10 00:49:13,784 INFO L87 Difference]: Start difference. First operand 883 states and 1107 transitions. Second operand 180 states. [2018-04-10 00:49:21,459 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-10 00:49:21,459 INFO L93 Difference]: Finished difference Result 1178 states and 1464 transitions. [2018-04-10 00:49:21,459 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 208 states. [2018-04-10 00:49:21,459 INFO L78 Accepts]: Start accepts. Automaton has 180 states. Word has length 436 [2018-04-10 00:49:21,460 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-10 00:49:21,463 INFO L225 Difference]: With dead ends: 1178 [2018-04-10 00:49:21,463 INFO L226 Difference]: Without dead ends: 883 [2018-04-10 00:49:21,467 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-10 00:49:21,468 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-10 00:49:21,480 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-10 00:49:21,480 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-10 00:49:21,481 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1106 transitions. [2018-04-10 00:49:21,481 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1106 transitions. Word has length 436 [2018-04-10 00:49:21,481 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-10 00:49:21,481 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1106 transitions. [2018-04-10 00:49:21,481 INFO L460 AbstractCegarLoop]: Interpolant automaton has 180 states. [2018-04-10 00:49:21,481 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1106 transitions. [2018-04-10 00:49:21,483 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 444 [2018-04-10 00:49:21,483 INFO L347 BasicCegarLoop]: Found error trace [2018-04-10 00:49:21,484 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-10 00:49:21,484 INFO L408 AbstractCegarLoop]: === Iteration 41 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-10 00:49:21,484 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-10 00:49:21,490 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-10 00:49:21,539 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-10 00:49:21,545 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-10 00:49:24,650 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-10 00:49:24,650 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-10 00:49:28,634 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-10 00:49:28,655 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-10 00:49:28,655 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [125, 125] total 186 [2018-04-10 00:49:28,655 INFO L442 AbstractCegarLoop]: Interpolant automaton has 186 states [2018-04-10 00:49:28,656 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 186 interpolants. [2018-04-10 00:49:28,657 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=4091, Invalid=30319, Unknown=0, NotChecked=0, Total=34410 [2018-04-10 00:49:28,657 INFO L87 Difference]: Start difference. First operand 883 states and 1106 transitions. Second operand 186 states. Received shutdown request... [2018-04-10 00:49:28,841 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-04-10 00:49:28,841 WARN L519 AbstractCegarLoop]: Verification canceled [2018-04-10 00:49:28,845 WARN L197 ceAbstractionStarter]: Timeout [2018-04-10 00:49:28,845 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 10.04 12:49:28 BasicIcfg [2018-04-10 00:49:28,845 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-04-10 00:49:28,846 INFO L168 Benchmark]: Toolchain (without parser) took 231298.63 ms. Allocated memory was 303.6 MB in the beginning and 881.3 MB in the end (delta: 577.8 MB). Free memory was 247.2 MB in the beginning and 430.4 MB in the end (delta: -183.2 MB). Peak memory consumption was 394.6 MB. Max. memory is 5.3 GB. [2018-04-10 00:49:28,847 INFO L168 Benchmark]: CDTParser took 0.19 ms. Allocated memory is still 303.6 MB. Free memory is still 265.8 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-04-10 00:49:28,847 INFO L168 Benchmark]: CACSL2BoogieTranslator took 208.90 ms. Allocated memory is still 303.6 MB. Free memory was 246.2 MB in the beginning and 237.2 MB in the end (delta: 9.1 MB). Peak memory consumption was 9.1 MB. Max. memory is 5.3 GB. [2018-04-10 00:49:28,847 INFO L168 Benchmark]: Boogie Preprocessor took 26.12 ms. Allocated memory is still 303.6 MB. Free memory was 237.2 MB in the beginning and 236.2 MB in the end (delta: 996.3 kB). Peak memory consumption was 996.3 kB. Max. memory is 5.3 GB. [2018-04-10 00:49:28,847 INFO L168 Benchmark]: RCFGBuilder took 306.82 ms. Allocated memory was 303.6 MB in the beginning and 464.0 MB in the end (delta: 160.4 MB). Free memory was 236.2 MB in the beginning and 432.2 MB in the end (delta: -196.0 MB). Peak memory consumption was 22.4 MB. Max. memory is 5.3 GB. [2018-04-10 00:49:28,848 INFO L168 Benchmark]: IcfgTransformer took 22.47 ms. Allocated memory is still 464.0 MB. Free memory was 432.2 MB in the beginning and 430.9 MB in the end (delta: 1.3 MB). Peak memory consumption was 1.3 MB. Max. memory is 5.3 GB. [2018-04-10 00:49:28,848 INFO L168 Benchmark]: TraceAbstraction took 230729.34 ms. Allocated memory was 464.0 MB in the beginning and 881.3 MB in the end (delta: 417.3 MB). Free memory was 430.9 MB in the beginning and 430.4 MB in the end (delta: 466.3 kB). Peak memory consumption was 417.8 MB. Max. memory is 5.3 GB. [2018-04-10 00:49:28,850 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.19 ms. Allocated memory is still 303.6 MB. Free memory is still 265.8 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 208.90 ms. Allocated memory is still 303.6 MB. Free memory was 246.2 MB in the beginning and 237.2 MB in the end (delta: 9.1 MB). Peak memory consumption was 9.1 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 26.12 ms. Allocated memory is still 303.6 MB. Free memory was 237.2 MB in the beginning and 236.2 MB in the end (delta: 996.3 kB). Peak memory consumption was 996.3 kB. Max. memory is 5.3 GB. * RCFGBuilder took 306.82 ms. Allocated memory was 303.6 MB in the beginning and 464.0 MB in the end (delta: 160.4 MB). Free memory was 236.2 MB in the beginning and 432.2 MB in the end (delta: -196.0 MB). Peak memory consumption was 22.4 MB. Max. memory is 5.3 GB. * IcfgTransformer took 22.47 ms. Allocated memory is still 464.0 MB. Free memory was 432.2 MB in the beginning and 430.9 MB in the end (delta: 1.3 MB). Peak memory consumption was 1.3 MB. Max. memory is 5.3 GB. * TraceAbstraction took 230729.34 ms. Allocated memory was 464.0 MB in the beginning and 881.3 MB in the end (delta: 417.3 MB). Free memory was 430.9 MB in the beginning and 430.4 MB in the end (delta: 466.3 kB). Peak memory consumption was 417.8 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 constructing difference of abstraction (883states) and interpolant automaton (currently 10 states, 186 states before enhancement), while PredicateComparison was comparing new predicate (quantifier-free) to 191 known predicates. - TimeoutResultAtElement [Line: 19]: Timeout (TraceAbstraction) Unable to prove that array index is always in bounds (line 19). Cancelled while BasicCegarLoop was constructing difference of abstraction (883states) and interpolant automaton (currently 10 states, 186 states before enhancement), while PredicateComparison was comparing new predicate (quantifier-free) to 191 known predicates. - TimeoutResultAtElement [Line: 24]: Timeout (TraceAbstraction) Unable to prove that array index is always in bounds (line 24). Cancelled while BasicCegarLoop was constructing difference of abstraction (883states) and interpolant automaton (currently 10 states, 186 states before enhancement), while PredicateComparison was comparing new predicate (quantifier-free) to 191 known predicates. - TimeoutResultAtElement [Line: 17]: Timeout (TraceAbstraction) Unable to prove that array index is always in bounds (line 17). Cancelled while BasicCegarLoop was constructing difference of abstraction (883states) and interpolant automaton (currently 10 states, 186 states before enhancement), while PredicateComparison was comparing new predicate (quantifier-free) to 191 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 6 procedures, 51 locations, 4 error locations. TIMEOUT Result, 230.6s OverallTime, 41 OverallIterations, 32 TraceHistogramMax, 136.0s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 5173 SDtfs, 14885 SDslu, 100557 SDs, 0 SdLazy, 100064 SolverSat, 10526 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 30.7s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 20639 GetRequests, 13763 SyntacticMatches, 992 SemanticMatches, 5883 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 358981 ImplicationChecksByTransitivity, 178.5s 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.5s AutomataMinimizationTime, 40 MinimizatonAttempts, 135 StatesRemovedByMinimization, 12 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.2s SsaConstructionTime, 1.1s SatisfiabilityAnalysisTime, 91.0s InterpolantComputationTime, 9031 NumberOfCodeBlocks, 9031 NumberOfCodeBlocksAsserted, 41 NumberOfCheckSat, 17980 ConstructedInterpolants, 0 QuantifiedInterpolants, 22473196 SizeOfPredicates, 2150 NumberOfNonLiveVariables, 12480 ConjunctsInSsa, 2346 ConjunctsInUnsatCore, 82 InterpolantComputations, 4 PerfectInterpolantSequences, 116686/192096 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-10_00-49-28-860.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-10_00-49-28-860.csv Completed graceful shutdown