java -Xmx6000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data ./data --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/ai/eq-bench/svcomp-DerefFreeMemtrack-32bit-Automizer_Fixed_noBitfields+AI_EQ_SS.epf -i ../../../trunk/examples/svcomp/array-examples/sanfoundry_24_false-valid-deref.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-453dfda-m [2018-04-09 20:40:50,976 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-04-09 20:40:50,978 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-04-09 20:40:50,991 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-04-09 20:40:50,991 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-04-09 20:40:50,992 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-04-09 20:40:50,992 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-04-09 20:40:50,994 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-04-09 20:40:50,996 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-04-09 20:40:50,997 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-04-09 20:40:50,998 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-04-09 20:40:50,998 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-04-09 20:40:50,999 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-04-09 20:40:51,000 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-04-09 20:40:51,001 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-04-09 20:40:51,003 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-04-09 20:40:51,005 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-04-09 20:40:51,007 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-04-09 20:40:51,008 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-04-09 20:40:51,010 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-04-09 20:40:51,012 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-04-09 20:40:51,012 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-04-09 20:40:51,012 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-04-09 20:40:51,013 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-04-09 20:40:51,014 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-04-09 20:40:51,016 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-04-09 20:40:51,016 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-04-09 20:40:51,017 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-04-09 20:40:51,017 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-04-09 20:40:51,018 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-04-09 20:40:51,018 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-04-09 20:40:51,019 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/ai/eq-bench/svcomp-DerefFreeMemtrack-32bit-Automizer_Fixed_noBitfields+AI_EQ_SS.epf [2018-04-09 20:40:51,042 INFO L110 SettingsManager]: Loading preferences was successful [2018-04-09 20:40:51,043 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-04-09 20:40:51,043 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-04-09 20:40:51,043 INFO L133 SettingsManager]: * ultimate.logging.details=de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation=DEBUG; [2018-04-09 20:40:51,044 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-04-09 20:40:51,044 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-04-09 20:40:51,044 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-04-09 20:40:51,044 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-04-09 20:40:51,044 INFO L133 SettingsManager]: * Parallel states before merging=1 [2018-04-09 20:40:51,045 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-04-09 20:40:51,045 INFO L131 SettingsManager]: Preferences of LTL2Aut differ from their defaults: [2018-04-09 20:40:51,045 INFO L133 SettingsManager]: * Property to check=[] a a: x > 42 [2018-04-09 20:40:51,045 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-04-09 20:40:51,045 INFO L133 SettingsManager]: * sizeof long=4 [2018-04-09 20:40:51,045 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-04-09 20:40:51,046 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-04-09 20:40:51,046 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-04-09 20:40:51,046 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-04-09 20:40:51,046 INFO L133 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2018-04-09 20:40:51,046 INFO L133 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2018-04-09 20:40:51,046 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-04-09 20:40:51,047 INFO L133 SettingsManager]: * sizeof long double=12 [2018-04-09 20:40:51,047 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-04-09 20:40:51,047 INFO L133 SettingsManager]: * Size of a code block=SingleStatement [2018-04-09 20:40:51,047 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-04-09 20:40:51,047 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-04-09 20:40:51,048 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-04-09 20:40:51,048 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-04-09 20:40:51,048 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-04-09 20:40:51,048 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-04-09 20:40:51,048 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-04-09 20:40:51,048 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-04-09 20:40:51,048 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-09 20:40:51,049 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-04-09 20:40:51,049 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-04-09 20:40:51,050 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-04-09 20:40:51,050 INFO L131 SettingsManager]: Preferences of Boogie Printer differ from their defaults: [2018-04-09 20:40:51,050 INFO L133 SettingsManager]: * Dump path:=C:\Users\alex\AppData\Local\Temp\ [2018-04-09 20:40:51,081 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-04-09 20:40:51,091 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully (re)initialized [2018-04-09 20:40:51,094 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-04-09 20:40:51,096 INFO L271 PluginConnector]: Initializing CDTParser... [2018-04-09 20:40:51,096 INFO L276 PluginConnector]: CDTParser initialized [2018-04-09 20:40:51,097 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-09 20:40:51,437 INFO L225 CDTParser]: Created temporary CDT project at /storage/ultimate/releaseScripts/default/UAutomizer-linux/data/FLAGf8859f177 [2018-04-09 20:40:51,544 INFO L287 CDTParser]: IsIndexed: true [2018-04-09 20:40:51,545 INFO L288 CDTParser]: Found 1 translation units. [2018-04-09 20:40:51,545 INFO L168 CDTParser]: Scanning sanfoundry_24_false-valid-deref.i [2018-04-09 20:40:51,546 INFO L210 ultiparseSymbolTable]: Include resolver: [2018-04-09 20:40:51,547 INFO L215 ultiparseSymbolTable]: [2018-04-09 20:40:51,547 INFO L218 ultiparseSymbolTable]: Function table: [2018-04-09 20:40:51,547 INFO L221 ultiparseSymbolTable]: Function definition of __U_MULTI_fsanfoundry____false_valid_deref_i__printOdd ('printOdd') in sanfoundry_24_false-valid-deref.i [2018-04-09 20:40:51,547 INFO L221 ultiparseSymbolTable]: Function definition of null ('main') in sanfoundry_24_false-valid-deref.i [2018-04-09 20:40:51,547 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-09 20:40:51,547 INFO L221 ultiparseSymbolTable]: Function definition of __U_MULTI_fsanfoundry____false_valid_deref_i__printEven ('printEven') in sanfoundry_24_false-valid-deref.i [2018-04-09 20:40:51,547 INFO L227 ultiparseSymbolTable]: Global variable table: [2018-04-09 20:40:51,547 INFO L233 ultiparseSymbolTable]: [2018-04-09 20:40:51,561 INFO L330 CDTParser]: Deleted temporary CDT project at /storage/ultimate/releaseScripts/default/UAutomizer-linux/data/FLAGf8859f177 [2018-04-09 20:40:51,566 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-04-09 20:40:51,567 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-04-09 20:40:51,568 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-04-09 20:40:51,568 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-04-09 20:40:51,574 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-04-09 20:40:51,575 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.04 08:40:51" (1/1) ... [2018-04-09 20:40:51,577 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2cd40a0e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.04 08:40:51, skipping insertion in model container [2018-04-09 20:40:51,577 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.04 08:40:51" (1/1) ... [2018-04-09 20:40:51,590 INFO L167 Dispatcher]: Using SV-COMP mode [2018-04-09 20:40:51,602 INFO L167 Dispatcher]: Using SV-COMP mode [2018-04-09 20:40:51,742 INFO L175 PostProcessor]: Settings: Checked method=main [2018-04-09 20:40:51,757 INFO L175 PostProcessor]: Settings: Checked method=main [2018-04-09 20:40:51,761 INFO L100 SccComputation]: Graph consists of 0 InCaSumBalls and 8 non ball SCCs. Number of states in SCCs 8. [2018-04-09 20:40:51,769 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.04 08:40:51 WrapperNode [2018-04-09 20:40:51,769 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-04-09 20:40:51,769 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-04-09 20:40:51,769 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-04-09 20:40:51,769 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-04-09 20:40:51,779 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.04 08:40:51" (1/1) ... [2018-04-09 20:40:51,779 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.04 08:40:51" (1/1) ... [2018-04-09 20:40:51,787 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.04 08:40:51" (1/1) ... [2018-04-09 20:40:51,787 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.04 08:40:51" (1/1) ... [2018-04-09 20:40:51,790 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.04 08:40:51" (1/1) ... [2018-04-09 20:40:51,795 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.04 08:40:51" (1/1) ... [2018-04-09 20:40:51,797 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.04 08:40:51" (1/1) ... [2018-04-09 20:40:51,799 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-04-09 20:40:51,799 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-04-09 20:40:51,799 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-04-09 20:40:51,800 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-04-09 20:40:51,801 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.04 08:40:51" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-04-09 20:40:51,864 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-04-09 20:40:51,864 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-04-09 20:40:51,864 INFO L136 BoogieDeclarations]: Found implementation of procedure __U_MULTI_fsanfoundry____false_valid_deref_i____VERIFIER_assert [2018-04-09 20:40:51,864 INFO L136 BoogieDeclarations]: Found implementation of procedure __U_MULTI_fsanfoundry____false_valid_deref_i__printEven [2018-04-09 20:40:51,864 INFO L136 BoogieDeclarations]: Found implementation of procedure __U_MULTI_fsanfoundry____false_valid_deref_i__printOdd [2018-04-09 20:40:51,865 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-04-09 20:40:51,865 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_error [2018-04-09 20:40:51,865 INFO L128 BoogieDeclarations]: Found specification of procedure __U_MULTI_fsanfoundry____false_valid_deref_i____VERIFIER_assert [2018-04-09 20:40:51,865 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-04-09 20:40:51,865 INFO L128 BoogieDeclarations]: Found specification of procedure __U_MULTI_fsanfoundry____false_valid_deref_i__printEven [2018-04-09 20:40:51,865 INFO L128 BoogieDeclarations]: Found specification of procedure __U_MULTI_fsanfoundry____false_valid_deref_i__printOdd [2018-04-09 20:40:51,865 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-04-09 20:40:51,865 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-04-09 20:40:51,865 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-04-09 20:40:52,058 INFO L259 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-04-09 20:40:52,058 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.04 08:40:52 BoogieIcfgContainer [2018-04-09 20:40:52,059 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-04-09 20:40:52,059 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-04-09 20:40:52,060 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-04-09 20:40:52,063 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-04-09 20:40:52,063 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 09.04 08:40:51" (1/3) ... [2018-04-09 20:40:52,064 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@612d96b7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.04 08:40:52, skipping insertion in model container [2018-04-09 20:40:52,064 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.04 08:40:51" (2/3) ... [2018-04-09 20:40:52,064 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@612d96b7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.04 08:40:52, skipping insertion in model container [2018-04-09 20:40:52,064 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.04 08:40:52" (3/3) ... [2018-04-09 20:40:52,066 INFO L107 eAbstractionObserver]: Analyzing ICFG sanfoundry_24_false-valid-deref.i [2018-04-09 20:40:52,074 INFO L131 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-04-09 20:40:52,079 INFO L143 ceAbstractionStarter]: Appying trace abstraction to program that has 4 error locations. [2018-04-09 20:40:52,119 INFO L128 ementStrategyFactory]: Using default assertion order modulation [2018-04-09 20:40:52,120 INFO L369 AbstractCegarLoop]: Interprodecural is true [2018-04-09 20:40:52,120 INFO L370 AbstractCegarLoop]: Hoare is true [2018-04-09 20:40:52,120 INFO L371 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-04-09 20:40:52,121 INFO L372 AbstractCegarLoop]: Backedges is TWOTRACK [2018-04-09 20:40:52,121 INFO L373 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-04-09 20:40:52,121 INFO L374 AbstractCegarLoop]: Difference is false [2018-04-09 20:40:52,121 INFO L375 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-04-09 20:40:52,121 INFO L380 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-04-09 20:40:52,122 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-04-09 20:40:52,137 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states. [2018-04-09 20:40:52,141 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2018-04-09 20:40:52,141 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:40:52,142 INFO L355 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-04-09 20:40:52,142 INFO L408 AbstractCegarLoop]: === Iteration 1 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:40:52,147 INFO L82 PathProgramCache]: Analyzing trace with hash 1687177289, now seen corresponding path program 1 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-09 20:40:52,160 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:40:52,177 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:40:52,183 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:40:52,207 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-09 20:40:52,207 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:40:52,234 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-04-09 20:40:52,256 INFO L320 seRefinementStrategy]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2018-04-09 20:40:52,256 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2, 2] imperfect sequences [] total 3 [2018-04-09 20:40:52,258 INFO L442 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-04-09 20:40:52,267 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-04-09 20:40:52,268 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-04-09 20:40:52,269 INFO L87 Difference]: Start difference. First operand 51 states. Second operand 4 states. [2018-04-09 20:40:52,370 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:40:52,371 INFO L93 Difference]: Finished difference Result 112 states and 144 transitions. [2018-04-09 20:40:52,371 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-04-09 20:40:52,372 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 13 [2018-04-09 20:40:52,372 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:40:52,381 INFO L225 Difference]: With dead ends: 112 [2018-04-09 20:40:52,381 INFO L226 Difference]: Without dead ends: 62 [2018-04-09 20:40:52,385 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-09 20:40:52,399 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2018-04-09 20:40:52,420 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 55. [2018-04-09 20:40:52,421 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 55 states. [2018-04-09 20:40:52,423 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 62 transitions. [2018-04-09 20:40:52,425 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 62 transitions. Word has length 13 [2018-04-09 20:40:52,425 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:40:52,425 INFO L459 AbstractCegarLoop]: Abstraction has 55 states and 62 transitions. [2018-04-09 20:40:52,425 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-04-09 20:40:52,426 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 62 transitions. [2018-04-09 20:40:52,427 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-04-09 20:40:52,428 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:40:52,428 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-09 20:40:52,428 INFO L408 AbstractCegarLoop]: === Iteration 2 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:40:52,428 INFO L82 PathProgramCache]: Analyzing trace with hash 2045146350, now seen corresponding path program 1 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-09 20:40:52,454 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:40:52,464 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:40:52,466 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:40:52,492 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-09 20:40:52,492 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:40:52,586 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-09 20:40:52,619 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:40:52,620 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 7 [2018-04-09 20:40:52,622 INFO L442 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-04-09 20:40:52,622 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-04-09 20:40:52,622 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-04-09 20:40:52,623 INFO L87 Difference]: Start difference. First operand 55 states and 62 transitions. Second operand 8 states. [2018-04-09 20:40:52,818 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:40:52,818 INFO L93 Difference]: Finished difference Result 84 states and 101 transitions. [2018-04-09 20:40:52,819 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-04-09 20:40:52,819 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 20 [2018-04-09 20:40:52,819 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:40:52,822 INFO L225 Difference]: With dead ends: 84 [2018-04-09 20:40:52,822 INFO L226 Difference]: Without dead ends: 82 [2018-04-09 20:40:52,824 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-09 20:40:52,825 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2018-04-09 20:40:52,834 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 73. [2018-04-09 20:40:52,834 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 73 states. [2018-04-09 20:40:52,836 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 86 transitions. [2018-04-09 20:40:52,836 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 86 transitions. Word has length 20 [2018-04-09 20:40:52,837 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:40:52,837 INFO L459 AbstractCegarLoop]: Abstraction has 73 states and 86 transitions. [2018-04-09 20:40:52,837 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-04-09 20:40:52,837 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 86 transitions. [2018-04-09 20:40:52,838 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2018-04-09 20:40:52,838 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:40:52,838 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-09 20:40:52,839 INFO L408 AbstractCegarLoop]: === Iteration 3 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:40:52,839 INFO L82 PathProgramCache]: Analyzing trace with hash -1745161864, now seen corresponding path program 1 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-09 20:40:52,845 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:40:52,852 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:40:52,854 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:40:52,885 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-04-09 20:40:52,885 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:40:52,909 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-04-09 20:40:52,929 INFO L320 seRefinementStrategy]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2018-04-09 20:40:52,929 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5, 5] imperfect sequences [] total 6 [2018-04-09 20:40:52,930 INFO L442 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-04-09 20:40:52,930 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-04-09 20:40:52,930 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2018-04-09 20:40:52,930 INFO L87 Difference]: Start difference. First operand 73 states and 86 transitions. Second operand 6 states. [2018-04-09 20:40:53,034 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:40:53,035 INFO L93 Difference]: Finished difference Result 101 states and 117 transitions. [2018-04-09 20:40:53,035 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-04-09 20:40:53,035 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 23 [2018-04-09 20:40:53,036 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:40:53,037 INFO L225 Difference]: With dead ends: 101 [2018-04-09 20:40:53,037 INFO L226 Difference]: Without dead ends: 76 [2018-04-09 20:40:53,038 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-09 20:40:53,038 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2018-04-09 20:40:53,045 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 73. [2018-04-09 20:40:53,046 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 73 states. [2018-04-09 20:40:53,047 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 85 transitions. [2018-04-09 20:40:53,048 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 85 transitions. Word has length 23 [2018-04-09 20:40:53,048 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:40:53,048 INFO L459 AbstractCegarLoop]: Abstraction has 73 states and 85 transitions. [2018-04-09 20:40:53,048 INFO L460 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-04-09 20:40:53,049 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 85 transitions. [2018-04-09 20:40:53,050 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2018-04-09 20:40:53,050 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:40:53,050 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-09 20:40:53,050 INFO L408 AbstractCegarLoop]: === Iteration 4 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:40:53,051 INFO L82 PathProgramCache]: Analyzing trace with hash -1074703395, now seen corresponding path program 1 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-09 20:40:53,061 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:40:53,074 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:40:53,077 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:40:53,137 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-09 20:40:53,138 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:40:53,231 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-09 20:40:53,264 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:40:53,264 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 12 [2018-04-09 20:40:53,265 INFO L442 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-04-09 20:40:53,265 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-04-09 20:40:53,265 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=101, Unknown=0, NotChecked=0, Total=132 [2018-04-09 20:40:53,265 INFO L87 Difference]: Start difference. First operand 73 states and 85 transitions. Second operand 12 states. [2018-04-09 20:40:53,463 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:40:53,463 INFO L93 Difference]: Finished difference Result 107 states and 123 transitions. [2018-04-09 20:40:53,464 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-04-09 20:40:53,464 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 30 [2018-04-09 20:40:53,464 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:40:53,465 INFO L225 Difference]: With dead ends: 107 [2018-04-09 20:40:53,465 INFO L226 Difference]: Without dead ends: 76 [2018-04-09 20:40:53,465 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-09 20:40:53,466 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2018-04-09 20:40:53,471 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 73. [2018-04-09 20:40:53,471 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 73 states. [2018-04-09 20:40:53,472 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 84 transitions. [2018-04-09 20:40:53,472 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 84 transitions. Word has length 30 [2018-04-09 20:40:53,472 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:40:53,472 INFO L459 AbstractCegarLoop]: Abstraction has 73 states and 84 transitions. [2018-04-09 20:40:53,472 INFO L460 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-04-09 20:40:53,472 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 84 transitions. [2018-04-09 20:40:53,473 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2018-04-09 20:40:53,473 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:40:53,473 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-09 20:40:53,473 INFO L408 AbstractCegarLoop]: === Iteration 5 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:40:53,473 INFO L82 PathProgramCache]: Analyzing trace with hash 657284238, 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-09 20:40:53,482 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:40:53,490 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:40:53,492 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:40:53,620 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-09 20:40:53,620 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:40:53,732 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-09 20:40:53,765 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:40:53,765 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 15 [2018-04-09 20:40:53,766 INFO L442 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-04-09 20:40:53,766 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-04-09 20:40:53,766 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=186, Unknown=0, NotChecked=0, Total=240 [2018-04-09 20:40:53,767 INFO L87 Difference]: Start difference. First operand 73 states and 84 transitions. Second operand 16 states. [2018-04-09 20:40:54,232 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:40:54,232 INFO L93 Difference]: Finished difference Result 122 states and 153 transitions. [2018-04-09 20:40:54,232 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-04-09 20:40:54,232 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 34 [2018-04-09 20:40:54,233 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:40:54,234 INFO L225 Difference]: With dead ends: 122 [2018-04-09 20:40:54,234 INFO L226 Difference]: Without dead ends: 120 [2018-04-09 20:40:54,235 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-09 20:40:54,236 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 120 states. [2018-04-09 20:40:54,246 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 120 to 109. [2018-04-09 20:40:54,246 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 109 states. [2018-04-09 20:40:54,248 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 132 transitions. [2018-04-09 20:40:54,249 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 132 transitions. Word has length 34 [2018-04-09 20:40:54,249 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:40:54,249 INFO L459 AbstractCegarLoop]: Abstraction has 109 states and 132 transitions. [2018-04-09 20:40:54,249 INFO L460 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-04-09 20:40:54,250 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 132 transitions. [2018-04-09 20:40:54,251 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2018-04-09 20:40:54,251 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:40:54,251 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-09 20:40:54,252 INFO L408 AbstractCegarLoop]: === Iteration 6 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:40:54,252 INFO L82 PathProgramCache]: Analyzing trace with hash 104818136, now seen corresponding path program 2 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-09 20:40:54,261 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:40:54,268 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:40:54,269 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:40:54,278 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-09 20:40:54,278 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:40:54,308 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-09 20:40:54,329 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:40:54,329 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 7 [2018-04-09 20:40:54,329 INFO L442 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-04-09 20:40:54,330 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-04-09 20:40:54,330 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-04-09 20:40:54,330 INFO L87 Difference]: Start difference. First operand 109 states and 132 transitions. Second operand 8 states. [2018-04-09 20:40:54,404 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:40:54,405 INFO L93 Difference]: Finished difference Result 132 states and 162 transitions. [2018-04-09 20:40:54,405 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-04-09 20:40:54,405 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 37 [2018-04-09 20:40:54,405 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:40:54,406 INFO L225 Difference]: With dead ends: 132 [2018-04-09 20:40:54,406 INFO L226 Difference]: Without dead ends: 130 [2018-04-09 20:40:54,406 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-09 20:40:54,407 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2018-04-09 20:40:54,414 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 127. [2018-04-09 20:40:54,414 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 127 states. [2018-04-09 20:40:54,415 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 154 transitions. [2018-04-09 20:40:54,415 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 154 transitions. Word has length 37 [2018-04-09 20:40:54,415 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:40:54,415 INFO L459 AbstractCegarLoop]: Abstraction has 127 states and 154 transitions. [2018-04-09 20:40:54,415 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-04-09 20:40:54,416 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 154 transitions. [2018-04-09 20:40:54,417 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2018-04-09 20:40:54,417 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:40:54,417 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-09 20:40:54,417 INFO L408 AbstractCegarLoop]: === Iteration 7 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:40:54,417 INFO L82 PathProgramCache]: Analyzing trace with hash -1386394728, 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-09 20:40:54,425 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:40:54,434 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:40:54,436 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:40:54,494 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-09 20:40:54,494 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:40:54,558 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-09 20:40:54,579 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:40:54,579 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 18 [2018-04-09 20:40:54,579 INFO L442 AbstractCegarLoop]: Interpolant automaton has 18 states [2018-04-09 20:40:54,580 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2018-04-09 20:40:54,580 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=59, Invalid=247, Unknown=0, NotChecked=0, Total=306 [2018-04-09 20:40:54,580 INFO L87 Difference]: Start difference. First operand 127 states and 154 transitions. Second operand 18 states. [2018-04-09 20:40:54,811 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:40:54,811 INFO L93 Difference]: Finished difference Result 170 states and 203 transitions. [2018-04-09 20:40:54,812 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-04-09 20:40:54,812 INFO L78 Accepts]: Start accepts. Automaton has 18 states. Word has length 51 [2018-04-09 20:40:54,812 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:40:54,813 INFO L225 Difference]: With dead ends: 170 [2018-04-09 20:40:54,814 INFO L226 Difference]: Without dead ends: 127 [2018-04-09 20:40:54,815 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-09 20:40:54,815 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states. [2018-04-09 20:40:54,825 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 127. [2018-04-09 20:40:54,825 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 127 states. [2018-04-09 20:40:54,827 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 153 transitions. [2018-04-09 20:40:54,827 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 153 transitions. Word has length 51 [2018-04-09 20:40:54,827 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:40:54,827 INFO L459 AbstractCegarLoop]: Abstraction has 127 states and 153 transitions. [2018-04-09 20:40:54,827 INFO L460 AbstractCegarLoop]: Interpolant automaton has 18 states. [2018-04-09 20:40:54,828 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 153 transitions. [2018-04-09 20:40:54,830 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2018-04-09 20:40:54,830 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:40:54,830 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-09 20:40:54,831 INFO L408 AbstractCegarLoop]: === Iteration 8 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:40:54,831 INFO L82 PathProgramCache]: Analyzing trace with hash -900606851, 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-09 20:40:54,840 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:40:54,854 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:40:54,857 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:40:55,017 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-09 20:40:55,018 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:40:55,123 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-09 20:40:55,144 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:40:55,144 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17] total 24 [2018-04-09 20:40:55,145 INFO L442 AbstractCegarLoop]: Interpolant automaton has 24 states [2018-04-09 20:40:55,145 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2018-04-09 20:40:55,145 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=95, Invalid=457, Unknown=0, NotChecked=0, Total=552 [2018-04-09 20:40:55,145 INFO L87 Difference]: Start difference. First operand 127 states and 153 transitions. Second operand 24 states. [2018-04-09 20:40:55,443 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:40:55,443 INFO L93 Difference]: Finished difference Result 176 states and 209 transitions. [2018-04-09 20:40:55,443 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2018-04-09 20:40:55,444 INFO L78 Accepts]: Start accepts. Automaton has 24 states. Word has length 58 [2018-04-09 20:40:55,444 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:40:55,445 INFO L225 Difference]: With dead ends: 176 [2018-04-09 20:40:55,445 INFO L226 Difference]: Without dead ends: 127 [2018-04-09 20:40:55,446 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-09 20:40:55,447 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states. [2018-04-09 20:40:55,456 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 127. [2018-04-09 20:40:55,456 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 127 states. [2018-04-09 20:40:55,457 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 152 transitions. [2018-04-09 20:40:55,458 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 152 transitions. Word has length 58 [2018-04-09 20:40:55,458 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:40:55,458 INFO L459 AbstractCegarLoop]: Abstraction has 127 states and 152 transitions. [2018-04-09 20:40:55,458 INFO L460 AbstractCegarLoop]: Interpolant automaton has 24 states. [2018-04-09 20:40:55,458 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 152 transitions. [2018-04-09 20:40:55,460 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2018-04-09 20:40:55,460 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:40:55,461 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-09 20:40:55,461 INFO L408 AbstractCegarLoop]: === Iteration 9 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:40:55,461 INFO L82 PathProgramCache]: Analyzing trace with hash -648305714, 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-09 20:40:55,474 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:40:55,488 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:40:55,492 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:40:55,701 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-09 20:40:55,701 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:40:55,973 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-09 20:40:55,993 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:40:55,993 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 31 [2018-04-09 20:40:55,994 INFO L442 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-04-09 20:40:55,994 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-04-09 20:40:55,994 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=174, Invalid=818, Unknown=0, NotChecked=0, Total=992 [2018-04-09 20:40:55,994 INFO L87 Difference]: Start difference. First operand 127 states and 152 transitions. Second operand 32 states. [2018-04-09 20:40:57,228 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:40:57,228 INFO L93 Difference]: Finished difference Result 215 states and 279 transitions. [2018-04-09 20:40:57,257 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2018-04-09 20:40:57,257 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 62 [2018-04-09 20:40:57,257 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:40:57,259 INFO L225 Difference]: With dead ends: 215 [2018-04-09 20:40:57,259 INFO L226 Difference]: Without dead ends: 213 [2018-04-09 20:40:57,260 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 157 GetRequests, 93 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-09 20:40:57,260 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 213 states. [2018-04-09 20:40:57,270 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 213 to 199. [2018-04-09 20:40:57,270 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 199 states. [2018-04-09 20:40:57,271 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 199 states to 199 states and 248 transitions. [2018-04-09 20:40:57,271 INFO L78 Accepts]: Start accepts. Automaton has 199 states and 248 transitions. Word has length 62 [2018-04-09 20:40:57,271 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:40:57,272 INFO L459 AbstractCegarLoop]: Abstraction has 199 states and 248 transitions. [2018-04-09 20:40:57,272 INFO L460 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-04-09 20:40:57,272 INFO L276 IsEmpty]: Start isEmpty. Operand 199 states and 248 transitions. [2018-04-09 20:40:57,273 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2018-04-09 20:40:57,273 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:40:57,273 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-09 20:40:57,273 INFO L408 AbstractCegarLoop]: === Iteration 10 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:40:57,273 INFO L82 PathProgramCache]: Analyzing trace with hash 2132897784, now seen corresponding path program 5 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-09 20:40:57,279 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:40:57,290 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:40:57,293 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:40:57,325 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-09 20:40:57,325 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:40:57,393 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-09 20:40:57,415 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:40:57,415 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 15 [2018-04-09 20:40:57,416 INFO L442 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-04-09 20:40:57,416 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-04-09 20:40:57,416 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=186, Unknown=0, NotChecked=0, Total=240 [2018-04-09 20:40:57,416 INFO L87 Difference]: Start difference. First operand 199 states and 248 transitions. Second operand 16 states. [2018-04-09 20:40:57,726 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:40:57,726 INFO L93 Difference]: Finished difference Result 240 states and 304 transitions. [2018-04-09 20:40:57,726 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-04-09 20:40:57,727 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 65 [2018-04-09 20:40:57,727 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:40:57,728 INFO L225 Difference]: With dead ends: 240 [2018-04-09 20:40:57,728 INFO L226 Difference]: Without dead ends: 238 [2018-04-09 20:40:57,729 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-09 20:40:57,729 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 238 states. [2018-04-09 20:40:57,737 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 238 to 235. [2018-04-09 20:40:57,738 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 235 states. [2018-04-09 20:40:57,739 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 292 transitions. [2018-04-09 20:40:57,739 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 292 transitions. Word has length 65 [2018-04-09 20:40:57,740 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:40:57,740 INFO L459 AbstractCegarLoop]: Abstraction has 235 states and 292 transitions. [2018-04-09 20:40:57,740 INFO L460 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-04-09 20:40:57,740 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 292 transitions. [2018-04-09 20:40:57,741 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2018-04-09 20:40:57,741 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:40:57,741 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-09 20:40:57,741 INFO L408 AbstractCegarLoop]: === Iteration 11 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:40:57,742 INFO L82 PathProgramCache]: Analyzing trace with hash 1126284152, 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-09 20:40:57,748 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:40:57,761 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:40:57,763 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:40:57,902 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-09 20:40:57,902 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:40:58,117 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-09 20:40:58,139 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:40:58,139 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21] total 30 [2018-04-09 20:40:58,139 INFO L442 AbstractCegarLoop]: Interpolant automaton has 30 states [2018-04-09 20:40:58,140 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2018-04-09 20:40:58,140 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=139, Invalid=731, Unknown=0, NotChecked=0, Total=870 [2018-04-09 20:40:58,140 INFO L87 Difference]: Start difference. First operand 235 states and 292 transitions. Second operand 30 states. [2018-04-09 20:40:58,572 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:40:58,572 INFO L93 Difference]: Finished difference Result 314 states and 385 transitions. [2018-04-09 20:40:58,573 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-04-09 20:40:58,573 INFO L78 Accepts]: Start accepts. Automaton has 30 states. Word has length 93 [2018-04-09 20:40:58,573 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:40:58,574 INFO L225 Difference]: With dead ends: 314 [2018-04-09 20:40:58,574 INFO L226 Difference]: Without dead ends: 235 [2018-04-09 20:40:58,575 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-09 20:40:58,575 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 235 states. [2018-04-09 20:40:58,585 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 235 to 235. [2018-04-09 20:40:58,585 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 235 states. [2018-04-09 20:40:58,587 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 291 transitions. [2018-04-09 20:40:58,587 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 291 transitions. Word has length 93 [2018-04-09 20:40:58,588 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:40:58,588 INFO L459 AbstractCegarLoop]: Abstraction has 235 states and 291 transitions. [2018-04-09 20:40:58,588 INFO L460 AbstractCegarLoop]: Interpolant automaton has 30 states. [2018-04-09 20:40:58,588 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 291 transitions. [2018-04-09 20:40:58,590 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 101 [2018-04-09 20:40:58,590 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:40:58,590 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-09 20:40:58,590 INFO L408 AbstractCegarLoop]: === Iteration 12 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:40:58,590 INFO L82 PathProgramCache]: Analyzing trace with hash -982231523, 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-09 20:40:58,598 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:40:58,612 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:40:58,614 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:40:58,782 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-09 20:40:58,782 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:40:58,957 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-09 20:40:58,978 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:40:58,978 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 25] total 36 [2018-04-09 20:40:58,978 INFO L442 AbstractCegarLoop]: Interpolant automaton has 36 states [2018-04-09 20:40:58,979 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2018-04-09 20:40:58,979 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=191, Invalid=1069, Unknown=0, NotChecked=0, Total=1260 [2018-04-09 20:40:58,979 INFO L87 Difference]: Start difference. First operand 235 states and 291 transitions. Second operand 36 states. [2018-04-09 20:40:59,522 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:40:59,522 INFO L93 Difference]: Finished difference Result 314 states and 384 transitions. [2018-04-09 20:40:59,523 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2018-04-09 20:40:59,523 INFO L78 Accepts]: Start accepts. Automaton has 36 states. Word has length 100 [2018-04-09 20:40:59,523 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:40:59,524 INFO L225 Difference]: With dead ends: 314 [2018-04-09 20:40:59,524 INFO L226 Difference]: Without dead ends: 235 [2018-04-09 20:40:59,526 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 225 GetRequests, 153 SyntacticMatches, 12 SemanticMatches, 60 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 972 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=607, Invalid=3175, Unknown=0, NotChecked=0, Total=3782 [2018-04-09 20:40:59,526 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 235 states. [2018-04-09 20:40:59,534 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 235 to 235. [2018-04-09 20:40:59,534 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 235 states. [2018-04-09 20:40:59,536 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 290 transitions. [2018-04-09 20:40:59,536 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 290 transitions. Word has length 100 [2018-04-09 20:40:59,536 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:40:59,536 INFO L459 AbstractCegarLoop]: Abstraction has 235 states and 290 transitions. [2018-04-09 20:40:59,536 INFO L460 AbstractCegarLoop]: Interpolant automaton has 36 states. [2018-04-09 20:40:59,536 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 290 transitions. [2018-04-09 20:40:59,538 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2018-04-09 20:40:59,538 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:40:59,538 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-09 20:40:59,538 INFO L408 AbstractCegarLoop]: === Iteration 13 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:40:59,538 INFO L82 PathProgramCache]: Analyzing trace with hash -872257576, 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-09 20:40:59,544 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:40:59,561 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:40:59,563 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:40:59,969 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-09 20:40:59,970 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:41:00,198 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-09 20:41:00,218 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:41:00,219 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [29, 29] total 42 [2018-04-09 20:41:00,219 INFO L442 AbstractCegarLoop]: Interpolant automaton has 42 states [2018-04-09 20:41:00,219 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 42 interpolants. [2018-04-09 20:41:00,220 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=251, Invalid=1471, Unknown=0, NotChecked=0, Total=1722 [2018-04-09 20:41:00,220 INFO L87 Difference]: Start difference. First operand 235 states and 290 transitions. Second operand 42 states. [2018-04-09 20:41:00,960 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:41:00,960 INFO L93 Difference]: Finished difference Result 314 states and 383 transitions. [2018-04-09 20:41:00,960 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 47 states. [2018-04-09 20:41:00,961 INFO L78 Accepts]: Start accepts. Automaton has 42 states. Word has length 107 [2018-04-09 20:41:00,961 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:41:00,962 INFO L225 Difference]: With dead ends: 314 [2018-04-09 20:41:00,962 INFO L226 Difference]: Without dead ends: 235 [2018-04-09 20:41:00,963 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 244 GetRequests, 159 SyntacticMatches, 14 SemanticMatches, 71 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1386 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=818, Invalid=4438, Unknown=0, NotChecked=0, Total=5256 [2018-04-09 20:41:00,964 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 235 states. [2018-04-09 20:41:00,969 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 235 to 235. [2018-04-09 20:41:00,969 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 235 states. [2018-04-09 20:41:00,971 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 289 transitions. [2018-04-09 20:41:00,971 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 289 transitions. Word has length 107 [2018-04-09 20:41:00,971 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:41:00,971 INFO L459 AbstractCegarLoop]: Abstraction has 235 states and 289 transitions. [2018-04-09 20:41:00,971 INFO L460 AbstractCegarLoop]: Interpolant automaton has 42 states. [2018-04-09 20:41:00,971 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 289 transitions. [2018-04-09 20:41:00,972 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 115 [2018-04-09 20:41:00,973 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:41:00,973 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-09 20:41:00,973 INFO L408 AbstractCegarLoop]: === Iteration 14 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:41:00,973 INFO L82 PathProgramCache]: Analyzing trace with hash -1087701571, 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-09 20:41:00,997 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:41:01,015 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:41:01,017 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:41:01,809 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-09 20:41:01,810 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:41:02,112 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-09 20:41:02,133 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:41:02,133 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [33, 33] total 48 [2018-04-09 20:41:02,133 INFO L442 AbstractCegarLoop]: Interpolant automaton has 48 states [2018-04-09 20:41:02,133 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 48 interpolants. [2018-04-09 20:41:02,134 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=319, Invalid=1937, Unknown=0, NotChecked=0, Total=2256 [2018-04-09 20:41:02,134 INFO L87 Difference]: Start difference. First operand 235 states and 289 transitions. Second operand 48 states. [2018-04-09 20:41:02,945 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:41:02,945 INFO L93 Difference]: Finished difference Result 320 states and 389 transitions. [2018-04-09 20:41:02,979 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 54 states. [2018-04-09 20:41:02,979 INFO L78 Accepts]: Start accepts. Automaton has 48 states. Word has length 114 [2018-04-09 20:41:02,980 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:41:02,981 INFO L225 Difference]: With dead ends: 320 [2018-04-09 20:41:02,981 INFO L226 Difference]: Without dead ends: 235 [2018-04-09 20:41:02,983 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 263 GetRequests, 165 SyntacticMatches, 16 SemanticMatches, 82 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1873 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=1060, Invalid=5912, Unknown=0, NotChecked=0, Total=6972 [2018-04-09 20:41:02,983 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 235 states. [2018-04-09 20:41:02,990 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 235 to 235. [2018-04-09 20:41:02,990 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 235 states. [2018-04-09 20:41:02,991 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 288 transitions. [2018-04-09 20:41:02,991 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 288 transitions. Word has length 114 [2018-04-09 20:41:02,991 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:41:02,992 INFO L459 AbstractCegarLoop]: Abstraction has 235 states and 288 transitions. [2018-04-09 20:41:02,992 INFO L460 AbstractCegarLoop]: Interpolant automaton has 48 states. [2018-04-09 20:41:02,992 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 288 transitions. [2018-04-09 20:41:02,993 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 119 [2018-04-09 20:41:02,993 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:41:02,993 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-09 20:41:02,993 INFO L408 AbstractCegarLoop]: === Iteration 15 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:41:02,993 INFO L82 PathProgramCache]: Analyzing trace with hash -627961266, 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-09 20:41:03,010 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:41:03,031 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:41:03,034 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:41:03,368 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-09 20:41:03,369 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:41:04,246 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-09 20:41:04,266 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:41:04,266 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [32, 32] total 63 [2018-04-09 20:41:04,267 INFO L442 AbstractCegarLoop]: Interpolant automaton has 64 states [2018-04-09 20:41:04,267 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 64 interpolants. [2018-04-09 20:41:04,268 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=606, Invalid=3426, Unknown=0, NotChecked=0, Total=4032 [2018-04-09 20:41:04,268 INFO L87 Difference]: Start difference. First operand 235 states and 288 transitions. Second operand 64 states. [2018-04-09 20:41:09,539 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:41:09,539 INFO L93 Difference]: Finished difference Result 407 states and 539 transitions. [2018-04-09 20:41:09,539 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 93 states. [2018-04-09 20:41:09,540 INFO L78 Accepts]: Start accepts. Automaton has 64 states. Word has length 118 [2018-04-09 20:41:09,540 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:41:09,542 INFO L225 Difference]: With dead ends: 407 [2018-04-09 20:41:09,542 INFO L226 Difference]: Without dead ends: 405 [2018-04-09 20:41:09,547 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 309 GetRequests, 173 SyntacticMatches, 0 SemanticMatches, 136 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3452 ImplicationChecksByTransitivity, 4.9s TimeCoverageRelationStatistics Valid=4624, Invalid=14282, Unknown=0, NotChecked=0, Total=18906 [2018-04-09 20:41:09,547 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 405 states. [2018-04-09 20:41:09,561 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 405 to 379. [2018-04-09 20:41:09,561 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 379 states. [2018-04-09 20:41:09,563 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 379 states to 379 states and 480 transitions. [2018-04-09 20:41:09,564 INFO L78 Accepts]: Start accepts. Automaton has 379 states and 480 transitions. Word has length 118 [2018-04-09 20:41:09,564 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:41:09,564 INFO L459 AbstractCegarLoop]: Abstraction has 379 states and 480 transitions. [2018-04-09 20:41:09,564 INFO L460 AbstractCegarLoop]: Interpolant automaton has 64 states. [2018-04-09 20:41:09,564 INFO L276 IsEmpty]: Start isEmpty. Operand 379 states and 480 transitions. [2018-04-09 20:41:09,566 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 122 [2018-04-09 20:41:09,566 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:41:09,566 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-09 20:41:09,566 INFO L408 AbstractCegarLoop]: === Iteration 16 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:41:09,567 INFO L82 PathProgramCache]: Analyzing trace with hash 1787685944, now seen corresponding path program 10 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 17 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 17 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-09 20:41:09,576 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:41:09,597 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:41:09,599 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:41:09,727 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-09 20:41:09,727 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:41:09,967 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-09 20:41:09,988 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:41:09,988 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 31 [2018-04-09 20:41:09,989 INFO L442 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-04-09 20:41:09,989 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-04-09 20:41:09,989 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=174, Invalid=818, Unknown=0, NotChecked=0, Total=992 [2018-04-09 20:41:09,989 INFO L87 Difference]: Start difference. First operand 379 states and 480 transitions. Second operand 32 states. [2018-04-09 20:41:11,240 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:41:11,241 INFO L93 Difference]: Finished difference Result 456 states and 588 transitions. [2018-04-09 20:41:11,241 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2018-04-09 20:41:11,241 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 121 [2018-04-09 20:41:11,241 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:41:11,243 INFO L225 Difference]: With dead ends: 456 [2018-04-09 20:41:11,243 INFO L226 Difference]: Without dead ends: 454 [2018-04-09 20:41:11,245 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 275 GetRequests, 211 SyntacticMatches, 0 SemanticMatches, 64 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 716 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=1096, Invalid=3194, Unknown=0, NotChecked=0, Total=4290 [2018-04-09 20:41:11,245 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 454 states. [2018-04-09 20:41:11,262 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 454 to 451. [2018-04-09 20:41:11,262 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-04-09 20:41:11,265 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 568 transitions. [2018-04-09 20:41:11,265 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 568 transitions. Word has length 121 [2018-04-09 20:41:11,265 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:41:11,266 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 568 transitions. [2018-04-09 20:41:11,266 INFO L460 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-04-09 20:41:11,266 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 568 transitions. [2018-04-09 20:41:11,269 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 178 [2018-04-09 20:41:11,269 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:41:11,269 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-09 20:41:11,269 INFO L408 AbstractCegarLoop]: === Iteration 17 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:41:11,270 INFO L82 PathProgramCache]: Analyzing trace with hash -405765320, 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-09 20:41:11,279 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:41:11,316 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:41:11,321 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:41:11,693 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-09 20:41:11,693 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:41:12,047 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-09 20:41:12,068 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:41:12,068 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [37, 37] total 54 [2018-04-09 20:41:12,068 INFO L442 AbstractCegarLoop]: Interpolant automaton has 54 states [2018-04-09 20:41:12,068 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 54 interpolants. [2018-04-09 20:41:12,069 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=395, Invalid=2467, Unknown=0, NotChecked=0, Total=2862 [2018-04-09 20:41:12,069 INFO L87 Difference]: Start difference. First operand 451 states and 568 transitions. Second operand 54 states. [2018-04-09 20:41:12,969 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:41:12,969 INFO L93 Difference]: Finished difference Result 602 states and 749 transitions. [2018-04-09 20:41:12,970 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 61 states. [2018-04-09 20:41:12,970 INFO L78 Accepts]: Start accepts. Automaton has 54 states. Word has length 177 [2018-04-09 20:41:12,970 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:41:12,972 INFO L225 Difference]: With dead ends: 602 [2018-04-09 20:41:12,972 INFO L226 Difference]: Without dead ends: 451 [2018-04-09 20:41:12,973 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 394 GetRequests, 283 SyntacticMatches, 18 SemanticMatches, 93 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2433 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=1333, Invalid=7597, Unknown=0, NotChecked=0, Total=8930 [2018-04-09 20:41:12,973 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-04-09 20:41:12,991 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-04-09 20:41:12,991 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-04-09 20:41:12,994 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 567 transitions. [2018-04-09 20:41:12,994 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 567 transitions. Word has length 177 [2018-04-09 20:41:12,995 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:41:12,995 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 567 transitions. [2018-04-09 20:41:12,995 INFO L460 AbstractCegarLoop]: Interpolant automaton has 54 states. [2018-04-09 20:41:12,995 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 567 transitions. [2018-04-09 20:41:12,998 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 185 [2018-04-09 20:41:12,999 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:41:12,999 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-09 20:41:12,999 INFO L408 AbstractCegarLoop]: === Iteration 18 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:41:12,999 INFO L82 PathProgramCache]: Analyzing trace with hash 1113895261, 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-09 20:41:13,008 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:41:13,045 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:41:13,050 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:41:13,616 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-09 20:41:13,616 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:41:14,057 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-09 20:41:14,078 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:41:14,078 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [41, 41] total 60 [2018-04-09 20:41:14,078 INFO L442 AbstractCegarLoop]: Interpolant automaton has 60 states [2018-04-09 20:41:14,079 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 60 interpolants. [2018-04-09 20:41:14,079 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=479, Invalid=3061, Unknown=0, NotChecked=0, Total=3540 [2018-04-09 20:41:14,079 INFO L87 Difference]: Start difference. First operand 451 states and 567 transitions. Second operand 60 states. [2018-04-09 20:41:15,311 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:41:15,312 INFO L93 Difference]: Finished difference Result 602 states and 748 transitions. [2018-04-09 20:41:15,346 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 68 states. [2018-04-09 20:41:15,346 INFO L78 Accepts]: Start accepts. Automaton has 60 states. Word has length 184 [2018-04-09 20:41:15,347 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:41:15,348 INFO L225 Difference]: With dead ends: 602 [2018-04-09 20:41:15,348 INFO L226 Difference]: Without dead ends: 451 [2018-04-09 20:41:15,350 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 413 GetRequests, 289 SyntacticMatches, 20 SemanticMatches, 104 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3066 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=1637, Invalid=9493, Unknown=0, NotChecked=0, Total=11130 [2018-04-09 20:41:15,350 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-04-09 20:41:15,359 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-04-09 20:41:15,359 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-04-09 20:41:15,361 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 566 transitions. [2018-04-09 20:41:15,361 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 566 transitions. Word has length 184 [2018-04-09 20:41:15,362 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:41:15,362 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 566 transitions. [2018-04-09 20:41:15,362 INFO L460 AbstractCegarLoop]: Interpolant automaton has 60 states. [2018-04-09 20:41:15,362 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 566 transitions. [2018-04-09 20:41:15,364 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 192 [2018-04-09 20:41:15,364 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:41:15,364 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-09 20:41:15,364 INFO L408 AbstractCegarLoop]: === Iteration 19 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:41:15,365 INFO L82 PathProgramCache]: Analyzing trace with hash 317472664, 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-09 20:41:15,386 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:41:15,414 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:41:15,418 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:41:16,020 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-09 20:41:16,020 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:41:16,552 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-09 20:41:16,573 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:41:16,573 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [45, 45] total 66 [2018-04-09 20:41:16,573 INFO L442 AbstractCegarLoop]: Interpolant automaton has 66 states [2018-04-09 20:41:16,574 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 66 interpolants. [2018-04-09 20:41:16,574 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=571, Invalid=3719, Unknown=0, NotChecked=0, Total=4290 [2018-04-09 20:41:16,574 INFO L87 Difference]: Start difference. First operand 451 states and 566 transitions. Second operand 66 states. [2018-04-09 20:41:17,813 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:41:17,813 INFO L93 Difference]: Finished difference Result 602 states and 747 transitions. [2018-04-09 20:41:17,813 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 75 states. [2018-04-09 20:41:17,813 INFO L78 Accepts]: Start accepts. Automaton has 66 states. Word has length 191 [2018-04-09 20:41:17,814 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:41:17,815 INFO L225 Difference]: With dead ends: 602 [2018-04-09 20:41:17,816 INFO L226 Difference]: Without dead ends: 451 [2018-04-09 20:41:17,818 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 432 GetRequests, 295 SyntacticMatches, 22 SemanticMatches, 115 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3772 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=1972, Invalid=11600, Unknown=0, NotChecked=0, Total=13572 [2018-04-09 20:41:17,818 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-04-09 20:41:17,826 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-04-09 20:41:17,827 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-04-09 20:41:17,828 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 565 transitions. [2018-04-09 20:41:17,828 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 565 transitions. Word has length 191 [2018-04-09 20:41:17,828 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:41:17,828 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 565 transitions. [2018-04-09 20:41:17,828 INFO L460 AbstractCegarLoop]: Interpolant automaton has 66 states. [2018-04-09 20:41:17,829 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 565 transitions. [2018-04-09 20:41:17,830 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 199 [2018-04-09 20:41:17,830 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:41:17,830 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-09 20:41:17,830 INFO L408 AbstractCegarLoop]: === Iteration 20 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:41:17,830 INFO L82 PathProgramCache]: Analyzing trace with hash -1001502467, 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-09 20:41:17,837 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:41:17,866 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:41:17,870 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:41:18,403 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-09 20:41:18,403 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:41:18,999 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-09 20:41:19,020 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:41:19,020 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [49, 49] total 72 [2018-04-09 20:41:19,020 INFO L442 AbstractCegarLoop]: Interpolant automaton has 72 states [2018-04-09 20:41:19,021 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 72 interpolants. [2018-04-09 20:41:19,021 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=671, Invalid=4441, Unknown=0, NotChecked=0, Total=5112 [2018-04-09 20:41:19,021 INFO L87 Difference]: Start difference. First operand 451 states and 565 transitions. Second operand 72 states. [2018-04-09 20:41:20,468 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:41:20,469 INFO L93 Difference]: Finished difference Result 602 states and 746 transitions. [2018-04-09 20:41:20,502 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 82 states. [2018-04-09 20:41:20,502 INFO L78 Accepts]: Start accepts. Automaton has 72 states. Word has length 198 [2018-04-09 20:41:20,503 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:41:20,505 INFO L225 Difference]: With dead ends: 602 [2018-04-09 20:41:20,506 INFO L226 Difference]: Without dead ends: 451 [2018-04-09 20:41:20,507 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 451 GetRequests, 301 SyntacticMatches, 24 SemanticMatches, 126 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4551 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=2338, Invalid=13918, Unknown=0, NotChecked=0, Total=16256 [2018-04-09 20:41:20,508 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-04-09 20:41:20,520 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-04-09 20:41:20,520 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-04-09 20:41:20,522 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 564 transitions. [2018-04-09 20:41:20,522 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 564 transitions. Word has length 198 [2018-04-09 20:41:20,523 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:41:20,523 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 564 transitions. [2018-04-09 20:41:20,523 INFO L460 AbstractCegarLoop]: Interpolant automaton has 72 states. [2018-04-09 20:41:20,523 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 564 transitions. [2018-04-09 20:41:20,525 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 206 [2018-04-09 20:41:20,525 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:41:20,526 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-09 20:41:20,526 INFO L408 AbstractCegarLoop]: === Iteration 21 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:41:20,526 INFO L82 PathProgramCache]: Analyzing trace with hash 118936568, 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-09 20:41:20,534 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:41:20,564 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:41:20,568 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:41:21,234 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-09 20:41:21,234 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:41:21,938 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-09 20:41:21,958 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:41:21,958 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [53, 53] total 78 [2018-04-09 20:41:21,959 INFO L442 AbstractCegarLoop]: Interpolant automaton has 78 states [2018-04-09 20:41:21,959 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 78 interpolants. [2018-04-09 20:41:21,959 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=779, Invalid=5227, Unknown=0, NotChecked=0, Total=6006 [2018-04-09 20:41:21,960 INFO L87 Difference]: Start difference. First operand 451 states and 564 transitions. Second operand 78 states. [2018-04-09 20:41:23,701 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:41:23,701 INFO L93 Difference]: Finished difference Result 602 states and 745 transitions. [2018-04-09 20:41:23,702 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 89 states. [2018-04-09 20:41:23,702 INFO L78 Accepts]: Start accepts. Automaton has 78 states. Word has length 205 [2018-04-09 20:41:23,702 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:41:23,704 INFO L225 Difference]: With dead ends: 602 [2018-04-09 20:41:23,704 INFO L226 Difference]: Without dead ends: 451 [2018-04-09 20:41:23,705 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 470 GetRequests, 307 SyntacticMatches, 26 SemanticMatches, 137 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5403 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=2735, Invalid=16447, Unknown=0, NotChecked=0, Total=19182 [2018-04-09 20:41:23,705 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-04-09 20:41:23,719 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-04-09 20:41:23,719 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-04-09 20:41:23,721 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 563 transitions. [2018-04-09 20:41:23,721 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 563 transitions. Word has length 205 [2018-04-09 20:41:23,721 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:41:23,722 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 563 transitions. [2018-04-09 20:41:23,722 INFO L460 AbstractCegarLoop]: Interpolant automaton has 78 states. [2018-04-09 20:41:23,722 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 563 transitions. [2018-04-09 20:41:23,724 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 213 [2018-04-09 20:41:23,724 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:41:23,725 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-09 20:41:23,725 INFO L408 AbstractCegarLoop]: === Iteration 22 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:41:23,725 INFO L82 PathProgramCache]: Analyzing trace with hash -817493859, 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-09 20:41:23,734 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:41:23,768 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:41:23,774 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:41:24,495 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-09 20:41:24,496 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:41:25,296 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-09 20:41:25,316 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:41:25,316 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [57, 57] total 84 [2018-04-09 20:41:25,317 INFO L442 AbstractCegarLoop]: Interpolant automaton has 84 states [2018-04-09 20:41:25,317 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 84 interpolants. [2018-04-09 20:41:25,318 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=895, Invalid=6077, Unknown=0, NotChecked=0, Total=6972 [2018-04-09 20:41:25,318 INFO L87 Difference]: Start difference. First operand 451 states and 563 transitions. Second operand 84 states. [2018-04-09 20:41:27,190 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:41:27,190 INFO L93 Difference]: Finished difference Result 602 states and 744 transitions. [2018-04-09 20:41:27,191 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 96 states. [2018-04-09 20:41:27,191 INFO L78 Accepts]: Start accepts. Automaton has 84 states. Word has length 212 [2018-04-09 20:41:27,191 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:41:27,193 INFO L225 Difference]: With dead ends: 602 [2018-04-09 20:41:27,193 INFO L226 Difference]: Without dead ends: 451 [2018-04-09 20:41:27,194 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 489 GetRequests, 313 SyntacticMatches, 28 SemanticMatches, 148 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6328 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=3163, Invalid=19187, Unknown=0, NotChecked=0, Total=22350 [2018-04-09 20:41:27,195 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-04-09 20:41:27,207 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-04-09 20:41:27,207 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-04-09 20:41:27,209 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 562 transitions. [2018-04-09 20:41:27,209 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 562 transitions. Word has length 212 [2018-04-09 20:41:27,210 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:41:27,210 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 562 transitions. [2018-04-09 20:41:27,210 INFO L460 AbstractCegarLoop]: Interpolant automaton has 84 states. [2018-04-09 20:41:27,210 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 562 transitions. [2018-04-09 20:41:27,212 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 220 [2018-04-09 20:41:27,212 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:41:27,213 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-09 20:41:27,213 INFO L408 AbstractCegarLoop]: === Iteration 23 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:41:27,213 INFO L82 PathProgramCache]: Analyzing trace with hash -176799656, 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-09 20:41:27,222 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:41:27,253 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:41:27,257 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:41:28,025 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-09 20:41:28,026 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:41:28,982 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-09 20:41:29,003 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:41:29,003 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [61, 61] total 90 [2018-04-09 20:41:29,003 INFO L442 AbstractCegarLoop]: Interpolant automaton has 90 states [2018-04-09 20:41:29,004 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 90 interpolants. [2018-04-09 20:41:29,004 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1019, Invalid=6991, Unknown=0, NotChecked=0, Total=8010 [2018-04-09 20:41:29,004 INFO L87 Difference]: Start difference. First operand 451 states and 562 transitions. Second operand 90 states. [2018-04-09 20:41:31,103 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:41:31,103 INFO L93 Difference]: Finished difference Result 602 states and 743 transitions. [2018-04-09 20:41:31,136 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 103 states. [2018-04-09 20:41:31,136 INFO L78 Accepts]: Start accepts. Automaton has 90 states. Word has length 219 [2018-04-09 20:41:31,136 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:41:31,138 INFO L225 Difference]: With dead ends: 602 [2018-04-09 20:41:31,138 INFO L226 Difference]: Without dead ends: 451 [2018-04-09 20:41:31,139 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 508 GetRequests, 319 SyntacticMatches, 30 SemanticMatches, 159 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7326 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=3622, Invalid=22138, Unknown=0, NotChecked=0, Total=25760 [2018-04-09 20:41:31,140 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-04-09 20:41:31,152 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-04-09 20:41:31,152 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-04-09 20:41:31,154 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 561 transitions. [2018-04-09 20:41:31,154 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 561 transitions. Word has length 219 [2018-04-09 20:41:31,155 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:41:31,155 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 561 transitions. [2018-04-09 20:41:31,155 INFO L460 AbstractCegarLoop]: Interpolant automaton has 90 states. [2018-04-09 20:41:31,155 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 561 transitions. [2018-04-09 20:41:31,157 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 227 [2018-04-09 20:41:31,157 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:41:31,158 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-09 20:41:31,158 INFO L408 AbstractCegarLoop]: === Iteration 24 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:41:31,158 INFO L82 PathProgramCache]: Analyzing trace with hash -1150947267, 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-09 20:41:31,167 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:41:31,201 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:41:31,206 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:41:32,130 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-09 20:41:32,131 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:41:33,221 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-09 20:41:33,241 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:41:33,242 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [65, 65] total 96 [2018-04-09 20:41:33,242 INFO L442 AbstractCegarLoop]: Interpolant automaton has 96 states [2018-04-09 20:41:33,242 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 96 interpolants. [2018-04-09 20:41:33,243 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1151, Invalid=7969, Unknown=0, NotChecked=0, Total=9120 [2018-04-09 20:41:33,243 INFO L87 Difference]: Start difference. First operand 451 states and 561 transitions. Second operand 96 states. [2018-04-09 20:41:35,732 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:41:35,732 INFO L93 Difference]: Finished difference Result 608 states and 749 transitions. [2018-04-09 20:41:35,732 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 110 states. [2018-04-09 20:41:35,732 INFO L78 Accepts]: Start accepts. Automaton has 96 states. Word has length 226 [2018-04-09 20:41:35,733 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:41:35,734 INFO L225 Difference]: With dead ends: 608 [2018-04-09 20:41:35,734 INFO L226 Difference]: Without dead ends: 451 [2018-04-09 20:41:35,736 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 527 GetRequests, 325 SyntacticMatches, 32 SemanticMatches, 170 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8397 ImplicationChecksByTransitivity, 3.4s TimeCoverageRelationStatistics Valid=4112, Invalid=25300, Unknown=0, NotChecked=0, Total=29412 [2018-04-09 20:41:35,736 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-04-09 20:41:35,744 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-04-09 20:41:35,744 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-04-09 20:41:35,745 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 560 transitions. [2018-04-09 20:41:35,745 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 560 transitions. Word has length 226 [2018-04-09 20:41:35,745 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:41:35,745 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 560 transitions. [2018-04-09 20:41:35,745 INFO L460 AbstractCegarLoop]: Interpolant automaton has 96 states. [2018-04-09 20:41:35,746 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 560 transitions. [2018-04-09 20:41:35,747 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 231 [2018-04-09 20:41:35,747 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:41:35,747 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-09 20:41:35,747 INFO L408 AbstractCegarLoop]: === Iteration 25 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:41:35,747 INFO L82 PathProgramCache]: Analyzing trace with hash -1222217906, 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-09 20:41:35,753 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:41:35,785 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:41:35,790 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:41:37,193 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-09 20:41:37,194 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:41:40,636 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-09 20:41:40,658 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:41:40,658 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [64, 64] total 127 [2018-04-09 20:41:40,659 INFO L442 AbstractCegarLoop]: Interpolant automaton has 128 states [2018-04-09 20:41:40,659 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 128 interpolants. [2018-04-09 20:41:40,660 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2238, Invalid=14018, Unknown=0, NotChecked=0, Total=16256 [2018-04-09 20:41:40,661 INFO L87 Difference]: Start difference. First operand 451 states and 560 transitions. Second operand 128 states. [2018-04-09 20:41:46,699 WARN L151 SmtUtils]: Spent 247ms on a formula simplification. DAG size of input: 252 DAG size of output 12 [2018-04-09 20:41:47,382 WARN L151 SmtUtils]: Spent 250ms on a formula simplification. DAG size of input: 247 DAG size of output 11 [2018-04-09 20:41:47,838 WARN L151 SmtUtils]: Spent 235ms on a formula simplification. DAG size of input: 244 DAG size of output 12 [2018-04-09 20:41:48,490 WARN L151 SmtUtils]: Spent 234ms on a formula simplification. DAG size of input: 239 DAG size of output 11 [2018-04-09 20:41:48,925 WARN L151 SmtUtils]: Spent 216ms on a formula simplification. DAG size of input: 236 DAG size of output 12 [2018-04-09 20:41:49,564 WARN L151 SmtUtils]: Spent 219ms on a formula simplification. DAG size of input: 231 DAG size of output 11 [2018-04-09 20:41:49,985 WARN L151 SmtUtils]: Spent 201ms on a formula simplification. DAG size of input: 228 DAG size of output 12 [2018-04-09 20:41:50,604 WARN L151 SmtUtils]: Spent 197ms on a formula simplification. DAG size of input: 223 DAG size of output 11 [2018-04-09 20:41:51,025 WARN L151 SmtUtils]: Spent 192ms on a formula simplification. DAG size of input: 220 DAG size of output 12 [2018-04-09 20:41:51,633 WARN L151 SmtUtils]: Spent 189ms on a formula simplification. DAG size of input: 215 DAG size of output 11 [2018-04-09 20:41:52,041 WARN L151 SmtUtils]: Spent 187ms on a formula simplification. DAG size of input: 212 DAG size of output 12 [2018-04-09 20:41:52,617 WARN L151 SmtUtils]: Spent 170ms on a formula simplification. DAG size of input: 207 DAG size of output 11 [2018-04-09 20:41:53,009 WARN L151 SmtUtils]: Spent 164ms on a formula simplification. DAG size of input: 204 DAG size of output 12 [2018-04-09 20:41:53,587 WARN L151 SmtUtils]: Spent 163ms on a formula simplification. DAG size of input: 199 DAG size of output 11 [2018-04-09 20:41:53,969 WARN L151 SmtUtils]: Spent 155ms on a formula simplification. DAG size of input: 196 DAG size of output 12 [2018-04-09 20:41:54,534 WARN L151 SmtUtils]: Spent 167ms on a formula simplification. DAG size of input: 191 DAG size of output 11 [2018-04-09 20:41:54,908 WARN L151 SmtUtils]: Spent 150ms on a formula simplification. DAG size of input: 188 DAG size of output 12 [2018-04-09 20:41:55,458 WARN L151 SmtUtils]: Spent 143ms on a formula simplification. DAG size of input: 183 DAG size of output 11 [2018-04-09 20:41:55,819 WARN L151 SmtUtils]: Spent 146ms on a formula simplification. DAG size of input: 180 DAG size of output 12 [2018-04-09 20:41:56,328 WARN L151 SmtUtils]: Spent 126ms on a formula simplification. DAG size of input: 175 DAG size of output 11 [2018-04-09 20:41:56,667 WARN L151 SmtUtils]: Spent 123ms on a formula simplification. DAG size of input: 172 DAG size of output 12 [2018-04-09 20:41:57,168 WARN L151 SmtUtils]: Spent 123ms on a formula simplification. DAG size of input: 167 DAG size of output 11 [2018-04-09 20:41:57,758 WARN L151 SmtUtils]: Spent 120ms on a formula simplification. DAG size of input: 164 DAG size of output 12 [2018-04-09 20:41:58,255 WARN L151 SmtUtils]: Spent 117ms on a formula simplification. DAG size of input: 159 DAG size of output 11 [2018-04-09 20:41:58,570 WARN L151 SmtUtils]: Spent 105ms on a formula simplification. DAG size of input: 156 DAG size of output 12 [2018-04-09 20:41:59,040 WARN L151 SmtUtils]: Spent 108ms on a formula simplification. DAG size of input: 151 DAG size of output 11 [2018-04-09 20:42:08,449 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:42:08,449 INFO L93 Difference]: Finished difference Result 791 states and 1059 transitions. [2018-04-09 20:42:08,449 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 189 states. [2018-04-09 20:42:08,449 INFO L78 Accepts]: Start accepts. Automaton has 128 states. Word has length 230 [2018-04-09 20:42:08,450 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:42:08,452 INFO L225 Difference]: With dead ends: 791 [2018-04-09 20:42:08,452 INFO L226 Difference]: Without dead ends: 789 [2018-04-09 20:42:08,455 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 613 GetRequests, 333 SyntacticMatches, 0 SemanticMatches, 280 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15068 ImplicationChecksByTransitivity, 27.0s TimeCoverageRelationStatistics Valid=18976, Invalid=60266, Unknown=0, NotChecked=0, Total=79242 [2018-04-09 20:42:08,455 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 789 states. [2018-04-09 20:42:08,473 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 789 to 739. [2018-04-09 20:42:08,473 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 739 states. [2018-04-09 20:42:08,476 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 739 states to 739 states and 944 transitions. [2018-04-09 20:42:08,476 INFO L78 Accepts]: Start accepts. Automaton has 739 states and 944 transitions. Word has length 230 [2018-04-09 20:42:08,476 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:42:08,477 INFO L459 AbstractCegarLoop]: Abstraction has 739 states and 944 transitions. [2018-04-09 20:42:08,477 INFO L460 AbstractCegarLoop]: Interpolant automaton has 128 states. [2018-04-09 20:42:08,477 INFO L276 IsEmpty]: Start isEmpty. Operand 739 states and 944 transitions. [2018-04-09 20:42:08,479 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 234 [2018-04-09 20:42:08,479 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:42:08,480 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-09 20:42:08,480 INFO L408 AbstractCegarLoop]: === Iteration 26 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:42:08,480 INFO L82 PathProgramCache]: Analyzing trace with hash 347112632, now seen corresponding path program 19 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 27 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 27 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-04-09 20:42:08,488 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:42:08,535 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:42:08,540 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:42:08,855 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-09 20:42:08,855 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:42:09,755 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-09 20:42:09,776 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:42:09,776 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [32, 32] total 63 [2018-04-09 20:42:09,776 INFO L442 AbstractCegarLoop]: Interpolant automaton has 64 states [2018-04-09 20:42:09,777 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 64 interpolants. [2018-04-09 20:42:09,777 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=606, Invalid=3426, Unknown=0, NotChecked=0, Total=4032 [2018-04-09 20:42:09,777 INFO L87 Difference]: Start difference. First operand 739 states and 944 transitions. Second operand 64 states. [2018-04-09 20:42:14,784 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:42:14,785 INFO L93 Difference]: Finished difference Result 888 states and 1156 transitions. [2018-04-09 20:42:14,785 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 93 states. [2018-04-09 20:42:14,785 INFO L78 Accepts]: Start accepts. Automaton has 64 states. Word has length 233 [2018-04-09 20:42:14,785 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:42:14,788 INFO L225 Difference]: With dead ends: 888 [2018-04-09 20:42:14,788 INFO L226 Difference]: Without dead ends: 886 [2018-04-09 20:42:14,789 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 539 GetRequests, 403 SyntacticMatches, 0 SemanticMatches, 136 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3452 ImplicationChecksByTransitivity, 4.8s TimeCoverageRelationStatistics Valid=4624, Invalid=14282, Unknown=0, NotChecked=0, Total=18906 [2018-04-09 20:42:14,789 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 886 states. [2018-04-09 20:42:14,807 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 886 to 883. [2018-04-09 20:42:14,807 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-09 20:42:14,810 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1120 transitions. [2018-04-09 20:42:14,811 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1120 transitions. Word has length 233 [2018-04-09 20:42:14,811 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:42:14,811 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1120 transitions. [2018-04-09 20:42:14,811 INFO L460 AbstractCegarLoop]: Interpolant automaton has 64 states. [2018-04-09 20:42:14,812 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1120 transitions. [2018-04-09 20:42:14,815 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 346 [2018-04-09 20:42:14,815 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:42:14,816 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-09 20:42:14,816 INFO L408 AbstractCegarLoop]: === Iteration 27 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:42:14,816 INFO L82 PathProgramCache]: Analyzing trace with hash -1245859144, 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-09 20:42:14,829 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:42:14,899 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:42:14,905 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:42:16,161 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-09 20:42:16,162 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:42:17,428 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-09 20:42:17,449 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:42:17,449 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [69, 69] total 102 [2018-04-09 20:42:17,450 INFO L442 AbstractCegarLoop]: Interpolant automaton has 102 states [2018-04-09 20:42:17,450 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 102 interpolants. [2018-04-09 20:42:17,450 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1291, Invalid=9011, Unknown=0, NotChecked=0, Total=10302 [2018-04-09 20:42:17,450 INFO L87 Difference]: Start difference. First operand 883 states and 1120 transitions. Second operand 102 states. [2018-04-09 20:42:20,310 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:42:20,310 INFO L93 Difference]: Finished difference Result 1178 states and 1477 transitions. [2018-04-09 20:42:20,310 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 117 states. [2018-04-09 20:42:20,310 INFO L78 Accepts]: Start accepts. Automaton has 102 states. Word has length 345 [2018-04-09 20:42:20,311 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:42:20,315 INFO L225 Difference]: With dead ends: 1178 [2018-04-09 20:42:20,315 INFO L226 Difference]: Without dead ends: 883 [2018-04-09 20:42:20,319 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 770 GetRequests, 555 SyntacticMatches, 34 SemanticMatches, 181 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9541 ImplicationChecksByTransitivity, 4.1s TimeCoverageRelationStatistics Valid=4633, Invalid=28673, Unknown=0, NotChecked=0, Total=33306 [2018-04-09 20:42:20,319 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-09 20:42:20,340 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-09 20:42:20,341 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-09 20:42:20,343 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1119 transitions. [2018-04-09 20:42:20,344 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1119 transitions. Word has length 345 [2018-04-09 20:42:20,344 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:42:20,344 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1119 transitions. [2018-04-09 20:42:20,344 INFO L460 AbstractCegarLoop]: Interpolant automaton has 102 states. [2018-04-09 20:42:20,344 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1119 transitions. [2018-04-09 20:42:20,348 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 353 [2018-04-09 20:42:20,348 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:42:20,348 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-09 20:42:20,348 INFO L408 AbstractCegarLoop]: === Iteration 28 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:42:20,349 INFO L82 PathProgramCache]: Analyzing trace with hash 108709853, 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-09 20:42:20,358 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:42:20,429 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:42:20,437 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:42:21,612 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-09 20:42:21,613 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:42:22,981 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-09 20:42:23,002 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:42:23,002 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [73, 73] total 108 [2018-04-09 20:42:23,002 INFO L442 AbstractCegarLoop]: Interpolant automaton has 108 states [2018-04-09 20:42:23,003 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 108 interpolants. [2018-04-09 20:42:23,003 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1439, Invalid=10117, Unknown=0, NotChecked=0, Total=11556 [2018-04-09 20:42:23,003 INFO L87 Difference]: Start difference. First operand 883 states and 1119 transitions. Second operand 108 states. [2018-04-09 20:42:26,279 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:42:26,280 INFO L93 Difference]: Finished difference Result 1178 states and 1476 transitions. [2018-04-09 20:42:26,280 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 124 states. [2018-04-09 20:42:26,280 INFO L78 Accepts]: Start accepts. Automaton has 108 states. Word has length 352 [2018-04-09 20:42:26,280 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:42:26,283 INFO L225 Difference]: With dead ends: 1178 [2018-04-09 20:42:26,283 INFO L226 Difference]: Without dead ends: 883 [2018-04-09 20:42:26,287 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 789 GetRequests, 561 SyntacticMatches, 36 SemanticMatches, 192 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10758 ImplicationChecksByTransitivity, 4.3s TimeCoverageRelationStatistics Valid=5185, Invalid=32257, Unknown=0, NotChecked=0, Total=37442 [2018-04-09 20:42:26,288 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-09 20:42:26,308 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-09 20:42:26,308 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-09 20:42:26,311 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1118 transitions. [2018-04-09 20:42:26,311 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1118 transitions. Word has length 352 [2018-04-09 20:42:26,312 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:42:26,312 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1118 transitions. [2018-04-09 20:42:26,312 INFO L460 AbstractCegarLoop]: Interpolant automaton has 108 states. [2018-04-09 20:42:26,312 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1118 transitions. [2018-04-09 20:42:26,315 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 360 [2018-04-09 20:42:26,316 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:42:26,316 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-09 20:42:26,316 INFO L408 AbstractCegarLoop]: === Iteration 29 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:42:26,316 INFO L82 PathProgramCache]: Analyzing trace with hash 1398247192, 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-09 20:42:26,325 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:42:26,388 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:42:26,393 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:42:27,652 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-09 20:42:27,652 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:42:29,161 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-09 20:42:29,183 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:42:29,183 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [77, 77] total 114 [2018-04-09 20:42:29,183 INFO L442 AbstractCegarLoop]: Interpolant automaton has 114 states [2018-04-09 20:42:29,184 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 114 interpolants. [2018-04-09 20:42:29,184 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1595, Invalid=11287, Unknown=0, NotChecked=0, Total=12882 [2018-04-09 20:42:29,185 INFO L87 Difference]: Start difference. First operand 883 states and 1118 transitions. Second operand 114 states. [2018-04-09 20:42:32,872 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:42:32,873 INFO L93 Difference]: Finished difference Result 1178 states and 1475 transitions. [2018-04-09 20:42:32,873 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 131 states. [2018-04-09 20:42:32,873 INFO L78 Accepts]: Start accepts. Automaton has 114 states. Word has length 359 [2018-04-09 20:42:32,873 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:42:32,876 INFO L225 Difference]: With dead ends: 1178 [2018-04-09 20:42:32,876 INFO L226 Difference]: Without dead ends: 883 [2018-04-09 20:42:32,878 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 808 GetRequests, 567 SyntacticMatches, 38 SemanticMatches, 203 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12048 ImplicationChecksByTransitivity, 4.8s TimeCoverageRelationStatistics Valid=5768, Invalid=36052, Unknown=0, NotChecked=0, Total=41820 [2018-04-09 20:42:32,878 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-09 20:42:32,898 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-09 20:42:32,898 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-09 20:42:32,901 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1117 transitions. [2018-04-09 20:42:32,901 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1117 transitions. Word has length 359 [2018-04-09 20:42:32,902 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:42:32,902 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1117 transitions. [2018-04-09 20:42:32,902 INFO L460 AbstractCegarLoop]: Interpolant automaton has 114 states. [2018-04-09 20:42:32,902 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1117 transitions. [2018-04-09 20:42:32,905 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 367 [2018-04-09 20:42:32,905 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:42:32,906 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-09 20:42:32,906 INFO L408 AbstractCegarLoop]: === Iteration 30 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:42:32,906 INFO L82 PathProgramCache]: Analyzing trace with hash 297942909, 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-09 20:42:32,915 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:42:32,962 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:42:32,968 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:42:34,450 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-09 20:42:34,450 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:42:36,264 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-09 20:42:36,285 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:42:36,285 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [81, 81] total 120 [2018-04-09 20:42:36,285 INFO L442 AbstractCegarLoop]: Interpolant automaton has 120 states [2018-04-09 20:42:36,286 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 120 interpolants. [2018-04-09 20:42:36,286 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1759, Invalid=12521, Unknown=0, NotChecked=0, Total=14280 [2018-04-09 20:42:36,286 INFO L87 Difference]: Start difference. First operand 883 states and 1117 transitions. Second operand 120 states. [2018-04-09 20:42:40,393 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:42:40,393 INFO L93 Difference]: Finished difference Result 1178 states and 1474 transitions. [2018-04-09 20:42:40,393 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 138 states. [2018-04-09 20:42:40,393 INFO L78 Accepts]: Start accepts. Automaton has 120 states. Word has length 366 [2018-04-09 20:42:40,393 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:42:40,396 INFO L225 Difference]: With dead ends: 1178 [2018-04-09 20:42:40,396 INFO L226 Difference]: Without dead ends: 883 [2018-04-09 20:42:40,399 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 827 GetRequests, 573 SyntacticMatches, 40 SemanticMatches, 214 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13411 ImplicationChecksByTransitivity, 5.5s TimeCoverageRelationStatistics Valid=6382, Invalid=40058, Unknown=0, NotChecked=0, Total=46440 [2018-04-09 20:42:40,399 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-09 20:42:40,411 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-09 20:42:40,411 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-09 20:42:40,413 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1116 transitions. [2018-04-09 20:42:40,413 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1116 transitions. Word has length 366 [2018-04-09 20:42:40,413 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:42:40,413 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1116 transitions. [2018-04-09 20:42:40,413 INFO L460 AbstractCegarLoop]: Interpolant automaton has 120 states. [2018-04-09 20:42:40,413 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1116 transitions. [2018-04-09 20:42:40,415 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 374 [2018-04-09 20:42:40,415 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:42:40,415 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-09 20:42:40,415 INFO L408 AbstractCegarLoop]: === Iteration 31 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:42:40,416 INFO L82 PathProgramCache]: Analyzing trace with hash -221756552, 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-09 20:42:40,421 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:42:40,469 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:42:40,474 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:42:41,941 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-09 20:42:41,941 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:42:43,781 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-09 20:42:43,802 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:42:43,802 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [85, 85] total 126 [2018-04-09 20:42:43,803 INFO L442 AbstractCegarLoop]: Interpolant automaton has 126 states [2018-04-09 20:42:43,803 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 126 interpolants. [2018-04-09 20:42:43,804 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1931, Invalid=13819, Unknown=0, NotChecked=0, Total=15750 [2018-04-09 20:42:43,804 INFO L87 Difference]: Start difference. First operand 883 states and 1116 transitions. Second operand 126 states. [2018-04-09 20:42:47,847 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:42:47,848 INFO L93 Difference]: Finished difference Result 1178 states and 1473 transitions. [2018-04-09 20:42:47,848 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 145 states. [2018-04-09 20:42:47,848 INFO L78 Accepts]: Start accepts. Automaton has 126 states. Word has length 373 [2018-04-09 20:42:47,848 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:42:47,851 INFO L225 Difference]: With dead ends: 1178 [2018-04-09 20:42:47,851 INFO L226 Difference]: Without dead ends: 883 [2018-04-09 20:42:47,854 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 846 GetRequests, 579 SyntacticMatches, 42 SemanticMatches, 225 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14847 ImplicationChecksByTransitivity, 5.8s TimeCoverageRelationStatistics Valid=7027, Invalid=44275, Unknown=0, NotChecked=0, Total=51302 [2018-04-09 20:42:47,854 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-09 20:42:47,870 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-09 20:42:47,870 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-09 20:42:47,873 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1115 transitions. [2018-04-09 20:42:47,873 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1115 transitions. Word has length 373 [2018-04-09 20:42:47,874 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:42:47,874 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1115 transitions. [2018-04-09 20:42:47,874 INFO L460 AbstractCegarLoop]: Interpolant automaton has 126 states. [2018-04-09 20:42:47,874 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1115 transitions. [2018-04-09 20:42:47,877 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 381 [2018-04-09 20:42:47,877 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:42:47,877 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-09 20:42:47,877 INFO L408 AbstractCegarLoop]: === Iteration 32 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:42:47,877 INFO L82 PathProgramCache]: Analyzing trace with hash 2085609245, 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-09 20:42:47,883 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:42:47,934 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:42:47,941 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:42:49,656 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-09 20:42:49,657 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:42:51,669 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-09 20:42:51,690 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:42:51,690 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [89, 89] total 132 [2018-04-09 20:42:51,691 INFO L442 AbstractCegarLoop]: Interpolant automaton has 132 states [2018-04-09 20:42:51,691 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 132 interpolants. [2018-04-09 20:42:51,692 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2111, Invalid=15181, Unknown=0, NotChecked=0, Total=17292 [2018-04-09 20:42:51,692 INFO L87 Difference]: Start difference. First operand 883 states and 1115 transitions. Second operand 132 states. [2018-04-09 20:42:55,863 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:42:55,863 INFO L93 Difference]: Finished difference Result 1178 states and 1472 transitions. [2018-04-09 20:42:55,863 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 152 states. [2018-04-09 20:42:55,863 INFO L78 Accepts]: Start accepts. Automaton has 132 states. Word has length 380 [2018-04-09 20:42:55,864 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:42:55,866 INFO L225 Difference]: With dead ends: 1178 [2018-04-09 20:42:55,866 INFO L226 Difference]: Without dead ends: 883 [2018-04-09 20:42:55,869 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 865 GetRequests, 585 SyntacticMatches, 44 SemanticMatches, 236 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16356 ImplicationChecksByTransitivity, 6.4s TimeCoverageRelationStatistics Valid=7703, Invalid=48703, Unknown=0, NotChecked=0, Total=56406 [2018-04-09 20:42:55,870 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-09 20:42:55,881 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-09 20:42:55,881 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-09 20:42:55,882 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1114 transitions. [2018-04-09 20:42:55,883 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1114 transitions. Word has length 380 [2018-04-09 20:42:55,883 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:42:55,883 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1114 transitions. [2018-04-09 20:42:55,883 INFO L460 AbstractCegarLoop]: Interpolant automaton has 132 states. [2018-04-09 20:42:55,883 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1114 transitions. [2018-04-09 20:42:55,885 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 388 [2018-04-09 20:42:55,885 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:42:55,885 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-09 20:42:55,885 INFO L408 AbstractCegarLoop]: === Iteration 33 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:42:55,885 INFO L82 PathProgramCache]: Analyzing trace with hash -952774696, 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-09 20:42:55,947 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:42:56,005 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:42:56,010 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:42:57,760 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-09 20:42:57,760 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:42:59,897 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-09 20:42:59,931 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:42:59,931 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [93, 93] total 138 [2018-04-09 20:42:59,932 INFO L442 AbstractCegarLoop]: Interpolant automaton has 138 states [2018-04-09 20:42:59,932 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 138 interpolants. [2018-04-09 20:42:59,933 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2299, Invalid=16607, Unknown=0, NotChecked=0, Total=18906 [2018-04-09 20:42:59,933 INFO L87 Difference]: Start difference. First operand 883 states and 1114 transitions. Second operand 138 states. [2018-04-09 20:43:04,925 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:43:04,925 INFO L93 Difference]: Finished difference Result 1178 states and 1471 transitions. [2018-04-09 20:43:04,925 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 159 states. [2018-04-09 20:43:04,925 INFO L78 Accepts]: Start accepts. Automaton has 138 states. Word has length 387 [2018-04-09 20:43:04,925 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:43:04,928 INFO L225 Difference]: With dead ends: 1178 [2018-04-09 20:43:04,928 INFO L226 Difference]: Without dead ends: 883 [2018-04-09 20:43:04,931 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 884 GetRequests, 591 SyntacticMatches, 46 SemanticMatches, 247 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17938 ImplicationChecksByTransitivity, 6.8s TimeCoverageRelationStatistics Valid=8410, Invalid=53342, Unknown=0, NotChecked=0, Total=61752 [2018-04-09 20:43:04,932 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-09 20:43:04,944 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-09 20:43:04,944 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-09 20:43:04,945 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1113 transitions. [2018-04-09 20:43:04,945 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1113 transitions. Word has length 387 [2018-04-09 20:43:04,945 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:43:04,945 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1113 transitions. [2018-04-09 20:43:04,945 INFO L460 AbstractCegarLoop]: Interpolant automaton has 138 states. [2018-04-09 20:43:04,945 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1113 transitions. [2018-04-09 20:43:04,947 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 395 [2018-04-09 20:43:04,947 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:43:04,948 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-09 20:43:04,948 INFO L408 AbstractCegarLoop]: === Iteration 34 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:43:04,948 INFO L82 PathProgramCache]: Analyzing trace with hash 1547544253, 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-09 20:43:04,953 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:43:05,008 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:43:05,015 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:43:07,082 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-09 20:43:07,083 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:43:09,474 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-09 20:43:09,495 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:43:09,495 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [97, 97] total 144 [2018-04-09 20:43:09,496 INFO L442 AbstractCegarLoop]: Interpolant automaton has 144 states [2018-04-09 20:43:09,496 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 144 interpolants. [2018-04-09 20:43:09,497 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2495, Invalid=18097, Unknown=0, NotChecked=0, Total=20592 [2018-04-09 20:43:09,497 INFO L87 Difference]: Start difference. First operand 883 states and 1113 transitions. Second operand 144 states. [2018-04-09 20:43:14,547 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:43:14,547 INFO L93 Difference]: Finished difference Result 1178 states and 1470 transitions. [2018-04-09 20:43:14,547 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 166 states. [2018-04-09 20:43:14,548 INFO L78 Accepts]: Start accepts. Automaton has 144 states. Word has length 394 [2018-04-09 20:43:14,548 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:43:14,550 INFO L225 Difference]: With dead ends: 1178 [2018-04-09 20:43:14,551 INFO L226 Difference]: Without dead ends: 883 [2018-04-09 20:43:14,555 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 903 GetRequests, 597 SyntacticMatches, 48 SemanticMatches, 258 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19593 ImplicationChecksByTransitivity, 7.6s TimeCoverageRelationStatistics Valid=9148, Invalid=58192, Unknown=0, NotChecked=0, Total=67340 [2018-04-09 20:43:14,556 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-09 20:43:14,576 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-09 20:43:14,576 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-09 20:43:14,578 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1112 transitions. [2018-04-09 20:43:14,578 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1112 transitions. Word has length 394 [2018-04-09 20:43:14,578 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:43:14,578 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1112 transitions. [2018-04-09 20:43:14,579 INFO L460 AbstractCegarLoop]: Interpolant automaton has 144 states. [2018-04-09 20:43:14,579 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1112 transitions. [2018-04-09 20:43:14,582 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 402 [2018-04-09 20:43:14,582 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:43:14,582 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-09 20:43:14,583 INFO L408 AbstractCegarLoop]: === Iteration 35 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:43:14,583 INFO L82 PathProgramCache]: Analyzing trace with hash -1991887816, 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-09 20:43:14,592 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:43:14,637 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:43:14,642 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:43:16,654 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-09 20:43:16,655 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:43:19,157 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-09 20:43:19,177 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:43:19,177 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [101, 101] total 150 [2018-04-09 20:43:19,178 INFO L442 AbstractCegarLoop]: Interpolant automaton has 150 states [2018-04-09 20:43:19,178 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 150 interpolants. [2018-04-09 20:43:19,179 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2699, Invalid=19651, Unknown=0, NotChecked=0, Total=22350 [2018-04-09 20:43:19,179 INFO L87 Difference]: Start difference. First operand 883 states and 1112 transitions. Second operand 150 states. [2018-04-09 20:43:25,051 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:43:25,051 INFO L93 Difference]: Finished difference Result 1178 states and 1469 transitions. [2018-04-09 20:43:25,051 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 173 states. [2018-04-09 20:43:25,051 INFO L78 Accepts]: Start accepts. Automaton has 150 states. Word has length 401 [2018-04-09 20:43:25,052 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:43:25,056 INFO L225 Difference]: With dead ends: 1178 [2018-04-09 20:43:25,056 INFO L226 Difference]: Without dead ends: 883 [2018-04-09 20:43:25,060 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 922 GetRequests, 603 SyntacticMatches, 50 SemanticMatches, 269 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21321 ImplicationChecksByTransitivity, 8.0s TimeCoverageRelationStatistics Valid=9917, Invalid=63253, Unknown=0, NotChecked=0, Total=73170 [2018-04-09 20:43:25,061 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-09 20:43:25,080 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-09 20:43:25,080 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-09 20:43:25,082 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1111 transitions. [2018-04-09 20:43:25,083 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1111 transitions. Word has length 401 [2018-04-09 20:43:25,083 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:43:25,083 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1111 transitions. [2018-04-09 20:43:25,083 INFO L460 AbstractCegarLoop]: Interpolant automaton has 150 states. [2018-04-09 20:43:25,083 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1111 transitions. [2018-04-09 20:43:25,086 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 409 [2018-04-09 20:43:25,087 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:43:25,087 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-09 20:43:25,087 INFO L408 AbstractCegarLoop]: === Iteration 36 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:43:25,087 INFO L82 PathProgramCache]: Analyzing trace with hash 304453213, 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-09 20:43:25,093 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:43:25,139 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:43:25,144 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:43:27,282 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-09 20:43:27,282 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:43:29,997 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-09 20:43:30,018 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:43:30,033 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [105, 105] total 156 [2018-04-09 20:43:30,033 INFO L442 AbstractCegarLoop]: Interpolant automaton has 156 states [2018-04-09 20:43:30,034 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 156 interpolants. [2018-04-09 20:43:30,034 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2911, Invalid=21269, Unknown=0, NotChecked=0, Total=24180 [2018-04-09 20:43:30,035 INFO L87 Difference]: Start difference. First operand 883 states and 1111 transitions. Second operand 156 states. [2018-04-09 20:43:36,101 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:43:36,101 INFO L93 Difference]: Finished difference Result 1178 states and 1468 transitions. [2018-04-09 20:43:36,101 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 180 states. [2018-04-09 20:43:36,101 INFO L78 Accepts]: Start accepts. Automaton has 156 states. Word has length 408 [2018-04-09 20:43:36,102 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:43:36,104 INFO L225 Difference]: With dead ends: 1178 [2018-04-09 20:43:36,104 INFO L226 Difference]: Without dead ends: 883 [2018-04-09 20:43:36,108 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 941 GetRequests, 609 SyntacticMatches, 52 SemanticMatches, 280 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23122 ImplicationChecksByTransitivity, 8.6s TimeCoverageRelationStatistics Valid=10717, Invalid=68525, Unknown=0, NotChecked=0, Total=79242 [2018-04-09 20:43:36,108 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-09 20:43:36,120 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-09 20:43:36,121 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-09 20:43:36,122 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1110 transitions. [2018-04-09 20:43:36,122 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1110 transitions. Word has length 408 [2018-04-09 20:43:36,122 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:43:36,122 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1110 transitions. [2018-04-09 20:43:36,122 INFO L460 AbstractCegarLoop]: Interpolant automaton has 156 states. [2018-04-09 20:43:36,122 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1110 transitions. [2018-04-09 20:43:36,124 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 416 [2018-04-09 20:43:36,124 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:43:36,125 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-09 20:43:36,125 INFO L408 AbstractCegarLoop]: === Iteration 37 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:43:36,125 INFO L82 PathProgramCache]: Analyzing trace with hash -685805416, 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-09 20:43:36,132 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:43:36,185 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:43:36,190 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:43:38,498 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-09 20:43:38,498 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:43:41,416 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-09 20:43:41,437 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:43:41,438 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [109, 109] total 162 [2018-04-09 20:43:41,438 INFO L442 AbstractCegarLoop]: Interpolant automaton has 162 states [2018-04-09 20:43:41,439 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 162 interpolants. [2018-04-09 20:43:41,440 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3131, Invalid=22951, Unknown=0, NotChecked=0, Total=26082 [2018-04-09 20:43:41,440 INFO L87 Difference]: Start difference. First operand 883 states and 1110 transitions. Second operand 162 states. [2018-04-09 20:43:48,196 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:43:48,196 INFO L93 Difference]: Finished difference Result 1178 states and 1467 transitions. [2018-04-09 20:43:48,196 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 187 states. [2018-04-09 20:43:48,196 INFO L78 Accepts]: Start accepts. Automaton has 162 states. Word has length 415 [2018-04-09 20:43:48,197 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:43:48,199 INFO L225 Difference]: With dead ends: 1178 [2018-04-09 20:43:48,199 INFO L226 Difference]: Without dead ends: 883 [2018-04-09 20:43:48,203 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 960 GetRequests, 615 SyntacticMatches, 54 SemanticMatches, 291 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24996 ImplicationChecksByTransitivity, 9.3s TimeCoverageRelationStatistics Valid=11548, Invalid=74008, Unknown=0, NotChecked=0, Total=85556 [2018-04-09 20:43:48,204 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-09 20:43:48,223 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-09 20:43:48,224 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-09 20:43:48,225 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1109 transitions. [2018-04-09 20:43:48,226 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1109 transitions. Word has length 415 [2018-04-09 20:43:48,226 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:43:48,226 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1109 transitions. [2018-04-09 20:43:48,226 INFO L460 AbstractCegarLoop]: Interpolant automaton has 162 states. [2018-04-09 20:43:48,226 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1109 transitions. [2018-04-09 20:43:48,229 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 423 [2018-04-09 20:43:48,230 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:43:48,230 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-09 20:43:48,230 INFO L408 AbstractCegarLoop]: === Iteration 38 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:43:48,230 INFO L82 PathProgramCache]: Analyzing trace with hash -383668739, 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-09 20:43:48,236 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:43:48,285 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:43:48,290 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:43:50,718 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-09 20:43:50,719 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:43:53,826 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-09 20:43:53,847 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:43:53,858 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [113, 113] total 168 [2018-04-09 20:43:53,859 INFO L442 AbstractCegarLoop]: Interpolant automaton has 168 states [2018-04-09 20:43:53,859 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 168 interpolants. [2018-04-09 20:43:53,860 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3359, Invalid=24697, Unknown=0, NotChecked=0, Total=28056 [2018-04-09 20:43:53,860 INFO L87 Difference]: Start difference. First operand 883 states and 1109 transitions. Second operand 168 states. [2018-04-09 20:44:00,901 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:00,901 INFO L93 Difference]: Finished difference Result 1178 states and 1466 transitions. [2018-04-09 20:44:00,902 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 194 states. [2018-04-09 20:44:00,902 INFO L78 Accepts]: Start accepts. Automaton has 168 states. Word has length 422 [2018-04-09 20:44:00,902 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:00,905 INFO L225 Difference]: With dead ends: 1178 [2018-04-09 20:44:00,905 INFO L226 Difference]: Without dead ends: 883 [2018-04-09 20:44:00,908 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 979 GetRequests, 621 SyntacticMatches, 56 SemanticMatches, 302 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26943 ImplicationChecksByTransitivity, 9.9s TimeCoverageRelationStatistics Valid=12410, Invalid=79702, Unknown=0, NotChecked=0, Total=92112 [2018-04-09 20:44:00,909 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-09 20:44:00,921 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-09 20:44:00,921 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-09 20:44:00,923 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1108 transitions. [2018-04-09 20:44:00,923 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1108 transitions. Word has length 422 [2018-04-09 20:44:00,923 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:00,923 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1108 transitions. [2018-04-09 20:44:00,923 INFO L460 AbstractCegarLoop]: Interpolant automaton has 168 states. [2018-04-09 20:44:00,923 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1108 transitions. [2018-04-09 20:44:00,925 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 430 [2018-04-09 20:44:00,925 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:00,926 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-09 20:44:00,926 INFO L408 AbstractCegarLoop]: === Iteration 39 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:00,926 INFO L82 PathProgramCache]: Analyzing trace with hash -1805155080, 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-09 20:44:00,932 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:00,981 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:00,987 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:03,720 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-09 20:44:03,721 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:07,230 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-09 20:44:07,251 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:44:07,251 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [117, 117] total 174 [2018-04-09 20:44:07,251 INFO L442 AbstractCegarLoop]: Interpolant automaton has 174 states [2018-04-09 20:44:07,252 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 174 interpolants. [2018-04-09 20:44:07,253 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3595, Invalid=26507, Unknown=0, NotChecked=0, Total=30102 [2018-04-09 20:44:07,253 INFO L87 Difference]: Start difference. First operand 883 states and 1108 transitions. Second operand 174 states. [2018-04-09 20:44:14,819 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:14,819 INFO L93 Difference]: Finished difference Result 1178 states and 1465 transitions. [2018-04-09 20:44:14,819 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 201 states. [2018-04-09 20:44:14,819 INFO L78 Accepts]: Start accepts. Automaton has 174 states. Word has length 429 [2018-04-09 20:44:14,820 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:14,822 INFO L225 Difference]: With dead ends: 1178 [2018-04-09 20:44:14,822 INFO L226 Difference]: Without dead ends: 883 [2018-04-09 20:44:14,826 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 998 GetRequests, 627 SyntacticMatches, 58 SemanticMatches, 313 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28963 ImplicationChecksByTransitivity, 11.2s TimeCoverageRelationStatistics Valid=13303, Invalid=85607, Unknown=0, NotChecked=0, Total=98910 [2018-04-09 20:44:14,826 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-09 20:44:14,839 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-09 20:44:14,839 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-09 20:44:14,877 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1107 transitions. [2018-04-09 20:44:14,877 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1107 transitions. Word has length 429 [2018-04-09 20:44:14,877 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:14,877 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1107 transitions. [2018-04-09 20:44:14,877 INFO L460 AbstractCegarLoop]: Interpolant automaton has 174 states. [2018-04-09 20:44:14,877 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1107 transitions. [2018-04-09 20:44:14,879 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 437 [2018-04-09 20:44:14,880 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:14,880 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-09 20:44:14,880 INFO L408 AbstractCegarLoop]: === Iteration 40 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:14,880 INFO L82 PathProgramCache]: Analyzing trace with hash -1228149347, 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-09 20:44:14,886 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:14,946 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:14,951 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:18,097 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-09 20:44:18,097 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:21,800 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-09 20:44:21,821 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:44:21,822 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [121, 121] total 180 [2018-04-09 20:44:21,822 INFO L442 AbstractCegarLoop]: Interpolant automaton has 180 states [2018-04-09 20:44:21,823 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 180 interpolants. [2018-04-09 20:44:21,824 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3839, Invalid=28381, Unknown=0, NotChecked=0, Total=32220 [2018-04-09 20:44:21,824 INFO L87 Difference]: Start difference. First operand 883 states and 1107 transitions. Second operand 180 states. [2018-04-09 20:44:29,502 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-04-09 20:44:29,502 INFO L93 Difference]: Finished difference Result 1178 states and 1464 transitions. [2018-04-09 20:44:29,502 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 208 states. [2018-04-09 20:44:29,502 INFO L78 Accepts]: Start accepts. Automaton has 180 states. Word has length 436 [2018-04-09 20:44:29,503 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-04-09 20:44:29,505 INFO L225 Difference]: With dead ends: 1178 [2018-04-09 20:44:29,505 INFO L226 Difference]: Without dead ends: 883 [2018-04-09 20:44:29,509 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1017 GetRequests, 633 SyntacticMatches, 60 SemanticMatches, 324 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31056 ImplicationChecksByTransitivity, 12.1s TimeCoverageRelationStatistics Valid=14227, Invalid=91723, Unknown=0, NotChecked=0, Total=105950 [2018-04-09 20:44:29,509 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-04-09 20:44:29,521 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-04-09 20:44:29,521 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-04-09 20:44:29,522 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1106 transitions. [2018-04-09 20:44:29,522 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1106 transitions. Word has length 436 [2018-04-09 20:44:29,522 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-04-09 20:44:29,522 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1106 transitions. [2018-04-09 20:44:29,522 INFO L460 AbstractCegarLoop]: Interpolant automaton has 180 states. [2018-04-09 20:44:29,522 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1106 transitions. [2018-04-09 20:44:29,524 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 444 [2018-04-09 20:44:29,524 INFO L347 BasicCegarLoop]: Found error trace [2018-04-09 20:44:29,525 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-09 20:44:29,525 INFO L408 AbstractCegarLoop]: === Iteration 41 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-04-09 20:44:29,525 INFO L82 PathProgramCache]: Analyzing trace with hash 1245999448, 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-09 20:44:29,531 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-04-09 20:44:29,579 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-04-09 20:44:29,585 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-04-09 20:44:32,697 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-09 20:44:32,697 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-04-09 20:44:36,677 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-09 20:44:36,697 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-04-09 20:44:36,698 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [125, 125] total 186 [2018-04-09 20:44:36,698 INFO L442 AbstractCegarLoop]: Interpolant automaton has 186 states [2018-04-09 20:44:36,699 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 186 interpolants. [2018-04-09 20:44:36,700 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=4091, Invalid=30319, Unknown=0, NotChecked=0, Total=34410 [2018-04-09 20:44:36,700 INFO L87 Difference]: Start difference. First operand 883 states and 1106 transitions. Second operand 186 states. Received shutdown request... [2018-04-09 20:44:43,426 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 192 states. [2018-04-09 20:44:43,426 WARN L519 AbstractCegarLoop]: Verification canceled [2018-04-09 20:44:43,430 WARN L197 ceAbstractionStarter]: Timeout [2018-04-09 20:44:43,431 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 09.04 08:44:43 BoogieIcfgContainer [2018-04-09 20:44:43,431 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-04-09 20:44:43,431 INFO L168 Benchmark]: Toolchain (without parser) took 231865.20 ms. Allocated memory was 306.7 MB in the beginning and 1.2 GB in the end (delta: 858.3 MB). Free memory was 250.2 MB in the beginning and 434.8 MB in the end (delta: -184.6 MB). Peak memory consumption was 673.6 MB. Max. memory is 5.3 GB. [2018-04-09 20:44:43,432 INFO L168 Benchmark]: CDTParser took 0.23 ms. Allocated memory is still 306.7 MB. Free memory is still 269.0 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-04-09 20:44:43,433 INFO L168 Benchmark]: CACSL2BoogieTranslator took 201.15 ms. Allocated memory is still 306.7 MB. Free memory was 250.2 MB in the beginning and 240.2 MB in the end (delta: 10.1 MB). Peak memory consumption was 10.1 MB. Max. memory is 5.3 GB. [2018-04-09 20:44:43,433 INFO L168 Benchmark]: Boogie Preprocessor took 29.49 ms. Allocated memory is still 306.7 MB. Free memory was 240.2 MB in the beginning and 239.2 MB in the end (delta: 996.3 kB). Peak memory consumption was 996.3 kB. Max. memory is 5.3 GB. [2018-04-09 20:44:43,433 INFO L168 Benchmark]: RCFGBuilder took 259.44 ms. Allocated memory was 306.7 MB in the beginning and 467.7 MB in the end (delta: 161.0 MB). Free memory was 239.2 MB in the beginning and 435.2 MB in the end (delta: -196.0 MB). Peak memory consumption was 22.5 MB. Max. memory is 5.3 GB. [2018-04-09 20:44:43,433 INFO L168 Benchmark]: TraceAbstraction took 231371.30 ms. Allocated memory was 467.7 MB in the beginning and 1.2 GB in the end (delta: 697.3 MB). Free memory was 435.2 MB in the beginning and 434.8 MB in the end (delta: 361.9 kB). Peak memory consumption was 697.7 MB. Max. memory is 5.3 GB. [2018-04-09 20:44:43,435 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.23 ms. Allocated memory is still 306.7 MB. Free memory is still 269.0 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 201.15 ms. Allocated memory is still 306.7 MB. Free memory was 250.2 MB in the beginning and 240.2 MB in the end (delta: 10.1 MB). Peak memory consumption was 10.1 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 29.49 ms. Allocated memory is still 306.7 MB. Free memory was 240.2 MB in the beginning and 239.2 MB in the end (delta: 996.3 kB). Peak memory consumption was 996.3 kB. Max. memory is 5.3 GB. * RCFGBuilder took 259.44 ms. Allocated memory was 306.7 MB in the beginning and 467.7 MB in the end (delta: 161.0 MB). Free memory was 239.2 MB in the beginning and 435.2 MB in the end (delta: -196.0 MB). Peak memory consumption was 22.5 MB. Max. memory is 5.3 GB. * TraceAbstraction took 231371.30 ms. Allocated memory was 467.7 MB in the beginning and 1.2 GB in the end (delta: 697.3 MB). Free memory was 435.2 MB in the beginning and 434.8 MB in the end (delta: 361.9 kB). Peak memory consumption was 697.7 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 192 states, 186 states before enhancement), while ReachableStatesComputation was computing reachable states (948 states constructedinput type IntersectNwa). - 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 192 states, 186 states before enhancement), while ReachableStatesComputation was computing reachable states (948 states constructedinput type IntersectNwa). - 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 192 states, 186 states before enhancement), while ReachableStatesComputation was computing reachable states (948 states constructedinput type IntersectNwa). - 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 192 states, 186 states before enhancement), while ReachableStatesComputation was computing reachable states (948 states constructedinput type IntersectNwa). - StatisticsResult: Ultimate Automizer benchmark data CFG has 6 procedures, 51 locations, 4 error locations. TIMEOUT Result, 231.3s OverallTime, 41 OverallIterations, 32 TraceHistogramMax, 138.3s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 5298 SDtfs, 15350 SDslu, 103013 SDs, 0 SdLazy, 103034 SolverSat, 10646 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 30.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 20767 GetRequests, 13763 SyntacticMatches, 992 SemanticMatches, 6012 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 372630 ImplicationChecksByTransitivity, 179.2s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=883occurred in iteration=26, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.6s AutomataMinimizationTime, 40 MinimizatonAttempts, 135 StatesRemovedByMinimization, 12 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.2s SsaConstructionTime, 1.0s SatisfiabilityAnalysisTime, 89.3s 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_AutomizerC.xml/Csv-Benchmark-0-2018-04-09_20-44-43-445.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_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-0-2018-04-09_20-44-43-445.csv Completed graceful shutdown