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-4cf2d92 [2018-03-28 12:35:47,294 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-03-28 12:35:47,296 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-03-28 12:35:47,310 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-03-28 12:35:47,311 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-03-28 12:35:47,312 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-03-28 12:35:47,313 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-03-28 12:35:47,315 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-03-28 12:35:47,317 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-03-28 12:35:47,318 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-03-28 12:35:47,319 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-03-28 12:35:47,319 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-03-28 12:35:47,320 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-03-28 12:35:47,321 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-03-28 12:35:47,322 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-03-28 12:35:47,324 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-03-28 12:35:47,326 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-03-28 12:35:47,328 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-03-28 12:35:47,329 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-03-28 12:35:47,331 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-03-28 12:35:47,333 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-03-28 12:35:47,333 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-03-28 12:35:47,334 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-03-28 12:35:47,335 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-03-28 12:35:47,336 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-03-28 12:35:47,337 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-03-28 12:35:47,337 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-03-28 12:35:47,338 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-03-28 12:35:47,338 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-03-28 12:35:47,339 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-03-28 12:35:47,339 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-03-28 12:35:47,340 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-03-28 12:35:47,365 INFO L110 SettingsManager]: Loading preferences was successful [2018-03-28 12:35:47,365 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-03-28 12:35:47,366 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-03-28 12:35:47,366 INFO L133 SettingsManager]: * ultimate.logging.details=de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation=DEBUG; [2018-03-28 12:35:47,367 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-03-28 12:35:47,367 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-03-28 12:35:47,367 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-03-28 12:35:47,367 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-03-28 12:35:47,368 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-03-28 12:35:47,368 INFO L131 SettingsManager]: Preferences of LTL2Aut differ from their defaults: [2018-03-28 12:35:47,368 INFO L133 SettingsManager]: * Property to check=[] a a: x > 42 [2018-03-28 12:35:47,368 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-03-28 12:35:47,368 INFO L133 SettingsManager]: * sizeof long=4 [2018-03-28 12:35:47,369 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-03-28 12:35:47,369 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-03-28 12:35:47,369 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-03-28 12:35:47,369 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-03-28 12:35:47,369 INFO L133 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2018-03-28 12:35:47,370 INFO L133 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2018-03-28 12:35:47,370 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-03-28 12:35:47,370 INFO L133 SettingsManager]: * sizeof long double=12 [2018-03-28 12:35:47,370 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-03-28 12:35:47,370 INFO L133 SettingsManager]: * Size of a code block=SingleStatement [2018-03-28 12:35:47,371 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-03-28 12:35:47,371 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-03-28 12:35:47,371 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-03-28 12:35:47,371 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-03-28 12:35:47,371 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-03-28 12:35:47,372 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-03-28 12:35:47,372 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-03-28 12:35:47,372 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-03-28 12:35:47,372 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-28 12:35:47,372 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-03-28 12:35:47,373 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-03-28 12:35:47,373 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-03-28 12:35:47,374 INFO L131 SettingsManager]: Preferences of Boogie Printer differ from their defaults: [2018-03-28 12:35:47,374 INFO L133 SettingsManager]: * Dump path:=C:\Users\alex\AppData\Local\Temp\ [2018-03-28 12:35:47,410 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-03-28 12:35:47,422 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully (re)initialized [2018-03-28 12:35:47,426 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-03-28 12:35:47,428 INFO L271 PluginConnector]: Initializing CDTParser... [2018-03-28 12:35:47,429 INFO L276 PluginConnector]: CDTParser initialized [2018-03-28 12:35:47,429 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-03-28 12:35:47,767 INFO L228 CDTParser]: Created temporary CDT project at /storage/ultimate/releaseScripts/default/UAutomizer-linux/data/FLAGaed645f9e [2018-03-28 12:35:47,896 INFO L291 CDTParser]: IsIndexed: true [2018-03-28 12:35:47,897 INFO L292 CDTParser]: Found 1 translation units. [2018-03-28 12:35:47,897 INFO L171 CDTParser]: Scanning sanfoundry_24_false-valid-deref.i [2018-03-28 12:35:47,899 INFO L210 ultiparseSymbolTable]: Include resolver: [2018-03-28 12:35:47,899 INFO L215 ultiparseSymbolTable]: [2018-03-28 12:35:47,899 INFO L218 ultiparseSymbolTable]: Function table: [2018-03-28 12:35:47,899 INFO L221 ultiparseSymbolTable]: Function definition of __U_MULTI_fsanfoundry____false_valid_deref_i__printOdd ('printOdd') in sanfoundry_24_false-valid-deref.i [2018-03-28 12:35:47,899 INFO L221 ultiparseSymbolTable]: Function definition of null ('main') in sanfoundry_24_false-valid-deref.i [2018-03-28 12:35:47,899 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-03-28 12:35:47,900 INFO L221 ultiparseSymbolTable]: Function definition of __U_MULTI_fsanfoundry____false_valid_deref_i__printEven ('printEven') in sanfoundry_24_false-valid-deref.i [2018-03-28 12:35:47,900 INFO L227 ultiparseSymbolTable]: Global variable table: [2018-03-28 12:35:47,900 INFO L233 ultiparseSymbolTable]: [2018-03-28 12:35:47,915 INFO L334 CDTParser]: Deleted temporary CDT project at /storage/ultimate/releaseScripts/default/UAutomizer-linux/data/FLAGaed645f9e [2018-03-28 12:35:47,919 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-03-28 12:35:47,923 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-03-28 12:35:47,924 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-03-28 12:35:47,924 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-03-28 12:35:47,929 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-03-28 12:35:47,930 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.03 12:35:47" (1/1) ... [2018-03-28 12:35:47,932 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5f91555a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 12:35:47, skipping insertion in model container [2018-03-28 12:35:47,933 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.03 12:35:47" (1/1) ... [2018-03-28 12:35:47,947 INFO L167 Dispatcher]: Using SV-COMP mode [2018-03-28 12:35:47,959 INFO L167 Dispatcher]: Using SV-COMP mode [2018-03-28 12:35:48,092 INFO L175 PostProcessor]: Settings: Checked method=main [2018-03-28 12:35:48,107 INFO L175 PostProcessor]: Settings: Checked method=main [2018-03-28 12:35:48,111 INFO L100 SccComputation]: Graph consists of 0 InCaSumBalls and 8 non ball SCCs. Number of states in SCCs 8. [2018-03-28 12:35:48,118 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 12:35:48 WrapperNode [2018-03-28 12:35:48,118 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-03-28 12:35:48,119 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-03-28 12:35:48,119 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-03-28 12:35:48,119 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-03-28 12:35:48,129 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 12:35:48" (1/1) ... [2018-03-28 12:35:48,129 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 12:35:48" (1/1) ... [2018-03-28 12:35:48,136 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 12:35:48" (1/1) ... [2018-03-28 12:35:48,136 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 12:35:48" (1/1) ... [2018-03-28 12:35:48,139 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 12:35:48" (1/1) ... [2018-03-28 12:35:48,145 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 12:35:48" (1/1) ... [2018-03-28 12:35:48,146 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 12:35:48" (1/1) ... [2018-03-28 12:35:48,148 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-03-28 12:35:48,148 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-03-28 12:35:48,149 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-03-28 12:35:48,149 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-03-28 12:35:48,150 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 12:35:48" (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-03-28 12:35:48,204 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-03-28 12:35:48,205 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-03-28 12:35:48,205 INFO L136 BoogieDeclarations]: Found implementation of procedure __U_MULTI_fsanfoundry____false_valid_deref_i____VERIFIER_assert [2018-03-28 12:35:48,205 INFO L136 BoogieDeclarations]: Found implementation of procedure __U_MULTI_fsanfoundry____false_valid_deref_i__printEven [2018-03-28 12:35:48,205 INFO L136 BoogieDeclarations]: Found implementation of procedure __U_MULTI_fsanfoundry____false_valid_deref_i__printOdd [2018-03-28 12:35:48,205 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-03-28 12:35:48,205 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_error [2018-03-28 12:35:48,205 INFO L128 BoogieDeclarations]: Found specification of procedure __U_MULTI_fsanfoundry____false_valid_deref_i____VERIFIER_assert [2018-03-28 12:35:48,205 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-03-28 12:35:48,206 INFO L128 BoogieDeclarations]: Found specification of procedure __U_MULTI_fsanfoundry____false_valid_deref_i__printEven [2018-03-28 12:35:48,206 INFO L128 BoogieDeclarations]: Found specification of procedure __U_MULTI_fsanfoundry____false_valid_deref_i__printOdd [2018-03-28 12:35:48,206 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-03-28 12:35:48,206 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-03-28 12:35:48,206 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-03-28 12:35:48,423 INFO L259 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-03-28 12:35:48,424 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.03 12:35:48 BoogieIcfgContainer [2018-03-28 12:35:48,424 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-03-28 12:35:48,425 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-03-28 12:35:48,425 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-03-28 12:35:48,427 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-03-28 12:35:48,427 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 28.03 12:35:47" (1/3) ... [2018-03-28 12:35:48,428 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5f048d64 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 28.03 12:35:48, skipping insertion in model container [2018-03-28 12:35:48,428 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 12:35:48" (2/3) ... [2018-03-28 12:35:48,428 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5f048d64 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 28.03 12:35:48, skipping insertion in model container [2018-03-28 12:35:48,428 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.03 12:35:48" (3/3) ... [2018-03-28 12:35:48,430 INFO L107 eAbstractionObserver]: Analyzing ICFG sanfoundry_24_false-valid-deref.i [2018-03-28 12:35:48,437 INFO L131 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-03-28 12:35:48,442 INFO L143 ceAbstractionStarter]: Appying trace abstraction to program that has 4 error locations. [2018-03-28 12:35:48,481 INFO L128 ementStrategyFactory]: Using default assertion order modulation [2018-03-28 12:35:48,482 INFO L369 AbstractCegarLoop]: Interprodecural is true [2018-03-28 12:35:48,482 INFO L370 AbstractCegarLoop]: Hoare is true [2018-03-28 12:35:48,482 INFO L371 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-03-28 12:35:48,482 INFO L372 AbstractCegarLoop]: Backedges is TWOTRACK [2018-03-28 12:35:48,483 INFO L373 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-03-28 12:35:48,483 INFO L374 AbstractCegarLoop]: Difference is false [2018-03-28 12:35:48,483 INFO L375 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-03-28 12:35:48,483 INFO L380 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-03-28 12:35:48,484 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-03-28 12:35:48,501 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states. [2018-03-28 12:35:48,505 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2018-03-28 12:35:48,505 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:35:48,506 INFO L355 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-28 12:35:48,506 INFO L408 AbstractCegarLoop]: === Iteration 1 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:35:48,511 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-03-28 12:35:48,524 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:35:48,544 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:35:48,551 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:35:48,572 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-28 12:35:48,573 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:35:48,607 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-28 12:35:48,630 INFO L320 seRefinementStrategy]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2018-03-28 12:35:48,630 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2, 2] imperfect sequences [] total 3 [2018-03-28 12:35:48,631 INFO L442 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-03-28 12:35:48,641 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-03-28 12:35:48,641 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-03-28 12:35:48,643 INFO L87 Difference]: Start difference. First operand 51 states. Second operand 4 states. [2018-03-28 12:35:48,767 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:35:48,768 INFO L93 Difference]: Finished difference Result 112 states and 144 transitions. [2018-03-28 12:35:48,768 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-03-28 12:35:48,770 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 13 [2018-03-28 12:35:48,770 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:35:48,780 INFO L225 Difference]: With dead ends: 112 [2018-03-28 12:35:48,780 INFO L226 Difference]: Without dead ends: 62 [2018-03-28 12:35:48,784 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-03-28 12:35:48,799 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2018-03-28 12:35:48,822 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 55. [2018-03-28 12:35:48,823 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 55 states. [2018-03-28 12:35:48,825 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 62 transitions. [2018-03-28 12:35:48,826 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 62 transitions. Word has length 13 [2018-03-28 12:35:48,827 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:35:48,827 INFO L459 AbstractCegarLoop]: Abstraction has 55 states and 62 transitions. [2018-03-28 12:35:48,827 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-03-28 12:35:48,827 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 62 transitions. [2018-03-28 12:35:48,829 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-03-28 12:35:48,829 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:35:48,830 INFO L355 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-28 12:35:48,830 INFO L408 AbstractCegarLoop]: === Iteration 2 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:35:48,830 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-03-28 12:35:48,838 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:35:48,847 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:35:48,850 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:35:48,876 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-28 12:35:48,876 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:35:48,981 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-28 12:35:49,002 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:35:49,003 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 7 [2018-03-28 12:35:49,004 INFO L442 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-03-28 12:35:49,004 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-03-28 12:35:49,004 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-03-28 12:35:49,005 INFO L87 Difference]: Start difference. First operand 55 states and 62 transitions. Second operand 8 states. [2018-03-28 12:35:49,242 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:35:49,242 INFO L93 Difference]: Finished difference Result 84 states and 101 transitions. [2018-03-28 12:35:49,243 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-03-28 12:35:49,243 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 20 [2018-03-28 12:35:49,243 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:35:49,245 INFO L225 Difference]: With dead ends: 84 [2018-03-28 12:35:49,245 INFO L226 Difference]: Without dead ends: 82 [2018-03-28 12:35:49,246 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-03-28 12:35:49,246 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2018-03-28 12:35:49,255 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 73. [2018-03-28 12:35:49,256 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 73 states. [2018-03-28 12:35:49,258 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 86 transitions. [2018-03-28 12:35:49,258 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 86 transitions. Word has length 20 [2018-03-28 12:35:49,258 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:35:49,258 INFO L459 AbstractCegarLoop]: Abstraction has 73 states and 86 transitions. [2018-03-28 12:35:49,258 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-03-28 12:35:49,259 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 86 transitions. [2018-03-28 12:35:49,260 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2018-03-28 12:35:49,260 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:35:49,260 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-03-28 12:35:49,260 INFO L408 AbstractCegarLoop]: === Iteration 3 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:35:49,261 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-03-28 12:35:49,272 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:35:49,282 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:35:49,284 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:35:49,306 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-03-28 12:35:49,306 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:35:49,326 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-03-28 12:35:49,347 INFO L320 seRefinementStrategy]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2018-03-28 12:35:49,347 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5, 5] imperfect sequences [] total 6 [2018-03-28 12:35:49,347 INFO L442 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-03-28 12:35:49,347 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-03-28 12:35:49,347 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2018-03-28 12:35:49,348 INFO L87 Difference]: Start difference. First operand 73 states and 86 transitions. Second operand 6 states. [2018-03-28 12:35:49,486 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:35:49,486 INFO L93 Difference]: Finished difference Result 101 states and 117 transitions. [2018-03-28 12:35:49,489 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-03-28 12:35:49,489 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 23 [2018-03-28 12:35:49,490 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:35:49,491 INFO L225 Difference]: With dead ends: 101 [2018-03-28 12:35:49,491 INFO L226 Difference]: Without dead ends: 76 [2018-03-28 12:35:49,492 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-03-28 12:35:49,492 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2018-03-28 12:35:49,502 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 73. [2018-03-28 12:35:49,502 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 73 states. [2018-03-28 12:35:49,503 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 85 transitions. [2018-03-28 12:35:49,504 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 85 transitions. Word has length 23 [2018-03-28 12:35:49,504 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:35:49,504 INFO L459 AbstractCegarLoop]: Abstraction has 73 states and 85 transitions. [2018-03-28 12:35:49,504 INFO L460 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-03-28 12:35:49,505 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 85 transitions. [2018-03-28 12:35:49,506 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2018-03-28 12:35:49,506 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:35:49,506 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-03-28 12:35:49,506 INFO L408 AbstractCegarLoop]: === Iteration 4 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:35:49,507 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-03-28 12:35:49,513 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:35:49,522 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:35:49,524 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:35:49,635 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 3 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-28 12:35:49,635 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:35:49,709 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 3 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-28 12:35:49,729 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:35:49,729 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 12 [2018-03-28 12:35:49,730 INFO L442 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-03-28 12:35:49,730 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-03-28 12:35:49,730 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=101, Unknown=0, NotChecked=0, Total=132 [2018-03-28 12:35:49,731 INFO L87 Difference]: Start difference. First operand 73 states and 85 transitions. Second operand 12 states. [2018-03-28 12:35:49,932 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:35:49,932 INFO L93 Difference]: Finished difference Result 107 states and 123 transitions. [2018-03-28 12:35:49,933 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-03-28 12:35:49,933 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 30 [2018-03-28 12:35:49,933 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:35:49,934 INFO L225 Difference]: With dead ends: 107 [2018-03-28 12:35:49,934 INFO L226 Difference]: Without dead ends: 76 [2018-03-28 12:35:49,935 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 45 SyntacticMatches, 4 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 46 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=73, Invalid=233, Unknown=0, NotChecked=0, Total=306 [2018-03-28 12:35:49,935 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2018-03-28 12:35:49,943 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 73. [2018-03-28 12:35:49,943 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 73 states. [2018-03-28 12:35:49,946 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 84 transitions. [2018-03-28 12:35:49,946 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 84 transitions. Word has length 30 [2018-03-28 12:35:49,947 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:35:49,947 INFO L459 AbstractCegarLoop]: Abstraction has 73 states and 84 transitions. [2018-03-28 12:35:49,947 INFO L460 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-03-28 12:35:49,947 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 84 transitions. [2018-03-28 12:35:49,948 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2018-03-28 12:35:49,949 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:35:49,949 INFO L355 BasicCegarLoop]: trace histogram [4, 4, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-28 12:35:49,949 INFO L408 AbstractCegarLoop]: === Iteration 5 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:35:49,949 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-03-28 12:35:49,956 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:35:49,965 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:35:49,967 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:35:50,077 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 0 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-28 12:35:50,077 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:35:50,214 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 0 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-28 12:35:50,249 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:35:50,249 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 15 [2018-03-28 12:35:50,250 INFO L442 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-03-28 12:35:50,251 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-03-28 12:35:50,251 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=186, Unknown=0, NotChecked=0, Total=240 [2018-03-28 12:35:50,252 INFO L87 Difference]: Start difference. First operand 73 states and 84 transitions. Second operand 16 states. [2018-03-28 12:35:50,791 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:35:50,791 INFO L93 Difference]: Finished difference Result 122 states and 153 transitions. [2018-03-28 12:35:50,792 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-03-28 12:35:50,792 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 34 [2018-03-28 12:35:50,792 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:35:50,793 INFO L225 Difference]: With dead ends: 122 [2018-03-28 12:35:50,793 INFO L226 Difference]: Without dead ends: 120 [2018-03-28 12:35:50,794 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-03-28 12:35:50,794 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 120 states. [2018-03-28 12:35:50,801 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 120 to 109. [2018-03-28 12:35:50,801 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 109 states. [2018-03-28 12:35:50,802 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 132 transitions. [2018-03-28 12:35:50,803 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 132 transitions. Word has length 34 [2018-03-28 12:35:50,803 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:35:50,803 INFO L459 AbstractCegarLoop]: Abstraction has 109 states and 132 transitions. [2018-03-28 12:35:50,803 INFO L460 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-03-28 12:35:50,803 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 132 transitions. [2018-03-28 12:35:50,805 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2018-03-28 12:35:50,805 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:35:50,805 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-03-28 12:35:50,805 INFO L408 AbstractCegarLoop]: === Iteration 6 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:35:50,805 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-03-28 12:35:50,815 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:35:50,823 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:35:50,825 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:35:50,839 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2018-03-28 12:35:50,840 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:35:50,883 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2018-03-28 12:35:50,904 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:35:50,904 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 7 [2018-03-28 12:35:50,904 INFO L442 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-03-28 12:35:50,904 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-03-28 12:35:50,905 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-03-28 12:35:50,905 INFO L87 Difference]: Start difference. First operand 109 states and 132 transitions. Second operand 8 states. [2018-03-28 12:35:50,984 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:35:50,984 INFO L93 Difference]: Finished difference Result 132 states and 162 transitions. [2018-03-28 12:35:50,984 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-03-28 12:35:50,985 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 37 [2018-03-28 12:35:50,985 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:35:50,986 INFO L225 Difference]: With dead ends: 132 [2018-03-28 12:35:50,986 INFO L226 Difference]: Without dead ends: 130 [2018-03-28 12:35:50,986 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-03-28 12:35:50,986 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2018-03-28 12:35:50,993 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 127. [2018-03-28 12:35:50,993 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 127 states. [2018-03-28 12:35:50,994 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 154 transitions. [2018-03-28 12:35:50,994 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 154 transitions. Word has length 37 [2018-03-28 12:35:50,994 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:35:50,995 INFO L459 AbstractCegarLoop]: Abstraction has 127 states and 154 transitions. [2018-03-28 12:35:50,995 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-03-28 12:35:50,995 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 154 transitions. [2018-03-28 12:35:50,996 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2018-03-28 12:35:50,996 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:35:50,996 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-03-28 12:35:50,996 INFO L408 AbstractCegarLoop]: === Iteration 7 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:35:50,997 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-03-28 12:35:51,003 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:35:51,013 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:35:51,015 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:35:51,075 INFO L134 CoverageAnalysis]: Checked inductivity of 41 backedges. 29 proven. 11 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-03-28 12:35:51,075 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:35:51,136 INFO L134 CoverageAnalysis]: Checked inductivity of 41 backedges. 29 proven. 11 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-03-28 12:35:51,157 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:35:51,157 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 18 [2018-03-28 12:35:51,157 INFO L442 AbstractCegarLoop]: Interpolant automaton has 18 states [2018-03-28 12:35:51,158 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2018-03-28 12:35:51,158 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=59, Invalid=247, Unknown=0, NotChecked=0, Total=306 [2018-03-28 12:35:51,158 INFO L87 Difference]: Start difference. First operand 127 states and 154 transitions. Second operand 18 states. [2018-03-28 12:35:51,481 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:35:51,482 INFO L93 Difference]: Finished difference Result 170 states and 203 transitions. [2018-03-28 12:35:51,482 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-03-28 12:35:51,482 INFO L78 Accepts]: Start accepts. Automaton has 18 states. Word has length 51 [2018-03-28 12:35:51,483 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:35:51,483 INFO L225 Difference]: With dead ends: 170 [2018-03-28 12:35:51,484 INFO L226 Difference]: Without dead ends: 127 [2018-03-28 12:35:51,485 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-03-28 12:35:51,485 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states. [2018-03-28 12:35:51,495 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 127. [2018-03-28 12:35:51,495 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 127 states. [2018-03-28 12:35:51,497 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 153 transitions. [2018-03-28 12:35:51,497 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 153 transitions. Word has length 51 [2018-03-28 12:35:51,497 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:35:51,497 INFO L459 AbstractCegarLoop]: Abstraction has 127 states and 153 transitions. [2018-03-28 12:35:51,497 INFO L460 AbstractCegarLoop]: Interpolant automaton has 18 states. [2018-03-28 12:35:51,498 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 153 transitions. [2018-03-28 12:35:51,500 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2018-03-28 12:35:51,500 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:35:51,500 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-03-28 12:35:51,500 INFO L408 AbstractCegarLoop]: === Iteration 8 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:35:51,500 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-03-28 12:35:51,513 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:35:51,526 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:35:51,529 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:35:51,648 INFO L134 CoverageAnalysis]: Checked inductivity of 57 backedges. 30 proven. 27 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-28 12:35:51,648 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:35:51,751 INFO L134 CoverageAnalysis]: Checked inductivity of 57 backedges. 30 proven. 27 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-28 12:35:51,771 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:35:51,772 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17] total 24 [2018-03-28 12:35:51,772 INFO L442 AbstractCegarLoop]: Interpolant automaton has 24 states [2018-03-28 12:35:51,772 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2018-03-28 12:35:51,772 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=95, Invalid=457, Unknown=0, NotChecked=0, Total=552 [2018-03-28 12:35:51,773 INFO L87 Difference]: Start difference. First operand 127 states and 153 transitions. Second operand 24 states. [2018-03-28 12:35:52,074 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:35:52,075 INFO L93 Difference]: Finished difference Result 176 states and 209 transitions. [2018-03-28 12:35:52,075 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2018-03-28 12:35:52,075 INFO L78 Accepts]: Start accepts. Automaton has 24 states. Word has length 58 [2018-03-28 12:35:52,075 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:35:52,076 INFO L225 Difference]: With dead ends: 176 [2018-03-28 12:35:52,076 INFO L226 Difference]: Without dead ends: 127 [2018-03-28 12:35:52,077 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-03-28 12:35:52,078 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states. [2018-03-28 12:35:52,087 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 127. [2018-03-28 12:35:52,087 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 127 states. [2018-03-28 12:35:52,088 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 152 transitions. [2018-03-28 12:35:52,089 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 152 transitions. Word has length 58 [2018-03-28 12:35:52,089 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:35:52,089 INFO L459 AbstractCegarLoop]: Abstraction has 127 states and 152 transitions. [2018-03-28 12:35:52,089 INFO L460 AbstractCegarLoop]: Interpolant automaton has 24 states. [2018-03-28 12:35:52,089 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 152 transitions. [2018-03-28 12:35:52,091 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2018-03-28 12:35:52,091 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:35:52,091 INFO L355 BasicCegarLoop]: trace histogram [8, 8, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-28 12:35:52,091 INFO L408 AbstractCegarLoop]: === Iteration 9 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:35:52,091 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-03-28 12:35:52,097 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:35:52,108 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:35:52,111 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:35:52,230 INFO L134 CoverageAnalysis]: Checked inductivity of 168 backedges. 0 proven. 168 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-28 12:35:52,230 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:35:52,564 INFO L134 CoverageAnalysis]: Checked inductivity of 168 backedges. 0 proven. 168 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-28 12:35:52,586 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:35:52,586 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 31 [2018-03-28 12:35:52,586 INFO L442 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-03-28 12:35:52,586 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-03-28 12:35:52,587 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=174, Invalid=818, Unknown=0, NotChecked=0, Total=992 [2018-03-28 12:35:52,587 INFO L87 Difference]: Start difference. First operand 127 states and 152 transitions. Second operand 32 states. [2018-03-28 12:35:53,823 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:35:53,823 INFO L93 Difference]: Finished difference Result 215 states and 279 transitions. [2018-03-28 12:35:53,824 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2018-03-28 12:35:53,824 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 62 [2018-03-28 12:35:53,824 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:35:53,825 INFO L225 Difference]: With dead ends: 215 [2018-03-28 12:35:53,825 INFO L226 Difference]: Without dead ends: 213 [2018-03-28 12:35:53,826 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-03-28 12:35:53,826 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 213 states. [2018-03-28 12:35:53,835 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 213 to 199. [2018-03-28 12:35:53,835 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 199 states. [2018-03-28 12:35:53,837 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 199 states to 199 states and 248 transitions. [2018-03-28 12:35:53,837 INFO L78 Accepts]: Start accepts. Automaton has 199 states and 248 transitions. Word has length 62 [2018-03-28 12:35:53,837 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:35:53,837 INFO L459 AbstractCegarLoop]: Abstraction has 199 states and 248 transitions. [2018-03-28 12:35:53,837 INFO L460 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-03-28 12:35:53,837 INFO L276 IsEmpty]: Start isEmpty. Operand 199 states and 248 transitions. [2018-03-28 12:35:53,838 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2018-03-28 12:35:53,838 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:35:53,838 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-03-28 12:35:53,838 INFO L408 AbstractCegarLoop]: === Iteration 10 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:35:53,839 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-03-28 12:35:53,845 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:35:53,857 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:35:53,859 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:35:53,894 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 0 proven. 30 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2018-03-28 12:35:53,894 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:35:53,960 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 0 proven. 30 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2018-03-28 12:35:53,990 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:35:53,990 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 15 [2018-03-28 12:35:53,990 INFO L442 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-03-28 12:35:53,991 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-03-28 12:35:53,991 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=186, Unknown=0, NotChecked=0, Total=240 [2018-03-28 12:35:53,991 INFO L87 Difference]: Start difference. First operand 199 states and 248 transitions. Second operand 16 states. [2018-03-28 12:35:54,291 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:35:54,292 INFO L93 Difference]: Finished difference Result 240 states and 304 transitions. [2018-03-28 12:35:54,292 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-03-28 12:35:54,292 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 65 [2018-03-28 12:35:54,293 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:35:54,294 INFO L225 Difference]: With dead ends: 240 [2018-03-28 12:35:54,294 INFO L226 Difference]: Without dead ends: 238 [2018-03-28 12:35:54,295 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-03-28 12:35:54,295 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 238 states. [2018-03-28 12:35:54,304 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 238 to 235. [2018-03-28 12:35:54,305 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 235 states. [2018-03-28 12:35:54,306 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 292 transitions. [2018-03-28 12:35:54,306 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 292 transitions. Word has length 65 [2018-03-28 12:35:54,306 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:35:54,307 INFO L459 AbstractCegarLoop]: Abstraction has 235 states and 292 transitions. [2018-03-28 12:35:54,307 INFO L460 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-03-28 12:35:54,307 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 292 transitions. [2018-03-28 12:35:54,309 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2018-03-28 12:35:54,309 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:35:54,309 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-03-28 12:35:54,309 INFO L408 AbstractCegarLoop]: === Iteration 11 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:35:54,309 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-03-28 12:35:54,316 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:35:54,329 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:35:54,332 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:35:54,476 INFO L134 CoverageAnalysis]: Checked inductivity of 218 backedges. 144 proven. 50 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2018-03-28 12:35:54,477 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:35:54,725 INFO L134 CoverageAnalysis]: Checked inductivity of 218 backedges. 144 proven. 50 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2018-03-28 12:35:54,746 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:35:54,763 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21] total 30 [2018-03-28 12:35:54,764 INFO L442 AbstractCegarLoop]: Interpolant automaton has 30 states [2018-03-28 12:35:54,764 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2018-03-28 12:35:54,764 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=139, Invalid=731, Unknown=0, NotChecked=0, Total=870 [2018-03-28 12:35:54,765 INFO L87 Difference]: Start difference. First operand 235 states and 292 transitions. Second operand 30 states. [2018-03-28 12:35:55,207 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:35:55,207 INFO L93 Difference]: Finished difference Result 314 states and 385 transitions. [2018-03-28 12:35:55,207 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-03-28 12:35:55,207 INFO L78 Accepts]: Start accepts. Automaton has 30 states. Word has length 93 [2018-03-28 12:35:55,207 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:35:55,209 INFO L225 Difference]: With dead ends: 314 [2018-03-28 12:35:55,209 INFO L226 Difference]: Without dead ends: 235 [2018-03-28 12:35:55,210 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-03-28 12:35:55,210 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 235 states. [2018-03-28 12:35:55,219 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 235 to 235. [2018-03-28 12:35:55,219 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 235 states. [2018-03-28 12:35:55,221 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 291 transitions. [2018-03-28 12:35:55,221 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 291 transitions. Word has length 93 [2018-03-28 12:35:55,222 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:35:55,222 INFO L459 AbstractCegarLoop]: Abstraction has 235 states and 291 transitions. [2018-03-28 12:35:55,222 INFO L460 AbstractCegarLoop]: Interpolant automaton has 30 states. [2018-03-28 12:35:55,222 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 291 transitions. [2018-03-28 12:35:55,224 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 101 [2018-03-28 12:35:55,224 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:35:55,224 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-03-28 12:35:55,224 INFO L408 AbstractCegarLoop]: === Iteration 12 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:35:55,224 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-03-28 12:35:55,234 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:35:55,253 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:35:55,255 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:35:55,454 INFO L134 CoverageAnalysis]: Checked inductivity of 248 backedges. 159 proven. 80 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2018-03-28 12:35:55,454 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:35:55,622 INFO L134 CoverageAnalysis]: Checked inductivity of 248 backedges. 159 proven. 80 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2018-03-28 12:35:55,643 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:35:55,643 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 25] total 36 [2018-03-28 12:35:55,643 INFO L442 AbstractCegarLoop]: Interpolant automaton has 36 states [2018-03-28 12:35:55,643 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2018-03-28 12:35:55,644 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=191, Invalid=1069, Unknown=0, NotChecked=0, Total=1260 [2018-03-28 12:35:55,644 INFO L87 Difference]: Start difference. First operand 235 states and 291 transitions. Second operand 36 states. [2018-03-28 12:35:56,125 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:35:56,125 INFO L93 Difference]: Finished difference Result 314 states and 384 transitions. [2018-03-28 12:35:56,125 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2018-03-28 12:35:56,125 INFO L78 Accepts]: Start accepts. Automaton has 36 states. Word has length 100 [2018-03-28 12:35:56,126 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:35:56,127 INFO L225 Difference]: With dead ends: 314 [2018-03-28 12:35:56,127 INFO L226 Difference]: Without dead ends: 235 [2018-03-28 12:35:56,128 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-03-28 12:35:56,128 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 235 states. [2018-03-28 12:35:56,138 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 235 to 235. [2018-03-28 12:35:56,138 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 235 states. [2018-03-28 12:35:56,140 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 290 transitions. [2018-03-28 12:35:56,141 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 290 transitions. Word has length 100 [2018-03-28 12:35:56,141 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:35:56,141 INFO L459 AbstractCegarLoop]: Abstraction has 235 states and 290 transitions. [2018-03-28 12:35:56,141 INFO L460 AbstractCegarLoop]: Interpolant automaton has 36 states. [2018-03-28 12:35:56,141 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 290 transitions. [2018-03-28 12:35:56,143 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2018-03-28 12:35:56,143 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:35:56,144 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-03-28 12:35:56,144 INFO L408 AbstractCegarLoop]: === Iteration 13 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:35:56,144 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-03-28 12:35:56,155 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:35:56,181 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:35:56,184 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:35:56,577 INFO L134 CoverageAnalysis]: Checked inductivity of 285 backedges. 167 proven. 117 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-03-28 12:35:56,578 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:35:56,828 INFO L134 CoverageAnalysis]: Checked inductivity of 285 backedges. 167 proven. 117 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-03-28 12:35:56,848 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:35:56,848 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [29, 29] total 42 [2018-03-28 12:35:56,849 INFO L442 AbstractCegarLoop]: Interpolant automaton has 42 states [2018-03-28 12:35:56,849 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 42 interpolants. [2018-03-28 12:35:56,849 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=251, Invalid=1471, Unknown=0, NotChecked=0, Total=1722 [2018-03-28 12:35:56,850 INFO L87 Difference]: Start difference. First operand 235 states and 290 transitions. Second operand 42 states. [2018-03-28 12:35:57,584 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:35:57,584 INFO L93 Difference]: Finished difference Result 314 states and 383 transitions. [2018-03-28 12:35:57,584 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 47 states. [2018-03-28 12:35:57,584 INFO L78 Accepts]: Start accepts. Automaton has 42 states. Word has length 107 [2018-03-28 12:35:57,585 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:35:57,586 INFO L225 Difference]: With dead ends: 314 [2018-03-28 12:35:57,586 INFO L226 Difference]: Without dead ends: 235 [2018-03-28 12:35:57,588 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-03-28 12:35:57,588 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 235 states. [2018-03-28 12:35:57,594 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 235 to 235. [2018-03-28 12:35:57,594 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 235 states. [2018-03-28 12:35:57,595 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 289 transitions. [2018-03-28 12:35:57,595 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 289 transitions. Word has length 107 [2018-03-28 12:35:57,595 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:35:57,595 INFO L459 AbstractCegarLoop]: Abstraction has 235 states and 289 transitions. [2018-03-28 12:35:57,595 INFO L460 AbstractCegarLoop]: Interpolant automaton has 42 states. [2018-03-28 12:35:57,595 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 289 transitions. [2018-03-28 12:35:57,597 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 115 [2018-03-28 12:35:57,597 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:35:57,597 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-03-28 12:35:57,597 INFO L408 AbstractCegarLoop]: === Iteration 14 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:35:57,597 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-03-28 12:35:57,614 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:35:57,638 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:35:57,642 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:35:58,183 INFO L134 CoverageAnalysis]: Checked inductivity of 329 backedges. 168 proven. 161 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-28 12:35:58,184 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:35:58,483 INFO L134 CoverageAnalysis]: Checked inductivity of 329 backedges. 168 proven. 161 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-28 12:35:58,504 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:35:58,504 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [33, 33] total 48 [2018-03-28 12:35:58,505 INFO L442 AbstractCegarLoop]: Interpolant automaton has 48 states [2018-03-28 12:35:58,505 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 48 interpolants. [2018-03-28 12:35:58,505 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=319, Invalid=1937, Unknown=0, NotChecked=0, Total=2256 [2018-03-28 12:35:58,506 INFO L87 Difference]: Start difference. First operand 235 states and 289 transitions. Second operand 48 states. [2018-03-28 12:35:59,269 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:35:59,269 INFO L93 Difference]: Finished difference Result 320 states and 389 transitions. [2018-03-28 12:35:59,269 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 54 states. [2018-03-28 12:35:59,269 INFO L78 Accepts]: Start accepts. Automaton has 48 states. Word has length 114 [2018-03-28 12:35:59,270 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:35:59,271 INFO L225 Difference]: With dead ends: 320 [2018-03-28 12:35:59,271 INFO L226 Difference]: Without dead ends: 235 [2018-03-28 12:35:59,273 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 263 GetRequests, 165 SyntacticMatches, 16 SemanticMatches, 82 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1873 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=1060, Invalid=5912, Unknown=0, NotChecked=0, Total=6972 [2018-03-28 12:35:59,273 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 235 states. [2018-03-28 12:35:59,280 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 235 to 235. [2018-03-28 12:35:59,280 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 235 states. [2018-03-28 12:35:59,281 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 288 transitions. [2018-03-28 12:35:59,281 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 288 transitions. Word has length 114 [2018-03-28 12:35:59,281 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:35:59,281 INFO L459 AbstractCegarLoop]: Abstraction has 235 states and 288 transitions. [2018-03-28 12:35:59,282 INFO L460 AbstractCegarLoop]: Interpolant automaton has 48 states. [2018-03-28 12:35:59,282 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 288 transitions. [2018-03-28 12:35:59,283 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 119 [2018-03-28 12:35:59,283 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:35:59,283 INFO L355 BasicCegarLoop]: trace histogram [16, 16, 15, 15, 15, 15, 15, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-28 12:35:59,283 INFO L408 AbstractCegarLoop]: === Iteration 15 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:35:59,284 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-03-28 12:35:59,299 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:35:59,316 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:35:59,319 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:35:59,726 INFO L134 CoverageAnalysis]: Checked inductivity of 780 backedges. 0 proven. 780 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-28 12:35:59,727 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:36:00,614 INFO L134 CoverageAnalysis]: Checked inductivity of 780 backedges. 0 proven. 780 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-28 12:36:00,635 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:36:00,635 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [32, 32] total 63 [2018-03-28 12:36:00,635 INFO L442 AbstractCegarLoop]: Interpolant automaton has 64 states [2018-03-28 12:36:00,636 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 64 interpolants. [2018-03-28 12:36:00,636 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=606, Invalid=3426, Unknown=0, NotChecked=0, Total=4032 [2018-03-28 12:36:00,636 INFO L87 Difference]: Start difference. First operand 235 states and 288 transitions. Second operand 64 states. [2018-03-28 12:36:06,082 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:36:06,082 INFO L93 Difference]: Finished difference Result 407 states and 539 transitions. [2018-03-28 12:36:06,082 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 93 states. [2018-03-28 12:36:06,082 INFO L78 Accepts]: Start accepts. Automaton has 64 states. Word has length 118 [2018-03-28 12:36:06,083 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:36:06,084 INFO L225 Difference]: With dead ends: 407 [2018-03-28 12:36:06,084 INFO L226 Difference]: Without dead ends: 405 [2018-03-28 12:36:06,088 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 309 GetRequests, 173 SyntacticMatches, 0 SemanticMatches, 136 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3452 ImplicationChecksByTransitivity, 5.0s TimeCoverageRelationStatistics Valid=4624, Invalid=14282, Unknown=0, NotChecked=0, Total=18906 [2018-03-28 12:36:06,088 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 405 states. [2018-03-28 12:36:06,099 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 405 to 379. [2018-03-28 12:36:06,099 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 379 states. [2018-03-28 12:36:06,102 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 379 states to 379 states and 480 transitions. [2018-03-28 12:36:06,102 INFO L78 Accepts]: Start accepts. Automaton has 379 states and 480 transitions. Word has length 118 [2018-03-28 12:36:06,102 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:36:06,102 INFO L459 AbstractCegarLoop]: Abstraction has 379 states and 480 transitions. [2018-03-28 12:36:06,103 INFO L460 AbstractCegarLoop]: Interpolant automaton has 64 states. [2018-03-28 12:36:06,103 INFO L276 IsEmpty]: Start isEmpty. Operand 379 states and 480 transitions. [2018-03-28 12:36:06,105 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 122 [2018-03-28 12:36:06,105 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:36:06,105 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-03-28 12:36:06,105 INFO L408 AbstractCegarLoop]: === Iteration 16 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:36:06,105 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-03-28 12:36:06,114 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:36:06,144 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:36:06,147 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:36:06,241 INFO L134 CoverageAnalysis]: Checked inductivity of 380 backedges. 0 proven. 168 refuted. 0 times theorem prover too weak. 212 trivial. 0 not checked. [2018-03-28 12:36:06,242 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:36:06,482 INFO L134 CoverageAnalysis]: Checked inductivity of 380 backedges. 0 proven. 168 refuted. 0 times theorem prover too weak. 212 trivial. 0 not checked. [2018-03-28 12:36:06,503 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:36:06,503 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 31 [2018-03-28 12:36:06,503 INFO L442 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-03-28 12:36:06,504 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-03-28 12:36:06,504 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=174, Invalid=818, Unknown=0, NotChecked=0, Total=992 [2018-03-28 12:36:06,504 INFO L87 Difference]: Start difference. First operand 379 states and 480 transitions. Second operand 32 states. [2018-03-28 12:36:07,681 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:36:07,681 INFO L93 Difference]: Finished difference Result 456 states and 588 transitions. [2018-03-28 12:36:07,682 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2018-03-28 12:36:07,682 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 121 [2018-03-28 12:36:07,682 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:36:07,684 INFO L225 Difference]: With dead ends: 456 [2018-03-28 12:36:07,684 INFO L226 Difference]: Without dead ends: 454 [2018-03-28 12:36:07,686 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 275 GetRequests, 211 SyntacticMatches, 0 SemanticMatches, 64 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 716 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=1096, Invalid=3194, Unknown=0, NotChecked=0, Total=4290 [2018-03-28 12:36:07,686 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 454 states. [2018-03-28 12:36:07,703 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 454 to 451. [2018-03-28 12:36:07,703 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-03-28 12:36:07,706 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 568 transitions. [2018-03-28 12:36:07,706 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 568 transitions. Word has length 121 [2018-03-28 12:36:07,707 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:36:07,707 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 568 transitions. [2018-03-28 12:36:07,707 INFO L460 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-03-28 12:36:07,707 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 568 transitions. [2018-03-28 12:36:07,710 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 178 [2018-03-28 12:36:07,710 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:36:07,711 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-03-28 12:36:07,711 INFO L408 AbstractCegarLoop]: === Iteration 17 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:36:07,711 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-03-28 12:36:07,720 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:36:07,756 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:36:07,761 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:36:08,167 INFO L134 CoverageAnalysis]: Checked inductivity of 992 backedges. 626 proven. 212 refuted. 0 times theorem prover too weak. 154 trivial. 0 not checked. [2018-03-28 12:36:08,167 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:36:08,532 INFO L134 CoverageAnalysis]: Checked inductivity of 992 backedges. 626 proven. 212 refuted. 0 times theorem prover too weak. 154 trivial. 0 not checked. [2018-03-28 12:36:08,553 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:36:08,553 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [37, 37] total 54 [2018-03-28 12:36:08,553 INFO L442 AbstractCegarLoop]: Interpolant automaton has 54 states [2018-03-28 12:36:08,554 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 54 interpolants. [2018-03-28 12:36:08,554 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=395, Invalid=2467, Unknown=0, NotChecked=0, Total=2862 [2018-03-28 12:36:08,554 INFO L87 Difference]: Start difference. First operand 451 states and 568 transitions. Second operand 54 states. [2018-03-28 12:36:09,483 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:36:09,483 INFO L93 Difference]: Finished difference Result 602 states and 749 transitions. [2018-03-28 12:36:09,483 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 61 states. [2018-03-28 12:36:09,483 INFO L78 Accepts]: Start accepts. Automaton has 54 states. Word has length 177 [2018-03-28 12:36:09,484 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:36:09,486 INFO L225 Difference]: With dead ends: 602 [2018-03-28 12:36:09,486 INFO L226 Difference]: Without dead ends: 451 [2018-03-28 12:36:09,487 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 394 GetRequests, 283 SyntacticMatches, 18 SemanticMatches, 93 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2433 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=1333, Invalid=7597, Unknown=0, NotChecked=0, Total=8930 [2018-03-28 12:36:09,487 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-03-28 12:36:09,501 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-03-28 12:36:09,501 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-03-28 12:36:09,504 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 567 transitions. [2018-03-28 12:36:09,504 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 567 transitions. Word has length 177 [2018-03-28 12:36:09,504 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:36:09,504 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 567 transitions. [2018-03-28 12:36:09,504 INFO L460 AbstractCegarLoop]: Interpolant automaton has 54 states. [2018-03-28 12:36:09,505 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 567 transitions. [2018-03-28 12:36:09,508 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 185 [2018-03-28 12:36:09,508 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:36:09,508 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-03-28 12:36:09,509 INFO L408 AbstractCegarLoop]: === Iteration 18 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:36:09,509 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-03-28 12:36:09,518 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:36:09,553 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:36:09,559 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:36:10,082 INFO L134 CoverageAnalysis]: Checked inductivity of 1050 backedges. 669 proven. 270 refuted. 0 times theorem prover too weak. 111 trivial. 0 not checked. [2018-03-28 12:36:10,083 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:36:10,537 INFO L134 CoverageAnalysis]: Checked inductivity of 1050 backedges. 669 proven. 270 refuted. 0 times theorem prover too weak. 111 trivial. 0 not checked. [2018-03-28 12:36:10,557 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:36:10,557 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [41, 41] total 60 [2018-03-28 12:36:10,558 INFO L442 AbstractCegarLoop]: Interpolant automaton has 60 states [2018-03-28 12:36:10,558 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 60 interpolants. [2018-03-28 12:36:10,558 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=479, Invalid=3061, Unknown=0, NotChecked=0, Total=3540 [2018-03-28 12:36:10,559 INFO L87 Difference]: Start difference. First operand 451 states and 567 transitions. Second operand 60 states. [2018-03-28 12:36:11,648 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:36:11,648 INFO L93 Difference]: Finished difference Result 602 states and 748 transitions. [2018-03-28 12:36:11,649 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 68 states. [2018-03-28 12:36:11,649 INFO L78 Accepts]: Start accepts. Automaton has 60 states. Word has length 184 [2018-03-28 12:36:11,649 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:36:11,650 INFO L225 Difference]: With dead ends: 602 [2018-03-28 12:36:11,651 INFO L226 Difference]: Without dead ends: 451 [2018-03-28 12:36:11,652 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 413 GetRequests, 289 SyntacticMatches, 20 SemanticMatches, 104 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3066 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=1637, Invalid=9493, Unknown=0, NotChecked=0, Total=11130 [2018-03-28 12:36:11,652 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-03-28 12:36:11,666 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-03-28 12:36:11,667 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-03-28 12:36:11,669 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 566 transitions. [2018-03-28 12:36:11,669 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 566 transitions. Word has length 184 [2018-03-28 12:36:11,669 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:36:11,669 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 566 transitions. [2018-03-28 12:36:11,669 INFO L460 AbstractCegarLoop]: Interpolant automaton has 60 states. [2018-03-28 12:36:11,670 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 566 transitions. [2018-03-28 12:36:11,673 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 192 [2018-03-28 12:36:11,673 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:36:11,674 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-03-28 12:36:11,674 INFO L408 AbstractCegarLoop]: === Iteration 19 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:36:11,674 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-03-28 12:36:11,683 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:36:11,722 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:36:11,728 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:36:12,248 INFO L134 CoverageAnalysis]: Checked inductivity of 1115 backedges. 705 proven. 335 refuted. 0 times theorem prover too weak. 75 trivial. 0 not checked. [2018-03-28 12:36:12,248 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:36:12,770 INFO L134 CoverageAnalysis]: Checked inductivity of 1115 backedges. 705 proven. 335 refuted. 0 times theorem prover too weak. 75 trivial. 0 not checked. [2018-03-28 12:36:12,790 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:36:12,791 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [45, 45] total 66 [2018-03-28 12:36:12,791 INFO L442 AbstractCegarLoop]: Interpolant automaton has 66 states [2018-03-28 12:36:12,791 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 66 interpolants. [2018-03-28 12:36:12,792 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=571, Invalid=3719, Unknown=0, NotChecked=0, Total=4290 [2018-03-28 12:36:12,792 INFO L87 Difference]: Start difference. First operand 451 states and 566 transitions. Second operand 66 states. [2018-03-28 12:36:14,030 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:36:14,030 INFO L93 Difference]: Finished difference Result 602 states and 747 transitions. [2018-03-28 12:36:14,030 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 75 states. [2018-03-28 12:36:14,030 INFO L78 Accepts]: Start accepts. Automaton has 66 states. Word has length 191 [2018-03-28 12:36:14,031 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:36:14,032 INFO L225 Difference]: With dead ends: 602 [2018-03-28 12:36:14,033 INFO L226 Difference]: Without dead ends: 451 [2018-03-28 12:36:14,035 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 432 GetRequests, 295 SyntacticMatches, 22 SemanticMatches, 115 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3772 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=1972, Invalid=11600, Unknown=0, NotChecked=0, Total=13572 [2018-03-28 12:36:14,035 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-03-28 12:36:14,044 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-03-28 12:36:14,044 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-03-28 12:36:14,045 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 565 transitions. [2018-03-28 12:36:14,045 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 565 transitions. Word has length 191 [2018-03-28 12:36:14,045 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:36:14,045 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 565 transitions. [2018-03-28 12:36:14,045 INFO L460 AbstractCegarLoop]: Interpolant automaton has 66 states. [2018-03-28 12:36:14,046 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 565 transitions. [2018-03-28 12:36:14,047 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 199 [2018-03-28 12:36:14,047 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:36:14,047 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-03-28 12:36:14,047 INFO L408 AbstractCegarLoop]: === Iteration 20 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:36:14,048 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-03-28 12:36:14,062 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:36:14,090 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:36:14,094 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:36:14,620 INFO L134 CoverageAnalysis]: Checked inductivity of 1187 backedges. 734 proven. 407 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2018-03-28 12:36:14,620 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:36:15,226 INFO L134 CoverageAnalysis]: Checked inductivity of 1187 backedges. 734 proven. 407 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2018-03-28 12:36:15,247 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:36:15,248 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [49, 49] total 72 [2018-03-28 12:36:15,248 INFO L442 AbstractCegarLoop]: Interpolant automaton has 72 states [2018-03-28 12:36:15,248 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 72 interpolants. [2018-03-28 12:36:15,249 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=671, Invalid=4441, Unknown=0, NotChecked=0, Total=5112 [2018-03-28 12:36:15,249 INFO L87 Difference]: Start difference. First operand 451 states and 565 transitions. Second operand 72 states. [2018-03-28 12:36:16,703 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:36:16,703 INFO L93 Difference]: Finished difference Result 602 states and 746 transitions. [2018-03-28 12:36:16,704 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 82 states. [2018-03-28 12:36:16,704 INFO L78 Accepts]: Start accepts. Automaton has 72 states. Word has length 198 [2018-03-28 12:36:16,705 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:36:16,707 INFO L225 Difference]: With dead ends: 602 [2018-03-28 12:36:16,707 INFO L226 Difference]: Without dead ends: 451 [2018-03-28 12:36:16,709 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-03-28 12:36:16,710 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-03-28 12:36:16,722 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-03-28 12:36:16,723 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-03-28 12:36:16,724 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 564 transitions. [2018-03-28 12:36:16,725 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 564 transitions. Word has length 198 [2018-03-28 12:36:16,725 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:36:16,725 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 564 transitions. [2018-03-28 12:36:16,725 INFO L460 AbstractCegarLoop]: Interpolant automaton has 72 states. [2018-03-28 12:36:16,725 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 564 transitions. [2018-03-28 12:36:16,728 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 206 [2018-03-28 12:36:16,728 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:36:16,728 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-03-28 12:36:16,728 INFO L408 AbstractCegarLoop]: === Iteration 21 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:36:16,728 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-03-28 12:36:16,736 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:36:16,776 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:36:16,783 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:36:17,531 INFO L134 CoverageAnalysis]: Checked inductivity of 1266 backedges. 756 proven. 486 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2018-03-28 12:36:17,531 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:36:18,320 INFO L134 CoverageAnalysis]: Checked inductivity of 1266 backedges. 756 proven. 486 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2018-03-28 12:36:18,341 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:36:18,341 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [53, 53] total 78 [2018-03-28 12:36:18,341 INFO L442 AbstractCegarLoop]: Interpolant automaton has 78 states [2018-03-28 12:36:18,342 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 78 interpolants. [2018-03-28 12:36:18,342 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=779, Invalid=5227, Unknown=0, NotChecked=0, Total=6006 [2018-03-28 12:36:18,342 INFO L87 Difference]: Start difference. First operand 451 states and 564 transitions. Second operand 78 states. [2018-03-28 12:36:20,137 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:36:20,137 INFO L93 Difference]: Finished difference Result 602 states and 745 transitions. [2018-03-28 12:36:20,137 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 89 states. [2018-03-28 12:36:20,137 INFO L78 Accepts]: Start accepts. Automaton has 78 states. Word has length 205 [2018-03-28 12:36:20,137 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:36:20,139 INFO L225 Difference]: With dead ends: 602 [2018-03-28 12:36:20,139 INFO L226 Difference]: Without dead ends: 451 [2018-03-28 12:36:20,141 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 470 GetRequests, 307 SyntacticMatches, 26 SemanticMatches, 137 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5403 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=2735, Invalid=16447, Unknown=0, NotChecked=0, Total=19182 [2018-03-28 12:36:20,141 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-03-28 12:36:20,155 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-03-28 12:36:20,155 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-03-28 12:36:20,157 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 563 transitions. [2018-03-28 12:36:20,157 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 563 transitions. Word has length 205 [2018-03-28 12:36:20,157 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:36:20,158 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 563 transitions. [2018-03-28 12:36:20,158 INFO L460 AbstractCegarLoop]: Interpolant automaton has 78 states. [2018-03-28 12:36:20,158 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 563 transitions. [2018-03-28 12:36:20,160 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 213 [2018-03-28 12:36:20,160 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:36:20,161 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-03-28 12:36:20,161 INFO L408 AbstractCegarLoop]: === Iteration 22 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:36:20,161 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-03-28 12:36:20,168 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:36:20,199 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:36:20,204 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:36:20,927 INFO L134 CoverageAnalysis]: Checked inductivity of 1352 backedges. 771 proven. 572 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2018-03-28 12:36:20,927 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:36:21,778 INFO L134 CoverageAnalysis]: Checked inductivity of 1352 backedges. 771 proven. 572 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2018-03-28 12:36:21,799 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:36:21,800 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [57, 57] total 84 [2018-03-28 12:36:21,800 INFO L442 AbstractCegarLoop]: Interpolant automaton has 84 states [2018-03-28 12:36:21,800 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 84 interpolants. [2018-03-28 12:36:21,801 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=895, Invalid=6077, Unknown=0, NotChecked=0, Total=6972 [2018-03-28 12:36:21,801 INFO L87 Difference]: Start difference. First operand 451 states and 563 transitions. Second operand 84 states. [2018-03-28 12:36:23,686 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:36:23,687 INFO L93 Difference]: Finished difference Result 602 states and 744 transitions. [2018-03-28 12:36:23,687 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 96 states. [2018-03-28 12:36:23,687 INFO L78 Accepts]: Start accepts. Automaton has 84 states. Word has length 212 [2018-03-28 12:36:23,688 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:36:23,690 INFO L225 Difference]: With dead ends: 602 [2018-03-28 12:36:23,690 INFO L226 Difference]: Without dead ends: 451 [2018-03-28 12:36:23,691 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-03-28 12:36:23,691 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-03-28 12:36:23,700 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-03-28 12:36:23,700 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-03-28 12:36:23,701 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 562 transitions. [2018-03-28 12:36:23,701 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 562 transitions. Word has length 212 [2018-03-28 12:36:23,701 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:36:23,701 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 562 transitions. [2018-03-28 12:36:23,701 INFO L460 AbstractCegarLoop]: Interpolant automaton has 84 states. [2018-03-28 12:36:23,701 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 562 transitions. [2018-03-28 12:36:23,702 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 220 [2018-03-28 12:36:23,703 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:36:23,703 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-03-28 12:36:23,703 INFO L408 AbstractCegarLoop]: === Iteration 23 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:36:23,703 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-03-28 12:36:23,709 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:36:23,741 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:36:23,747 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:36:24,556 INFO L134 CoverageAnalysis]: Checked inductivity of 1445 backedges. 779 proven. 665 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-03-28 12:36:24,557 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:36:25,499 INFO L134 CoverageAnalysis]: Checked inductivity of 1445 backedges. 779 proven. 665 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-03-28 12:36:25,520 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:36:25,520 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [61, 61] total 90 [2018-03-28 12:36:25,520 INFO L442 AbstractCegarLoop]: Interpolant automaton has 90 states [2018-03-28 12:36:25,520 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 90 interpolants. [2018-03-28 12:36:25,521 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1019, Invalid=6991, Unknown=0, NotChecked=0, Total=8010 [2018-03-28 12:36:25,521 INFO L87 Difference]: Start difference. First operand 451 states and 562 transitions. Second operand 90 states. [2018-03-28 12:36:27,644 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:36:27,644 INFO L93 Difference]: Finished difference Result 602 states and 743 transitions. [2018-03-28 12:36:27,644 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 103 states. [2018-03-28 12:36:27,645 INFO L78 Accepts]: Start accepts. Automaton has 90 states. Word has length 219 [2018-03-28 12:36:27,645 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:36:27,646 INFO L225 Difference]: With dead ends: 602 [2018-03-28 12:36:27,646 INFO L226 Difference]: Without dead ends: 451 [2018-03-28 12:36:27,648 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 508 GetRequests, 319 SyntacticMatches, 30 SemanticMatches, 159 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7326 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=3622, Invalid=22138, Unknown=0, NotChecked=0, Total=25760 [2018-03-28 12:36:27,648 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-03-28 12:36:27,661 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-03-28 12:36:27,661 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-03-28 12:36:27,663 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 561 transitions. [2018-03-28 12:36:27,663 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 561 transitions. Word has length 219 [2018-03-28 12:36:27,664 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:36:27,664 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 561 transitions. [2018-03-28 12:36:27,664 INFO L460 AbstractCegarLoop]: Interpolant automaton has 90 states. [2018-03-28 12:36:27,664 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 561 transitions. [2018-03-28 12:36:27,666 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 227 [2018-03-28 12:36:27,667 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:36:27,667 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-03-28 12:36:27,667 INFO L408 AbstractCegarLoop]: === Iteration 24 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:36:27,667 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-03-28 12:36:27,680 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:36:27,710 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:36:27,715 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:36:28,669 INFO L134 CoverageAnalysis]: Checked inductivity of 1545 backedges. 780 proven. 765 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-28 12:36:28,669 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:36:29,731 INFO L134 CoverageAnalysis]: Checked inductivity of 1545 backedges. 780 proven. 765 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-28 12:36:29,752 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:36:29,752 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [65, 65] total 96 [2018-03-28 12:36:29,752 INFO L442 AbstractCegarLoop]: Interpolant automaton has 96 states [2018-03-28 12:36:29,753 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 96 interpolants. [2018-03-28 12:36:29,753 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1151, Invalid=7969, Unknown=0, NotChecked=0, Total=9120 [2018-03-28 12:36:29,754 INFO L87 Difference]: Start difference. First operand 451 states and 561 transitions. Second operand 96 states. [2018-03-28 12:36:32,309 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:36:32,310 INFO L93 Difference]: Finished difference Result 608 states and 749 transitions. [2018-03-28 12:36:32,310 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 110 states. [2018-03-28 12:36:32,310 INFO L78 Accepts]: Start accepts. Automaton has 96 states. Word has length 226 [2018-03-28 12:36:32,310 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:36:32,312 INFO L225 Difference]: With dead ends: 608 [2018-03-28 12:36:32,312 INFO L226 Difference]: Without dead ends: 451 [2018-03-28 12:36:32,313 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-03-28 12:36:32,314 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-03-28 12:36:32,326 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-03-28 12:36:32,327 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-03-28 12:36:32,328 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 560 transitions. [2018-03-28 12:36:32,329 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 560 transitions. Word has length 226 [2018-03-28 12:36:32,329 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:36:32,329 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 560 transitions. [2018-03-28 12:36:32,329 INFO L460 AbstractCegarLoop]: Interpolant automaton has 96 states. [2018-03-28 12:36:32,329 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 560 transitions. [2018-03-28 12:36:32,332 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 231 [2018-03-28 12:36:32,332 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:36:32,332 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-28 12:36:32,332 INFO L408 AbstractCegarLoop]: === Iteration 25 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:36:32,333 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-03-28 12:36:32,340 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:36:32,372 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:36:32,378 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:36:33,598 INFO L134 CoverageAnalysis]: Checked inductivity of 3348 backedges. 0 proven. 3348 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-28 12:36:33,598 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:36:37,007 INFO L134 CoverageAnalysis]: Checked inductivity of 3348 backedges. 0 proven. 3348 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-28 12:36:37,027 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:36:37,028 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [64, 64] total 127 [2018-03-28 12:36:37,028 INFO L442 AbstractCegarLoop]: Interpolant automaton has 128 states [2018-03-28 12:36:37,029 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 128 interpolants. [2018-03-28 12:36:37,029 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2238, Invalid=14018, Unknown=0, NotChecked=0, Total=16256 [2018-03-28 12:36:37,030 INFO L87 Difference]: Start difference. First operand 451 states and 560 transitions. Second operand 128 states. [2018-03-28 12:36:43,010 WARN L151 SmtUtils]: Spent 259ms on a formula simplification. DAG size of input: 252 DAG size of output 12 [2018-03-28 12:36:43,684 WARN L151 SmtUtils]: Spent 236ms on a formula simplification. DAG size of input: 247 DAG size of output 11 [2018-03-28 12:36:44,144 WARN L151 SmtUtils]: Spent 241ms on a formula simplification. DAG size of input: 244 DAG size of output 12 [2018-03-28 12:36:44,789 WARN L151 SmtUtils]: Spent 225ms on a formula simplification. DAG size of input: 239 DAG size of output 11 [2018-03-28 12:36:45,235 WARN L151 SmtUtils]: Spent 217ms on a formula simplification. DAG size of input: 236 DAG size of output 12 [2018-03-28 12:36:45,868 WARN L151 SmtUtils]: Spent 213ms on a formula simplification. DAG size of input: 231 DAG size of output 11 [2018-03-28 12:36:46,294 WARN L151 SmtUtils]: Spent 199ms on a formula simplification. DAG size of input: 228 DAG size of output 12 [2018-03-28 12:36:46,900 WARN L151 SmtUtils]: Spent 190ms on a formula simplification. DAG size of input: 223 DAG size of output 11 [2018-03-28 12:36:47,324 WARN L151 SmtUtils]: Spent 201ms on a formula simplification. DAG size of input: 220 DAG size of output 12 [2018-03-28 12:36:47,927 WARN L151 SmtUtils]: Spent 187ms on a formula simplification. DAG size of input: 215 DAG size of output 11 [2018-03-28 12:36:48,335 WARN L151 SmtUtils]: Spent 185ms on a formula simplification. DAG size of input: 212 DAG size of output 12 [2018-03-28 12:36:48,915 WARN L151 SmtUtils]: Spent 171ms on a formula simplification. DAG size of input: 207 DAG size of output 11 [2018-03-28 12:36:49,302 WARN L151 SmtUtils]: Spent 164ms on a formula simplification. DAG size of input: 204 DAG size of output 12 [2018-03-28 12:36:49,877 WARN L151 SmtUtils]: Spent 163ms on a formula simplification. DAG size of input: 199 DAG size of output 11 [2018-03-28 12:36:50,286 WARN L151 SmtUtils]: Spent 166ms on a formula simplification. DAG size of input: 196 DAG size of output 12 [2018-03-28 12:36:50,858 WARN L151 SmtUtils]: Spent 162ms on a formula simplification. DAG size of input: 191 DAG size of output 11 [2018-03-28 12:36:51,224 WARN L151 SmtUtils]: Spent 147ms on a formula simplification. DAG size of input: 188 DAG size of output 12 [2018-03-28 12:36:51,772 WARN L151 SmtUtils]: Spent 146ms on a formula simplification. DAG size of input: 183 DAG size of output 11 [2018-03-28 12:36:52,139 WARN L151 SmtUtils]: Spent 146ms on a formula simplification. DAG size of input: 180 DAG size of output 12 [2018-03-28 12:36:52,655 WARN L151 SmtUtils]: Spent 129ms on a formula simplification. DAG size of input: 175 DAG size of output 11 [2018-03-28 12:36:53,003 WARN L151 SmtUtils]: Spent 125ms on a formula simplification. DAG size of input: 172 DAG size of output 12 [2018-03-28 12:36:53,522 WARN L151 SmtUtils]: Spent 122ms on a formula simplification. DAG size of input: 167 DAG size of output 11 [2018-03-28 12:36:53,847 WARN L151 SmtUtils]: Spent 114ms on a formula simplification. DAG size of input: 164 DAG size of output 12 [2018-03-28 12:36:54,329 WARN L151 SmtUtils]: Spent 108ms on a formula simplification. DAG size of input: 159 DAG size of output 11 [2018-03-28 12:36:54,647 WARN L151 SmtUtils]: Spent 111ms on a formula simplification. DAG size of input: 156 DAG size of output 12 [2018-03-28 12:36:55,111 WARN L151 SmtUtils]: Spent 100ms on a formula simplification. DAG size of input: 151 DAG size of output 11 [2018-03-28 12:36:55,417 WARN L151 SmtUtils]: Spent 100ms on a formula simplification. DAG size of input: 148 DAG size of output 12 [2018-03-28 12:37:04,595 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:04,596 INFO L93 Difference]: Finished difference Result 791 states and 1059 transitions. [2018-03-28 12:37:04,596 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 189 states. [2018-03-28 12:37:04,596 INFO L78 Accepts]: Start accepts. Automaton has 128 states. Word has length 230 [2018-03-28 12:37:04,596 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:04,599 INFO L225 Difference]: With dead ends: 791 [2018-03-28 12:37:04,599 INFO L226 Difference]: Without dead ends: 789 [2018-03-28 12:37:04,602 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 613 GetRequests, 333 SyntacticMatches, 0 SemanticMatches, 280 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15068 ImplicationChecksByTransitivity, 26.5s TimeCoverageRelationStatistics Valid=18976, Invalid=60266, Unknown=0, NotChecked=0, Total=79242 [2018-03-28 12:37:04,602 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 789 states. [2018-03-28 12:37:04,621 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 789 to 739. [2018-03-28 12:37:04,621 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 739 states. [2018-03-28 12:37:04,624 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 739 states to 739 states and 944 transitions. [2018-03-28 12:37:04,624 INFO L78 Accepts]: Start accepts. Automaton has 739 states and 944 transitions. Word has length 230 [2018-03-28 12:37:04,625 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:04,625 INFO L459 AbstractCegarLoop]: Abstraction has 739 states and 944 transitions. [2018-03-28 12:37:04,625 INFO L460 AbstractCegarLoop]: Interpolant automaton has 128 states. [2018-03-28 12:37:04,625 INFO L276 IsEmpty]: Start isEmpty. Operand 739 states and 944 transitions. [2018-03-28 12:37:04,628 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 234 [2018-03-28 12:37:04,628 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:04,628 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-03-28 12:37:04,628 INFO L408 AbstractCegarLoop]: === Iteration 26 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:04,629 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-03-28 12:37:04,638 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:04,686 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:04,692 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:05,058 INFO L134 CoverageAnalysis]: Checked inductivity of 1652 backedges. 0 proven. 780 refuted. 0 times theorem prover too weak. 872 trivial. 0 not checked. [2018-03-28 12:37:05,058 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:05,972 INFO L134 CoverageAnalysis]: Checked inductivity of 1652 backedges. 0 proven. 780 refuted. 0 times theorem prover too weak. 872 trivial. 0 not checked. [2018-03-28 12:37:05,993 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:05,993 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [32, 32] total 63 [2018-03-28 12:37:05,994 INFO L442 AbstractCegarLoop]: Interpolant automaton has 64 states [2018-03-28 12:37:05,994 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 64 interpolants. [2018-03-28 12:37:05,994 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=606, Invalid=3426, Unknown=0, NotChecked=0, Total=4032 [2018-03-28 12:37:05,995 INFO L87 Difference]: Start difference. First operand 739 states and 944 transitions. Second operand 64 states. [2018-03-28 12:37:11,125 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:11,125 INFO L93 Difference]: Finished difference Result 888 states and 1156 transitions. [2018-03-28 12:37:11,125 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 93 states. [2018-03-28 12:37:11,125 INFO L78 Accepts]: Start accepts. Automaton has 64 states. Word has length 233 [2018-03-28 12:37:11,126 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:11,128 INFO L225 Difference]: With dead ends: 888 [2018-03-28 12:37:11,128 INFO L226 Difference]: Without dead ends: 886 [2018-03-28 12:37:11,129 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 539 GetRequests, 403 SyntacticMatches, 0 SemanticMatches, 136 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3452 ImplicationChecksByTransitivity, 4.9s TimeCoverageRelationStatistics Valid=4624, Invalid=14282, Unknown=0, NotChecked=0, Total=18906 [2018-03-28 12:37:11,129 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 886 states. [2018-03-28 12:37:11,144 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 886 to 883. [2018-03-28 12:37:11,145 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-03-28 12:37:11,147 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1120 transitions. [2018-03-28 12:37:11,147 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1120 transitions. Word has length 233 [2018-03-28 12:37:11,147 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:11,147 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1120 transitions. [2018-03-28 12:37:11,147 INFO L460 AbstractCegarLoop]: Interpolant automaton has 64 states. [2018-03-28 12:37:11,147 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1120 transitions. [2018-03-28 12:37:11,150 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 346 [2018-03-28 12:37:11,150 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:11,150 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-03-28 12:37:11,150 INFO L408 AbstractCegarLoop]: === Iteration 27 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:11,150 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-03-28 12:37:11,157 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:11,208 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:11,214 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:12,279 INFO L134 CoverageAnalysis]: Checked inductivity of 4220 backedges. 2598 proven. 872 refuted. 0 times theorem prover too weak. 750 trivial. 0 not checked. [2018-03-28 12:37:12,280 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:13,562 INFO L134 CoverageAnalysis]: Checked inductivity of 4220 backedges. 2598 proven. 872 refuted. 0 times theorem prover too weak. 750 trivial. 0 not checked. [2018-03-28 12:37:13,583 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:13,584 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [69, 69] total 102 [2018-03-28 12:37:13,584 INFO L442 AbstractCegarLoop]: Interpolant automaton has 102 states [2018-03-28 12:37:13,584 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 102 interpolants. [2018-03-28 12:37:13,585 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1291, Invalid=9011, Unknown=0, NotChecked=0, Total=10302 [2018-03-28 12:37:13,585 INFO L87 Difference]: Start difference. First operand 883 states and 1120 transitions. Second operand 102 states. [2018-03-28 12:37:16,525 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:16,525 INFO L93 Difference]: Finished difference Result 1178 states and 1477 transitions. [2018-03-28 12:37:16,526 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 117 states. [2018-03-28 12:37:16,526 INFO L78 Accepts]: Start accepts. Automaton has 102 states. Word has length 345 [2018-03-28 12:37:16,526 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:16,529 INFO L225 Difference]: With dead ends: 1178 [2018-03-28 12:37:16,529 INFO L226 Difference]: Without dead ends: 883 [2018-03-28 12:37:16,530 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 770 GetRequests, 555 SyntacticMatches, 34 SemanticMatches, 181 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9541 ImplicationChecksByTransitivity, 3.9s TimeCoverageRelationStatistics Valid=4633, Invalid=28673, Unknown=0, NotChecked=0, Total=33306 [2018-03-28 12:37:16,531 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-03-28 12:37:16,545 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-03-28 12:37:16,545 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-03-28 12:37:16,547 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1119 transitions. [2018-03-28 12:37:16,547 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1119 transitions. Word has length 345 [2018-03-28 12:37:16,547 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:16,547 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1119 transitions. [2018-03-28 12:37:16,547 INFO L460 AbstractCegarLoop]: Interpolant automaton has 102 states. [2018-03-28 12:37:16,547 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1119 transitions. [2018-03-28 12:37:16,550 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 353 [2018-03-28 12:37:16,550 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:16,550 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-03-28 12:37:16,550 INFO L408 AbstractCegarLoop]: === Iteration 28 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:16,550 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-03-28 12:37:16,560 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:16,629 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:16,640 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:17,852 INFO L134 CoverageAnalysis]: Checked inductivity of 4334 backedges. 2697 proven. 986 refuted. 0 times theorem prover too weak. 651 trivial. 0 not checked. [2018-03-28 12:37:17,853 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:19,307 INFO L134 CoverageAnalysis]: Checked inductivity of 4334 backedges. 2697 proven. 986 refuted. 0 times theorem prover too weak. 651 trivial. 0 not checked. [2018-03-28 12:37:19,328 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:19,328 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [73, 73] total 108 [2018-03-28 12:37:19,329 INFO L442 AbstractCegarLoop]: Interpolant automaton has 108 states [2018-03-28 12:37:19,329 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 108 interpolants. [2018-03-28 12:37:19,330 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1439, Invalid=10117, Unknown=0, NotChecked=0, Total=11556 [2018-03-28 12:37:19,330 INFO L87 Difference]: Start difference. First operand 883 states and 1119 transitions. Second operand 108 states. [2018-03-28 12:37:22,679 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:22,680 INFO L93 Difference]: Finished difference Result 1178 states and 1476 transitions. [2018-03-28 12:37:22,680 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 124 states. [2018-03-28 12:37:22,680 INFO L78 Accepts]: Start accepts. Automaton has 108 states. Word has length 352 [2018-03-28 12:37:22,680 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:22,683 INFO L225 Difference]: With dead ends: 1178 [2018-03-28 12:37:22,683 INFO L226 Difference]: Without dead ends: 883 [2018-03-28 12:37:22,685 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 789 GetRequests, 561 SyntacticMatches, 36 SemanticMatches, 192 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10758 ImplicationChecksByTransitivity, 4.5s TimeCoverageRelationStatistics Valid=5185, Invalid=32257, Unknown=0, NotChecked=0, Total=37442 [2018-03-28 12:37:22,685 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-03-28 12:37:22,699 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-03-28 12:37:22,699 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-03-28 12:37:22,701 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1118 transitions. [2018-03-28 12:37:22,701 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1118 transitions. Word has length 352 [2018-03-28 12:37:22,701 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:22,702 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1118 transitions. [2018-03-28 12:37:22,702 INFO L460 AbstractCegarLoop]: Interpolant automaton has 108 states. [2018-03-28 12:37:22,702 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1118 transitions. [2018-03-28 12:37:22,705 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 360 [2018-03-28 12:37:22,705 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:22,705 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-03-28 12:37:22,706 INFO L408 AbstractCegarLoop]: === Iteration 29 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:22,706 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-03-28 12:37:22,719 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:22,772 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:22,778 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:24,113 INFO L134 CoverageAnalysis]: Checked inductivity of 4455 backedges. 2789 proven. 1107 refuted. 0 times theorem prover too weak. 559 trivial. 0 not checked. [2018-03-28 12:37:24,113 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:25,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-03-28 12:37:25,674 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:25,674 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [77, 77] total 114 [2018-03-28 12:37:25,674 INFO L442 AbstractCegarLoop]: Interpolant automaton has 114 states [2018-03-28 12:37:25,675 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 114 interpolants. [2018-03-28 12:37:25,675 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1595, Invalid=11287, Unknown=0, NotChecked=0, Total=12882 [2018-03-28 12:37:25,675 INFO L87 Difference]: Start difference. First operand 883 states and 1118 transitions. Second operand 114 states. [2018-03-28 12:37:29,405 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:29,405 INFO L93 Difference]: Finished difference Result 1178 states and 1475 transitions. [2018-03-28 12:37:29,405 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 131 states. [2018-03-28 12:37:29,405 INFO L78 Accepts]: Start accepts. Automaton has 114 states. Word has length 359 [2018-03-28 12:37:29,406 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:29,408 INFO L225 Difference]: With dead ends: 1178 [2018-03-28 12:37:29,408 INFO L226 Difference]: Without dead ends: 883 [2018-03-28 12:37:29,411 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 808 GetRequests, 567 SyntacticMatches, 38 SemanticMatches, 203 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12048 ImplicationChecksByTransitivity, 4.9s TimeCoverageRelationStatistics Valid=5768, Invalid=36052, Unknown=0, NotChecked=0, Total=41820 [2018-03-28 12:37:29,411 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-03-28 12:37:29,424 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-03-28 12:37:29,424 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-03-28 12:37:29,427 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1117 transitions. [2018-03-28 12:37:29,427 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1117 transitions. Word has length 359 [2018-03-28 12:37:29,428 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:29,428 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1117 transitions. [2018-03-28 12:37:29,428 INFO L460 AbstractCegarLoop]: Interpolant automaton has 114 states. [2018-03-28 12:37:29,428 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1117 transitions. [2018-03-28 12:37:29,433 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 367 [2018-03-28 12:37:29,433 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:29,433 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-03-28 12:37:29,433 INFO L408 AbstractCegarLoop]: === Iteration 30 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:29,434 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-03-28 12:37:29,442 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:29,516 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:29,525 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:30,911 INFO L134 CoverageAnalysis]: Checked inductivity of 4583 backedges. 2874 proven. 1235 refuted. 0 times theorem prover too weak. 474 trivial. 0 not checked. [2018-03-28 12:37:30,911 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:32,883 INFO L134 CoverageAnalysis]: Checked inductivity of 4583 backedges. 2874 proven. 1235 refuted. 0 times theorem prover too weak. 474 trivial. 0 not checked. [2018-03-28 12:37:32,904 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:32,919 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [81, 81] total 120 [2018-03-28 12:37:32,920 INFO L442 AbstractCegarLoop]: Interpolant automaton has 120 states [2018-03-28 12:37:32,920 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 120 interpolants. [2018-03-28 12:37:32,921 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1759, Invalid=12521, Unknown=0, NotChecked=0, Total=14280 [2018-03-28 12:37:32,921 INFO L87 Difference]: Start difference. First operand 883 states and 1117 transitions. Second operand 120 states. [2018-03-28 12:37:37,121 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:37,122 INFO L93 Difference]: Finished difference Result 1178 states and 1474 transitions. [2018-03-28 12:37:37,122 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 138 states. [2018-03-28 12:37:37,122 INFO L78 Accepts]: Start accepts. Automaton has 120 states. Word has length 366 [2018-03-28 12:37:37,122 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:37,125 INFO L225 Difference]: With dead ends: 1178 [2018-03-28 12:37:37,125 INFO L226 Difference]: Without dead ends: 883 [2018-03-28 12:37:37,127 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 827 GetRequests, 573 SyntacticMatches, 40 SemanticMatches, 214 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13411 ImplicationChecksByTransitivity, 5.6s TimeCoverageRelationStatistics Valid=6382, Invalid=40058, Unknown=0, NotChecked=0, Total=46440 [2018-03-28 12:37:37,128 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-03-28 12:37:37,140 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-03-28 12:37:37,140 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-03-28 12:37:37,142 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1116 transitions. [2018-03-28 12:37:37,142 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1116 transitions. Word has length 366 [2018-03-28 12:37:37,142 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:37,142 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1116 transitions. [2018-03-28 12:37:37,142 INFO L460 AbstractCegarLoop]: Interpolant automaton has 120 states. [2018-03-28 12:37:37,142 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1116 transitions. [2018-03-28 12:37:37,144 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 374 [2018-03-28 12:37:37,145 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:37,145 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-03-28 12:37:37,145 INFO L408 AbstractCegarLoop]: === Iteration 31 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:37,145 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-03-28 12:37:37,156 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:37,210 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:37,220 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:38,739 INFO L134 CoverageAnalysis]: Checked inductivity of 4718 backedges. 2952 proven. 1370 refuted. 0 times theorem prover too weak. 396 trivial. 0 not checked. [2018-03-28 12:37:38,739 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:40,599 INFO L134 CoverageAnalysis]: Checked inductivity of 4718 backedges. 2952 proven. 1370 refuted. 0 times theorem prover too weak. 396 trivial. 0 not checked. [2018-03-28 12:37:40,620 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:40,620 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [85, 85] total 126 [2018-03-28 12:37:40,621 INFO L442 AbstractCegarLoop]: Interpolant automaton has 126 states [2018-03-28 12:37:40,621 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 126 interpolants. [2018-03-28 12:37:40,622 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1931, Invalid=13819, Unknown=0, NotChecked=0, Total=15750 [2018-03-28 12:37:40,622 INFO L87 Difference]: Start difference. First operand 883 states and 1116 transitions. Second operand 126 states. [2018-03-28 12:37:44,731 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:44,731 INFO L93 Difference]: Finished difference Result 1178 states and 1473 transitions. [2018-03-28 12:37:44,732 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 145 states. [2018-03-28 12:37:44,732 INFO L78 Accepts]: Start accepts. Automaton has 126 states. Word has length 373 [2018-03-28 12:37:44,732 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:44,735 INFO L225 Difference]: With dead ends: 1178 [2018-03-28 12:37:44,735 INFO L226 Difference]: Without dead ends: 883 [2018-03-28 12:37:44,740 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 846 GetRequests, 579 SyntacticMatches, 42 SemanticMatches, 225 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14847 ImplicationChecksByTransitivity, 5.9s TimeCoverageRelationStatistics Valid=7027, Invalid=44275, Unknown=0, NotChecked=0, Total=51302 [2018-03-28 12:37:44,741 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-03-28 12:37:44,760 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-03-28 12:37:44,760 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-03-28 12:37:44,763 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1115 transitions. [2018-03-28 12:37:44,763 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1115 transitions. Word has length 373 [2018-03-28 12:37:44,763 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:44,763 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1115 transitions. [2018-03-28 12:37:44,764 INFO L460 AbstractCegarLoop]: Interpolant automaton has 126 states. [2018-03-28 12:37:44,764 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1115 transitions. [2018-03-28 12:37:44,766 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 381 [2018-03-28 12:37:44,766 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:44,766 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-03-28 12:37:44,766 INFO L408 AbstractCegarLoop]: === Iteration 32 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:44,766 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-03-28 12:37:44,772 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:44,825 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:44,832 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:47,048 INFO L134 CoverageAnalysis]: Checked inductivity of 4860 backedges. 3023 proven. 1512 refuted. 0 times theorem prover too weak. 325 trivial. 0 not checked. [2018-03-28 12:37:47,049 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:49,113 INFO L134 CoverageAnalysis]: Checked inductivity of 4860 backedges. 3023 proven. 1512 refuted. 0 times theorem prover too weak. 325 trivial. 0 not checked. [2018-03-28 12:37:49,135 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:49,135 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [89, 89] total 132 [2018-03-28 12:37:49,135 INFO L442 AbstractCegarLoop]: Interpolant automaton has 132 states [2018-03-28 12:37:49,136 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 132 interpolants. [2018-03-28 12:37:49,136 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2111, Invalid=15181, Unknown=0, NotChecked=0, Total=17292 [2018-03-28 12:37:49,137 INFO L87 Difference]: Start difference. First operand 883 states and 1115 transitions. Second operand 132 states. [2018-03-28 12:37:53,489 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:53,489 INFO L93 Difference]: Finished difference Result 1178 states and 1472 transitions. [2018-03-28 12:37:53,489 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 152 states. [2018-03-28 12:37:53,489 INFO L78 Accepts]: Start accepts. Automaton has 132 states. Word has length 380 [2018-03-28 12:37:53,490 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:53,492 INFO L225 Difference]: With dead ends: 1178 [2018-03-28 12:37:53,492 INFO L226 Difference]: Without dead ends: 883 [2018-03-28 12:37:53,495 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 865 GetRequests, 585 SyntacticMatches, 44 SemanticMatches, 236 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16356 ImplicationChecksByTransitivity, 7.0s TimeCoverageRelationStatistics Valid=7703, Invalid=48703, Unknown=0, NotChecked=0, Total=56406 [2018-03-28 12:37:53,496 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-03-28 12:37:53,507 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-03-28 12:37:53,507 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-03-28 12:37:53,509 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1114 transitions. [2018-03-28 12:37:53,510 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1114 transitions. Word has length 380 [2018-03-28 12:37:53,510 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:53,510 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1114 transitions. [2018-03-28 12:37:53,510 INFO L460 AbstractCegarLoop]: Interpolant automaton has 132 states. [2018-03-28 12:37:53,510 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1114 transitions. [2018-03-28 12:37:53,512 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 388 [2018-03-28 12:37:53,512 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:53,512 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-03-28 12:37:53,513 INFO L408 AbstractCegarLoop]: === Iteration 33 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:53,513 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-03-28 12:37:53,520 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:53,571 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:53,577 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:55,523 INFO L134 CoverageAnalysis]: Checked inductivity of 5009 backedges. 3087 proven. 1661 refuted. 0 times theorem prover too weak. 261 trivial. 0 not checked. [2018-03-28 12:37:55,523 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:57,708 INFO L134 CoverageAnalysis]: Checked inductivity of 5009 backedges. 3087 proven. 1661 refuted. 0 times theorem prover too weak. 261 trivial. 0 not checked. [2018-03-28 12:37:57,730 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:57,730 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [93, 93] total 138 [2018-03-28 12:37:57,731 INFO L442 AbstractCegarLoop]: Interpolant automaton has 138 states [2018-03-28 12:37:57,731 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 138 interpolants. [2018-03-28 12:37:57,732 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2299, Invalid=16607, Unknown=0, NotChecked=0, Total=18906 [2018-03-28 12:37:57,733 INFO L87 Difference]: Start difference. First operand 883 states and 1114 transitions. Second operand 138 states. Received shutdown request... [2018-03-28 12:37:58,452 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2018-03-28 12:37:58,452 WARN L519 AbstractCegarLoop]: Verification canceled [2018-03-28 12:37:58,456 WARN L197 ceAbstractionStarter]: Timeout [2018-03-28 12:37:58,456 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 28.03 12:37:58 BoogieIcfgContainer [2018-03-28 12:37:58,456 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-03-28 12:37:58,457 INFO L168 Benchmark]: Toolchain (without parser) took 130537.38 ms. Allocated memory was 307.8 MB in the beginning and 923.3 MB in the end (delta: 615.5 MB). Free memory was 251.3 MB in the beginning and 814.9 MB in the end (delta: -563.6 MB). Peak memory consumption was 51.9 MB. Max. memory is 5.3 GB. [2018-03-28 12:37:58,458 INFO L168 Benchmark]: CDTParser took 0.18 ms. Allocated memory is still 307.8 MB. Free memory is still 269.9 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-03-28 12:37:58,459 INFO L168 Benchmark]: CACSL2BoogieTranslator took 194.66 ms. Allocated memory is still 307.8 MB. Free memory was 250.3 MB in the beginning and 241.1 MB in the end (delta: 9.2 MB). Peak memory consumption was 9.2 MB. Max. memory is 5.3 GB. [2018-03-28 12:37:58,459 INFO L168 Benchmark]: Boogie Preprocessor took 29.34 ms. Allocated memory is still 307.8 MB. Free memory was 241.1 MB in the beginning and 240.1 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 5.3 GB. [2018-03-28 12:37:58,459 INFO L168 Benchmark]: RCFGBuilder took 275.54 ms. Allocated memory was 307.8 MB in the beginning and 469.8 MB in the end (delta: 162.0 MB). Free memory was 240.1 MB in the beginning and 438.2 MB in the end (delta: -198.1 MB). Peak memory consumption was 23.5 MB. Max. memory is 5.3 GB. [2018-03-28 12:37:58,460 INFO L168 Benchmark]: TraceAbstraction took 130031.78 ms. Allocated memory was 469.8 MB in the beginning and 923.3 MB in the end (delta: 453.5 MB). Free memory was 437.0 MB in the beginning and 814.9 MB in the end (delta: -377.9 MB). Peak memory consumption was 75.6 MB. Max. memory is 5.3 GB. [2018-03-28 12:37:58,462 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.18 ms. Allocated memory is still 307.8 MB. Free memory is still 269.9 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 194.66 ms. Allocated memory is still 307.8 MB. Free memory was 250.3 MB in the beginning and 241.1 MB in the end (delta: 9.2 MB). Peak memory consumption was 9.2 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 29.34 ms. Allocated memory is still 307.8 MB. Free memory was 241.1 MB in the beginning and 240.1 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 5.3 GB. * RCFGBuilder took 275.54 ms. Allocated memory was 307.8 MB in the beginning and 469.8 MB in the end (delta: 162.0 MB). Free memory was 240.1 MB in the beginning and 438.2 MB in the end (delta: -198.1 MB). Peak memory consumption was 23.5 MB. Max. memory is 5.3 GB. * TraceAbstraction took 130031.78 ms. Allocated memory was 469.8 MB in the beginning and 923.3 MB in the end (delta: 453.5 MB). Free memory was 437.0 MB in the beginning and 814.9 MB in the end (delta: -377.9 MB). Peak memory consumption was 75.6 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 40 states, 138 states before enhancement), while PredicateComparison was comparing new predicate (quantifier-free) to 163 known predicates. - TimeoutResultAtElement [Line: 19]: Timeout (TraceAbstraction) Unable to prove that array index is always in bounds (line 19). Cancelled while BasicCegarLoop was constructing difference of abstraction (883states) and interpolant automaton (currently 40 states, 138 states before enhancement), while PredicateComparison was comparing new predicate (quantifier-free) to 163 known predicates. - TimeoutResultAtElement [Line: 24]: Timeout (TraceAbstraction) Unable to prove that array index is always in bounds (line 24). Cancelled while BasicCegarLoop was constructing difference of abstraction (883states) and interpolant automaton (currently 40 states, 138 states before enhancement), while PredicateComparison was comparing new predicate (quantifier-free) to 163 known predicates. - TimeoutResultAtElement [Line: 17]: Timeout (TraceAbstraction) Unable to prove that array index is always in bounds (line 17). Cancelled while BasicCegarLoop was constructing difference of abstraction (883states) and interpolant automaton (currently 40 states, 138 states before enhancement), while PredicateComparison was comparing new predicate (quantifier-free) to 163 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 6 procedures, 51 locations, 4 error locations. TIMEOUT Result, 129.9s OverallTime, 33 OverallIterations, 32 TraceHistogramMax, 81.8s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 3457 SDtfs, 11516 SDslu, 62598 SDs, 0 SdLazy, 61103 SolverSat, 7762 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 18.7s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 12943 GetRequests, 8819 SyntacticMatches, 552 SemanticMatches, 3571 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 158133 ImplicationChecksByTransitivity, 98.3s 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.4s AutomataMinimizationTime, 32 MinimizatonAttempts, 135 StatesRemovedByMinimization, 12 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 0.7s SatisfiabilityAnalysisTime, 45.3s InterpolantComputationTime, 5683 NumberOfCodeBlocks, 5683 NumberOfCodeBlocksAsserted, 33 NumberOfCheckSat, 11300 ConstructedInterpolants, 0 QuantifiedInterpolants, 10890548 SizeOfPredicates, 1270 NumberOfNonLiveVariables, 7884 ConjunctsInSsa, 1466 ConjunctsInUnsatCore, 66 InterpolantComputations, 4 PerfectInterpolantSequences, 63118/99544 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-03-28_12-37-58-471.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-03-28_12-37-58-471.csv Completed graceful shutdown